Logica proposizionale

N

to base b (cioè, riferendosi all’osservazione precedente, appartenente a B)

∈

d(b) = min{n : n range(d)} (generalmente d(b) = 0) e ad ogni elemento

di C viene associato un numero (strettamente) maggiore di quelli associati

agli elementi da cui è stato ottenuto. Il valore della graduazione d su un dato

∈

elemento x C si dice grado dell’elemento. Nel caso proposizionale sono

2

graduazioni le seguenti funzioni: l’altezza dell’albero sintattico , la lunghez-

za della stringa e il numero di occorrenze di connettivi.

In realtà, quando si scrivono formule proposizionali, si usano anche tutti

∨, →, ↔).

gli altri connettivi (cioè Come vedremo più avanti, essi vengono

∧ ¬.

definiti sulla base di e

Convenzioni sulle parentesi.

1. Si possono omettere le parentesi che racchiudono l’intera formula;

2. ai connettivi viene convenzionalmente data la seguente priorità:

¬

∧, ∨

→

↔

1 Un insieme X si dice chiuso rispetto alla funzione n-aria f se per ogni n-upla

x , . . . , x di elementi di X, anche f (x , . . . , x ) è un elemento di X.

0 n−1 0 n−1

2 Nel seguito il grado di una proposizione sarà, convenzionalmente, l’altezza di tale

albero diminuita di 1. Bisogna tener conto però che, siccome abbiamo scelto come primitivi

¬ ∧,

i connettivi e per calcolare il grado di una formula proposizionale bisogna costruirne

l’albero utilizzando solo tali connettivi (ovvero riscrivere la formula usando le definizioni

∨, → ↔

di e e poi costruirne l’albero). 2

intendendo con questo che i connettivi posti più in alto legano più

strettamente di quelli in basso. Seguendo questa convenzione, si può

omettere una coppia di parentesi purché tale operazione non alteri

la tavola di verità della formula in questione (si tenga presente, ad

¬(A ∧ ¬A ∧

esempio, che B) e B hanno tavole di verità diverse e

quindi tali parentesi non si possono omettere);

∧ ∧ ∧

3. per l’associatività di (vedi più avanti), le scritture (A B) C,

∧ ∧ ∧ ∧

A (B C) e A B C saranno considerate tutte la stessa formula

(poiché le prime due hanno la stessa tavola di verità). Analogamente

∨.

per il

Esercizi.

1. Verificare quali delle seguenti stringhe sono formule proposizionali e

quali no, costruire l’albero sintattico corrispondente e spiegare dove

eventualmente la costruzione fallisce (e per quale ragione), determinare

−

il grado (= altezza dell’albero 1) della formula:

¬¬A

→ ∨ ¬C))

(A (B

¬¬(A → B)

→ ∧ →

(((A B) A) B)

∧ ∨

(¬A B) C)

∧ ∨

((¬A B) C)

2. Eliminare le parentesi non necessarie applicando le convenzioni:

∧ → ¬A))

(A (¬B

∨ ∧ → ∧ ¬B))

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

3. Reintrodurre le parentesi nelle seguenti stringhe in modo da ottenere

formule, costruire l’albero sintattico ed elencare sottoformule, sotto-

formule e connettivi principali:

∧ ∨

(¬A B) C

→ ∨ ¬C

A B

→ ∧ →

(A B) A B

→ ∧ →

A (B A B)

∨ ∧ → ¬A

A (B C)

∧ ∧ ∨ ¬C

(A B C) 3

Semantica

Tavole di verità

Consideriamo l’insieme di tutti i connettivi che abbiamo definito. Ad og-

nuno di essi corrisponde una tavola di verità che ne determina univocamente

la semantica. ¬A

A

0 1

1 0

∧ ∨

A B A B A B A B

0 0 0 0 0 0

0 1 0 0 1 1

1 0 0 1 0 1

1 1 1 1 1 1

↔

→ A B A B

A B A B 0 0 1

0 0 1 0 1 0

0 1 1 1 0 0

1 0 0 1 1 1

1 1 1

La scelta di questi connettivi è convenzionale: in realtà si potrebbero

considerare anche altri connettivi, come l’XOR informatico (che indicher-

⊕

emo con ) o il “né ... né...”, corrispondente al NOR informatico (che

↓),

indicheremo con ciascuno accompagnato dalla sua tavola semantica.

↓

⊕ A B A B

A B A B 0 0 1

0 0 0 0 1 0

0 1 1 1 0 0

1 0 1 1 1 0

1 1 0

B C {¬, ∧, ∨, →, ↔, ⊕, ↓}

Un sottoinsieme dell’insieme = dei connettivi

si dice base se per ogni connettivo non appartenente a tale insieme esiste

B

una formula contenente solo i connettivi di tale che l’ultima colonna della

sua tavola di verità sia uguale all’ultima colonna di quella corrispondente al

3

connettivo prescelto . B {¬, ∧}

A lezione si è visto che = è una base: infatti gli altri connettivi

sono stati definiti a partire da essi ponendo:

3 B ∈ C,

Più precisamente, è una base se per ogni connettivo binario AcB è logica-

c

mente equivalente (nel senso che definiremo più avanti) ad una formula contente solo A,

B C).

B, parentesi e connettivi di (e analogamente per ogni connettivo unario di

4

• ∨ ¬(¬F ∧ ¬G);

F B come abbreviazione di

• → ¬F ∨

F G come abbreviazione di G;

• ↔ → ∧ →

F G come abbreviazione di (F G) (G F ),

⊕ ↓.

e da questi si possono facilmente definire e

Esercizi. {¬, ∧}, {¬, ∨}, {¬, →}

1. Verificare che sono basi i seguenti insiemi: e

{↓}.

Seguendo l’albero di costruzione, è possibile utilizzare le tavole di verità

dei connettivi per costruire la tavola di verità di una formula qualunque.

S {A } F(S)

Sia ora = , . . . , A un insieme di formule atomiche, e sia

1 n

l’insieme di formule che si possono costruire a partire da esse.

S

Un assegnamento su è definito come una funzione

A S → {0,

: 1}. F(S).

Tale funzione si estende in maniera naturale a tutte le formule di

Osservazione. Data una formula F , ogni assegnamento sulle sue sottoformule

atomiche corrisponde ad una riga della tavola di verità: dunque calcolare la tavola

di verità è equivalente a considerare tutti i possibili assegnamenti (sulle sue sotto-

formule atomiche). A S ∈ F(S),

Definizione 2. Dato un assegnamento su ed una formula F

A A)

diremo che modella F (o, equivalentemente, che F è vera rispetto ad

A(F A |=

se ) = 1. In questo caso scriveremo F . A A(F

F si dirà soddisfacibile se esiste un assegnamento tale che ) = 1.

F si dirà valida (o che F è una tautologia, o che è sempre vera) se per

A A(F |=

ogni assegnamento si ha ) = 1. In questo caso scriveremo F .

F si dirà insoddisfacibile (o che F è una contraddizione) se non è

A A(F

soddisfacibile, cioè se per ogni assegnamento si ha ) = 0.

Osservazione. ¬F

È evidente che F è una tautologia sse è una contraddizione.

Inoltre F è soddisfacibile sse F non è una contraddizione, e ogni tautologia è anche

soddisfacibile.

Infine, F è valida (rispettivamente, soddisfacibile o contraddizione) se nella colonna

terminale della sua tavola di verità compare solo l’1 (risp. ,almeno un 1, nessun 1).

5 |=

Definizione 3. Si dice che G è conseguenza (logica) di F (e si scrive F

|=

G) se ogni assegnamento che modella F modella anche G. In simboli, F G

A, A |= A |=

sse per ogni assegnamento se F allora G. ≡

F e G si dicono (logicamente) equivalenti (e si scrive F G) sse sono

|= |=

una conseguenza logica dell’altra, cioè se F G e G F .

|= |= →

Proposizione 1. F G se e solo se F G.

≡ |= ↔

F G se e solo se F G.

F

Per analogia, se è un insieme di formule e G è un’altra formula, di-

F F |=

remo che G è conseguenza logica di (e scriveremo G) se per ogni

A F A(G)

assegnamento che modella tutte le formule di si ha = 1.

V

F F

È evidente che se è finito, indicando con la congiunzione di tutte

F,

le formule che compaiono in si ha

^ ^

F |= F |= |= F →

G sse G sse G.

Esercizi.

1. Costruire le tavole di verità delle seguenti proposizioni:

→ →

(A A) A

→ →

A (A A)

∨ → ∧

A B A B

∨ ∧ → ∧ ∨

A (B C) (A C) D

→ →

A (B A)

2. Costruire le tavole di verità delle seguenti formule e dire se sono

tautologie, contraddizioni o nessuna delle due:

→ ∨ ∧ ¬C) ↔

(¬A B) ((A B)

→ ∧ → ¬B)

(A B) (A

→ ∨ ∨ → ¬A)

(A (B C)) (C

→ ∧ ∨ ∧

((A B) C) (A D)

3. Per ciascuna delle coppie di formule seguenti dire se sono equivalenti

tra di loro:

∧ ∨ → ¬B) →

(A B) C e (A C

→ → → →

((A B) B) B e A B

→ → → → ∨

((A B) A) A e (C D) C

↔ ∧ ∨ ∧ ¬B)) ¬B

A ((¬A B) (A e

∨ ∧ ∨ ¬C →

A (¬B C) e B A 6

4. Stabilire se:

→ ∧ |= → →

A B C (A B) C

F {¬A → → ¬C ∨

5. Sia = B, B C, A}. Stabilire se:

F |= A

6. Mostrare che le seguenti affermazioni sono equivalenti:

|=

(a) F G

|= →

(b) F G

∧ ¬G

(c) F è insoddisfacibile

≡ ∧

(d) F F G.

7. Mostrare che le seguenti affermazioni sono equivalenti:

≡

(a) F G

|= ↔

(b) F G

∧ ¬G) ∨ ∧

(c) (F (¬F G) è insoddisfacibile.

8. Stabilire se le seguenti formule sono valide:

∨ ∧ → → →

(A B) (B C) (¬C A)

→ ∧ → → → →

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

→ → ↔ ∧ →

(A B) C A B C

→ → ↔ ∧ →

A (B C) A B C

9. Verificare la validità delle seguenti leggi logiche notevoli:

7 →

Legge dell’identità A A

↔ ¬¬A

Legge della doppia negazione A

∧ ∧ ↔ ∧

Commutatività di A B B A

∧ ∧ ∧ ↔ ∧ ∧

Associatività di (A B) C A (B C)

∨ ∨ ↔ ∨

Commutatività di A B B A

∨ ∨ ∨ ↔ ∨ ∨

Associatività di (A B) C A (B C)

∧ ∧ ↔

Idempotenza di A A A

∨ ∨ ↔

Idempotenza di A A A

∧ ∧ →

Eliminazione di A B A

∨ → ∨

Introduzione di A A B

∧ ∨ ↔ ∧ ∨ ∧

Distributività A (B C) (A B) (A C)

∨ ∧ ↔ ∨ ∧ ∨

Distributività A (B C) (A B) (A C)

∧ ∨ ↔

Legge di assorbimento A (A B) A

∨ ∧ ↔

Legge di assorbimento A (A B) A

¬(A ∧ ↔ ∨ ¬B)

Legge di De Morgan B) (¬A