1 Logica propoziţională clasică

Prof. univ. dr. Dumitru GHEORGHIU

Sintaxa LPCLimbajul LPC:n atomi propoziţionali: p, q, r, s, p1, p2, …, q1, q2, …n operatori propoziţionali: ¬ (negaţie), & (conjuncţie), ∨

(disjuncţie), ⊃ (condiţional), ≡ (bicondiţional)n semne tehnice: (, ), [, ]

Atomii sunt variabile ale LPC: unui atom i se pot atribui valorile logice adevărat (“1”) sau fals (“0”).Operatorii sunt constante ale LPC, citite, respectiv, “nu” (“nu este cazul că”, “nu este adevărat că”, “non-”), “şi”, “sau”, “dacă …, atunci …”, “dacă şi numai dacă”.

2

Sintaxa LPC

n Operatorii ¬ şi & sunt primitivi.n Se numeşte formulă a LPC orice şir de simboluri

construit conform următoarelor reguli:

(R1) Orice atom propoziţional este formulă (atomică)(R2) Dacă A este o formulă, atunci (¬A) este o

formulă (non-atomică)(R3) Dacă A şi B sunt formule, atunci (A & B) este

formulă (non-atomică)

3

Sintaxa LPC

n (¬((¬(p & q)) & (¬r))) este o formulă, ((p ¬&) q (r¬nu este o formulă.

n Dacă A este o formulă sau (A) este o formulă, atunci A este aceeaşi formulă cu (A). Astfel, formula de mai sus devine ¬(¬(p & q) & ¬r).

n În absenţa parantezelor, ¬ are prioritate asupra &. De exemplu, formula ¬(p & q) înseamnă “nu deopotrivă p şi q”, în timp ce formula ¬p & qînseamnă “deopotrivă non-p şi q”.

4

Sintaxa LPC

n Următoarele clauze definesc subformulele unei formule:n Orice formulă este propria sa subformulăn Orice subformulă a lui A este subformulă a ¬A

n Orice subformulă a lui A sau B este subformulă a lui A & B

n Fie A = ¬(¬p & ¬q). Subformulele lui A sunt p, q, ¬p, ¬q, ¬p & ¬q şi ¬(¬p & ¬q). Ordinea de prezentare a acestora corespunde ordinii în care A a fost construită conform (R1)-(R3).

5

Semantica LPCn În LPC există doar două valori logice: adevărat, notat cu 1, şi

fals, notat cu 0.n Definiţiile semantice ale & şi ¬ sunt date de următoarele tabele

de adevăr:Tabelul 2.1 Tabelul 2.2

p q p & q p ¬p1 1 1 1 01 0 0 0 10 1 00 0 0

6

Semantica LPC

n Operatorii ∨, ⊃, ≡. Pentru oricare două formule A şi B,n A ∨ B prescurtează ¬(¬A & ¬B)n A ⊃ B prescurtează (¬A ∨ B)n A ≡ B prescurtează ((A ⊃ B) & (B ⊃ A))

n În absenţa parantezelor, ¬ are prioritate asupra &, ∨, ⊃ şi ≡.

n Pe lângă indicarea ordinii operaţiilor, parantezele elimină ambiguităţile. E.g., nu vom scrie p & q ∨ r, ci p & (q ∨ r) sau (p & q) ∨ r.

7

Semantica LPCn Folosind tabelele 2.1 şi 2.2, putem construi tabele de adevăr

pentru orice formulă.

Tabelul 2.3 Tabel de adevăr pentru p ∨ q

p q ¬p ¬q ¬p & ¬q ¬(¬p & ¬q) p ∨ q1 1 0 0 0 1 11 0 0 1 0 1 10 1 1 0 0 1 10 0 1 1 1 0 0

8

Semantica LPC

Tabelul 2.4 Tabel de adevăr pentru p ⊃ q

p q ¬p ¬p ∨ q p ⊃ q

1 1 0 1 11 0 0 0 00 1 1 1 10 0 1 1 1

9

Semantica LPC

Tabelul 2.5 Tabel de adevăr pentru p ≡ q

p q p ⊃ q q ⊃ p (p ⊃ q) & (q ⊃ p) p ≡ q

1 1 1 1 1 11 0 0 1 0 00 1 1 0 0 00 0 1 1 1 1

10

Semantica LPC

n Pentru oricare trei formule A, B, şi C,n (A & B) & C este aceeaşi formulă cu A & B & Cn (A ∨ B) ∨ C este aceeaşi formulă cu A ∨ B ∨ C

n Întrucât formulele (A & B) & C şi A & B & C au acelaşi tabel de adevăr, parantezele pot fi eliminate, acelaşi fiind cazul cu formulele (A ∨ B) ∨ C .

n Prin contrast, A & (B ∨ C) sau (A & B) ∨ C nu au acelaşi tabel de adevăr, deci parantezele nu pot fi eliminate.

11

Semantica LPC

12

n O interpretare este o funcție v care atribuie fiecărui atom una şi numai una dintre valorile 1 şi 0. Dacă v atribuie unui atom pvaloarea 1, scriem v(p) = 1, iar dacă v atribuie unui atom pvaloarea 0, scriem v(p) = 0.

n Pentru o mulţime de n atomi propoziţionali există 2n interpretări distincte.

n Dată fiind o interpretare v, aceasta se extinde la o funcţie, numită funcţie de adevăr şi notată tot cu v, care atribuie fiecărei formule propoziţionale o valoare logică (unic determinată).

n Fie formula A = (¬p ∨ q) & r. În interpretarea în care v(p) = v(q) = 0 şi v(r) = 1, v(A) = 1, iar în interpretarea în care v(p) = v(r) = 1 şi v(q) = 0, v(A) = 0.

Semantica LPCn Fie A o formulă și v o interpretare a formulei A. v este un model

al formulei A, dacă v(A) = 1. v este un contra-model al formulei A, dacă v(A) = 0.

n O formulă A este validă, dacă orice interpretare a formulei Aeste un model al formulei A. O formulă este nevalidă, dacă există cel puțin un contra-model al formulei A.

n O formulă A este nerealizabilă, dacă orice interpretare a formulei A este un contra-model al formulei A. O formulă A este realizabilă, dacă cel puțin o interpretare a formulei A este un model al formulei A.

13

Formule realizabile şi

valide

Formule realizabile şi nevalide

Formule nerealizabile

Semantica LPCn ¬p ∨ (p & q) este realizabilă, deoarece ia valoarea 1 în orice

interpretare în care v(p) = 0, dar este nevalidă, deoarece ia valoarea 0 în interpretarea în care v(p) = 1 şi v(q) = 0.

n p & ¬p este nerealizabilă. ¬(p & ¬p) şi p ∨ ¬p sunt valide.

n Formulele valide se mai numesc tautologii sau legi logice. Formulele nerealizabile se mai numesc formule inconsistente. Formulele realizabile şi nevalide se mai numesc formule contingente.

n Pentru orice formulă A, A este validă ddacă ¬A este nerealizabilă şi ¬A este validă ddacă A este nerealizabilă.

14

Semantica LPCn O interpretare v a unei mulţimi de formule

propoziţionale Γ este un model al mulţimii Γ, dacă v(A) = 1 pentru orice formulă A ∈ Γ.

n O mulţime de formule este realizabilă, dacă are cel puţin un model şi este nerealizabilă, dacă nu are nici un model.

n {¬p, ¬p ∨ q, p ∨ q} este realizabilă, având modelul v(p) = 0, v (q) = 1.

n {p, q, ¬p ∨ ¬q} este nerealizabilă, deoarece pentru v(p) = v(q) = 1, avem v(¬p ∨ ¬q) = 0.

15

Semantica LPC

n O formulă B este consecinţă logică a formulei A, în simboluri A ⊨ B, dacă orice model al formulei A este model al formulei B.

n Vom scrie A ⊭ B, dacă nu este cazul că A ⊨ B.n Dacă A ⊨ B, atunci se mai spune că A implică logic B.

n Fie A şi B, două formule oarecare:

A & B ⊨ A, A & B ⊨ B, A ⊨ A ∨ B, B ⊨ A ∨ B.

16

Semantica LPC

n A ⊨ B ddacă A & ¬B este nerealizabilă.

n Dacă o formulă A & ¬B este realizabilă, atunci A ⊭ B. În acest caz spunem că orice model al formulei A &¬B este un contra-model al pretenţiei că A ⊨ B.

n Întrucât interpretarea v(p) = 1, v(q) = 0 este model al formulei (p ∨ q) & ¬q, această interpretare este un contra-model al pretenţiei că p ∨ q ⊨ q.

17

Semantica LPCn O formulă B este consecinţă logică a unei mulţimi de formule Γ,

în simboluri Γ ⊨ B, dacă orice model al mulţimii Γ este model al formulei B.

n Fie A şi B, două formule oarecare:{A, B} ⊨ A ∧ B, {A, A ⊃ B} ⊨ B, {¬A, A ∨ B } ⊨ B.

n Γ ⊨ B ddacă mulţimea Γ ∪ {¬B} este nerealizabilă.

n Dacă Γ ∪ ¬{B} este realizabilă, atunci Γ ⊭ B. În acest caz,spunem că orice model al mulţimii Γ ∪ ¬{B} este contra-modelal pretenţiei că B este consecinţă logică din Γ.

n Întrucât interpretarea v(p) = 1, v(q) = v(r) = 0 este model almulţimii {p ∨ q, ¬q, ¬r ∨ p, ¬r}, această interpretare estecontra-model al pretenţiei că {p ∨ q, ¬q, r ⊃ p} ⊨ r.

18

Semantica LPCn Se spune că două formule A, B sunt echivalente logic, în

simboluri A ↔ B, dacă orice model al formulei A este model al formulei B şi reciproc. Prin definiţie, A ↔ B ddacă A ⊨ B şi B ⊨A.

n Fie A şi B, două formule oarecare:A ∨ B ↔ B ∨ A, A ∧ B ↔ B ∧ A, ¬¬A ↔ A.

n Fie CA o formulă care conţine una sau mai multe apariţii aleformulei A şi CB o formulă obţinută din CA prin înlocuirea a celpuţin unei apariţii a formulei A cu formula B. Dacă A ↔ B,atunci CA ↔ CB (Teorema înlocuirii).

n Fie formula (p ∨ q) & ¬q. Întrucât p ∨ q ↔ q ∨ p, avem(p ∨ q) & ¬q ↔ (q ∨ p) & ¬q

19

Metoda tabelelor de adevărn Este (p & (p ⊃ q)) ⊃ q realizabilă?

p q p ⊃ q p & (p ⊃ q) (p & (p ⊃ q)) ⊃ q1 1 1 1 1

1 0 0 0 1

0 1 1 0 1

0 0 1 0 1

20

Metoda tabelelor de adevărn Este ((p ⊃ q) ⊃ p) & ¬p realizabilă?

p q p ⊃ q (p ⊃ q) ⊃ p ¬p ((p ⊃ q) ⊃ p) & ¬p1 1 1 1 0 01 0 0 1 0 00 1 1 0 1 00 0 1 0 1 0

21

Metoda tabelelor de adevărn Tabelele de adevăr pot fi folosite şi pentru a decide dacă o

formulă este consecinţă logică a unei mulţimi de formule.

n Este ¬p este consecinţă logică din {p ⊃ q, ¬q}?n {p ⊃ q, ¬q} ⊨ ¬p ddacă mulţimea de formule {p ⊃ q, ¬q, ¬¬p}

este nerealizabilă.

22

p q p ⊃ q ¬q ¬¬p1 1 1 0 11 0 0 1 10 1 1 0 00 0 1 1 0

Unele reguli semantice ale LPCn Următoarele două echivalențe exprimă idempotența & şi ∨:

(1) A & A ↔ A(2) A ∨ A ↔ A

n Următoarele două echivalențe exprimă regulile distributivităţiipentru & şi ∨:

(3) (A & (B ∨ C)) ↔ ((A & B) ∨ (A & C))(4) (A ∨ (B & C)) ↔ ((A ∨ B) & (A ∨ C))

n Următoarele două echivalenţe exprimă regulile lui De Morgan:(5) ¬(A & B) ↔ (¬A ∨ ¬B)(6) ¬(A ∨ B) ↔ (¬A & ¬B)

23

Metoda formelor normalen Un literal este un atom sau negaţia unui atom. Atomii fără

negaţie se numesc literali pozitivi, iar atomii cu negaţie se numesc literali negativi .

n O clauză disjunctivă este o disjuncţie de literali L1 ∨ … ∨ Ln, n ≥1, iar o clauză conjunctivă este o conjuncţie de literali L1 & … &Ln, n ≥ 1.

n O formulă în formă normală conjunctivă (FNC) este o conjuncţie de clauze disjunctive C1 & … & Cm, m ≥ 1.

n O formulă în formă normală disjunctivă (FND) este o disjuncţie de clauze conjunctive C1 ∨ … ∨ Cm, m ≥ 1.

24

Metoda formelor normale

n FNC şi FND se identifică atunci când formula este un literal şi atunci când formula este o conjuncţie sau o disjuncţie de literali.

n (p ∨ q) & (r ∨ s) & (¬p ∨ ¬q ∨ ¬r) este în FNC.

n (¬p & q) ∨ r ∨ (¬q & r) este în FND.

n p ∨ q este atât în FNC, cât şi în FND.

n (p ∨ q) & ((p & r) ∨ (q & s)) nu este nici în FNC, nici în FND.

25

Metoda formelor normaleAlgoritmul de normalizare

1. B ≡ C ↔ (B ⊃ C) & (C ⊃ B)2. B ⊃ C ↔ ¬B ∨ C3. ¬¬B ↔ B regula dublei negații4. ¬(B & C) ↔ ¬B ∨ ¬C regula lui De Morgan pentru &5. ¬(B ∨ C) ↔ ¬B & ¬C regula lui De Morgan pentru ∨6. B & (C ∨ D) ↔ (B & C) ∨ (B & D) distributivitatea & față de ∨7. B ∨ (C & D) ↔ (B ∨ C) & (B ∨ D) distributivitatea ∨ față de &

8. B & B ↔ B idempotența &9. B ∨ B ↔ B idempotența ∨10. B & (C ∨ ¬C ) ↔ B simplificare11. B ∨ (C & ¬C ) ↔ B simplificare

26

Metoda formelor normaleAlgoritmul de normalizare

n Înlocuieşte orice sub-formulă de forma B ≡ C cu (B ⊃ C ) & (C ⊃B) şi orice sub-formulă de forma B ⊃ C cu ¬B ∨ C

n Înlocuieşte orice sub-formulă de forma ¬¬B cu B, orice sub-formulă de forma ¬(B & C) cu ¬B ∨ ¬C şi orice sub-formulă de forma ¬(B ∨ C) cu ¬B & ¬C.

n Pentru a obţine o formulă în FNC, înlocuieşte orice sub-formulă de forma B ∨ (C & D) sau (C & D) ∨ B cu (B ∨ C) & (B ∨ D).

n Pentru a obţine o formulă în FND, înlocuieşte orice sub-formulă de forma B & (C ∨ D) sau (C ∨ D) & B cu (B & C) ∨ (B & D).

n Orice formulă propoziţională este echivalentă logic cu o formulă în FNC şi cu o formulă în FND.

27

Metoda formelor normalen Să se normalizeze (p ∨ q) ⊃ (¬q & p)1. Eliminăm ⊃:

¬(p ∨ q) ∨ (¬q & p)2. De Morgan pentru ∨:

(¬p & ¬q) ∨ (¬q & p) FND3. Distributivitatea ∨ faţă de &:

[(¬p & ¬q) ∨ ¬q] & [(¬p & ¬q) ∨ p]4. Distributivitatea ∨ faţă de &:

(¬p ∨ ¬q) & (¬q ∨ ¬q) & (¬p ∨ p) & (¬q ∨ p) FNC5. Idempotenţa ∨ și simplificarea:

(¬p ∨ ¬q) & ¬q & (¬q ∨ p) FNC

28

Metoda formelor normale

n O clauză disjunctivă C este validă ddacă există cel puţin un atom x astfel încât x ∈ C şi ¬x ∈ C

n O formulă în FNC este validă ddacă toate clauzele sale sunt valide

n O clauză conjunctivă, C, este nerealizabilă ddacă există cel puţin un atom x astfel încât x ∈ C şi ¬x ∈ C

n O formulă în FND este nerealizabilă ddacă toate clauzele sale sunt nerealizabile

29

Metoda formelor normaleAlgoritmul de decizie prin forme normale

1. Se aduce A la FNC:n Dacă FNC este validă, atunci A este validăn Dacă nu acesta este cazul, se aduce A la FND; dacă FND

este nerealizabilă, atunci A este nerealizabilăn Dacă nici acesta nu este cazul, atunci A este contingentă

2. Se aduce A la FND:n Dacă FND este nerealizabilă, atunci A este nerealizabilăn Dacă nu acesta este cazul, se aduce ¬A la FND; dacă FND

astfel obţinută este nerealizabilă, atunci A este validăn Dacă nici acesta nu este cazul, atunci A este contingentă

30

Metoda formelor normalen Să se decidă dacă [(p ⊃ q) ⊃ p] ⊃ p este validă1. Eliminăm ⊃:

[(¬p ∨ q) ⊃ p] ⊃ p[¬(¬p ∨ q) ∨ p] ⊃ p¬[¬(¬p ∨ q) ∨ p] ∨ p

2. De Morgan pentru ∨ și eliminarea dublei negații:[¬¬(¬p ∨ q) & ¬p] ∨ p[(¬p ∨ q) & ¬p] ∨ p

3. Distributivitatea ∨ faţă de &:(p ∨ ¬p ∨ q) & (p ∨ ¬p) FNC

Întrucât FNC este validă, formula inițială este validă.

31

Metoda formelor normale

n Fie Γ = {A1, …, An}. Γ ⊨ B ddacă formula A1 & … & An & ¬B este nerealizabilă

n Pentru a decide dacă {A1, …, An} ⊨ B:n formăm conjuncţia A1 & … & An & ¬Bn aducem această conjuncţie la FND șin aplicăm algoritmul de decizie prin forme

normale.

32

Metoda formelor normalen Să se decidă dacă p & q, ¬(p & r) ⊨ ¬r

1. p & q & ¬(p & r) & ¬¬r2. De Morgan pentru & și eliminarea dublei negații:

p & q & (¬p ∨ ¬r) & r3. Distributivitatea & faţă de ∨:

p & q & [(r & ¬p) ∨ (r & ¬r)]4. Distributivitatea & faţă de ∨:

(p & q & r & ¬p) ∨ (p & q & r & ¬r) FND

n Întrucât FND este nerealizabilă, p & q, ¬(p & r) ⊨ ¬r

33

Metoda rezoluției

n Pentru concizie, în loc de „clauză disjunctivă” vom scrie „clauză”

n Clauzele sunt considerate mulțimi de literali; formulele in FNC sunt considerate mulțimi de clauze

n (p ∨ q ∨ ¬r) & (r ∨ s) & ¬p & (¬q ∨ ¬s) devine

{{p, q, ¬r}, {r, s}, {¬p}, {¬q, ¬s}}

34

Metoda rezoluțiein Două clauze, C1 şi C2, se numesc x-rezolubile dacă există cel

puţin un atom x astfel încât x ∈ C1 şi ¬x ∈ C2.n {p, q, ¬r} și {¬q, ¬s} sunt q-rezolubile, {p, q, ¬r} și {r, s} sunt

r-rezolubile.n Fie C1 şi C2 clauze x-rezolubile. Se numeşte rezolventul clauzelor

C1 şi C2 în raport cu x, rezx(C1, C2), clauza obţinută prin reuniunea clauzei C1 din care am eliminat atomul x cu clauza C2din care am eliminat pe ¬x:

rezx(C1, C2) = {C1 − {x} ∪ C2 − {¬x}}n Rez(C1, C2) denotă mulţimea tuturor rezolvenţilor clauzelor C1 şi

C2.

35

Metoda rezoluțiein C1 = {p, ¬q, r} şi C2 = {q, ¬r, s}.

n rezq(C1, C2) = {p, r, ¬r, s}n rezr(C1, C2) = {p, ¬q, q, s}n Rez(C1, C2) = {{p, r, ¬r, s}, {p, ¬q, q, s}}.

n Fie C1 şi C2 clauze x-rezolubile. Rezolventul în raport cu x al clauzelor C1 şi C2 este consecinţă logică a mulţimii {C1, C2}:

{C1, C2} ⊨ rezx(C1, C2).n Fie o mulţime de clauze, Σ, şi o clauză C. O derivare prin

rezoluţie a clauzei C din Σ este un şir finit de clauze C1, …, Cn, astfel încât Cn = C şi pentru orice Ci, 1 ≤ i ≤ n, sau Ci ∈ Σ, sau Ci∈ Rez(Cj, Ck), unde j, k < i.

n Dacă există o derivare prin rezoluţie a clauzei C din Σ, atunci scriem Σ ⊢Rez C.

36

Metoda rezoluțiein C1 = {p, q, ¬s}, C2 = {p, q, r, s}, C3 = {¬q, r}, C4 = {¬p}, C =

{r}n Următorul şir de clauze arată că {C1, C2, C3, C4} ⊢Rez C:

1. {p, q, ¬s} C1

2. {p, q, r, s} C2

3. {p, q, r} din 1, 2, rezs

4. {¬q, r} C3

5. {p, r} din 3, 4, rezq

6. {¬p} C4

7. {r} din 5, 6, rezp

n Dacă Σ ⊢Rez C, atunci Σ ⊨ C.

37

Metoda rezoluției

n Se numeşte clauza vidă, ∅, mulţimea vidă de literali. Pentru orice atom x, ∅ poate fi obţinută numai ca rezolvent al clauzelor {x} şi {¬x}.

n Întrucât ∅ nu are membri care să ia valoarea 1, ∅ este nerealizabilă.

n Dacă Σ ⊢Rez C şi clauza C este nerealizabilă, atunci Σeste nerealizabilă.

n În particular, dacă Σ ⊢Rez ∅, atunci Σ este nerealizabilă.n Încercarea de a deriva prin rezoluţie clauza vidă dintr-o

mulţime de clauze este esenţa metodei rezoluţiei.

38

Metoda rezoluțiein (p ∨ q ∨ ¬r) & ¬p & (p ∨ q ∨ r) & (p ∨ ¬q)n C1 = {p, q, ¬r}, C2 = {¬p}, C3 = {p, q, r}, C4 = {p, ¬q}

n C5 = rezr(C1, C3) = {p, q}n C6 = rezq(C4, C5) = {p}n C7 = rezp(C2, C6) = ∅

n Putem continua obținerea de rezolvenți:

n C8 = rezp(C1, C2) = {q, ¬r}n C9 = rezp(C2, C5) = {q}n ........................................

39

Metoda rezoluțiein Pentru a decide prin rezoluţie dacă o formulă A este sau nu

validă, lucrăm cu formula ¬A, pe care o aducem la FNC.n Să se decidă dacă (p & (p ⊃ q)) ⊃ q este validă

1. ¬[(p & (p ⊃ q)) ⊃ q]2. p & (¬p ∨ q) & ¬q FNC3. C1 = {p}, C2 = {¬p, q}, C3 = {¬q}

n C4 = rezp(C1, C2) = {q}n C5 = rezq(C3, C4) = ∅

n ¬[(p & (p ⊃ q)) ⊃ q] este nerealizabilă, deci (p & (p ⊃ q)) ⊃ qeste validă.

40

Metoda rezoluțiein Pentru a decide dacă {A1, …, An} ⊨ B:

n formăm conjuncţia A1 & … & An & ¬Bn aducem această conjuncţie la FNC șin aplicăm metoda rezoluției

n Să se decidă dacă {p, q} ⊨ p & q

1. p & q & ¬(p & q)2. p & q & (¬p ∨ ¬q) FNC3. {{p}, {q}, {¬p}, {¬q}}

n Întrucât această mulțime este nerealizabilă, {p, q} ⊨ p & q

41