Logică - Varianta 3

O posibilă rezolvare pentru subiectul postat pe Info3BNecenzurat .

1) a) Teorema de reprezentare a unei funcții booleene ca o FNCP (enunț).

Fie orice n ∈ N*, orice f ∈ FB şi oricare numedistincte de variabile x1, x2, ... , xn. Atunci f se poate reprezenta în mod unic ca o FNCP peste X = {x1, x2, ... , xn}, sub forma:

b) Să se arate că în B =legile absorbției și distributivității sunt adevărate.

Legea absorbției: (x + y) * x = x și (x * y) + x = x;

Legea distributivității: (x + y) * z = (z * x) + (z * y) și (x * y) + z = (z + x) * (z + y).

2) a) Definiția constructivă a arborelui atașat formulelor din LP (Arb(f) pentru fiecare f ∈ LP).
Baza: Fie F = A. Atunci arborele atașat lui F este:

Pas constructiv: Fie F = (¬F1) iar arborele atașat lui F1 se cunoaște, Arb(F1). Atunci, arborele atașat lui F va fi:

Fie F = (F1 ∨ F2) și se cunoaște Arb(F1) și Arb(F2). Atunci Arb(F) va fi (pentru F = (F1 ∧ F2) se obține similar):

b) Fie F = A ∧ ¬(B ∨ C) și structura S dată prin S(A) = 0, S(B) = 1, S(C) = 0. Să se găsească S(F) folosind definiția.

S(F) = S(A ∧ ¬(B ∨ C)) = S(A) ∧ S(¬(B ∨ C)) = S(A) ∧ ¬(S(B ∨ C)) = S(A) ∧ ¬(S(B) ∨ S(C)) = 0 ∧ ¬(1 ∨ 0) = 0 ∧ 0 = 0.

3) a) Teorema rezoluției pentru LP (enunț).

Fie clauzele C1, C2 , R. Spunem că R este rezolventul lui C1, C2, pe scurt, R = ResL(C1, C2), dacă şi numai dacă există un literal L ∈ C1 astfel încât ¬L ∈ C2 şi R = (C1 \ {L}) U (C2 \ {L}).

b) Să se arate ca formula A este consecință semantică din mulțimea de formule M = {A ∨ B ∨ C, A ∨ ¬B, A ∨ ¬C, ¬A ∨ ¬C} folosind metoda rezoluției.

Rezolvarea acestui exercițiu presupune scrierea elementelor din M sub următoarea formă adăugând la sfârșit:
(A ∨ B ∨ C) ∧ (A ∨ ¬B) ∧ (A ∨ ¬C) ∧ (¬A ∨ ¬C) ∧ ¬A.
Prin rezoluție rezultă următoarea schemă din care rezultă că A este consecință semantică.