l Logica predicatelor

Logica predicatelor

Tema pentru laboratorul 8

1. Formalizați în logica predicatelor unul din exemplele nerezolvate (11 - 23) de pe această pagină

2. Transformați în formă clauzală, urmărind cei 8 pași de la curs, formula:
¬ ∃ x R(x, x) ∧ ∃ x ∀ y (R(x, y) ∧ S(y, x)) ∧ ∀ x ∃ y (R(x, y) ↔ S(x, y))

3. Se dă următoarea definiție a unui termen în logica predicatelor: un termen e fie o variabilă, fie o funcție de termeni (constantele sunt asimilate funcțiilor fără parametri) 

type term = V of string
            | F of string * term list
Scrieti o funcție recursivă care tipărește un termen. De exemplu, printterm (F ("f", [V "x"; F ("g", [F ("a", []); V "y"]) ])) va tipări f(x, g(a, y)).

Probleme de rezolvat

1. Scrieți o funcție care primește un nume de variabilă și un termen și determină (returnează adevărat/fals) dacă variabila respectivă apare sau nu în termen.

2. Scrieți o funcție care ia ca parametru o formulă propozițională în formă normală conjunctivă (reprezentată ca listă de liste de literali) și un nume de propoziție, și returnează lista tuturor rezolvenților care se pot crea cu literalul respectiv. (Eliminați eventuali literali duplicați din clauză, și simplificați în caz că apare un alt literal împreună cu negația lui).

3. Scrieți o funcție care ia ca parametru o formulă de ordinul I, după tipul dat mai jos, și returnează mulțimea numelor tuturor variabilelor libere din formulă (o mulțime de șiruri). 

type predform = Pr of string * term list
                | Neg of predform
                | And of predform * predform
                | Or of predform * predform
                | Forall of string * predform
4. Scrieți o funcție care ia ca parametru o formulă cuantificată universal, după tipul de mai sus, și redenumește variabila legată, folosind un alt nume dat ca parametru (despre care se presupune că nu mai apare liber în formulă).
Marius Minea
Last modified: Mon Nov 11 22:20:00 EET 2013