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


Marius Minea
Last modified: Wed Nov 1 13:50:00 EET 2017