Appunti di logica

Alberi semantici proposizionali

Il metodo degli alberi semantici si basa sulla ricerca di controesempi (ragionamento per assurdo), che in generale funziona come segue:

Tautologie: es. A→(B→A): assumiamo che sia falsa, allora A deve essere vera e B→A deve essere falsa, quindi B deve essere vera e A falsa. Per falsificare la formula abbiamo assunto che A sia sia vera che falsa, cosa che non è possibile per il principio di bivalenza, quindi non esiste una valutazione che la rende falsa e pertanto è una tautologia.

(A→(B→C)) →(B ʌ A→C): affinché B ʌ A→C sia falso, B ʌ A deve essere vero e C falso. Per falsificare il conseguente, B e A devono essere veri e C falso. Affinché sia vero (A→(B→C), A deve essere falso oppure B→C deve essere vero. Il 1° caso è escluso.

dal fatto che abbiamo assunto A vero.

Nel 2° caso, per avere B→C vero, B deve essere falso oppure C vero. Il 1°caso è escluso perché abbiamo assunto che B ʌ A sia vero e il 2° èescluso perché abbiamo assunto che C sia falso, quindi dovremmo assumere che C sia sia vero che falso. Pertanto, la formula non è falsificabile ed è una tautologia.

(A ʌ B) v ¬B: affinché (A ʌ B) v ¬B sia falsa, occorre che sia falsa A ʌ B eo falsa ¬B. Se ¬B deve essere falsa, allora B deve essere vera. Se A ʌ B deve essere falsa, allora A deve essere falsa o B falsa. Il 2° caso è escluso perché abbiamo assunto B vero. Se A è falso e B è vero abbiamo una valutazione che falsifica la formula, quindi essa non è una tautologia.

Conseguenza logica: es.

A, A→B B: assumiamo vere le premesse e falsa la conclusione. Se A→B⊨o deve essere vero, allora A è falso o B è vero. Il

1° caso è escluso perché stiamo assumendo A vero. Il 2° caso è escluso perché stiamo assumendo B falso. Non è possibile trovare un'argomentazione che renda vere le premesse e falsa la conclusione, quindi l'inferenza è corretta. B, A→B A: se A→B deve essere vero, A è falso oppure B è vero.⊨o Entrambi i casi sono possibili, quindi il nesso di conseguenza logica non sussiste. Equivalenza logica: es. ¬A v B A→B: ci sono due casi che falsificano l'equivalenza: o ¬A v B è≡o vero e A→B è falso, oppure ¬A v B è falso e A→B è vero. Se A→B è falso, allora A è vero e B è falso. Se ¬A v B è vero, allora ¬A è vero oppure B è vero. Il 1° caso è escluso perché assumiamo A vero, quindi non può essere vero allora ¬A. Il 2° caso è escluso perché assumiamo

B falso- Se ¬A v B è falso, allora ¬A è falso, e quindi A è vero, e B è falso. Se A→B è vero, alloraA è falso oppure B è vero ed entrambi i casi contraddicono le assunzioni.Quindi, l’equivalenza logica sussiste.

Gli alberi semantici permettono di meccanizzare la ricerca di controesempi, essicostituiscono un esempio di calcolo logico che fornisce degli algoritmi per decidere leproprietà e le relazioni logiche. Per descriverne la struttura occorre introdurre alcunitermini:

Grafo: struttura con nodi e archi che collegano i nodi.

Cammino: sequenza di archi.

Albero: grafo in cui, per ogni coppia di nodi, esiste un solo cammino.

1N è figlio d M se N è immediatamente sotto M (es. 2 e 1, 3 e 2, 4 e 2). 2N è genitore di M se N è immediatamente sopra M (es. 1 e 2, 2 e 3, 2 e 4).

Foglia: nodo che non ha figli (es. 3, 5, 6).

Radice: nodo che non ha genitori (es. 1).

Ramo: cammino

Un albero semantico proposizionale è un albero nel quale i nodi sono etichettati da asserzioni relative a formule proposizionali. Le asserzioni possibili sono: V:A, che afferma che la proposizione A è vera, e F:A, che afferma che A è falsa. Ciò permette di rappresentare esplicitamente e chiaramente le conseguenze delle ipotesi che possiamo fare sulle valutazioni delle formule.

Un albero si costruisce mediante le seguenti regole:

1. [Vʌ]: V: A ʌ B
   [Fʌ]: F: A ʌ B
   V:A
   F:A
   F:B
   V:B
2. [Vv]: V: A v B
   [Fv]: F: A v B
   V:A
   V:B
   F:A
   F:B
3. [V→]: V: A→B
   [F→]: F: A→B
   F:A
   V:B
   V:A
   F:B
4. [V:¬]: V: ¬A
   [F: ¬]: F: ¬A
   F:A
   V:A

Tali regole permettono di prolungare l'albero da una radice a una foglia (es. 1 2, 2 4, 4 6).

Discendenti di un nodo: suoi figli, figli dei suoi figli e così via fino alle foglie.

Sottoalbero: insieme di nodi che sono discendenti di N e archi che li connettono (es. sottoalbero con come radice il nodo 2).

prolungando lo stesso ramo, o di indurre una biforcazione, dividendo il ramo. L'albero inizia scegliendo un nodo come radice (V:A o F:A) e una volta esaminato un nodo lo si segna con *. Un ramo si dice completato se non vi sono più regole che si possono applicare, chiuso se contiene due nodi segnati con V:A e F:A e aperto se non contiene alcuna affermazione V:A e F:A. Un albero si dice completato se tutti i rami sono completati, chiuso se tutti i rami sono chiusi e aperto se contiene almeno un ramo aperto.

Es. V: (B v ¬A) ʌ (A v ¬B)*

V: B v ¬A*

V: A v ¬B*

V:B V: ¬A*

V:A V: ¬B*

F:A(aperto) F:B V:A V: ¬B*(chiuso) (chiuso) F:B(aperto)

Un ramo aperto dà una situazione possibile che rende vera la formula, mentre un ramo chiuso dà una situazione impossibile.

F: A→(B→A)*

V:A

F: B→A*

V:B

F:A Non ci sono casi possibili che falsifichino la formula, perché assumerla falsa porta alla contraddizione tra V:A e F:A.

Per verificare se A

A→B B F:B⊨ V:AV: A→B*F:A V:B Tutti i rami sono chiusi, non cisono valutazioni che invalidino l'inferenza, quindi è corretta.¬A, A→B ¬B F: ¬B*⊨ V: ¬A*V: A→B*V:BF:AF:A V:B I due rami sono aperti, quindil'inferenza non è corretta.¬A→B C, ¬B→¬A ʌ D, D→B C B⊻ ⊻ ⊨In questo caso occorre introdurre le regole per :⊻[V⊻]: A B [F⊻]: A B⊻ ⊻V:A F:A V:A F:AF:B V:B V:B F:BF:BV: ¬A→B C*⊻V: ¬B→¬A ʌ D*V: D→B C *⊻F: ¬A* V: B C*⊻V:A F: ¬B* V: ¬A ʌ D*F: ¬B* V: ¬A ʌ D* V:B V: ¬AV:B V: ¬A* V:DV:D F:AF:A F:D V: B C*⊻V:B F:BF:C V:C

Per verificare l'equivalenza logica, occorre completare l'albero con radice F: A↔B.

Se l'albero è completato allora A e B sono logicamente equivalenti, se ha almeno unramo aperto allora A non è logicamente equivalente a B. Un ramo aperto consente didefinire una valutazione

• [V→]: V:A→B
• [F→]: A→B
• [V→]: V:A
• [F→]: B
• [V→]: A
• [F→]: B
• [F→]: A
• [Es.]: A ∧ (B ∨ C)
• [F→]: (A ∧ B) ∨ (A ∧ C)
• [V→]: A ∧ (B ∨ C)*
• [F→]: A ∧ (B ∨ C)*
• [F→]: (A ∧ B) ∨ (A ∧ C)*
• [V→]: (A ∧ B) ∨ (A ∧ C)*
• [V→]: A ∧ B*
• [V→]: A ∧ C*
• [F→]: B
• [F→]: C
• [V→]: A ∧ B
• [V→]: A ∧ C
• [F→]: A
• [F→]: B
• [F→]: A
• [F→]: C
• [V→]: B
• [V→]: C
• [V→]: A ∧ B
• [V→]: A ∧ C
• [F→]: A
• [F→]: B
• [V→]: A
• [F→]: A
• [F→]: C
• [V→]: B
• [V→]: C

• [F→]: (A→B)↔(¬A ∧ B)*
• [V→]: A→B*
• [F→]: A→B*
• [F→]: ¬A ∧ B*
• [V→]: ¬A ∧ B*
• [F→]: A
• [F→]: B
• [V→]: A
• [F→]: ¬A*
• [F→]: B
• [F→]: ¬A*
• [V→]: A
• [V→]: ¬A*
• [V→]: B
• [V→]: A
• [F→]: ¬A
• [F→]: B
• [F→]: A
• [F→]: ¬A
• [V→]: B
• [V→]: A
• [F→]: A
• [F→]: C
• [V→]: B
• [V→]: C
• [V→]: A
• [F→]: A
• [F→]: C
• [V→]: B
• [V→]: C

è completato non esiste una valutazione che rende vere tutte2 nle formule e quindi l’insieme non è soddisfacibile, mentre se ha almeno un ramoaperto, allora l’insieme è soddisfacibile. Un ramo aperto definisce una valutazioneche rende vere tutte le formule. In questo caso si cerca un esempio e non uncontroesempio. Es:{ A ʌ B, ¬A v B, A→B} V: A ʌ B*V: ¬A v B*V: A→B*V:AV:BV: ¬A* V:BF:A F:A V:B Almeno un ramo è aperto,quindi l’insieme di formule è soddisfacibile. La valutazione che rende vere tutte leformule è: V:A e V:B.

Connettivi possibili

Ogni connettivo binario è associato a una funzione di verità, cioè una funzione cheha per argomenti coppie di valori di verità e ha valori in {V, F} f:{V;F} x{V, F}→{V, F}. Una funzione di verità f associa a ogni coppia possibile di valori V e Funo e uno solo valore V o F. Per esempio: A ʌ B è associata alla funzione f(V, V)=V,

f(V,F)= F, f(F, V)= F, f(F, F)= F (tavola di verità di ʌ).

Ogni formula proposizionale con due lettere proposizionali potrà avere associata una delle 16 seguenti funzioni di verità: