Introduzione alla logica matematica
Silvana Badaloni Paolo Bison
Fondamenti di Informatica 1 A.A. 2004/05
Universit`a di Padova
Introduzione alla logica matematica, Paolo Bison, A.A. 2004-05, 2004-10-26 – p.1/29
Logica matematica
formalizzazione dei meccanismi di ragionamento
la logica studia proposizioni
una proposizione può essere vera o falsa
logica a due valori di verità
Formalizzazione
sintassi
in che modo scrivere le proposizioni
semantica
significato delle proposizioni
Introduzione alla logica matematica, Paolo Bison, A.A. 2004-05, 2004-10-26 – p.3/29
Logica proposizionale
P1: Se fa caldo ed è umido allora pioverà
P2: Se è umido ed è estate allora fa caldo
P3: adesso è umido
P4: adesso è estate si vuole verificare:
P5: pioverà
Logica proposizionale
Ad ogni proposizione elementare viene associata una variabile proposizionale
A = fa caldo
B = è umido
C = è estate
D = pioverà
Introduzione alla logica matematica, Paolo Bison, A.A. 2004-05, 2004-10-26 – p.5/29
Logica proposizionale
La rappresentazione per l’esempio è
F1: A ∧ B → D
F2: B ∧ C → A
F3: B
F4: C
si vuole dimostrare che da F1-F4 segue logicamente:
F5: D
∧ rappresenta la congiunzione (and)
→ rappresenta la implicazione logica
Sintassi
La logica proposizionale tratta formule.
Una formula è composta da:
formule atomiche o atomi (A, B, C, ...)
connettivi logici
parentesi ( )
Introduzione alla logica matematica, Paolo Bison, A.A. 2004-05, 2004-10-26 – p.7/29
Connettivi logici
¬ not
negazione
∨ or
disgiunzione
∧ and
congiunzione
→ if then
implicazione
↔ if and only if
bi-implicazione
Formule ben formate
Una formula è ben formata (FBF) se e solo se essa è ottenibile applicando le seguenti regole:
1. un atomo è una FBF
2. se F è una FBF, allora (¬F ) è una FBF
3. se F e G sono FBF, allora lo sono anche (F ∨ G), (F ∧ G), (F → G) e (F ↔ G)
Introduzione alla logica matematica, Paolo Bison, A.A. 2004-05, 2004-10-26 – p.9/29
Priorità dei connettivi
Stabilendo un ordinamento tra i connettivi è possibile
eliminare alcune parentesi. L’ordine adottato è il seguente:
1. ¬
2. ∧, ∨
3. →, ↔
Semantica
la semantica della logica proposizionale richiede l’introduzione dei valori di verità
B = {T, F}
dare una interpretazione vuol dire trovare una funzione V : F → {T, F}
essendo F l’insieme delle formule ben formate FBF del Calcolo Proposizionale.
Introduzione alla logica matematica, Paolo Bison, A.A. 2004-05, 2004-10-26 – p.11/29
Valore di verità di una formula
Si può calcolare il valore di verità di una espressione del Calcolo Proposizionale a partire
dai valore di verità delle formule atomiche che la compongono (interpretazioni) e
dalle tabelle di verità dei connettivi logici.
Tabelle di verità dei connettivi logici
A B (¬A) (A ∧ B) (A ∨ B) (A → B) (A ↔ B)
T T F T T T T
T F F F T F F
F T T F T T F
F F T F F T T
Introduzione alla logica matematica, Paolo Bison, A.A. 2004-05, 2004-10-26 – p.13/29
Tautologie
Alcune formule sono vere in tutte le interpretazioni.
((P ∧ (P → Q)) → Q)
P Q (P → Q) P ∧ (P → Q) ((P ∧ (P → Q)) → Q)
T T T T T
T F F F T
F T T F T
F F T F T
Tautologie o formule valide.
Contraddizioni
formule che sono false in tutte le interpretazioni.
((P → Q) ∧ P ) ∧ (¬Q)
P Q (P → Q) (¬Q) ((P → Q) ∧ P ) ∧ (¬Q)
T T T F F
T F F T F
F T T F F
F F T T F
Contraddizioni o formule inconsistenti.
Introduzione alla logica matematica, Paolo Bison, A.A. 2004-05, 2004-10-26 – p.15/29
Decidibilità della logica proposizionale
Ogni formula è finita e contiene un numero finito di formule atomiche:
quindi è sempre possibile determinare se essa è valida, inconsistente o ne’ l’uno ne’ l’altro.
La logica proposizionale è decidibile.
Equivalenza Logica
Due formule F e G sono
equivalenti, e si indica con F ≡ G, se e solo se esse hanno lo stesso valore di verità in tutte le interpretazioni.
Si può dimostrare che F ≡ G se e solo se la formula (F ↔ G) è una tautologia.
Introduzione alla logica matematica, Paolo Bison, A.A. 2004-05, 2004-10-26 – p.17/29
Relazioni di equivalenza logica - I
F ≡ F identità
¬(¬F ) ≡ F doppia negazione (G ∧ G) ≡ G idempotenza (G ∨ G) ≡ G idempotenza (G∧T) ≡ G legge dei neutri (G∧F) ≡ F legge dei neutri (G∨T) ≡ T legge dei neutri (G∨F) ≡ G legge dei neutri (G ∧ ¬G) ≡ F esclusione
Relazioni di equivalenza logica - II
(G ∨ ¬G) ≡ T complementarietà
((F ∧ G) ∧ H) ≡ ((F ∧ (G ∧ H) associatività ((F ∨ G) ∨ H) ≡ ((F ∨ (G ∨ H) associatività
(F ∧ G) ≡ (G ∧ F ) commutatività
(F ∨ G) ≡ (G ∨ F ) commutatività
(F ∧ (G ∨ H)) ≡ ((F ∧ G) ∨ (F ∧ H)) distributività (F ∨ (G ∧ H)) ≡ ((F ∨ G) ∧ (F ∨ H)) distributività
¬(F ∨ G) ≡ (¬F ∧ ¬G) legge di De Morgan
¬(F ∧ G) ≡ (¬F ∨ ¬G) legge di De Morgan
Introduzione alla logica matematica, Paolo Bison, A.A. 2004-05, 2004-10-26 – p.19/29
Relazioni di equivalenza logica - III
(F ∨ (F ∧ G)) ≡ F assorbimento
(F ∧ (F ∨ G)) ≡ F assorbimento
(F ∨ (¬F ∧ G)) ≡ (F ∨ G) assorbimento
(F ∧ (¬F ∨ G)) ≡ (F ∧ G) assorbimento
(F → G) ≡ (¬F ∨ G) eliminazione implicazione (F → (G → H)) ≡ (G → (F → H)) proprietà implicazione (F → (G → H)) ≡ ((F ∧ G) → H) proprietà implicazione (F ↔ G) ≡ ((F → G) ∧ (G → F )) doppia implicazione
Esempio - I
verificare che le seguenti formule sono equivalenti:
(a) (P ∧ Q) → ¬ (P ∧ R) (b) ¬ (P ∧ Q ∧ R) (a) (P ∧ Q) → ¬(P ∧ R) elimin.impl.
≡ ¬(P ∧ Q) ∨ ¬(P ∧ R) DeMorgan
≡ ¬(P ∧ Q ∧ P ∧ R) commutativa
≡ ¬(P ∧ P ∧ Q ∧ R) idempotenza
≡ ¬(P ∧ Q ∧ R) (b)
Introduzione alla logica matematica, Paolo Bison, A.A. 2004-05, 2004-10-26 – p.21/29
Esempio - IIa
Verificare se la seguente formula è una tautologia:
(a) (A → B) → ((A → ¬B) → ¬A)
tabella di verità
A B (A → B) (A → ¬B) ((A → ¬B) → ¬A) (a)
T T T F T T
T F F T F T
F T T T T T
F F T T T T
Esempio - IIb
relazione di equivalenza
(A → B) → ((A → ¬B) → ¬A) ≡ propr. impl.
≡ ((A → B) ∧ ((A → ¬B)) → ¬A) elim. impl.
≡ ((¬A ∨ B) ∧ (¬A ∨ ¬B)) → ¬A elim. impl.
≡ ¬((¬A ∨ B) ∧ (¬A ∨ ¬B)) ∨ ¬A distributiva
≡ ¬(¬A ∨ (B ∧ ¬B)) ∨ ¬A neutri
≡ ¬(¬A∨F) ∨ ¬A neutri
≡ ¬(¬A) ∨ ¬A doppia neg.
≡ A ∨ ¬A compl.
≡ T.
Introduzione alla logica matematica, Paolo Bison, A.A. 2004-05, 2004-10-26 – p.23/29
Do it yourself - I
Si dica se la seguente formula è una tautologia:
¬P ∧ (P ∨ Q) ∧ (¬ (P ∨ Q) ∨ P ) ∧ ¬ (P ∨ Q)
Si dica se le seguenti espressioni del calcolo proposizionale sono o non sono equivalenti:
(a) (P ∧ Q) → R (b) P → ¬ (Q → R)
Si dica se la seguente formula del calcolo proposizionale
((R → T ) ∧ (T → R) ∧ T ) → R
Connettivi logici in Java
applicabili ad operandi di tipo boolean
operatore unario
! not
operatori binari
& and
ˆ xor (or esclusivo)
| or
&& and condizionale
|| or condizionale
Introduzione alla logica matematica, Paolo Bison, A.A. 2004-05, 2004-10-26 – p.25/29
Connettivi logici in Java
tabelle di verità
A e B espressioni di tipo boolean
A B !A A&B A|B AˆB
true true false true true false
true false false false true true
false true true false true true
false false true false false false
Esempi di espressioni
k>=0 & k<n (ERRATO 0<=k<n)
k<0 | k>=n
!(k>=0 & k<n)
!(x>0 | y<x)&(x<=0)
Introduzione alla logica matematica, Paolo Bison, A.A. 2004-05, 2004-10-26 – p.27/29
Connettivi condizionali
il secondo operando viene valutato se e solo se
il primo è true se l’operatore è &&
il primo è false se l’operatore è ||
esempi
k>=0 && k<n
k<0 || k>=n
a!=0 && b/a>100 (ERRATO a!=0 & b/a>100)
a==0 & (c=b)>100 (ERRATO a==0 && (c=b)>100)
Do it yourself - II
esprimere il connettivo xor in termini degli altri connettivi
Introduzione alla logica matematica, Paolo Bison, A.A. 2004-05, 2004-10-26 – p.29/29
