Introduzione alla logica matematica Paolo Bison
Fondamenti di Informatica Ingegneria Meccanica
Università di Padova A.A. 2008/09
lucidi basati su note della prof. S. Badaloni
Introduzione alla logica matematica, Paolo Bison, FI08, 2008-09-29 – p.1
Logica matematica
formalizzazione dei meccanismi di ragionamento
la logica studia proposizioni
una proposizione può essere vera o falsa
logica a due valori di verità
Introduzione alla logica matematica, Paolo Bison, FI08, 2008-09-29 – p.2
Formalizzazione
sintassi
in che modo scrivere le proposizioni
semantica
significato delle proposizioni
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, FI08, 2008-09-29 – p.5
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
Introduzione alla logica matematica, Paolo Bison, FI08, 2008-09-29 – p.6
Sintassi
La logica proposizionale tratta formule.
Una formula è composta da:
formule atomiche o atomi (A, B, C, ...)
connettivi logici
parentesi ( )
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, FI08, 2008-09-29 – p.9
Priorità dei connettivi
Stabilendo un ordinamento tra i connettivi è possibile eliminare alcune parentesi. L’ordine adottato è il seguente:
1. ¬ 2. ∧ , ∨ 3. → , ↔
Introduzione alla logica matematica, Paolo Bison, FI08, 2008-09-29 – p.10
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.
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, FI08, 2008-09-29 – p.13
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.
Introduzione alla logica matematica, Paolo Bison, FI08, 2008-09-29 – p.14
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.
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, FI08, 2008-09-29 – p.17
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
Introduzione alla logica matematica, Paolo Bison, FI08, 2008-09-29 – p.18
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
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, FI08, 2008-09-29 – p.21
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
Introduzione alla logica matematica, Paolo Bison, FI08, 2008-09-29 – p.22
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.
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
Tipo logical in Fortran
insieme dei valori di verità (falso, vero)
operatori
.not. .and. .or. .eqv. .neqv.
costanti
le due parole chiave .FALSE. e .TRUE.
operatori di confronto
< <= > >= / = ==
notazione equivalente
.lt. .le. .gt. .ge. .eq. .ne.
Introduzione alla logica matematica, Paolo Bison, FI08, 2008-09-29 – p.25
Semantica operatori logici
a b .not. a a .and. b a .or. b a .eqv. b a .neqv. b
F F T F F T F
F T T F T F T
T F F F T F T
T T F T T T F
Introduzione alla logica matematica, Paolo Bison, FI08, 2008-09-29 – p.26
Priorità operatori
ordine dal maggiore al minore
**
* / + -
< <= > >= == /=
.not.
.and.
.or.
.eqv .neqv.
ordine di valutazione:
da sinistra a destra eccetto ** e .not.
Esempi d’uso
logical :: p,u,q integer :: x=0,y=10
u= x >=0 .and. x <9 ! ERRATO 0<=x<9 p=.FALSE.;q=x>y;
u=x .gt. y .and. p
u=p .eqv. q ! test uguaglianza per logical,
! errato usare ==
pari.f90
!
! pari.f90
! data una sequenza, terminata da 0, di numeri positivi in ingresso
! stampa T se sono tutti pari, F altrimenti program pari
logical :: tuttiPari integer :: n tuttiPari=.TRUE.
do read *,n
if (n<0) then; stop; end if ! dati in ingresso non corretti if (n==0) then; exit; end if
tuttiPari= tuttiPari .and. n - (n/2)*2 == 0 end do
print *,tuttiPari end program pari
Introduzione alla logica matematica, Paolo Bison, FI08, 2008-09-29 – p.29
Do it yourself - II
esprimere il connettivo xor (or esclusivo) in termini degli altri connettivi
A B A xor B
true true false true false true false true true false false false
Introduzione alla logica matematica, Paolo Bison, FI08, 2008-09-29 – p.30
