1. Clausal form :
In this form, the formula is made up of a number of clauses, where each clause is composed of a number of literals connected by OR logical connectives only.
A clausal form formula must be transformed into another formula with the following characteristics :
2. Horn Clausal form :
A Horn clause is a clause (a disjunction of literals) with at most one positive, i.e. unnegated, literal. A clause with at most one positive (unnegated) literal is called a Horn Clause.
Types of Horn Clauses :
Examples :
Clausal form :
Literals can be positive literals or negative literals. For the forms of the individual clauses where each of is a disjunction of literals. For the clause form :
NOT(P1) OR NOT(P2) OR . OR NOT(Pn) OR Q1 OR Q2 OR . OR Qm
The above clause has n negative literals and m positive literals. This clause can be transformed into the following equivalent logical formula :
P1 AND P2 AND . AND Pn => Q1 OR Q2 OR . OR Qm
where ‘=>’ is the implies symbol.
Horn Clausal form :
(i) The Horn clause,
NOT(P1) OR NOT(P2) OR . OR NOT(Pn) OR Q
Can be transformed into the clause :
P1 AND P2 AND … AND Pn => Q
which is written in Datalog as the following rules.
Q :- P1, P2, . Pn.
The above Datalog Rule, is hence a Horn clause.
Meaning : If the predicates P1 AND P2 AND … AND Pn, are all true for a particular binding to their variable arguments, then Q is also true and can hence be inferred.
(ii) The Horn clause,
NOT(P1) OR NOT(P2) OR . OR NOT (Pn)
Can be transformed into
P1 AND P2 AND … AND Pn =>
which is written in Datalog as follows :
P1, P2, . Pn.
The above Datalog expression can be considered as an integrity constraint, where all the predicates must be true to satisfy the query.