Ho un problema con la logica per algebra di base (insiemi)
Buongiorno!
Vi chiedo un aiuto per dimostrare l'uguaglianza tra due insiemi (in particolare siamo dell'ambibto MCD) ${d∈ NN:d|a ∧ d|b}={d∈ NN:d|b ∧ d|r}$.
in particolare indico con r il resto della divisione euclidea $a=q*b+r$ con b diverso da 0 ecc. ecc.
L'idea è mostrare la doppia inclusione e il professore dice:
⊆) vera poiché se $d|a$ ∧ $d|b$ allora $d|(a-bq)=r$ e va benissimo questa scrittura.
Però non mi torna per nulla l'equivalenza delle due proposizioni definenti gli insiemi, cioè non mi pare dimostri quello che voglio che un elemento che rispetta la proposizione del primo insieme rispetta quella del secondo, vediamolo meglio:
Poniamo A:=d|a, B:=d|a, C:=d|r
Ora faccio la tabella ad otto entrate (logica) con A, B, C e scrivo le colonne $A ∧ B$, poi $A ∧ ((A ∧ B)=>C$
Mi aspetterei che le colonne $A ∧ B$ che definiscono il primo insieme coincida con i valori di verità di $A ∧ ((A ∧ B)=>C)$ del secondo, ma così non è!
Però mi pare corretto perche la dimostrazione dice che se ho A e B ciò implica C. Dunque il secondo insieme deve rispettare B ∧ (A e B che implica C).
Ma questo vuol dire che definisco due insiemi diversi, avendo valori di veritàdi versi, e quindi la dimostrazione sarebbe errata. Deduco che non riesco a capire dove sbaglio nella mia interpretazione, ed essendo qualcosa di base vorrei capire l'errore.
Vi chiedo un aiuto per dimostrare l'uguaglianza tra due insiemi (in particolare siamo dell'ambibto MCD) ${d∈ NN:d|a ∧ d|b}={d∈ NN:d|b ∧ d|r}$.
in particolare indico con r il resto della divisione euclidea $a=q*b+r$ con b diverso da 0 ecc. ecc.
L'idea è mostrare la doppia inclusione e il professore dice:
⊆) vera poiché se $d|a$ ∧ $d|b$ allora $d|(a-bq)=r$ e va benissimo questa scrittura.
Però non mi torna per nulla l'equivalenza delle due proposizioni definenti gli insiemi, cioè non mi pare dimostri quello che voglio che un elemento che rispetta la proposizione del primo insieme rispetta quella del secondo, vediamolo meglio:
Poniamo A:=d|a, B:=d|a, C:=d|r
Ora faccio la tabella ad otto entrate (logica) con A, B, C e scrivo le colonne $A ∧ B$, poi $A ∧ ((A ∧ B)=>C$
Mi aspetterei che le colonne $A ∧ B$ che definiscono il primo insieme coincida con i valori di verità di $A ∧ ((A ∧ B)=>C)$ del secondo, ma così non è!
Però mi pare corretto perche la dimostrazione dice che se ho A e B ciò implica C. Dunque il secondo insieme deve rispettare B ∧ (A e B che implica C).
Ma questo vuol dire che definisco due insiemi diversi, avendo valori di veritàdi versi, e quindi la dimostrazione sarebbe errata. Deduco che non riesco a capire dove sbaglio nella mia interpretazione, ed essendo qualcosa di base vorrei capire l'errore.
Risposte
A me sembra che tu ti stia complicando le cose. In particolare, non capisco come tu possa costruire tabelle della verità su formule definite su tutto \(\mathbb{N}\). Inoltre non mi sembra che tu abbia studiato molto l'interdipendenza tra le formule.
Consideriamo gli insiemi \(D_a = \{ d\in\mathbb{N} : d|a \}\), \(D_b = \{ d\in\mathbb{N} : d|a \}\) e \(D_r = \{ d\in\mathbb{N} : d|r \}\) con \(r = a - \lfloor a/b\rfloor b\). Per comodità e per usare la tua stessa notazione, poniamo anche \(q = \lfloor a/b\rfloor\).
Tu vuoi dimostrare che \(D_b\cap D_a = D_b\cap D_r\).
Supponiamo di avere \(d\in D_b\cap D_a\), allora esistono \(\alpha, \beta\in \mathbb{N}\) tali che \(a = \alpha d\), \(b = \beta d\) e quindi \(r = (\alpha - q\beta)d\). Questo dimostra \(D_b\cap D_a \subseteq D_b\cap D_r\).
Supponi quindi di avere \(d\in D_b\cap D_r\), allora esistono \(\rho, \beta\in \mathbb{N}\) tali che \(r = \rho d\), \(b = \beta d\) e quindi \(a = (\beta q + \rho)d\). Questo dimostra l'implicazione inversa.
Consideriamo gli insiemi \(D_a = \{ d\in\mathbb{N} : d|a \}\), \(D_b = \{ d\in\mathbb{N} : d|a \}\) e \(D_r = \{ d\in\mathbb{N} : d|r \}\) con \(r = a - \lfloor a/b\rfloor b\). Per comodità e per usare la tua stessa notazione, poniamo anche \(q = \lfloor a/b\rfloor\).
Tu vuoi dimostrare che \(D_b\cap D_a = D_b\cap D_r\).
Supponiamo di avere \(d\in D_b\cap D_a\), allora esistono \(\alpha, \beta\in \mathbb{N}\) tali che \(a = \alpha d\), \(b = \beta d\) e quindi \(r = (\alpha - q\beta)d\). Questo dimostra \(D_b\cap D_a \subseteq D_b\cap D_r\).
Supponi quindi di avere \(d\in D_b\cap D_r\), allora esistono \(\rho, \beta\in \mathbb{N}\) tali che \(r = \rho d\), \(b = \beta d\) e quindi \(a = (\beta q + \rho)d\). Questo dimostra l'implicazione inversa.
In particolare, non capisco come tu possa costruire tabelle della verità su formule definite su tutto N.
Non ho ben capito questa tua obiezione in realtà. Perché io valuto la tabella prendendo un $d in NN$ e dico che d è nell'insieme ${d∈N:d|a∧d|b}$ se e solo se $d|a∧d|b$ è un predicato che diventa enunciato: vero!
Ci saranno d che rendono vero $A:=d|a$ e non $B:=d|b$ (quindi falsa la loro congiunzione), altri che rendono vero entrambe (quidni "e" vera), altri acora falsa la prima e vera la seconda. La tabella valuta i valori di verità della congiunzione ∧.
Ora, in ogni caso, siano gli insiemi \(D_a = \{ d\in\mathbb{N} : d|a \}\), \(D_b = \{ d\in\mathbb{N} : d|a \}\) e \(D_r = \{ d\in\mathbb{N} : d|r \}\).
Quando scriviamo $D_b\cap D_a$ adesempio in $d in D_b\cap D_a <=> d in D_b ∧ d in D_a <=> d|a ∧ d|b$ in termini di definizione abbiamo riscomposto il problema al caso iniziale.
facciamone solo una che tanto il dubbio è lo stesso quindi ⊆
Quindi se io voglio \(D_b\cap D_a ⊆ D_b\cap D_r\), questo si ha quando rispetto che $d in D_b\cap D_a => d in D_b\cap D_r $ (**)
(** questo perché $A⊆B <=> x in A => x in B$)
Insomma quando scrivi
Supponiamo di avere \(d\in D_b\cap D_a\), allora esistono \(\alpha, \beta\in \mathbb{N}\) tali che \(a = \alpha d\), \(b = \beta d\) e quindi \(r = (\alpha - q\beta)d\). Questo dimostra \(D_b\cap D_a \subseteq D_b\cap D_r\).
Il mio dubbio rimane perché non riesco a vedere il motivo per cui dimostrando che se d|a e d|b implica che d|r allora questo equivalga a dire che "d" è nell'insieme $D_b∩D_r={d∈N:d|b∧d|r}$ perché il "conteunto/sottoinsieme di" vorrebbe dire mostrare (**) e a me non sembra di star facendo questo.
[EDIT]
Quindi anche quello da me fatto nel primo messaggio era sbagliato, però mi sembra di dover mostrare che
$d in D_b∩D_a => d in D_b∩D_r$ cioè quando è vero l'antecedente è vero il conseguente.
Ma non funziona comunque perché componendo la tavola di verità ho
A | B | C | A∧B | A∧((A∧B)=>C) | A∧B => A∧((A∧B)=>C)
V | V | V |..V..|........ V.............|..........V
V | V | F |..V..|.........F.............|...........F
e si nota già subito che quando vale A∧B quindi d è nel primo insieme intersezione non è detto valga A∧B => A∧((A∧B)=>C) cioè nel secondo insieme intersezione dunque $d in D_b∩D_a$ non implica $d in D_b∩D_r$ e non varrebbe l'inclusione
Siano \(\phi_1\), \(\phi_2\) e \(\phi_3\) tre termini dipendenti da una variabile libera \(x\). Il fatto che nessuno dei termini sia sempre vero o falso non significa che al variare di \(x\), \(\phi_1(x)\), \(\phi_2(x)\) e \(\phi_3(x)\) possano assumere tutte le combinazioni possibili. Per esempio, i tre termini potrebbero essere uguali e quindi assumere sempre lo stesso valore, oppure una potrebbe essere la negazione di un'altra.
Nel caso di \(d|a\), \(d|b\) e \(d|r\) alcune combinazioni non si verificano ed è esattamente quello che devi dimostrare.
Per fare un'altro esempio, pensa a \(d|a\), \(a|b\) e \(d|b\). La seconda non dipende da \(d\), quindi è sempre vera o falsa. Se è sempre vera, allora avrai \(d|a \rightarrow d|b\) in virtù della proprietà transitiva. Se è falsa, ma \(b|a\) è vera, allora avrai \(d|b \rightarrow d|a\) sempre in virtù della proprietà transitiva. Insomma, a seconda di \(a\) e \(b\) avrai possibilità differenti.
Nel caso di \(d|a\), \(d|b\) e \(d|r\) alcune combinazioni non si verificano ed è esattamente quello che devi dimostrare.
Per fare un'altro esempio, pensa a \(d|a\), \(a|b\) e \(d|b\). La seconda non dipende da \(d\), quindi è sempre vera o falsa. Se è sempre vera, allora avrai \(d|a \rightarrow d|b\) in virtù della proprietà transitiva. Se è falsa, ma \(b|a\) è vera, allora avrai \(d|b \rightarrow d|a\) sempre in virtù della proprietà transitiva. Insomma, a seconda di \(a\) e \(b\) avrai possibilità differenti.
Hai ragione anche tu 
Quindi correggimi se sbaglio, riprendendo la tabellina di cui sopra: siccome abbiamo dimostrato tramite $r=(α−qβ)d$ che $d|r$ OGNI volta che A∧B è vera dimostro (poste le proposizioni A,B, C come sopra) che C (cioè d|r) è vera, in altre parole A∧B=>C è sempre vera in tale contesto (proprio perché antecedente e conseguente lo sono sempre), quindi la seconda riga di quella tavola di verità in realtà ho dimostrato non verificarsi.
In effetti è la prima riga a sussistere in virtù di quanto detto.
Ti sembra giusto? Te lo chiedo per capire se ho capito
.
Quindi correggimi se sbaglio, riprendendo la tabellina di cui sopra: siccome abbiamo dimostrato tramite $r=(α−qβ)d$ che $d|r$ OGNI volta che A∧B è vera dimostro (poste le proposizioni A,B, C come sopra) che C (cioè d|r) è vera, in altre parole A∧B=>C è sempre vera in tale contesto (proprio perché antecedente e conseguente lo sono sempre), quindi la seconda riga di quella tavola di verità in realtà ho dimostrato non verificarsi.
In effetti è la prima riga a sussistere in virtù di quanto detto.
Ti sembra giusto? Te lo chiedo per capire se ho capito
.
Si tratta di \(\wedge\) e non \(\vee\), ma il resto è giusto.
Sì, ovviamente è un typo come si deduce anche da quanto ho scritto sopra. Ho corretto per mantenere maggior chiarezza.
Ti ringrazio moltissimo per il tuo aiuto, davvero!
Ti ringrazio moltissimo per il tuo aiuto, davvero!
Potrei continuare la discussione con un'altra domanda? Essendo sempre un argomento di logica terra-terra mi sembra inutile aprire un'altra pagina.. credo possa servire di più mantenendo unite dato il titolo non troppo specifico. Ad ogni modo..
Il mio dubbio è il seguente.
Ho una asserzione da dimostrare del tipo (A, Binsiemi): A=B or A∩B=ø
Ora, la dimostrazione procede come segue: prende un elemento in A∩B e mostra che se ciò accade allora A=B.
Non capisco perché però una tale dimostrazione dimostri la disgiunzione "or" secondo la logica basilare che conosco.
Grazie per il tuo aiuto vict
[EDIT]
Potrebbe essere che essendo la tavoladi verità di "p or q" sempre vera tranne quando q e p sono ENTRAMBE false, allora andando io a dimostrare che se q è falsa p è sempre vera (non ho mai il caso q falso e p falso) insomma ottengo una tabella solo di verità (tautologica).
Problema smile a quelli di apertura. E' corretto?
Il mio dubbio è il seguente.
Ho una asserzione da dimostrare del tipo (A, Binsiemi): A=B or A∩B=ø
Ora, la dimostrazione procede come segue: prende un elemento in A∩B e mostra che se ciò accade allora A=B.
Non capisco perché però una tale dimostrazione dimostri la disgiunzione "or" secondo la logica basilare che conosco.
Grazie per il tuo aiuto vict
[EDIT]
Potrebbe essere che essendo la tavoladi verità di "p or q" sempre vera tranne quando q e p sono ENTRAMBE false, allora andando io a dimostrare che se q è falsa p è sempre vera (non ho mai il caso q falso e p falso) insomma ottengo una tabella solo di verità (tautologica).
Problema smile a quelli di apertura. E' corretto?
Scusate l'intromissione ma ero curioso di sapere se fosse corretto dato che avendo letto la discussione con interesse ero curioso di avere una conferma o meno 
"mat.pasc":
[EDIT]
Potrebbe essere che essendo la tavoladi verità di "p or q" sempre vera tranne quando q e p sono ENTRAMBE false, allora andando io a dimostrare che se q è falsa p è sempre vera (non ho mai il caso q falso e p falso) insomma ottengo una tabella solo di verità (tautologica).
Problema smile a quelli di apertura. E' corretto?
La domanda qual è?
L'ultima cosa che voleva dimostrare mat.pasc non è mica vera: dati due insiemi \(A\) e \(B\), non è mica detto che debba essere per forza \(A = B\) oppure \(A \cap B = \varnothing\).
L'ultima cosa che voleva dimostrare mat.pasc non è mica vera: dati due insiemi \(A\) e \(B\), non è mica detto che debba essere per forza \(A = B\) oppure \(A \cap B = \varnothing\).
Sì non mi ero nemmeno accorto ma solo perché in realtà mi interessava l'essenza della questione e non ho letto realmente la dimostrazione cercata. Mi spiego meglio:
Mi chiedevo se dovendo dimostrare un asserto diciamo "p v q" allora se prendo un q falso e dimostro che ciò mi garantisce di avere una p sempre vera allora concludo che p v q vale è un enunciato valido?
La spiegazione dellavalidità del processo è (ora sì)
Giusto?
Mi chiedevo se dovendo dimostrare un asserto diciamo "p v q" allora se prendo un q falso e dimostro che ciò mi garantisce di avere una p sempre vera allora concludo che p v q vale è un enunciato valido?
La spiegazione dellavalidità del processo è (ora sì)
[EDIT]
Potrebbe essere che essendo la tavoladi verità di "p or q" sempre vera tranne quando q e p sono ENTRAMBE false, allora andando io a dimostrare che se q è falsa p è sempre vera (non ho mai il caso q falso e p falso) insomma ottengo una tabella solo di verità (tautologica).
Problema smile a quelli di apertura. E' corretto?
Giusto?
Per dimostrare che vale $p vv q$, basta far vedere che se $q$ è falsa allora è vera $p$.
Questo mi pare risulti evidente dalla tavola di verità di $not q -> p$ che è identica a quella di $p vv q$... E grazie al cavolo!
Infatti, per definizione di implicazione, la proposizione $not q -> p$ è la stessa cosa di $p vv not (not q) = p vv q$.
Questo mi pare risulti evidente dalla tavola di verità di $not q -> p$ che è identica a quella di $p vv q$... E grazie al cavolo!
Infatti, per definizione di implicazione, la proposizione $not q -> p$ è la stessa cosa di $p vv not (not q) = p vv q$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo