1 logica propozitionala clasica

1 Logica propoziional clasic

Prof. univ. dr. Dumitru GHEORGHIU

Sintaxa LPCLimbajul LPC:n atomi propoziionali: p, q, r, s, p1, p2, , q1, q2, n operatori propoziionali: (negaie), & (conjuncie),

(disjuncie), (condiional), (bicondiional)n semne tehnice: (, ), [, ]

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

2

Sintaxa LPC

n Operatorii i & sunt primitivi.n Se numete formul a LPC orice ir de simboluri

construit conform urmtoarelor reguli:(R1) Orice atom propoziional 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 (rnu este o formul.

n Dac A este o formul sau (A) este o formul, atunci A este aceeai formul cu (A). Astfel, formula de mai sus devine ((p & q) & r).

n n absena parantezelor, are prioritate asupra &. De exemplu, formula (p & q) nseamn nu deopotriv p i q, n timp ce formula p & qnseamn deopotriv non-p i q.

4

Sintaxa LPC

n Urmtoarele clauze definesc subformulele unei formule:n Orice formul este propria sa subformuln Orice subformul a lui A este subformul a An Orice subformul a lui A sau B este subformul a

lui A & Bn 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: adevrat, notat cu 1, i

fals, notat cu 0.n Definiiile semantice ale & i sunt date de urmtoarele tabele

de adevr: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 absena parantezelor, are prioritate asupra &, , i .

n Pe lng indicarea ordinii operaiilor, parantezele elimin ambiguitile. 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 adevr

pentru orice formul.

Tabelul 2.3 Tabel de adevr 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 adevr 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 adevr 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 aceeai formul cu A & B & Cn (A B) C este aceeai formul cu A B C

n ntruct formulele (A & B) & C i A & B & C au acelai tabel de adevr, parantezele pot fi eliminate, acelai fiind cazul cu formulele (A B) C .

n Prin contrast, A & (B C) sau (A & B) C nu au acelai tabel de adevr, deci parantezele nu pot fi eliminate.

11

Semantica LPC

12

n O interpretare este o funcie v care atribuie fiecrui 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 mulime de n atomi propoziionali exist 2n interpretri distincte.

n Dat fiind o interpretare v, aceasta se extinde la o funcie, numit funcie de adevr i notat tot cu v, care atribuie fiecrei formule propoziionale 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 puin 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 puin 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 mulimi de formule

propoziionale G este un model al mulimii G, dac v(A) = 1 pentru orice formul A G.

n O mulime de formule este realizabil, dac are cel puin un model i este nerealizabil, dac nu are nici un model.

n {p, p q, p q} este realizabil, avnd 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 preteniei c A B.

n ntruct interpretarea v(p) = 1, v(q) = 0 este model al formulei (p q) & q, aceast interpretare este un contra-model al preteniei c p q q.

17

Semantica LPCn O formul B este consecin logic a unei mulimi de formule G,

n simboluri G B, dac orice model al mulimii G 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 G B ddac mulimea G {B} este nerealizabil.n Dac G {B} este realizabil, atunci G B. n acest caz,

spunem c orice model al mulimii G {B} este contra-modelal preteniei c B este consecin logic din G.

n ntruct interpretarea v(p) = 1, v(q) = v(r) = 0 este model almulimii {p q, q, r p, r}, aceast interpretare estecontra-model al preteniei 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 definiie, 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 conine una sau mai multe apariii aleformulei A i CB o formul obinut din CA prin nlocuirea a celpuin unei apariii a formulei A cu formula B. Dac A B,atunci CA CB (Teorema nlocuirii).

n Fie formula (p q) & q. ntruct p q q p, avem(p q) & q (q p) & q

19

Metoda tabelelor de adevrn 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 adevrn 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 adevrn Tabelele de adevr pot fi folosite i pentru a decide dac o

formul este consecin logic a unei mulimi de formule.n Este p este consecin logic din {p q, q}?n {p q, q} p ddac mulimea 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 Urmtoarele dou echivalene exprim idempotena & i :

(1) A & A A(2) A A A

n Urmtoarele dou echivalene exprim regulile distributivitiipentru & i :

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

n Urmtoarele dou echivalene 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 negaia unui atom. Atomii fr

negaie se numesc literali pozitivi, iar atomii cu negaie se numesc literali negativi .

n O clauz disjunctiv este o disjuncie de literali L1 Ln, n 1, iar o clauz conjunctiv este o conjuncie de literali L1 & &Ln, n 1.

n O formul n form normal conjunctiv (FNC) este o conjuncie de clauze disjunctive C1 & & Cm, m 1.

n O formul n form normal disjunctiv (FND) este o disjuncie de clauze conjunctive C1 Cm, m 1.

24

Metoda formelor normale

n FNC i FND se identific atunci cnd formula este un literal i atunci cnd formula este o conjuncie sau o disjuncie 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 att n FNC, ct i n FND.n (p q)