Logică - Varianta 1

Subiectul a fost preluat de pe site-ul Info3BNecenzurat. Rezolvarea subiectului este originală.

1. a) Definiția noțiunii de algebră booleană

Se numește algebră booleană un 4-uplu P, P = <M, ⊥, ∇, ~>, format din orice mulțime nevida M (suportul algebrei) două operații binare ⊥, ∇ : M x M -> M și o operație unară ~ : M -> M, care satisfac condițiile:

1. x ⊥ y = y ⊥ x comutativitatea (a lui ⊥)


2. (x ⊥ y) ⊥ z = x ⊥ (y ⊥ z) asociativitatea (a lui ⊥)


3. x ⊥ (y ∇ z) = (x ⊥ y) ∇ (x ⊥ z) distributivitatea ( a lui ⊥ fața de ∇)


4. (x ⊥ y) ∇ y = y absorbție


5. (x ⊥ (~x)) ∇ y = y legea contradicției


6. x ∇ y = y ∇ x comutativitatea (a lui ∇)


7. (x ∇ y) ∇ z = x ∇ (y ∇ z) asociativitatea (a lui ∇)


8. x ∇ (y ⊥ z) = (x ∇ y) ⊥ (x ∇ z) distributivitatea ( a lui ∇ față de ⊥)


9. (x ∇ y) ⊥ y = y absorbție


10. (x ∇ (~x)) ⊥ y = y legea tautologiei

b) Să se exemplifice teorema de descompunere pentru funcțiile boolene pentru n = 3 și k = 2.

Teorema de descompunere pentru cazul în care n = 3 și k = 2 este următoarea:

Unde x₁, x₂, x₃ sunt variabilele funcției f, α₁, α₂ sunt valorile lui x₁ respectiv x₂

Se stie că x¹ = x și x⁰ = ¬x.

2. a) Algoritmul lui Horn (enunț).

  Pasul 1. i := 0.

  Pasul 2.

        Cât_timp ((există în F o clauză C de forma A₁ ∧ A₂ ∧ A₃ …… ∧ A_k → B, cu A₁, A₂ , A₃ , ... , A_k marcaţi şi B nemarcat sau de forma A₁ ∧ A₂ ∧ A₃ …… ∧ A_k → 0, cu A₁, A₂, A₃, ... , A_k marcaţi) şi (i = 0))

        execută

            Pasul 3. Alege un asemenea C ca mai sus.

            Pasul 4. Dacă ( C = A₁ ∧ A₂ ∧ A₃ …… ∧ A_k → B )

            atunci

                Pasul 5. Marchează B peste tot în F.

            altfel

                Pasul 6. i := 1.

            Sf_Dacă

        Sf_Cât_timp

  Pasul 7. Dacă ( i = 0 )

  atunci

        Pasul 8. Scrie „DA”.

        Pasul 9. Scrie S, cu S(A) = 1 dacă ş i numai dacă A apare în F şi este marcată.

  altfel

        Pasul 10. Scrie „NU”.

  Sf_Dacă.

b) Să se arate că următoarea formulă din LP este tautologie folosing metoda rezoluției.

F = (A ∧ B ∧ C) ∨ (A ∧ ¬B) ∨ (A ∧ ¬C) ∨ (¬A ∧ ¬C) ∨ ¬A

Pentru a arăta ca o formulă este tautologie este de ajuns să demonstrăm ca negația acesteia este falsă. Formula F după negație arată cam așa:

F = (¬A ∨ ¬B ∨ ¬C) ∧ (¬A ∨ B) ∧ (¬A ∨ C) ∧ (A ∨ C) ∧ A

Folosind metoda rezoluției trebuie să gasim clauza vidă pentru ca formula negată să fie falsă. Obervam ca dacă luam prima si a patra cauză apoi rezultatul cu clauza a doua si apoi cu ultima clauză ajungem la clauza vidă.

Am ajuns la clauza vidă deci formula inițială este tautologie.

3. a) Definiția constructivă a sintaxei logicii propoziționale (LP).

Fie o mulţime numărabilă de variabile propoziţionale (formule elementare , formule atomice pozitive , atomi pozitivi), A = {A1, A2, … }. Fie, de asemenea, C = {¬, ∨, ∧} mulţimea conectorilor/conectivelor logici/logice non (negaţia), sau (disjuncţia), respectiv şi (conjuncţia) şi P = { ( , ) } mulţimea parantezelor (rotunde). Formulele (elementele lui LP) vor fi „cuvinte” (expresii bine formate) peste alfabetul L = A U C U P:

Baza (formulele elementare sunt formule). A ∈ LP .

Pas constructiv (obţinere formule noi din formule vechi).

(i) Dacă F ∈ LP atunci (¬F) ∈ LP.

(ii) Dacă F1, F2 ∈ LP atunci ( F1 ∨ F2 ) ∈ LP.

(iii) Dacă F1, F2 ∈ LP atunci ( F1 ∧ F2 ) ∈ LP.

(iv) Dacă F ∈ LP atunci (F) ∈ LP.

(v) Nimic altceva nu este formulă.

b) Să se calculeze numărul total de n-FND-uri.

Vor exista C de 3 la n luate cate k forme normale disjunctive n-are, deci numărul de n-FND-uri va fi egal cu:

C de 3 la n luate cate 0 + ... + = 2³ⁿ