Logica e conoscenza

Valtri Connettivi Vero-Funzionali

F V V F FF F V V VALTRI CONNETTIVI VERO-FUNZIONALI- NAND, "O" incompatibile, uso vero-funzionale di "o" (diverso da quello della disgiunzione inclusiva ed esclusiva); si utilizza quando non si possono fare due cose insieme; es. Si mangia o si parla!" I due disgiunti non possono essere entrambi veri, ma possono essere entrambi falsi. A Nand BA B FV V VV F VF V VF F∧¬B) ∨ ∨ ∧¬B) Logicamente equivalente a (A (¬A∧B) (¬A ∧Tavola di verità complementare e, quindi, logicamente equivalente a ¬(A B) - da cui il nome Nand- NOR, né A né B A B A Nor BV V FV F FF V FF F V∧¬B Logicamente equivalente a ¬A ∨ Logicamente equivalente a ¬ (A B) - da cui il nome Nor

RIASSUNTO ∧ ∨A B A B A B (A → B) (A «︎ B)A ¬A V V V V V VV F V F F V F FF V F V F V V FF F F F V V

Utilizzando le tavole di verità si calcolano i valori di verità che le forme proposizionali assumono

quando si attribuisce un valore di verità alle lettere proposizionali che compaiono in esse.

(A → B) → (¬A → B)

V V F V V V

V F F F F V

F V V V V V

F F F V F V

∧ ∨

A B (A ¬ B) ¬ (A <-> B)

V V V F

V F F V

F V F V

F F F V

• Le proposizioni che hanno la forma di una tautologia

Sono sempre vere, indipendentemente dalla verità o falsità delle proposizioni semplici che figurano in esse. Non forniscono informazioni sulla realtà.

• Parigi è la capitale della Francia - dà un'informazione
• Parigi è la capitale della Francia o Parigi non è la capitale della Francia - sempre vera, ma non dà alcuna informazione
• Tautologico - banale - inutile (nel linguaggio comune). Fondamentali in logica per determinare la correttezza delle regole di inferenza (trasmissione della verità dalle premesse alla conclusione)
• ∨ ∧ (A → B) <-> (A C → B C)
• ∨ ∧ ∨ ∧ ∨ ∧ A B C A → B A C B C (A C → B C) (A → B) <-> (A C → B C)
• V V V V V V V V
• V V F V V F F F
• V F V F V F F V
• V F F F V F F V
• F V V V V V V V
• F V F V F F V F
• F F V F F V V F
• F F F F F F V F
• V V V V V V V V
• V V F V V F F F
• V F V F V F F V
• V F F F V F F V
• F V V V V V V V
• F V F V F F V F
• F F V F F V V F
• F F F F F F V F
• V V V V V V V V
• V V F V V F F F
• V F V F V F F V
• V F F F V F F V
• F V V V V V V V
• F V F V F F V F
• F F V F F V V F
• F F F F F F V F
• ∨¬ (A → (¬A → B C)
• CONTRADDIZIONE
• Quando la forma proposizionale assume sempre

valore F qualunque siano i valori di verità delle proposizioni che la compongono, allora abbiamo una contraddizione•

NB: la negazione di una tautologia è una contraddizione e, viceversa, la negazione di una contraddizione è una tautologia.

Classificazione delle forme proposizionali•

La fp ha sempre valore V: tautologia

La fp ha almeno un valore V e almeno un valore F: contingente

La fp ha sempre valore F: contraddizione

Tautologie importanti ∨

Principio del Terzo Escluso A ¬A Data una qualsiasi proposizione A, A è vera o è falsa.∧¬A)

Principio di non contraddizione ¬ (A Data una qualsiasi proposizione A, non può essere simultaneamente vera e falsa. ∧ ∧B) ∧

Proprietà associativa della congiunzione A (B∧C) <-> (A C Il valore di verità della congiunzione non dipende dall'ordine delle lettere proposizionali (così come per la somma in matematica!).∨ ∨ ∨

1. Proprietà associativa della Disgiunzione: (A (B C)) <-> ((A B) C)
2. Proprietà commutativa della congiunzione: (A B) <-> (B A)
3. Proprietà commutativa della Disgiunzione: (A B) <-> (B A)
4. Proprietà distributiva della congiunzione rispetto alla disgiunzione: (A (B∨C)) <-> ((A&B) (A&C))
5. Proprietà distributiva della disgiunzione rispetto alla congiunzione: (A (B&C)) <-> ((A∨B) (A∨C))
6. Prima Legge di De Morgan: (A B) <-> ¬(¬A∨¬B)
7. Seconda Legge di De Morgan: (A B) <-> ¬(¬A∧¬B)
8. Equivalenza Logica: Si dice che una forma proposizionale è logicamente equivalente ad un'altra se e solo se le due forme proposizionali hanno lo stesso valore di verità in corrispondenza di ogni assegnazione

equivalenti se e solo se la forma proposizionale X <-> Y è una tautologia.

Dimostrazione: Se due forme proposizionali X e Y assumono sempre lo stesso valore di verità, allora il loro bicondizionale X «︎ Y assume sempre valore V, quindi è una tautologia. Viceversa, se il bicondizionale ha sempre valore V, le due forme proposizionali X e Y assumono sempre lo stesso valore di verità, e quindi sono logicamente equivalenti.

Tutte le tautologie che sono dei bicondizionali sanciscono l’equivalenza logica dei loro due membri. ∧, Comunque, data una fp, esiste una fb ad essa logicamente equivalente che contiene solo i connettivi ¬, e ∨.

Tutte le tautologie che sono dei condizionali sanciscono la conseguenza logica del conseguente dall’antecedente.

Le seguenti fp sono logicamente equivalenti?

1. ∨ ∧ ∨1. A (A B) (A SI¬B)
2. ∧ ∨2. B) SI¬(A ¬A ¬B→
3. ∧3. A B SI¬(A ¬B)→
4. ∧4. B) NO¬(A ¬A

• La forma proposizionale X è conseguenza logica della forma proposizionale Y se e solo se, per ogni assegnazione di valori di verità alle lettere proposizionali che compaiono in esse, se Y ha valore V, allora X ha valore V.
• Più semplicemente: se e solo se ogni volta che Y è vera, allora è vera anche X.

• ∧ ∧Se A B ha valore V, allora A ha valore V, per cui A è conseguenza logica di A B
• ∨ ∨Se A ha valore V, allora A B ha valore V, per cui A B è conseguenza logica di A
• →Se A ha valore V, B, avendo antecedente falso, ha valore V, per cui B è conseguenza logica di ¬A

Prima forma della legge di concatenazione (A→B) → ((B→C) → (A→C))

Seconda forma della legge di concatenazione (A→B) (B→C) → (A→C)

Leggi di concatenazione: Le due leggi esprimono il fatto che dalle due

è veraper tutte le assegnazioni di valori di verità alle lettere proposizionali che rendono vere Y1, Y2, …, Yn.

Più semplicemente: se e solo se X è vera ogni volta che sono vere Y1, Y2, …, Yn.

TEOREMA: la forma proposizionale X è conseguenza logica delle forme proposizionali Y1, Y2, …, Yn se e solose la forma proposizionale∧ ∧ ∧Y1 Y2 … Yn → X è una tatuologia.

Verifica di tautologie col metodo indiretto

(A→B) → ((B→C) → (A→C))

F(A→B) → ((B→C) → (A→C))

V F F(A→B) → ((B→C) → (A→C))

V F V F F(A→B) → ((B→C) → (A→C))

V F V F V F F(A→B) → ((B→C) → (A→C))

V V F F F V F F V F F

Siamo pervenuti ad una contraddizione: la forma proposizionale non potendo avere valore F, è unatautologia.

Con il metodo del controesempio, dimostriamo che è una tautologia (¬A→¬B) →