Un megadubbio di logica
Inizialmente volevo rispondere qui https://www.matematicamente.it/forum/vi ... 0#p8520670 perché leggendo la discussione mi è tornato in mente un dubbio che ho da qualche tempo e non riesco bene a decifrare e non ho ancora risolto del tutto. Infatti leggendo ho finalmente capito alcune cose che potrebbero essere utili. Tuttavia vedendo che la domanda è ancora in corso non ho voluto aggiungere e importunare nella discussione e ho quindi pensato di aprirne una nuova qui.
Di fatto un esercizio di qualche tempo fa mi aveva portato a dover come ultimo passo dimostrare (insiemistica)
$[(x in A ⋁ x in B)=> x in A]=> (x in B => x in A)$ che so dover essere vera.
Dalle parole della discussione mi sembra di capire che posso riscriverla così: $[(x in A ⋁ x in B)=> x in A ∧ x in B]=> x in A$
Adesso analizzando $[(x in A ⋁ x in B)=> x in A ⋀ x in B]$ e partendo da $x in B$ mi verrebbe da dire che vale $(x in A ⋁ x in B)$ poiché vale una delle due e così concludere sfruttando $=>x in A$
Il mio "però" è questo. Formalmente $x in A ⋁ x in B$ potrei riscriverlo dicendo che è equivalente a $x !in A => x in B$ ma a questo punto $[(x !in A => x in B)=> x in A ∧ x in B]$ come sfrutto $x in B$ per giungere a dire che $(x !in A => x in B)$ è vera? Essendo equivalente alla precedente dovrei riuscirci in qualche modo, ma non so come dato che a priori non so che $x !in A$ e sarebbe una ipotesi aggiuntiva.
Il punto è che l'esercizio chiedeva esplicitamente di sfruttare la logica, quindi non mi interessano soluzioni più semplcii di inclusione ovvie, serve proprio per far esercitare su questo e vorrei capire meglio come stanno le cose.
Di fatto un esercizio di qualche tempo fa mi aveva portato a dover come ultimo passo dimostrare (insiemistica)
$[(x in A ⋁ x in B)=> x in A]=> (x in B => x in A)$ che so dover essere vera.
Dalle parole della discussione mi sembra di capire che posso riscriverla così: $[(x in A ⋁ x in B)=> x in A ∧ x in B]=> x in A$
Adesso analizzando $[(x in A ⋁ x in B)=> x in A ⋀ x in B]$ e partendo da $x in B$ mi verrebbe da dire che vale $(x in A ⋁ x in B)$ poiché vale una delle due e così concludere sfruttando $=>x in A$
Il mio "però" è questo. Formalmente $x in A ⋁ x in B$ potrei riscriverlo dicendo che è equivalente a $x !in A => x in B$ ma a questo punto $[(x !in A => x in B)=> x in A ∧ x in B]$ come sfrutto $x in B$ per giungere a dire che $(x !in A => x in B)$ è vera? Essendo equivalente alla precedente dovrei riuscirci in qualche modo, ma non so come dato che a priori non so che $x !in A$ e sarebbe una ipotesi aggiuntiva.
Il punto è che l'esercizio chiedeva esplicitamente di sfruttare la logica, quindi non mi interessano soluzioni più semplcii di inclusione ovvie, serve proprio per far esercitare su questo e vorrei capire meglio come stanno le cose.
Risposte
Di preciso l'esercizio cosa chiede?
In teoria chiedeva questo: $[(x in A ⋁ x in B)=> x in A]=> (x in B => x in A)$ da dimostrarsi, ma chiedeva espressamente di non sfruttare inclusioni ma ridurre alla logica con cui son state definite inclusioni ecc.
Di fatto: $A∪B⊆A=>B⊆A$, ho solo tradotto.
Da qui poi prendevano forma i dubbi:
Di fatto: $A∪B⊆A=>B⊆A$, ho solo tradotto.
Da qui poi prendevano forma i dubbi:
Dalle parole della discussione mi sembra di capire che posso riscriverla così: $[(x in A ⋁ x in B)=> x in A ∧ x in B]=> x in A$
Adesso analizzando $[(x in A ⋁ x in B)=> x in A ⋀ x in B]$ e partendo da $x in B$ mi verrebbe da dire che vale $(x in A ⋁ x in B)$ poiché vale una delle due e così concludere sfruttando $=>x in A$
Il mio dubbio è questo. Formalmente $x in A ⋁ x in B$ potrei riscriverlo dicendo che è equivalente a $x !in A => x in B$ ma a questo punto $[(x !in A => x in B)=> x in A ∧ x in B]$ come sfrutto $x in B$ per giungere a dire che $(x !in A => x in B)$ è vera? Essendo equivalente alla precedente dovrei riuscirci in qualche modo, ma non so come dato che a priori non so che $x !in A$ e sarebbe una ipotesi aggiuntiva.
Il punto è che l'esercizio chiedeva esplicitamente di sfruttare la logica, quindi non mi interessano soluzioni più semplcii di inclusione ovvie, serve proprio per far esercitare su questo e vorrei capire meglio come stanno le cose.
Devi partire dalla formula \[\forall x, x \in A \cup B \to x \in A\] e usando solo le leggi che regolano il comportamento dei connettivi (oltre alla definzione di unione al primo passaggio) devi arrivare alla formula \[\forall x, x \in B \to x \in A\]
Ma la premessa è falsa... se $A$ è vuoto e $B$ no, per ogni $x\in B$, \(x\in A\cup B=B\), e del resto non può stare anche in $A$.
In effetti ero andato a memoria sull'esercizio di qualche tempo fa e potrei aver detto una fesseria. Però quello che mi importava era più che altro capire l'essenza.
L'idea era quella, infatti avevo scritto la definizione di unione $x in AUB <=> x in A or x in b$
in poche parole la tua prima
$ [(x in A ⋁ x in B)=> x in A]$
e la tua seconda
$(x in B => x in A) $
Che assime davano il teorema:
$[(x in A ⋁ x in B)=> x in A]=> (x in B => x in A) $
Rimanendo generici la domanda voleva essere se voglio dimostrare: $[(A⋁B)=>A]=>[B=>A]$
avendo letto la discussione che avevo linkato mi dovrei dimostrare $[((A⋁B)=>A)∧B]=>A$ che essendo $A⋁B$ logicamente equivalente a $\notB=>A$ dovrebbe voler dire dimostrare $[((\notB=>A)=>A)∧B]=>A$
Per questo dicevo:
Formalmente $x in A ⋁ x in B$ potrei riscriverlo dicendo che è equivalente a $x !in A => x in B$ ma a questo punto $[(x !in A => x in B)=> x in A ∧ x in B]$ come sfrutto $x in B$ per giungere a dire che $(x !in A => x in B)$ è vera? Essendo equivalente alla precedente dovrei riuscirci in qualche modo, ma non so come dato che a priori non so che $x !in A$ e sarebbe una ipotesi aggiuntiva.
"G.D.":
Devi partire dalla formula \[\forall x, x \in A \cup B \to x \in A\] e usando solo le leggi che regolano il comportamento dei connettivi (oltre alla definzione di unione al primo passaggio) devi arrivare alla formula \[\forall x, x \in B \to x \in A\]
L'idea era quella, infatti avevo scritto la definizione di unione $x in AUB <=> x in A or x in b$
in poche parole la tua prima
$ [(x in A ⋁ x in B)=> x in A]$
e la tua seconda
$(x in B => x in A) $
Che assime davano il teorema:
$[(x in A ⋁ x in B)=> x in A]=> (x in B => x in A) $
Rimanendo generici la domanda voleva essere se voglio dimostrare: $[(A⋁B)=>A]=>[B=>A]$
avendo letto la discussione che avevo linkato mi dovrei dimostrare $[((A⋁B)=>A)∧B]=>A$ che essendo $A⋁B$ logicamente equivalente a $\notB=>A$ dovrebbe voler dire dimostrare $[((\notB=>A)=>A)∧B]=>A$
Per questo dicevo:
Formalmente $x in A ⋁ x in B$ potrei riscriverlo dicendo che è equivalente a $x !in A => x in B$ ma a questo punto $[(x !in A => x in B)=> x in A ∧ x in B]$ come sfrutto $x in B$ per giungere a dire che $(x !in A => x in B)$ è vera? Essendo equivalente alla precedente dovrei riuscirci in qualche modo, ma non so come dato che a priori non so che $x !in A$ e sarebbe una ipotesi aggiuntiva.
"megas_archon":
Ma la premessa è falsa... se $A$ è vuoto e $B$ no, per ogni $x\in B$, \(x\in A\cup B=B\), e del resto non può stare anche in $A$.
Bisogna provare che se \(A \cup B \subseteq A\), allora \(B \subseteq A\).
Se \(A = \varnothing \ne B\), allora \(A \cup B = \varnothing \cup B = B \not \subseteq A = \varnothing\), nel qual caso la premessa del "se... allora..." non vale, quindi non vedo il problema quale sia.
@aritmetico
Il fatto che valga la legge di importazione-esportazione del condizionale (i.e. \(A \to (B \to C) \equiv (A \land B) \to C\)) non significa che tu debba usarla per forza.
In secondo luogo, la legge di importazione-esportazione ti dice in cosa si trasforma la formula da provare, non è una dimostrazione della formula, né di quella iniziale né di quella che si ottiene applicando la legge di importazione-esportazione.
In questo caso, provare usando solo la logica che se \(A \cup B \subseteq A\), allora \(B \subseteq A\), consiste in quanto segue: \[A \cup B \subseteq A\\ \forall x, x \in A \cup B \to x \in A\\ \forall x, (x \in A \lor x \in B) \to x \in A\\ \forall x, \lnot (x \in A \lor x \in B) \lor x \in A\\ \forall x, x \in A \lor \lnot (x \in A \lor x \in B)\\ \forall x, x \in A \lor (x \notin A \land x \notin B)\\ \forall x, (x \in A \lor x \notin A) \land (x \in A \lor x \notin B)\\ \forall x, \top \land (x \notin B \lor x \in A)\\ \forall x, x \notin B \lor x \in A\\ \forall x, x \in B \to x \in A\\ B \subseteq A\] La legge di importazione-esportazione giustifica la seguente dimostrazione più insiemistica, per così dire.
Sia per ipotesi \(A \cup B \subseteq A\) e si voglia provare che, allora, \(B \subseteq A\). Sia[nota]Qui si sta importando l'antecedente del condizionale che costituisce la tesi, o, se vuoi, l'antecedente del condizionale che costituisce il conseguente del condizionale che traduce il teorema in un'unica formula.[/nota] \(x \in B\). Se \(x \in B\), allora, per definizione di unione \(x \in A \cup B\). Data l'ipotesi, segue che \(x \in A\). Quindi: se \(x \in B\), allora \(x \in A\). Per definzione, allora \(B \subseteq A\).
Il fatto che valga la legge di importazione-esportazione del condizionale (i.e. \(A \to (B \to C) \equiv (A \land B) \to C\)) non significa che tu debba usarla per forza.
In secondo luogo, la legge di importazione-esportazione ti dice in cosa si trasforma la formula da provare, non è una dimostrazione della formula, né di quella iniziale né di quella che si ottiene applicando la legge di importazione-esportazione.
In questo caso, provare usando solo la logica che se \(A \cup B \subseteq A\), allora \(B \subseteq A\), consiste in quanto segue: \[A \cup B \subseteq A\\ \forall x, x \in A \cup B \to x \in A\\ \forall x, (x \in A \lor x \in B) \to x \in A\\ \forall x, \lnot (x \in A \lor x \in B) \lor x \in A\\ \forall x, x \in A \lor \lnot (x \in A \lor x \in B)\\ \forall x, x \in A \lor (x \notin A \land x \notin B)\\ \forall x, (x \in A \lor x \notin A) \land (x \in A \lor x \notin B)\\ \forall x, \top \land (x \notin B \lor x \in A)\\ \forall x, x \notin B \lor x \in A\\ \forall x, x \in B \to x \in A\\ B \subseteq A\] La legge di importazione-esportazione giustifica la seguente dimostrazione più insiemistica, per così dire.
Sia per ipotesi \(A \cup B \subseteq A\) e si voglia provare che, allora, \(B \subseteq A\). Sia[nota]Qui si sta importando l'antecedente del condizionale che costituisce la tesi, o, se vuoi, l'antecedente del condizionale che costituisce il conseguente del condizionale che traduce il teorema in un'unica formula.[/nota] \(x \in B\). Se \(x \in B\), allora, per definizione di unione \(x \in A \cup B\). Data l'ipotesi, segue che \(x \in A\). Quindi: se \(x \in B\), allora \(x \in A\). Per definzione, allora \(B \subseteq A\).
Grazie, direi spiegazione non chiara.. di più!
Potrei farti solo un'ultima domanda, mi sono accorto che in effetti sono stato un ufficio complicazione affari semplici, tuttavia ho questo quesito che mi porto dietro.
In questo caso è palese che l'importazione.esportazione usarla complica solo le cose, tuttavia tutti i passaggi sono equivalenze logiche:
$[(x in A or x in B)=> x in A]=> (x in B => x in A)$
$[((x in A or x in B)=> x in A) and x in B]=>x in A)$
$[((x !in B => x in A)=> x in A) and x in B]=>x in A)$
Insomma logicamente sono tutti equivalenti, però dimostrare l'ultima ho solo complicato le cose invece di migliorarle, giusto?
In poche parole vorrei capire se ho sbagliato qualcosa oppure se in effetti è tutto logicamente corretto sebbene possa essere inutile (ossia se dimostrare l'ultima equivale a dimostrare la prima o se vi sono errori che non scorgo).
Potrei farti solo un'ultima domanda, mi sono accorto che in effetti sono stato un ufficio complicazione affari semplici, tuttavia ho questo quesito che mi porto dietro.
In questo caso è palese che l'importazione.esportazione usarla complica solo le cose, tuttavia tutti i passaggi sono equivalenze logiche:
$[(x in A or x in B)=> x in A]=> (x in B => x in A)$
$[((x in A or x in B)=> x in A) and x in B]=>x in A)$
$[((x !in B => x in A)=> x in A) and x in B]=>x in A)$
Insomma logicamente sono tutti equivalenti, però dimostrare l'ultima ho solo complicato le cose invece di migliorarle, giusto?
In poche parole vorrei capire se ho sbagliato qualcosa oppure se in effetti è tutto logicamente corretto sebbene possa essere inutile (ossia se dimostrare l'ultima equivale a dimostrare la prima o se vi sono errori che non scorgo).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo