Logica proposizionale e Logica del primo ordine

Logica Proposizionale

Paradosso di Russell: "Sia R_L l'insieme di tutti gli insiemi che non contengono se stessi

se R∈R ⇒ R∉Rse R∉R ⇒ R∈R

Paradosso!

Sintassi Log. Proposizionale

Alfabeto:

1. Lettere enunciative: al più numerabile A₁,..A_j,...
2. Connettivi: ¬, ∧, ∨, ⇒, ⇔;
3. Simboli ausiliari: ), (;

Tra le stringhe su questo alf. (x es. A₁⇒¬)A₂∧∧∨A₃) definiano le formule ben formate:

1. Ogni lett. enunciativa è F.B.F.;
2. Se ϕ, B sono F.B.F. allora: (ϕ⇒B), (ϕ∧B), (ϕ∨B) (ϕ⇔B), (ϕϕ)
3. Nient'altro è una F.B.F.;

Esempio: ¬ (¬⇒A)∧B, ma lo è (¬(A∧B)⇒(A⇒(B∨A)))

Possiamo costruire l'albero di struttura della F.B.F.

TUTTE LE SOTTOFORME DI F SONO IN CORR. BIUNIVOCA CON I SOTTOALBERI DEL L'ALBERO SI STRUTTURE :

St.fm F : {A,B, (A∧B), ∼ (A∧B), (B∨A), (A⇒(B∨A)), F }

VI SONO TROPPE PARENTESI, SI INTRODUCE UNA PROPRIETA' SUGLI OPERATORI CONNETTIVI LOGICI.

ES:

3⋅2-5 = 11

3⋅2-5 = 21

CONVENZIONE CHE USIAMO

A⇒B⇒C = (A⇒B)⇒C

E CONNETTIVI UGUALI SI ASSOCIANO A SX

ESEMPIO

DI PRIMA

∼(A∧B) ⇔ A⇒ B∨A

VICEVERSA:

C⇒ A⇒B ⇔ ∼ A∧B∨C

((C ⇒ A)⇒B) ⇔ ((∼A) ∧B∨C)

(SEMANTICA) UNA INTERPRETAZIONE È UNA FUNZIONE:

υ: {F F.B.F} ------> {0,1}

CHE SODDISFA:

1) υ(F ) = 1 - υ(∼F );

2) υ(F ∧B) = min{υ(d ), υ(B)};

3) υ (d∨B) = max{υ(d ), υ(B)}

PIÙ COMODO LAVORARE CON LE TABB. DI VERITÀ

υ(d) | υ(d) | SU DISPERSE

0 | 1

1 | 0

Metodi formali/Sistemi deduttivi

Finalità: avere metodi automatici per verificare

Idea: Partendo dall'insieme Γ e da un insieme di assiomi A_x, con delle regole di riscrittura (di inferenza) cerchiamo di generare una sequenza di formule:

• Γ, A_x |- D₀, Γ, A_x, D₀ |- D₁, ..., Γ, D₀, D₁, D_n, Γ, A_x |- D_n = cd

La cui ultima è cd, e scriveremo Γ, A_x |- cd. Si cercano sist. formali che siano:

• Corretti: Γ, A_x |- cd ⇒ Γ |- cd
• Completi: M |- cd ⇒ Γ, A_x |- cd

Teoria L (Sistemi Hilbertiano x Logica Proposizionale)

1. Sintassi: F.B.F. che contengono ∼, ⇒
2. Assiomi:

• A_x:
  • A₁: cd ⇒ (B ⇒ cd)
  • A₂: (cd ⇒ (B ⇒ E)) ⇒ ((cd ⇒ B) ⇒ (cd ⇒ E))
  • A₃: (vcd ⇒ B) ⇒ ((vcd ⇒ B) ⇒ cd)

Osservazione: Gli assiomi sono in realtà schemi di assiomi, poiché cd, B, E sono F.B.F generiche, non solo cett. elencate.

Esempio da A₂

• cd = (C ⇒ D)
• B = (D ⇒ v A)
• (C ⇒ P) ⇒ ((D ⇒ v A) ⇒ (C ⇒ D))

Regola d'inferenza: Modus Ponens cd, cd ⇒ B ⇒ B

Definizione: Se da un insieme di formule Γ usando gli assiomi A_x e il M.P. ottengo una seq. D₁, ..., D_m F.B.T. t.c.

• Γ, A_x |- D₁, Γ, D₁, A_x |- D₂, ..., Γ, D₀, ..., D_n, A_x |- D_n = cd

dove D_i è ottenuta da due

Esempio

{ B⇒A, A∨B, ¬A } è insoddisfacibile?

Δ = { ¬B∨A, A∨B, ¬A }

Aⁿ = { ¬B, A }, Aⁿ = { B }, Aⁿ = {A }

Δⁿ = ¯_R e quindi dal teorema di correttezza e completezza per refutazione Δ è insodd.

Algoritmo Generico Γ ⊨ α

1) Γ ⊨ α ⟺ Δ_Γ ∪ { ¬α } è insoddisf. ⟺ Δ_Γ^C ¯_R

2) Ricavo le clausole Δ_α.

3) Ris (Δ_α^C) = Δ_α ∪ { R | R risolvente di due clausole Δ_α^C }

S := Δ^C

while □ ∉ S do:

if S := Ris(S) exit “Δ non è insod.”

else S := Ris(S)

exit “Δ insoddisfacibile”

In pratica calcolo Δ = Ris(Δ), Ris(Ris(S)), ..., Risⁿ(Δ)

... Se ∉ Ris^m(Δ^C) per qualche m, allora esco “Δ è insodd.”

Altrimenti c'è un N Ris^N(Δ^C) = Ris (Ris N(Δ^C)) = Ris^N+1(Δ^C)

Infatti, se Δ_α contiene n lettere, la clausola più grande che posso costruire contiene 2ⁿ lettere ⟹ N di possibili clausole ≤ 2^L

Esempio

{ (¬A∨B)∧(¬B∨A) } ⊨ ¬C∨B∨A ?

Δ = Γ ∪ { ¬C∨B∨A } = { (¬A∨B)∧(¬B∨A), ¬C∨B∨A }

PROP). Se Aⁿ è una lett. predicativa di arietà n e t₂,...,t_n sono termini

         Aⁿ(t₂,t₂,...,t_n) è una form. atomica.

ESEMPI

A¹, g³(x,y), f²(f³(x,y), g¹(g³(x))) è atomica

f³(A²(x,y),t) non è una f. atomica! (almeno un termine!)

Se A²(f²(x,y),z) la interpretiamo come x+y su D=Z, A²(x,y) come

x\y allora x\y+z non ha senso

mentre A²(f²(x,y),z) si interpreta come x+y\z

A²(A³(x,y,z), f²(x,y)) non è una f. atomica

DEF

FORMULE BEN FORMATE (F.B.F.)

1. Ogni f. atomica è una F.B.F;
2. Se α è una F.B.F. allora (¬α), (∀x α), (∃x α) sono F.B.F;
3. Se α, β sono F.B.F. allora (α∧β), (α∨β), (α→β), (α↔β) sono F.B.F.;
4. Nient’altro è una F.B.F.

ESERCIZIO: In uno schermo 2x2 pixel, se un pixel è acceso, allora

almeno uno dei pixel contigui si accende, se un pixel ha due pixel

contigui accesi, allora si spegne, mostrare che non si può disegnare

la diagonale principale

                   P_i,j = {1 se (i,j) è acceso

                    0 altrimenti

                    x=i,1,2

                     j=1,2

I₃(Aⁿ) ⊆ D_x...xD n-volte

mi associa/interpreta una rel n-aria

Es. Sia L un linguaggio del I^o ordine con cod={a₁, b₂, c} P={E(x,y), B(x,y)} f=̅ {f(x), +(x,y), P(x,y)} Con interpretazione D=ℕ

I_x a→1 b→2 c→3

I₂: f(x) → x → x+1 +(x, y) → x+y → x+1 P(x, y)|1 → (x, y)|1 → x=y

I₃: E(x,y)|1 → I₂(E) = I_w

I₃: B(x,y)|1 → I₃(b) = e

Le formule:

1. E (P(x,y) + (q,x)) si interpreta come x∙y = 1+x ;
2. B(a,b) ∨ ∃y E (P(x,y), +(q,x)) => ∀x (P(x, +(q,x)|1), ︳) l₂∧B(x,y)

si interpreta come "Se 1<2 oppure esiste y ∊ ℕ t.c. x∙y=1+x , allora per ogni x ∊ ℕ x∙(1+x) ≠ 2 ∧ x = x "

oss. la formula 1) non è né vera né falsa, ma può essere soddisf. da certi assegnamenti delle var. libere

x=5 x=1 y=2 y=3 y=1

1∙2 = 1+1 che è vera 3∙1 ≠ 1+3 che non è vera

la formula 2) è falsa perché 1<2 è vera ⇒ antec. vero, cons. quente falso perché ∀x non è vero ︳ x=x

Es.: se avessi avuto I₃(B)=e = era falsa lo stesso perchè non è vero ∀x ∊ ℕ x∙(1+x)≰2 (basta x=1)

Quindi la verità di una formula dipende dagli assegnamenti alle var. libere

D_σ (assegnamento) dato un linguaggio L del primo ordine, e una interpretazione ⟨D, I⟩, un assegn. σ e una funzione