DIMOSTRAZIONE DI TAUTOLOGIE

DIMOSTRAZIONE DI TAUTOLOGIE
Andrea Corradini e Francesca Levi
Dipartimento di Informatica
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 1
Dimostrazione di Tautologie
Calcolo Proposizionale per formalizzare Enunciati: Esempio
I
Tre amici, Antonio, Bruno e Corrado, sono incerti se andare al
cinema.
I
Introduciamo tre proposizioni:
I
I
I
I
Si sa che:
I
Se Corrado va al cinema, allora ci va anche Antonio;
I
I
A ≡“Antonio va al cinema”
B ≡ “Bruno va al cinema”
C ≡ “Corrado va al cinema”
C ⇒A
Condizione necessaria affinché Antonio vada al cinema è che ci vada
Bruno.
I
A. Corradini e F.Levi
A⇒B
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 2
Dimostrazione di Tautologie
Calcolo Proposizionale per formalizzare Enunciati: Esempio
(cont.)
I
Il giorno successivo possiamo affermare con certezza che:
I
Se Corrado è andato al cinema, allora ci è andato anche Bruno
I
I
I
I
B⇒C
Se Corrado non è andato al cinema, allora non ci è andato nemmeno
Bruno
I
I
(¬A) ∧ (¬B) ∧ (¬C )
Se Bruno è andato al cinema, allora ci è andato anche Corrado
I
I
C ⇒B
Nessuno dei tre amici è andato al cinema
(¬C ) ⇒ (¬B)
Per rispondere alla domanda, dobbiamo capire quale di queste quattro
proposizioni è conseguenza logica delle proposizioni precedenti
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 3
Dimostrazione di Tautologie
Come possiamo essere certi della risposta?
I
Bisogna determinare quale delle ultime 4 formule è conseguenza logica
delle premesse, cioè quale delle seguenti formule è una tautologia:
1.
2.
3.
4.
((C
((C
((C
((C
⇒ A) ∧ (A ⇒ B)) ⇒ (C ⇒ B)
⇒ A) ∧ (A ⇒ B)) ⇒ ((¬A) ∧ (¬B) ∧ (¬C ))
⇒ A) ∧ (A ⇒ B)) ⇒ (B ⇒ C )
⇒ A) ∧ (A ⇒ B)) ⇒ ((¬C ) ⇒ (¬B))
I
Si possono verificare con tabelle di verità o trovando un
controesempio
I
Chiaramente la (1) è una tautologia, mentre la (2), (3) e la (4) non
sono tautologie !!!!
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 4
Dimostrazione di Tautologie
Come si vede che una Formula non è una Tautologia?
I
Esempio: (3) ((C ⇒ A) ∧ (A ⇒ B)) ⇒ (B ⇒ C )
I
Basta trovare un’interpretazione che la rende falsa (un
controesempio)
I
I
I
I
I
Determiniamo valori di verità per A, B e C che rendano falsa la formula
Poiché è un’implicazione, è falsa solo quando la premessa è vera e la
conseguenza è falsa
Quindi (B ⇒ C ) deve essere falso, quindi {B 7→ T, C 7→ F}
A questo punto si vede che per qualunque valore di A la premessa è
vera.
Quindi le seguenti interpretazioni rendono la formula falsa:
{A 7→ T, B 7→ T, C 7→ F} e {A 7→ F, B 7→ T, C 7→ F}
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 5
Dimostrazione di Tautologie
Dimostrazione di Tautologie
Abbiamo detto che: Per dimostrare che p è una tautologia possiamo:
I
Usare le tabelle di verità, sfruttando quelle dei connettivi
I
I
Del tutto meccanico, richiede di considerare 2n casi, dove n è il numero
di variabili proposizionali in p
In alternativa, possiamo cercare di costruire una dimostrazione
I
I
I
Usando delle leggi (tautologie già dimostrate)
Usando opportune regole di inferenza
Si possono impostare vari tipi di dimostrazioni
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 6
Dimostrazione di Tautologie
Dimostrazione di Tautologie
I
I
Il sistema di dimostrazioni che presenteremo è ispirato alla struttura
delle dimostrazioni dell’aritmetica
Consente di dimostrare equivalenze tautologiche p ≡ q
I
I
Si usano delle leggi per l’equivalenza
Regola di Inferenza: il principio di sostituzione
I
Ma come è strutturata una dimostrazione?
I
Cominciamo dall’aritmetica rivisitando una semplice dimostrazione ed
analizzandone la struttura
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 7
Dimostrazione di Tautologie
Dimostrazioni: cominciamo dall’Aritmetica
I
Mostriamo che (a + b)(a − b) = a2 − b2
(a + b)(a − b)
= {(distributività (x + y )z = xz + yz) con a al posto di y , b al posto
di z e (a − b) al posto di x}
a(a − b) + b(a − b)
= {(distributività x(y − z) = xy − xz), due volte, la prima volta
applicata la prima volta con x = a, y = a, z = b e la seconda con
x = b, y = a, z = b}
(aa − ab) + (ba − bb)
= {(quadrato xx = x 2 ), due volte, e (associatività) della somma
a2 −ab + ba − b2 }
= (commutatività) del prodotto, e (differenza −x + x = 0)
a2 + 0 − b2
= {(elemento neutro x + 0 = x)}
a2 − b2
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 8
Dimostrazione di Tautologie
Struttura di una semplice Dimostrazione
I
Nella dimostrazione vista abbiamo
I
una sequenza di eguaglianze
I
I
Ogni eguaglianza ha come giustificazione una o più leggi
(dell’aritmetica)
I
I
es: a2 + 0 − b2 = a2 − b2
es: x + 0 = x (Elemento neutro)
La correttezza di ogni eguaglianza è basata su una regola di
inferenza: il principio di sostituzione. Informalmente:
“Sostituendo eguali con eguali il valore non cambia”
I
I
es: dalla legge sappiamo che a2 + 0 = a2
sostituendo a2 + 0 con a2 in a2 + 0 − b2 otteniamo a2 − b2
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 9
Dimostrazione di Tautologie
Principio di Sostituzione
I
Esprime una proprietà fondamentale dell’eguaglianza
I
Consente di trasformare le espressioni usando le ben note leggi
algebriche
I
“Se p = q allora il valore di una espressione r in cui compare p
non cambia se p è sostituito con q”
I
I
In formule, r = r[q/p] oppure r = rpq
Qui p = q è una legge, e r = r[q/p] è l’eguaglianza da essa
giustificata, grazie al principio di sostituzione
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 10
Dimostrazione di Tautologie
Principio di Sostituzione nel Calcolo Proposizionale
I
Nel Calcolo Proposizionale vale una proprietà analoga per
l’equivalenza
I
“Se P ≡ Q allora il valore di una formula R in cui compare P
non cambia se P è sostituito con Q”
I
In formule, R ≡ R[Q/P] oppure R ≡ RQ
P
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 11
Dimostrazione di Tautologie
Dimostrazioni di Equivalenze Tautologiche
I
Come per equazioni algebriche si può provare P1 ≡ Pn nel modo
seguente:
P1
≡
{giustificazione}
P2
...
Pn−1
≡
{giustificazione}
Pn
I
Dove ogni passo ha la forma
R
≡
{P ≡ Q}
R[Q/P]
I
Ogni passo è corretto per il Principio di Sostituzione dove P ≡ Q è
una legge (tautologia)
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 12
Dimostrazione di Tautologie
Leggi del Calcolo Proposizionale
I
Una legge è una tautologia.
I
Di solito una tautologia viene chiamata “legge” quando descrive
importanti proprietà di uno o più connettivi logici, e delle relazioni tra
loro.
Per ogni legge che introduciamo, bisognerebbe verificare che sia una
tautologia
I
I
I
I
I
a volte è ovvio
a volte lo mostreremo con tabelle di verità
a volte presenteremo una dimostrazione in cui usiamo solo leggi
introdotte in precedenza
spesso lo lasceremo come esercizio...
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 13
Dimostrazione di Tautologie
Leggi per l’Equivalenza
I
p ≡ p (Riflessività)
I
(p ≡ q) ≡ (q ≡ p) (Simmetria)
I
((p ≡ q) ≡ r ) ≡ (p ≡ (q ≡ r )) (Associatività)
I
(p ≡ T) ≡ p (Unità)
I
((p ≡ q) ∧ (q ≡ r )) ⇒ (p ≡ r ) (Transitività)
I
Esempio di dimostrazione: (Unità)
P
T
F
A. Corradini e F.Levi
–
(P
T
F
(1)
Dip.to Informatica
≡
T
F
(2)
T)
T
T
(1)
≡
T
T
(3)
P
T
F
(1)
Logica per la Programmazione a.a. 15/16 –
pag. 14
Dimostrazione di Tautologie
Leggi per Congiunzione e Disgiunzione (1)
p∨q ≡q∨p
p∧q ≡q∧p
(Commutatività)
p ∨ (q ∨ r ) ≡ (p ∨ q) ∨ r
p ∧ (q ∧ r ) ≡ (p ∧ q) ∨ r
(Associatività)
p ∧ (q ∨ r ) ≡ (p ∧ q) ∨ (p ∧ r ) (Distributività)
p ∨ (q ∧ r ) ≡ (p ∨ q) ∧ (p ∨ r )
I
Esercizio: dimostrare la (Distributività) con le tabelle di verità
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 15
Dimostrazione di Tautologie
Leggi per Congiunzione e Disgiunzione (2)
p∨p ≡p
p∧p ≡p
(Idempotenza)
p∧T≡p
p∨F≡p
(Unità)
p ∧ F ≡ F (Zero) (Dominanza)
p∨T≡T
I
Esercizio: dimostrare alcune leggi con tabelle di verità
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 16
Dimostrazione di Tautologie
Leggi della Negazione
¬(¬p) ≡ p
(Doppia Negazione)
p ∨ ¬p ≡ T
p ∧ ¬p ≡ F
(Terzo escluso)
(Contraddizione)
¬T ≡ F
¬F ≡ T
(T: F)
(F: T)
¬(p ∧ q) ≡ ¬p ∨ ¬q (De Morgan)
¬(p ∨ q) ≡ ¬p ∧ ¬q
I
Esercizio: dimostrare alcune le leggi di De Morgan con tabelle di
verità
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 17
Dimostrazione di Tautologie
Leggi della Implicazione
I
(p ⇒ q) ≡ (¬p ∨ q) (Elim- ⇒)
I
(p ≡ q) ≡ (p ⇒ q) ∧ (q ⇒ p) (Elim- ≡)
I
(p ⇐ q) ≡ (q ⇒ p) (Elim- ⇐ )
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 18
Dimostrazione di Tautologie
Una Semplice Dimostrazione
Teorema: p ∨ (q ∨ r ) ≡ (p ∨ q) ∨ (p ∨ r )
(p ∨ q) ∨ (p ∨ r )
≡
{(p ∨ q) ≡ (q ∨ p) (Commutatività)}
(q ∨ p) ∨ (p ∨ r )
≡
{(Associatività)}
q ∨ (p ∨ (p ∨ r ))
≡
{(Associatività)}
q ∨ ((p ∨ p) ∨ r ))
≡
{(Idempotenza)}
q ∨ (p ∨ r ))
≡
{(Associatività)}
(q ∨ p) ∨ r
≡
{(Commutatività)}
(p ∨ q) ∨ r
≡
{(Associatività)}
p ∨ (q ∨ r )
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 19
Dimostrazione di Tautologie
Commenti
I
La dimostrazione fatta usando le leggi garantisce la correttezza della
dimostrazione grazie al Principio di Sostituzione
I
Nel seguito semplificheremo le dimostrazioni, saltando passi ovvi
come l’applicazione di Associatività, Commutatività e Idempotenza
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 20
Dimostrazione di Tautologie
Commenti
I
Si può mostrare che tutte le tautologie del Calcolo Proposizionale
sono dimostrabili a partire dall’insieme delle leggi visto sinora
I
Naturalmente la tecnica non automatizza le dimostrazioni. Rimane a
carico nostro la scelta delle leggi da usare, da quale membro della
equivalenza partire, l’organizzazione della sequenza dei passaggi
I
Conviene comunque, per motivi di espressività e compattezza delle
definizioni, introdurre altre leggi derivate che sono molto utili in
pratica
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 21
Dimostrazione di Tautologie
La (1) è una Tautologia (Transitività dell’implicazione)
((C ⇒ A) ∧ (A ⇒ B)) ⇒(C ⇒ B)
≡
{(Elim.-⇒)}
¬((C ⇒ A) ∧ (A ⇒ B)) ∨ (C ⇒ B)
≡
{(Elim.-⇒), 3 volte}
¬((¬C ∨ A) ∧ (¬A ∨ B)) ∨ (¬C ∨ B)
≡
{(De Morgan)}
¬(¬C ∨ A) ∨ ¬(¬A ∨ B) ∨ (¬C ∨ B)
≡
{(De Morgan) 2 volte, (Doppia Neg.)}
(C ∧ ¬A) ∨ (A ∧ ¬B) ∨ (¬C ∨ B)
≡
{(Comm.), (Assoc.)}
((C ∧¬A) ∨¬C ) ∨ ((A ∧¬B) ∨ B)
≡
{(Distr.) 2 volte}
((C ∨ ¬C ) ∧ (¬A ∨ ¬C )) ∨ ((A ∨ B) ∧ (¬B ∨ B))
≡
{(Terzo Escluso) 2 volte}
(T ∧ (¬A ∨ ¬C )) ∨ ((A ∨ B) ∧ T)
≡
{(Unità)}
(¬A ∨ ¬C ) ∨ (A ∨ B)
≡
{(Terzo Escluso)}
T ∨¬C ∨ B
≡
{(Zero)}
T
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 22
Dimostrazione di Tautologie
Leggi Derivate: Complemento
p ∨ (¬p ∧ q) ≡ p ∨ q (Complemento)
p ∧ (¬p ∨ q) ≡ p ∧ q
I
Dimostriamo come esempio la prima p ∨ (¬p ∧ q) ≡ p ∨ q
I
p ∨ (¬p ∧ q)
≡
{(Distr.)}
(p ∨ ¬p) ∧ (p ∨ q)
≡
{(Terzo Escluso)}
T ∧ (p ∨ q)
≡
{(Unità)}
(p ∨ q)
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 23
Dimostrazione di Tautologie
Leggi Derivate: Assorbimento
p ∧ (p ∨ q) ≡ p (Assorbimento)
p ∨ (p ∨ q) ≡ p
I
Dimostriamo come esempio la prima p ∧ (p ∨ q) ≡ p
I
p ∧ (p ∨ q)
≡
{(Unità)}
(p ∨ F) ∧ (p ∨ q)
≡
{(Distr.)}
p ∨ (F ∧ q)
≡
{(Zero)}
p∨F
≡
{(Unità)}
p
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 24
Dimostrazione di Tautologie
Esercizi Proposti
Dimostrare tramite una dimostrazione per sostituzione che le seguenti
formule sono tautologie:
I
((Q ⇒ P) ⇒ R) ≡ ((P ⇒ R) ∧ (¬Q ⇒ R)),
I
(P ∧ Q) ⇒ Q,
I
(P ∧ (P ⇒ Q)) ⇒ Q,
I
((Q ∨ S) ∧ (Q ⇒ ¬P)) ⇒ (P ⇒ S).
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 25
Dimostrazione di Tautologie
Insiemi Funzionalmente Completi di Connettivi Logici
I
Abbiamo introdotto 6 tipi di connettivo logico:
Connettivo
not
and, e
or , o
se p allora q
p se e solo se q
p se q
Forma simbolica
¬p
p∧q
p∨q
p⇒q
p≡q
p ⇐ q
Operazione corrispondente
negazione
congiunzione
disgiunzione
implicazione
equivalenza
conseguenza
I
Alcuni possono essere definiti in termini di altri.
I
Molti sottoinsiemi sono “funzionalmente completi” cioè permettono
di derivare tutti gli altri.
I
Vediamo che {∧, ¬} è funzionalmente completo.
I
Esercizio: dimostrare che anche {∨, ¬} e {⇒, ¬} sono
funzionalmente completi.
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 26
Dimostrazione di Tautologie
L’Insieme {∧, ¬} è funzionalmente completo
I
Occorre mostrare che una qualunque formula proposizionale è
equivalente a una formula che contiene solo {∧, ¬}. Per induzione
strutturale sulla sintassi delle formule:
I
I
implicazione (⇒), conseguenza ( ⇐ ) ed equivalenza (≡) possono
essere eliminate.
disgiunzione:
p∨q
≡
{(Doppia Neg.)}
¬¬(p ∨ q)
≡
{(De Morgan)}
¬(¬p ∧ ¬q)
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 27
Dimostrazione di Tautologie
Il Connettivo “NAND”
I
Si consideri il connettivo proposizionale binario nand la cui semantica
è definita dalla seguente tabella di verità:
P
F
F
T
T
I
Q
F
T
F
T
P nand Q
T
T
T
F
Esercizio: si provi che l’insieme {nand} è funzionalmente completo.
A. Corradini e F.Levi
–
Dip.to Informatica
Logica per la Programmazione a.a. 15/16 –
pag. 28