Logică și structuri discrete - Tema 6

Tema se predă asistentului prin e-mail (subiect: LSD tema 6) până miercuri ora 23 (scrisă după standardele afișate pe pagina cursului, și împreună cu problemele date după laboratorul 5)

Exercițiul 1 Scrieți o funcție care ia ca parametru o formulă propozițională (expresie booleană) cu operatorii de conjuncție, disjuncție, negație și propoziții cu nume arbitrare, și returnează o listă de atribuiri la propoziții (perechi string * bool) pentru care formula e adevărată, sau generează excepția Not_found dacă formula nu e realizabilă.
Exemple Pentru Or (V "a", V "b") funcția ar putea returna [("a", true)] sau [("b", true)] sau [("a", true);("b", true)] sau [("b", true);("a", true)].
Indicatii Folosiți sau adaptați următoarele funcții ajutătoare:

la curs am scris o funcție care returnează un nume de variabilă propozițională dintr-o formulă (vezi mai jos)
În exercițiile rezolvate (nr. 2) aveți o funcție care simplifică o formulă în care apar constante boolene

Scrieți o funcție simplify_var nume_prop bool_val formula adaptând simplify. Funcția returnează formula simplificată obținută înlocuind peste tot propoziția dată cu o valoare booleană (true sau false).
Pentru soluția propriu-zisă, scrieți o funcție ajutătoare recursivă care are lista cu perechi de atriburi ca parametru-acumulator suplimentar: rezolva_aux lista_perechi formula
Funcția cerută o va apela pe aceasta cu lista vidă ca atribuire inițială:
let rezolva = rezolva_aux []
Presupunem că funcția primește o expresie deja simplificată, sau putem folosi simplify pe argumentul inițial: rezolva (simplify formula)
În final, scrieți funcția principală rezolva_aux.

Dacă formula e B true sau B false avem răspunsul. În caz de succes, returnați lista ca valoare normală sau generați excepția Not_found pentru a semnala o formulă nerealizabilă.
Altfel, formula nu e constantă, și puteți obține cu findvar numele unei propoziții.
Alegeți pe rând true sau false pentru această propoziție, simplificați formula cu simplify_var, adăugați perechea (nume, valoare) la listă și continuați cu apelul recursiv.
Dacă obțineți un eșec cu prima valoare, tratați excepția continuând cu al doilea apel. Acesta va furniza direct rezultatul, atât în caz de succes cât și de eșec.

type bform = B of bool | V of string
           | Neg of bform
           | And of bform * bform
           | Or of bform * bform

let rec findvar = function        (* parcurge formula pana la prima variabila *)
  | B _ -> raise Not_found        (* caz de baza: nu avem propoziție *)
  | V p -> p                        (* am găsit, returnăm *)
  | Neg f -> findvar f                (* caută în unica subformulă *)
  | And (f1, f2) | Or (f1, f2) ->
     try findvar f1                (* caută în prima subformulă *)
     with Not_found -> findvar f2        (* dacă nu, caută în a doua *)
;;
findvar (And (V "p", Or(V "q", B true)));;
;;
findvar (B false)
;;
findvar (V "a");;

Marius Minea

Last modified: Sat Nov 7 8:50:00 EET 2015