Î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
Puteți scrie valori de această formă direct, de exemplu And (Or (V "a", V "b"), Neg (V "c")). Alternativ, folosiți acest program, care 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. Includeți funcțiile voastre ca să folosească direct formula citită de la intrare, sau scrieți o funcție care s-o tipărească în forma necesară, cu And, Or, etc. și o copiați apoi în programul vostru.
1. Mulțimea propozițiilor
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. Normalizarea negației Scrieți o funcție care ia ca parametru o formulă propozițională și verifică (returnează true) dacă negația e aplicată doar direct propozițiilor (deci nu e aplicată unor formule mai complexe).
3. Polaritatea propozițiilor O apariție a unei propoziții într-o formulă se spune că are polaritate pozitivă dacă se află sub un număr par de negații, și negativă dacă se află sub un număr impar de negații.
a) Scrieți o funcție care determină dacă o propoziție apare doar pozitiv (variantă: doar negativ) într-o formulă.
b) Scrieți o funcție care ia ca parametri o formulă și o propoziție și returnează o pereche de booleni care semnifică dacă propoziția apare pozitiv respectiv negativ în formulă.
c) Scrieți o funcție care determină mulțimea tuturor propozițiilor care apar doar pozitiv / doar negativ (variantă: o pereche cu ambele mulțimi) într-o formulă.
4. Simplificare cu atribuiri 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), ș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.
5. E realizabilă formula?
Pornind de la temă, scrieți o funcție care determină (simplu dar ineficient) daca o formulă e realizabilă:
dacă formula e evaluată la o constantă (cazul de bază), valoarea (true/false) dă răspunsul
altfel, putem găsi o variabilă, și încercăm pe rând să o înlocuim cu true resp. false.
6. Influența unei variabile
Determinați dacă valoarea unei propoziții p poate influența valoarea de adevăr a unei formule f, și în caz afirmativ, produceți o listă de atribuiri pentru celelalte variabile pentru care formula își schimbă valoarea de adevăr când p își schimbă valoarea de adevăr.
Problema e echivalentă cu determinarea unei atribuiri care face realizabilă formula f|p=F xor f|p=T, adică o atribuire a celorlalte variabile pentru care valoarea lui f fixând p=F nu e egală cu valoarea lui f setând p=T.
Pentru tipul care descrie structura formulei, considerați propoziții, negație, conjuncție și disjuncție.
7. Forma normală conjunctivă 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.
Pentru tipul care descrie structura formulei, considerați propoziții, negație, conjuncție și disjuncție.
8. Scrierea cu paranteze
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.