LPExerciii Logica PropoziionalEx2.1 Scriei toi rezolvenii pentru formula: F = ( A B C ) ( B C ) ( A C ) ( B C ) Ex2.2 Scriei toi rezolvenii pentru formula: F = ( A B C ) ( B C ) ( B C ) A Ex2.3 Scriei toi rezolvenii pentru formula: F = ( B C ) ( A C ) ( B ) ( A B ) ( A B C ) Ex2.4 Scriei un program care s afieze toi rezolvenii pentru o formul LP aflat n FNC. Ex2.5 Scriei urmtoarele formule Horn sub form implicaional: a) F = (A B C) A B (D C) b) F = B D (A C D B) (D B) c) F = A B C (B D) (A B D) d) F = (C D) (A B) C e) F = C (B D) (A C D) B Ex2.6 Stabilii cu ajutorul algoritmului lui Horn dac urmtoarele formule sunt satisfiabile; n caz afirmativ precizai o structur pentru care formula gsit ca satisfiabil este adevrat: a) F = A D C ( A B) ( A B ) b) F = (A D B) A (A C) (C D) Ex2.7 Stabilii cu ajutorul algoritmului lui Horn dac urmtoarele formule sunt satisfiabile; n caz afirmativ precizai o structur pentru care formula gsit ca satisfiabil este adevrat: a) F = (A D) C (C A) (C B D) B b) F = ( AB ) ( C D A ) C B Ex2.8 Stabilii cu ajutorul algoritmului lui Horn dac urmtoarele formule sunt satisfiabile; n caz afirmativ precizai o structur pentru care formula gsit ca satisfiabil este adevrat: a) F = (A B C) C B A b) F = (B D) E C B (B D B) Ex2.9 Stabilii cu ajutorul algoritmului lui Horn dac urmtoarele formule sunt satisfiabile; n caz afirmativ precizai o structur pentru care formula gsit ca satisfiabil este adevrat: a) F = (B C A) (B D) B C b) F = C (B D) (A C D) B Ex2.10 (Scriei un program ntr-un limbaj de programare cunoscut care s transforme o formul Horn (n FNC) ntr-o formul horn sub form implicaional (se va verifica dac formula este Horn). Ex2.11 Gsii FND, FNC pentru formula: F = (A B C)CD Scriei un program ntr-un limbaj de programare cunoscut care s transforme o formul oarecare n FNC. Ex2.12 Demonstrai utiliznd algoritmul rezoluiei c formula (A B C) este consecin semantic din mulimea de formule: {(A B), (B C), (A C), (A B C)} Ex2.13 Parantetizai corect apoi construii arborele asociat pentru fiecare din formulele urmtoare: a) F = ( A B C ) A B b) F = C ( B D ) ( C D) D Ex2.14 Parantetizai corect apoi construii arborele asociat pentru fiecare din formulele urmtoare: a) F = D C B C D b) F = (C D B) (A B) (A D) Ex2.15 Parantetizai corect apoi construii arborele asociat pentru fiecare din formulele urmtoare:

a) F = (A A) (A B D C) b) F = (D A C A (D B)) Ex2.16 Realizai un program ntr-un limbaj de programare cunoscut care s genereze i s afieze arborele asociat unei formule. Ex2.17 Care din urmtoarele formule sunt tautologii ?

p ( q r ); ( p q ) r; ((p q) r) (p (q r)); (p (q r)) ((p q) r); (p r q s) ((p q)(r s));

Algoritm HornIntrare: Orice formul Horn, F, reprezentat ca mulime de clauze, clauzele componente fiind clauze Horn diferite de clauza vid i scrise sub form implicaional . Ieire: DA, n cazul n care formula F este satisfiabil (furnizndu-se i o asignare S care este model pentru F) i NU n caz contrar (F nu este satisfiabil). Metod (de marcare): Pasul 1. i := 0. Pasul 2. Ct_timp ((exist n F o clauz C de forma A1 A2 A3 Ak B, cu A1, A2, A3, ... , Ak marcai i B nemarcat sau de forma A1 A2 A3 Ak 0, cu A1, A2, A3, ... , Ak marcai) i (i = 0)) execut: Pasul 3. Alege un asemenea C ca mai sus. Pasul 4. Dac ( C = A1 A2 A3 Ak B ) atunci Pasul 5. Marcheaz B peste tot n F. altfel Pasul 6. i := 1. Sf_Dac Sf_Ct_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.