Logică propozițională

În rezolvarea problemelor, vom folosi pentru expresii boolene un tip recursiv similar cu următorul (cu variațiuni, dacă în expresii 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

1. Scrieți o funcție care ia ca parametru o expresie booleană și returnează mulțimea tuturor propozițiilor (identificatorilor) care apar în expresie.
Folosiți mulțimi de șiruri, cu modulul: module S = Set.Make(String)

2. Scrieți o mulțime care ia ca parametri o funcție parțială de adevăr, definită pentru anumite propoziții (identificatori), și o expresie, și returnează expresia în care aceste propoziții sunt înlocuite cu valorile false și true.

3. Scrieți o funcție care ia ca parametru o expresie booleană care poate conține constante (false sau true) și simplifică expresia după regulile cunoscute din algebra booleană.

4. Scrieți o funcție care ia ca parametru o formulă propozițională și returnează o formulă echivalentă, în care negația e aplicată doar direct propozițiilor. (Folosiți regulile lui de Morgan.)

Marius Minea

Last modified: Tue Oct 29 8:10:00 EEST 2013