F.I.A.
Cătălin Stoean
Laboratorul numărul 5
Fundamente teoretice
Complexitatea expresiei
Complexitatea lui P ∈ P* se calculează în felul următor:
Complexitatea atomilor este 0;
Complexitatea lui ⎤ P este egală cu complexitatea lui P, iterată cu 1;
Complexitatea lui P ο Q este egală cu complexitatea lui P, adunată cu
complexitatea lui Q, iterată cu 1 (ο reprezintă un conector binar).
Se notează cu K(P).
Exerciţiul 1: Calculaţi complexitatea pentru următoarea expresie logică:
(p ∧(⎤ q ∨ r)) ∧(⎤ p ∧ q)
Rezolvare:
K((p ∧(⎤ q ∨ r)) ∧(⎤ p ∧ q)) = K((p ∧(⎤ q ∨ r))) + K(⎤ p ∧ q) + 1 = K(p) + K(⎤ q ∨ r)
+ 1 + K(⎤ p) + K(q) + 2 = K(⎤ q) + K(r) + 2 + 1 + k(q) + 2 = 6
Metodologia lui Sward
O variabilă se numeşte completă dacă este inclusă împreună cu negaţia ei în
cadrul expresiei logice analizate.
Algoritmul:
1. Se transformă expresia logică astfel încât să obţinem o formulă de bază (construită
numai cu operatorii ∨, ∧ şi ⎤ ).
2. Identificăm variabilele incomplete şi le substituim cu 0.
3. Aplicăm regulile de reducere de mai jos, dupa care mergem la pasul 2.
Reguli de reducere:
• ∅∧1=∅
• ∅∨1=1
• ∅∧0=0
• ∅ ∨ 0 = ∅, unde ∅ reprezintă o formulă
Exerciţiul 2: Să se testeze veridicitatea pentru următoarea expresie logică:
((p1 ∧ (p3 → p2)) ∨ (⎤ p1 ∧ p2 ∧ (p4 ↔ p5) ∨ ⎤ p6)) ∨(⎤ p4 ∧ p6 ∨ (p1 → p4))
Rezolvare:
((p1 ∧ (⎤ p3 ∨ p2)) ∨ (⎤ p1 ∧ p2 ∧ ((p4 → p5) ∧ (p5 → p4)) ∨ ⎤ p6)) ∨ (⎤ p4 ∧ p6 ∨ (⎤ p1
∨ p4))
((p1 ∧ (⎤ p3 ∨ p2)) ∨ (⎤ p1 ∧ p2 ∧ ((⎤ p4 ∨ p5) ∧ (⎤ p5 ∨ p4)) ∨ ⎤ p6)) ∨ (⎤ p4 ∧ p6 ∨ (⎤ p1
∨ p4))
1
p2 este variabilă în stare incompletă, deci va fi înlocuită cu valoarea logică 0. Rezultă:
((p1 ∧ ⎤ p3) ∨ ⎤ p6 ∨ (⎤ p4 ∧ p6 ∨ (⎤ p1 ∨ p4))
⎤ p3 este o variabilă în stare parţială şi va fi substituită cu valoarea logică 0. Vom avea:
⎤ p6 ∨ (⎤ p4 ∧ p6 ∨ (⎤ p1 ∨p4))
⎤ p1 reprezintă variabila incompletă; va fi substituită cu 0:
⎤ p6 ∨ (⎤ p4 ∧ p6 ∨ p4)
Atât p4, cât şi p6 se găsesc în stare completă. Vom proceda, prin urmare, la o
eliminare pe ramuri a uneia dintre ele: înlocuim p4 cu valoarea logică 1. Rezultă ⎤ p6.
Non-veridicitatea expresiei iniţiale a fost astfel probată.
Consecinţă. Interpretare. Model.
Orice formulă cu n atomi în componenţă admite 2n interpretări.
Exemplu:
F: (p1 ∨ p2) ∧ p3
Formula F = F(p1, p2, p3) este adevărată in interpretarea I = (⎤ p1, p2, p3) petru că
(F)
V = (0 ∨ 1 ) ∧ 1 = 1
Fie interpretarea J = (p1, p3, ⎤ p3). Formula F este falsă în această interpretare J.
Definuţia 1: O interpretare I satisface o formulă F a logicii propoziţiilor dacă formula F
este adevărată în interpretarea I. I este model pentru F.
Definiţia 2: Formula F este validă dacă şi numai dacă este adevărată în toate interpretările
(de exemplu, p ∨ ⎤ p).
Definiţia 3: Formula F este inconsistentă dacă şi numai dacă este falsă în toate
interpretările (de exemplu, p ∧ ⎤ p).
Definiţia 4: O formulă este consistentă dacă şi numai dacă nu este inconsistentă, adică
există cel puţin o interpretare astfel încât ea să fie adevărată în acea interpretare.
Definiţia 5: O familie M de formule este realizabilă dacă şi numai dacă există o evaluare
booleană V, cu V(F) = 1, pentru orice formulă F din M. Din punct de vedere semantic,
acest termen este echivalent cu consistenţa.
Exerciţiul 3: Arătaţi că următoarea expresie logică(numită tollendo tollens) este
realizabilă:
(⎤ q ∧ (p → q)) → ⎤ p
Rezolvare: (⎤ q ∧ (p → q)) → ⎤ p = ⎤ (⎤ q ∧ (⎤ p ∨ q))∨⎤ p
Procedând cu metoda lui Sward, observăm că ⎤ p este variabilă incompletă: o
înlocuim cu 0 şi rezultă
⎤ (⎤ q ∧ q) = ⎤ 0 = 1
Se observă că formula de mai sus, nu numai că este realizabilă, este chiar validă.
Tollendo tollens este o tautologie.
Se poate rezolva şi cu ajutorul tabelei de adevăr:
2
p q ⎤p ⎤p∨q ⎤q ⎤ q ∧ (⎤ p ∨ q) ⎤ (⎤ q ∧ (⎤ p ∨ q)) ⎤ (⎤ q ∧ (⎤ p ∨ q))∨⎤p
0 0 1 1 1 1 0 1
0 1 1 1 0 0 1 1
1 0 0 0 1 0 1 1
1 1 0 1 0 0 1 1
Definiţia 6: Spunem că p este consecinţă logică a familiei de propoziţii {p1, p2, …,
pn}dacă şi numai dacă din V(p1) = V(p2) = … = V(pn) = 1 se obţine V(p) = 1.
Propoziţie: Fie formulele p1, p2, …, pn. Formula p este consecinţă logică a premizelor
p1, p2, …, pn dacă şi numai dacă p1 ∧ p2 ∧ … ∧ pn ∧ ⎤ p este nerealizabilă.
Exerciţiul 4: Arătaţi că c este o consecinţă logică a mulţimii de formule
S = {(a ∧ b) ∨ (b ∧ c), (a ∧ b) → c}
Rezolvare: Urmărim definiţia 6: avem
• V(b ∧ (a ∨ c)) = 1 ⇒ V(b) = 1 şi V(a ∨ c) = 1;
• V((a ∧ b) → c) = V(⎤ (a ∧ b) ∨ c) = 1 ⇒ V(⎤ a ∨ ⎤ b ∨ c) = 1.
Ştim că V(⎤ b) = 0 ⇒ V(⎤ a ∨ ⎤ b ∨ c) = V(⎤ a ∨ c) = 1. Avem aşadar V(a ∨ c) = 1
şi V(⎤ a ∨ c) = 1 ⇒ V(c) = 1.
Exerciţiul 4 se poate rezolva însă şi prin folosirea propoziţiei de mai sus: avem de
de monstrat că formula
[(a ∧ b) ∨ (b ∧ c)] ∧ [(a ∧ b) → c] ∧ ⎤ c
este nerealizabilă.
Formula de mai sus este echivalentă cu următoarea:
b ∧ (a ∨ c) ∧ (⎤ a ∨ ⎤ b ∨ c) ∧ ⎤ c
Luăm a = 1 ⇒ b ∧ c ∧ (⎤ b ∨ c) ∧ ⎤ c. Se observă că avem c ∧ ⎤ c care este nerealizabilă.
Dacă luăm a = 0 ⇒ b ∧ c ∧ ⎤ c ⇒ formulă nerealizabilă.
Aşadar, c este consecinţă logică pentru mulţimea S (S╞═ c).
Exerciţiul 5: Fie următoarele formule logice:
p1: a → b
p2: ⎤ b
p: ⎤ a
Arătaţi că p este consecinţă logică pentru mulţimea {p1, p2}.
Rezolvare: Avem de arătat că (a → b) ∧ ⎤ b ∧ a este nerealizabilă.
(⎤ a ∨ b) ∧ ⎤ b ∧ a ⇔ [(⎤ a ∧ ⎤ b) ∨ (b ∧ ⎤ b)] ∧ a ⇔ (⎤ a ∧ ⎤ b) ∧ a ⇔ (a ∧ ⎤ a) ∧ (⎤ b ∧ a)
care este nerealizabilă.
Exerciţiul se putea rezolva şi cu ajutorul unui tablou logic.
3
Forme normale
Literalul reprezintă o variabilă pozitivă sau negativă (simplă sau negată).
Numim conjuncţie elementară sau clauză conjunctivă o conjuncţie de literali de
forma c = ∧ li, cu i luând valori de la 1 la n (n > 1).
Numim formă normală disjunctivă (FND) o expresie a logicii predicatelor de
forma c1 ∨ c2 ∨ … ∨ cm, unde ck este conjuncţie elementară, cu k ∈ {1, 2, …, n}. Altfel
spus, FND este o disjuncţie de conjuncţii elementare.
În mod analog se definesc disjuncţia elementară şi forma normală conjunctivă.
Exerciţiul 6: Aduceţi următoarea expresie logică la o formă normală disjunctivă:
(a → b) → ((a ∧ b) → ⎤ c)
Rezolvare:
(a → b) → ((a ∧ b) → ⎤ c) ⇔ ⎤ (a → b) ∨ ( ⎤ (a ∧ b) ∨ ⎤ c) ⇔
⎤ ( ⎤ a ∨ b) ∨ ( ⎤ a ∨ ⎤ b ∨ ⎤ c) ⇔ (a ∧ ⎤ b) ∨ ⎤ a ∨ ⎤ b ∨ ⎤ c
Forma normală disjunctivă perfectă a unei formule este dată de formula care se
găseşte în FND şi, în plus, toţi termenii conţin toţi atomii formulei.
Etapele construcţiei unei frome normale disjunctive perfecte:
• Construcţia FND
• Identificarea literalilor care apar în formulă
• Pentru literalii care nu apar în formulă se procedează astfel:
a∧1=a
a∨⎤a=1
a1 ∧ (a2 ∨ a3) = (a1 ∧ a2) ∨ (a1 ∧ a3)
Exerciţiul 7: Aduceţi la forma normală disjunctivă perfectă următoarea formulă:
(a1 ∧ a2 ∧ ⎤ a3) ∨ (a1 → (a2 → a3))
Rezolvare:
Aplicând algoritmul prezentat mai sus, vom obţine:
(a1 ∧ a2 ∧ ⎤ a3) ∨ (a1 → (a2 → a3)) = (a1 ∧ a2 ∧ ⎤ a3) ∨ (⎤ a1 ∨ (⎤ a2 ∨ a3) =
(a1 ∧ a2 ∧ ⎤ a3) ∨ ⎤ a1 ∨ ⎤ a2 ∨ a3
Am obţinut FND. Continuăm, conform algoritmului prezentat:
⎤ a1 = ⎤ a1 ∧ 1 = ⎤ a1 ∧ (a2 ∨ ⎤ a2) = (⎤ a1 ∧ a2) ∨ (⎤ a1 ∧ ⎤ a2)
⎤ a1 ∧ a2 = (⎤ a1 ∧ a2) ∧ 1 = (⎤ a1 ∧ a2) ∧ (a3 ∨ ⎤ a3) = (⎤ a1 ∧ a2 ∧ a3) ∨ (⎤ a1 ∧
a2 ∧ ⎤ a3)
⎤ a1 ∧ ⎤ a2 = (⎤ a1 ∧ ⎤ a2) ∧ 1 = (⎤ a1 ∧ ⎤ a2) ∧ (a3 ∨ ⎤ a3) = (⎤ a1 ∧ ⎤ a2 ∧ a3) ∨
(⎤a1 ∧ ⎤ a2 ∧ ⎤ a3)
⎤ a2 = ⎤ a2 ∧ 1 = ⎤ a2 ∧ (a1 ∨ ⎤ a1) = (⎤ a2 ∧ a1) ∨ (⎤ a2 ∧ ⎤ a1)
⎤ a2 ∧ a1 = (⎤ a2 ∧ a1) ∧ 1 = (⎤ a2 ∧ a1) ∧ (a3 ∨ ⎤ a3) = (⎤ a2 ∧ a1 ∧ a3) ∨ (⎤ a2 ∧
a1 ∧ ⎤ a3)
4
⎤ a2 ∧ ⎤ a1 = (⎤ a2 ∧ ⎤ a1) ∧ 1 = (⎤ a2 ∧ ⎤ a1) ∧ (a3 ∨ ⎤ a3) = (⎤ a2 ∧ ⎤ a1 ∧ a3) ∨
(⎤ a2 ∧ ⎤ a1 ∧ ⎤ a3)
a3 = a3 ∧ 1 = a3 ∧ (a2 ∨ ⎤ a2) = (a3 ∧ a2) ∨ (a3 ∧ ⎤ a2)
a3 ∧ a2 = (a3 ∧ a2) ∧ 1 = (a3 ∧ a2) ∧ (a1 ∨ ⎤ a1) = (a3 ∧ a2 ∧ a1) ∨ (a3 ∧ a2 ∧
⎤ a1)
a3 ∧ ⎤ a2 = (a3 ∧ ⎤ a2) ∧ 1 = (a3 ∧ ⎤ a2) ∧ (a1 ∨ ⎤ a1) = (a3 ∧ ⎤ a2 ∧ a1) ∨ (a3 ∧ ⎤
a2 ∧ ⎤ a1)
Obţinem forma finală a FNDP:
(a1 ∧ a2 ∧ ⎤ a3) ∨ ⎤ a1 ∨ ⎤ a2 ∨ a3 = (a1 ∧ a2 ∧ ⎤ a3) ∨ (⎤ a1 ∧ a2 ∧ a3) ∨ (⎤ a1 ∧ a2 ∧
⎤ a3) ∨ (⎤ a1 ∧ ⎤ a2 ∧ a3) ∨ (⎤a1 ∧ ⎤ a2 ∧ ⎤ a3) ∨ (⎤ a2 ∧ a1 ∧ a3) ∨ (⎤ a2 ∧ a1 ∧ ⎤ a3) ∨
∨ (a3 ∧ a2 ∧ a1)
Forma normală conjunctivă perfectă a unei formule este dată de formula care se
găseşte în FNC şi, în plus, toţi termenii conţin toţi atomii formulei.
Etapele construcţiei unei frome normale conjunctive perfecte:
• Construcţia FNC
• Identificarea literalilor care apar în formulă
• Pentru literalii care nu apar în formulă se procedează astfel:
a∨0=a
a∧⎤a=0
a1 ∨ (a2 ∧ a3) = (a1 ∨ a2) ∧ (a1 ∨ a3)
Exerciţiul 7: Aduceţi la forma normală conjunctivă perfectă următoarea formulă:
(a1 ∨ a2) ∧ (a2 → a1) ∧ (a1 → a3) ∧ (⎤ a1 → ⎤ a3)
Soluţie: Aducem la FNC:
(a1 ∨ a2) ∧ (⎤ a2 ∨ a1) ∧ (⎤ a1 ∨ a3) ∧ (a1 ∨ ⎤ a3)
a1 ∨ a2 = (a1 ∨ a2) ∨ 0 = (a1 ∨ a2) ∨ (a3 ∧ ⎤a3) = (a1 ∨ a2 ∨ a3) ∧ (a1 ∨ a2 ∨ ⎤a3)
În mod analog,
⎤ a2 ∨ a1 = (⎤ a2 ∨ a1) ∨ 0 = (⎤ a2 ∨ a1 ∨ a3) ∧ (⎤ a2 ∨ a1 ∨ ⎤ a3)
⎤ a1 ∨ a3 = (⎤ a1 ∨ a3 ∨ a2) ∧ (⎤ a1 ∨ a3 ∨ ⎤ a2)
a1 ∨ ⎤ a3 = (a1 ∨ ⎤ a3 ∨ a2) ∧ (a1 ∨ ⎤ a3 ∨ ⎤ a2)
Am obţinut următoarea FNCD:
(a1 ∨ a2) ∧ (a2 → a1) ∧ (a1 → a3) ∧ (⎤ a1 → ⎤ a3) = (a1 ∨ a2 ∨ a3) ∧ (a1 ∨ a2 ∨
⎤ a3) ∧ (⎤ a2 ∨ a1 ∨ a3) ∧ (⎤ a2 ∨ a1 ∨ ⎤ a3) ∧ (⎤ a1 ∨ a3 ∨ a2) ∧ (⎤ a1 ∨ a3 ∨ ⎤ a2)