In
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premi ...
, a clause is a
propositional formula
In propositional logic, a propositional formula is a type of syntactic formula which is well formed and has a truth value. If the values of all variables in a propositional formula are given, it determines a unique truth value. A propositional fo ...
formed from a finite collection of
literals (atoms or their negations) and
logical connectives
In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary co ...
. A clause is true either whenever at least one of the literals that form it is true (a disjunctive clause, the most common use of the term), or when all of the literals that form it are true (a conjunctive clause, a less common use of the term). That is, it is a finite
disjunction
In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor ...
or
conjunction
Conjunction may refer to:
* Conjunction (grammar), a part of speech
* Logical conjunction, a mathematical operator
** Conjunction introduction, a rule of inference of propositional logic
* Conjunction (astronomy)
In astronomy, a conjunction occ ...
of literals, depending on the context. Clauses are usually written as follows, where the symbols
are literals:
:
Empty clauses
A clause can be empty (defined from an empty set of literals). The empty clause is denoted by various symbols such as
,
, or
. The truth evaluation of an empty disjunctive clause is always
. This is justified by considering that
is the neutral element of the
monoid
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
Monoids a ...
.
The truth evaluation of an empty conjunctive clause is always
. This is related to the concept of a
vacuous truth
In mathematics and logic, a vacuous truth is a conditional or universal statement (a universal statement that can be converted to a conditional statement) that is true because the antecedent cannot be satisfied. For example, the statement "sh ...
.
Implicative form
Every nonempty (disjunctive) clause is logically equivalent to an
implication of a head from a body, where the head is an arbitrary literal of the clause and the body is the
conjunction
Conjunction may refer to:
* Conjunction (grammar), a part of speech
* Logical conjunction, a mathematical operator
** Conjunction introduction, a rule of inference of propositional logic
* Conjunction (astronomy)
In astronomy, a conjunction occ ...
of the negations of the other literals. That is, if a
truth assignment causes a clause to be true, and none of the literals of the body satisfy the clause, then the head must also be true.
This equivalence is commonly used in
logic programming
Logic programming is a programming paradigm which is largely based on formal logic. Any program written in a logic programming language is a set of sentences in logical form, expressing facts and rules about some problem domain. Major logic pr ...
, where clauses are usually written as an implication in this form. More generally, the head may be a disjunction of literals. If
are the literals in the body of a clause and
are those of its head, the clause is usually written as follows:
:
* If ''n'' = 1 and ''m'' = 0, the clause is called a (
Prolog
Prolog is a logic programming language associated with artificial intelligence and computational linguistics.
Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is intended primaril ...
) fact.
* If ''n'' = 1 and ''m'' > 0, the clause is called a (Prolog) rule.
* If ''n'' = 0 and ''m'' > 0, the clause is called a (Prolog) query.
* If ''n'' > 1, the clause is no longer
Horn.
See also
*
Conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a canon ...
*
Disjunctive normal form
In boolean logic, a disjunctive normal form (DNF) is a canonical normal form of a logical formula consisting of a disjunction of conjunctions; it can also be described as an OR of ANDs, a sum of products, or (in philosophical logic) a ''cluster c ...
*
Horn clause In mathematical logic and logic programming, a Horn clause is a logical formula of a particular rule-like form which gives it useful properties for use in logic programming, formal specification, and model theory. Horn clauses are named for the logi ...
References
{{reflist
External links
Clause logic related terminology
Propositional calculus
Predicate logic
Logic programming