Introduzione alla logica matematica

(1)

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

(2)

Logica matematica

formalizzazione dei meccanismi di ragionamento

la logica studia proposizioni

una proposizione può essere vera o falsa

logica a due valori di verità

(3)

Formalizzazione

sintassi

in che modo scrivere le proposizioni

semantica

significato delle proposizioni

(4)

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à

(5)

Logica proposizionale

Ad ogni proposizione elementare viene associata una variabile proposizionale

A = fa caldo

B = è umido

C = è estate

D = pioverà

(6)

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

(7)

Sintassi

La logica proposizionale tratta formule.

Una formula è composta da:

formule atomiche o atomi (A, B, C, ...)

connettivi logici

parentesi ( )

(8)

Connettivi logici

¬ not

negazione

∨ or

disgiunzione

∧ and

congiunzione

→ if then

implicazione

↔ if and only if

bi-implicazione

(9)

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)

(10)

Priorità dei connettivi

Stabilendo un ordinamento tra i connettivi è possibile

eliminare alcune parentesi. L’ordine adottato è il seguente:

1. ¬

2. ∧, ∨ 3. →, ↔

(11)

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.

(12)

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.

(13)

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

(14)

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.

(15)

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.

(16)

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.

(17)

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.

(18)

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

(19)

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

(20)

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

(21)

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)

(22)

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

(23)

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.

(24)

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 è una contraddizione.

(25)

Connettivi logici in Java

applicabili ad operandi di tipo boolean

operatore unario

! not

operatori binari

& and

ˆ xor (or esclusivo)

| or

&& and condizionale

|| or condizionale

(26)