Î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 bform = B of bool V of string Neg of bform And of bform * bform Or of bform * bform Impl of bform * bform
Puteți scrie valori de această formă direct, de exemplu And (Or (V "a", V "b"), Neg (V "c")). Alternativ, puteți genera automat formule în acest format (și modifica codul, adăugând implicație, etc).
1. 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).
2. Substituții din dicționar Scrieți o funcție care ia ca parametri o formulă propozițională și un dicționar cu chei propoziții si valori boolene, si returnează o formulă în care propozițiile din dicționar au fost substituite cu valorile lor.
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. Simplificarea constantelor Scrieți o funcție care simplifică o formulă propozițională care poate conține constante boolene, folosind diverse reguli (tautologii) cunoscute: idempotență, operații cu constante boolene, eliminarea dublei negații. Combinați apoi cu problema 2 pentru a simplifica o formulă în care unele propoziții au valori cunoscute.
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ă (cu propoziții, negație, conjuncție și disjuncție) ș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.
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.