Clause (logic)

From Wikipedia, the free encyclopedia

For other uses, see Clause (disambiguation).

In logic, a clause is a disjunction of literals. In propositional logic, clauses are usually written as follows, where the symbols $l i$ are literals:

$l_1 \vee \cdots \vee l_n$

In some cases, clauses are written as sets of literals, so that clause above would be written as $\{l_1, \ldots, l_n\}$ . That this set is to be interpreted as the disjunction of its elements is then hinted from the context. A clause can be empty; in this case, it is an empty set of literals. The empty clause is denoted by various symbols such as $\empty$ , $\bot$ , or $\Box$ . The truth evaluation of an empty clause is always $f a l s e$ .

In first-order logic, a clause is the universal quantification of all free variables of a quantifier-free disjunction of literals. Formally, a first-order literal is formula of the kind of $P(t_1,\ldots,t_n)$ , where $P$ is a predicate of arity $n$ and each $t i$ is an arbitrary term, possibly containing variables. If $L_1,\ldots,L_m$ are literals, and $x_1,\ldots,x_k$ are their (free) variables, then $\forall x_1,\ldots,x_k . L_1,\ldots,L_m$ is a clause. First-order clauses are sometimes written omitting the quantifiers, so that the above clause is written $L_1,\ldots,L_m$ . This omission is justified by the fact that, for being a clause, a disjunction of literals must have all variables universally quantified. In case a clause is valid or checked for validity, this universal quantification is also implicit in the semantics. However, the definition of satisfiability assumes free variables to be existentially quantified, so the omission of quantifier is to be taken as a convention and not as a consequence of how the semantics deal with free variables.

In logic programming, clauses are usually written as the implication of a head from a body. In the simpest case, the body is a conjunction of literals while the head is a single literal. More generally, the head may be a disjunction of literals. If $b_1,\ldots,b_m$ are the literals in the body of a clause and $h_1,\ldots,h_n$ those of its head, the clause is usually written: