IASE 1/4 Cap. 3.1 Limbajul de calcul propoziţional

Metode de rezolvare a problemelor

3.1. Limbajul de calcul propoziţional

3.1.1. Sintaxa şi semantica calculului propoziţional

Calculul propoziţional a fost definit de Whitehead şi Rusell (1910) în celebra carte “Principia Mathematica”. Importanţa matematică a calculului propoziţional este deosebită, acesta stând la baza definirii oricărui sistem logic formal. Calculul propoziţional modern se bazează pe dezvoltările şi modernizările aduse ulterior de Hilbert şi Ackermann.

3.1.1.1. Vocabularul limbajului de calcul propoziţional Vocabularul limbajului este format din următoarele categorii de simboluri: - Variabilele propoziţionale notate prin simbolurile a, b, c,…,a1, b1, c1, …. Mulţimea

variabilelor propoziţionale (propoziţiilor) se notează în cele ce urmează cu V; - Conectivele logice ∧ (conjuncţie), ∨ (disjuncţie) şi ⎤ (negaţie); - Parantezele rotunde “(” şi “)”;

3.1.1.2. Sintaxa calculului propoziţional Definiţia 1. Mulţimea formulelor (enunţurilor sintactic corecte) ale calculului propoziţional, mulţime

notată cu P, se defineşte recursiv prin următoarele reguli: 1) simbolurile propoziţionale aparţin lui P: P∈⇒∈∀ xVx 2) dacă a, b∈P atunci a∧b, a∨b, ⎤ a, (a)∈P; 3) o combinaţie de simboluri din V aparţine lui P dacă şi numai dacă ea se obţine prin

aplicarea de un număr finit de ori a regulilor 1) şi 2). Se consideră algebra (B2,•,⊕,’) unde B2={0,1} şi, pentru orice x, y∈B2, operaţiile •, ⊕ şi ‘ sunt

definite de relaţiile: x•y=min{x, y}=xy; (1) x⊕y=max{x, y}=x+y-xy; x’=1-x. Propoziţia 1. Algebra (B2,•,⊕,’) este o algebră booleană.

3.1.1.3. Semantica limbajului de calcul propoziţional Definirea semanticii calculului propoziţional presupune definirea unei funcţii I:P→B2, care să

atribuie fiecărei formule o valoare de adevăr. Dat fiind faptul că funcţia I dă o semnificaţie formulelor limbajului P, permiţând interpretarea acestora, aceasta este denumită interpretare.

Definiţia 2. Se numeşte interpretare orice morfism al algebrelor (P,∧,∨,⎤ ) şi (B2,•,⊕,’). Din definiţia 2 rezultă că orice interpretare I, I:P→B2, satisface următoarele proprietăţi oricare

ar fi formulele a, b∈P: I(a∨b)=I(a)⊕I(b)=max{I(a),I(b)}; (2) I(a∧b)=I(a) •I(b)=min{I(a),I(b)}; I(⎤ a)=1-I(a). Remarca 1. Având în vedere că în calculul propoziţional orice interpretare satisface prin

definiţie proprietăţile (2), rezultă că valoarea de adevăr a oricărei formule F∈P este bine determinată de valorile de adevăr atribuite de interpretarea I variabilelor propoziţionale. Dacă în formula F apar n variabile propoziţionale atunci există 2n interpretări posibile ale formulei F (funcţii I).

O interpretare asociază fiecărei formule F∈P o valoare de adevăr notată I(F)∈B2, convenind că valoarea de fals=0, iar valoarea de adevărat=1.

3.

IASE 2/4 Cap. 2. Limbajul LPA Prolog

Notând cu x1, x2,…,xn variabilele care apar în F, atunci pentru orice interpretare I, valoarea de adevăr a formulei F este dată de o relaţie de forma:

I(F)=I(F(x1, x2,…,xn))=f(I(x1), I(x2),…,I(xn)) (3) În această viziune, fiecare formulă F poate fi echivalată cu o funcţie logică f. Pe mulţimea P se introduc două conective (operaţii) noi, → şi ↔, numite implicaţie logică, respectiv echivalenţă logică, a căror semantică este definită după cum urmează:

⎪⎩

⎪⎨⎧ ==

=→;1

;0)(1)(0)(

cazuricelelaltein

sidaca bIaIbaI (4)

⎩⎨⎧ =→=→

=↔.0

;1)()(1)(

contrarcazindaca abIbaI

baI (5)

Oricare ar fi formulele a, b∈P, se obţine următoarea semnificaţie a conectivelor → şi ↔:

I(a) I(b) I(a→b) I(b→a) I(a↔b)

0 0 1 1 1

0 1 1 0 0

1 0 0 1 0

1 1 1 1 1 Exerciţii: Să se arate că:

1. a→b ≈ ⎤ a∨b 2. ⎤ (a∧⎤b) ≈ ⎤ a∨b 3. ⎤ (a∧b) ≈ ⎤ a∨ ⎤ b 4. a↔b ≈ (a→b) ∧ (b→a) ≈ (b ∧ a) ∨ (⎤ a ∧ ⎤ b) Aplicaţie: a – dacă e soare; b – e frumos. Definiţia 3. Se spune că formula F∈P este consistentă dacă există o interpretare I pentru care

I(F)=1 (pentru care formula este adevărate). O formulă care nu este consistentă se numeşte inconsistentă. O mulţime de formule {F1,F2,…,Fn} este consistentă dacă există o interpretare I pentru care I(F1)= I(F2)=… =I(Fn)=1 (pentru care toate formulele sunt adevărate). Remarca 2. Mulţimea {F1,F2,…,Fn} este consistentă dacă şi numai dacă formula F1∧F2

∧…∧Fn este consistentă. Definiţia 4. O formulă F∈P se numeşte validă sau irefutabilă dacă este adevărată în orice interpretare, adică ∀I, I(F)=1. O formulă validă se mai numeşte şi tautologie. O formulă care nu este validă este denumită invalidă. Ex.: a∨⎤ a. Remarca 3. O formulă invalidă poate fi adevărată într-o interpretare particulară, în timp ce o formulă inconsistentă este întotdeauna falsă.

Relaţiile dintre conceptele de validitate, consistenţă, invaliditate, inconsistenţă şi valorile de adevăr luate de expresii pentru combinaţiile de valori de adevăr ale formulelor atomice componente sunt ilustrate în tabelul de mai jos.

Validă Invalidă

Întotdeauna adevărată

Nu întotdeauna adevărată şi nu întotdeauna falsă

Întotdeauna falsă

Consistentă Inconsistentă

Contingentă

Se observă existenţa unei categorii de expresii, care nu sunt nici întotdeauna valide, nici întotdeauna inconsistente. Astfel de expresii, care pentru unele combinaţii ale valorilor de adevăr ale formulelor atomice componente iau valoarea "adevărat", iar pentru alte combinaţii ale valorilor de adevăr ale formulelor atomice componente iau valoarea "fals", sunt denumite expresii contingente.

IASE 3/4 Cap. 3.1 Limbajul de calcul propoziţional

Definiţia 5. Fie S={F1,F2,…,Fn}⊆P o mulţime de formule şi C∈P o formulă. Se spune că C este deductibilă semantic din S sau C este o consecinţă logică a lui S, dacă pentru orice interpretare I pentru care I(F1)=I(F2)=…=I(Fn)=1 avem I(C)=1. Se notează acest fapt prin {F1,F2,…,Fn}╞ C (6) Remarca 4. Se spune că expresia {F1,F2,…,Fn}╞ C este o teoremă, {F1,F2,…,Fn} constituind ipoteza, iar C concluzia teoremei respective. Semnul “╞ “ este denumit simbol de asertare a validităţii. Remarca 5. Dacă mulţimea premizelor este vidă, teorema se rescrie sub forma ╞ C, ceea ce semnifică faptul că C este o tautologie (adevărată în orice ipoteză). Având în vedere acest aspect, orice tautologie a calculului propoziţional poate fi considerată o teoremă. De asemenea, a demonstra teorema {F1,F2,…,Fn}╞ C revine în a demonstra că formula

F1∧F2 ∧…∧Fn → C este o tautologie, adică ╞ F1∧F2 ∧…∧Fn → C. Există anumite tautologii ale calculului propoziţional denumite axiome, prin asertarea cărora se pot deduce toate celelalte tautologii ale limbajului. Sistemul axiomatic al calculului propoziţional, definit de Hilbert şi Ackermann are la bază următoarele axiome: i) ╞ A∨A→A principiul tautologiei; ii) ╞ A→A∨B principiul adiţiunii; iii) ╞ A∨B→B∨A principiul comutativităţii; iv) ╞ (A→B)→((C∨A)→(C∨B)) principiul însumării.

3.1.2. Principiul deducţiei Propoziţia 2. (Principiul deducţiei)

Se spune că {F1,F2,…,Fn}╞C dacă şi numai dacă {F1,F2,…,Fn, ⎤C} este inconsistentă. Demonstraţie: Directă ): Pentru orice interpretare I pentru care I(F1)=I(F2)=…I(Fn)=1 avem conform ipotezei I(C)=1, deci I(⎤C)=1-I(C)=1-1=0. Inversă ): Dacă I este o interpretare pentru care I(F1)=I(F2)=…I(Fn)=1, atunci în mod obligatoriu I(⎤C)=0 ({F1,F2,…,Fn, ⎤C} fiind inconsistentă), deci I(C)=1- I(⎤C)=1-0=1.

3.1.3. Echivalenţă logică Definiţia 6. Două formule F1, F2∈P se numesc echivalente dacă, pentru orice interpretare I, există egalitatea I(F1)=I(F2): F1 ≈ F2 ∀I, I(F1)=I(F2).

Ex.: C(a∨b) ≈ Ca∧Cb C(a∧b) ≈ Ca∨Cb a∨(a∧b) ≈ a a∨a ≈ a Propoziţia 3. Relaţia ≈ este o relaţie de echivalenţă. Demonstraţie: F1 ≈ F2 ╞ (F1 ↔F2), adică ╞ (F1 ↔F2) este o tautologie i) reflexivă: ∀ F, F ≈ F, adică ╞ (F ↔F), I(F) = I(F). ii) simetrică: F1 ≈ F2 atunci ╞ (F1 ↔F2), deci ╞ (F2 ↔F1) => F2 ≈ F1 sau I(F1) = I(F2),

I(F2) = I(F1) => F2 ≈ F1. iii) tranzitivă: F1 ≈ F2 şi F2 ≈ F3, atunci ╞ (F1 ↔F2) şi ╞ (F2 ↔F3), deci ╞ (F1 ↔F3) => F1 ≈

F3 sau I(F1) = I(F2) şi I(F2) = I(F3), deci I(F1) = I(F3) => F1 ≈ F3. Se defineşte prin P/≈ mulţimea claselor de echivalenţă, o clasă de echivalenţă a formulei a∈P

fiind definită [a] = {x∈P | x ≈ a}. Ex.: F1 = a∨(b∧c) ≈ (a∨b)∧ (a∨c), (a∨b)∧ (a∨c) ∈ [F1] Se consideră toate formulele care au un singur simbol propoziţional, pe care îl vom nota cu p. p∧⎤ p ∈ [fals] p∨⎤ p ∈ [adevărat] p∧p∧p ∈ [p] ⎤ p∨(⎤ (p∧p) ∈ [⎤ p] Definiţia 7. Introducându-se relaţia ≤ pe mulţimea P/≈, [a] ≤ [b] este adevărată dacă şi numai

dacă ╞ (a → b) este o tautologie (sau dacă a ╞ b).

IASE 4/4 Cap. 2. Limbajul LPA Prolog

Remarcă: Fie a şi b două formule astfel încât ╞ (a → b). Dacă c ∈ [a] şi d ∈ [b], atunci se poate verifica că ╞ (c → d); prin urmare, definiţia anterioară este corect formulată şi nu depinde de alegerea reprezentanţilor.

Propoziţia 4. Relaţia ≤ este o relaţie de ordine pe P/≈. i) reflexivă: ∀ a, ╞ (a→ a), adică [a] ≤ [a]. ii) antisimetrică: adică [a] ≤ [b] şi [b] ≤ [a], atunci ╞ (a→ b) şi ╞ (b→ a), atunci ╞ (a ↔ b),

deci a ≈ b, adică [a] = [b]. iii) tranzitivă: [a] ≤ [b] şi [b] ≤ [c], atunci ╞ (a → b) şi ╞ (b → c), rezultă ╞ (a → c), adică

[a] ≤ [c]. Propoziţia 5. Mulţimea parţial ordonată (P, ≤) este o latice în care:

sup([a], [b]) = [a ∨ b] inf([a], [b]) = [a ∧ b]

Demonstraţie: ♦ [a ∨ b] = sup([a], [b]) (cel mai mic majorant) ╞ a →(a∨b) şi ╞ b →(a∨b) dar conf def ≤ => [a] ≤ [a ∨ b] şi [b] ≤ [a ∨ b]. Ca urmare, [a ∨ b] este un majorant al mulţimii {[a], [b]}. Fie t un alt majorant [a] ≤ [t] şi rezultă ╞ (a→ t) ╞ (a∨b) → t [b] ≤ [t] şi rezultă ╞ (b→ t) şi conform def. ≤ rezultă [a ∨ b] ≤ [t] => [a ∨ b] este cel mai mic majorant deci sup([a], [b]) = [a ∨ b].

♦ [a ∧ b] = inf([a], [b]) cel mai mare minorant ╞ a →(a∧b) şi ╞ b →(a∧b) conf def ≤ , [a] ≤ [a ∧ b] şi [b] ≤ [a ∧ b]. Ca urmare, [a ∧ b] este un minorant al mulţimii {[a], [b]}. Fie f un alt minorant [a] ≤ [f] şi rezultă ╞ (a→ f) ╞ (a∧b) → f => [a ∧ b] ≤ [f]

deci, inf([a], [b]) = [a ∧ b] [b] ≤ [f] şi rezultă ╞ (b→ f) Propoziţia 6. Laticea (P/≈, ≤) este o algebră booleană (distributivă şi complementată), cunoscută sub numele de laticea Linderbaum.

Remarcă: (P/≈, ∨, ∧, ⎤, f, t) ⎯→⎯I (B2, ⊕, •, ’, 0, 1) Orice interpretare este un morfism al celor două algebre booleene. A interpreta o formulă F în care apar variabilele propoziţionale x1’, x2, ..., xn revine în a calcula valoarea unei funcţii logice f = fF, f : 22 BBn → , valoarea de adevăr a formulei F fiind dată de relaţia: ( ) ( )( ) ( ) ( ) ( )( )nn xIxIxIfxxxFIFI KK ,,,,, 2121 == .

Propoziţia 7. Există n22 funcţii definite pe nB2 cu valori în B2

Propoziţia 8. Relaţia de echivalenţă logică are următoarele proprietăţi: i) F∨G ≈ G∨F; F∧G ≈ G∧F (comutativitate) ii) F∨(G∨H) ≈ (F∨G)∨H; F∧(G∧H) ≈ (F∧G)∧H (asociativitate) iii) F∨(G∧H) ≈ (F∨G) ∧(F∨H); F∧ (G∧H)≈ (F∧G) ∧ (F∧H) iv) F∨F ≈ F, F∧F ≈ F idempotenţă v) F∨(F∧G) ≈ F, F ∧ (F∨G) ≈ F absorbţie vi) F∨⎤F ≈ t; F∧⎤F≈ f vii) ⎤ (⎤F) ≈ F principiul dublei negaţii viii) ⎤ (F∨G) ≈⎤F∧⎤G

⎤ (F∧G) ≈⎤F∨⎤G (De Morgan) oricare ar fi formulele F, G, H ∈P, t=true, f=false.