A) Fiind dată o formulă propozițională, (1) transformați-o în formă normală conjunctivă și (2) scrieți o formulă echirealizabilă folosind transformarea Tseitin.
Alegeți o formulă cu cel puțin 4 propoziții și cel puțin 5 operatori logici, pe cel puțin 3 nivele de subformule.
(Subformulele (subexpresiile) sunt formulele (expresiile) mai simple din care e construită formula (expresia), aplicând operatorii).
De exemplu, expresia aritmetică 2 * (3 + 4 * 5) are operatori/subexpresii pe trei nivele: 2 * ... care în subexpresia dreaptă conține 3 + ..., care conține 4 * 5.
B) Scrieți o funcție care ia ca parametru o formulă propozițională și returnează numărul subformulelor ei, tipărind în același timp fiecare subformulă, precedată de numărul ei de ordine.
Folosiți o funcție ajutătoare care ia ca parametru suplimentar numărul de subformule întâlnite până în prezent și returnează numărul actualizat (după prelucrarea subformulei date). Inițial, apelați funcția ajutătoare cu valoarea 0.
Exercițiu pregătitor
Modificați programul prezentat la curs care determină realizabilitatea unei formule. Adăugați în funcții cod care tipărește după fiecare prelucrare valorile noi obținute (după caz, clauza, întreaga formulă, sau mulțimea literalelor adevărate). Rulați codul pe un exemplu urmărind prelucrările făcute.
Probleme propuse
În rezolvarea problemelor, vom folosi pentru expresii (formule) propoziționale un tip recursiv similar cu următorul (cu variațiuni, dacă în formule considerăm că pot apărea sau nu constante, implicație, etc.).
type bexp = B of bool V of string Neg of bexp And of bexp * bexp Or of bexp * bexp Impl of bexp * bexp
Programul atasat citeste o formulă propozițională (pâna la sfârșitul intrării, Ctrl-D/Ctrl-Z), cu operatorii + (sau), * (si), ~ (nu) si litere ca propoziții. Construiește o expresie cu tipul de mai sus și o tipărește (cu exces de paranteze). Puteți să îl folosiți pentru a prelucra o formulă citită direct de la intrare. Altfel, scrieți direct expresii cum ar fi And (Or (V "a", V "b"), Neg (V "c")).
1. Scrieți o funcție care ia ca parametru o formulă propozițională și returnează mulțimea tuturor propozițiilor (identificatorilor) care apar în formulă.
Folosiți mulțimi de șiruri, cu modulul: module S = Set.Make(String)
2. Scrieți o funcție care ia ca parametri un dicționar (o funcție parțială de adevăr, definită pentru anumite propoziții (identificatori)), și o formulă propozițională, și returnează formula în care propozițiile din dicționar sunt înlocuite cu valorile corespunzătoare false sau true, simplificând formula prin evaluările parțiale care se pot face.
3. Scrieți o funcție care ia ca parametru o formulă propozițională și o transformă în formă normală conjunctivă.
Obțineți întâi o formulă echivalentă, în care negația e aplicată doar direct propozițiilor, folosind regulile lui de Morgan. Apoi aplicați recursiv distributivitatea disjuncției față de conjuncție.
4. Transformați (ca în exercițiul anterior) o formulă în formă normală conjunctivă, reprezentată ca listă de clauze.
5. Scrieți o funcție care ia ca parametru o formulă propozițională și o tipărește
cu minimul necesare de paranteze, ținând cont de precedența operatorilor.
Sunt necesare paranteze dacă prioritatea operatorului dintr-o subformulă
e mai mică decât prioritatea operatorului aplicat în exterior, de ex. ... * (a + b). Când tipăriți o subexpresie, dați ca parametru un număr reprezentând
prioritatea operatorului aplicat în exterior.