Logică propozițională

Î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. 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. 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.

6. 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.

7. 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.


Marius Minea
Last modified: Wed Nov 4 10:40:00 EET 2015