Predicate Logic
Predicate logic, also called first-order logic, is a formal system that extends propositional logic. The primary application of predicate logic is also to model statements in natural language; however, it is more expressive than propositional logic, given its larger set of rules.
Domain
There are only two distinct values: true and false, denoted by T and F respectively.
Syntax
The rules for constructing expressions in predicate logic follow.
Negation
A negation is denoted by the following symbol: .
Connective
A connective is one of the following symbols: .
Quantifier
A quantifier is one of the following symbols: .
Variable
An variable is denoted by a string of letters without spaces, starting with a lowercase letter. For instance:
Quantification
A quantification is denoted by a quantifier followed by a variable. It may be preceded by a negation. For instance:
Function
A function is denoted by a string of letters without spaces, starting with an uppercase letter; then, a list of elements enclosed in parentheses, separated by commas. For instance:
Predicate
A predicate is denoted by a function which may be preceded by a negation. Then, it may be preceded by a quantification. If so, a colon follows the quantification, and the rest is enclosed in parentheses. For instance:
Clause
A clause is either of the following: a predicate; or a clause, followed by a connective, followed by a clause. In the second case, it must be enclosed in parentheses. A clause may be preceded by a negation. For instance:
Semantics
The rules for determining the value of expressions follow.
Negation
A negation in predicate logic is treated in the same way as in propositional logic.
Variable
A variable represents a unit on which a clause acts. It can represent any idea.
Quantification
A quantification represents a statement about a variable. means "for all a" and means "for at least one a".
Function
A function also represents a statement about one or more variables. The value of a function is one of T and F, but not both or neither. The conditions under which the value is T or F are defined arbitrarily. For instance, a function
means "a owes money to b".
Predicate
A predicate is simply the extension of a function. The value of a predicate is also one of T and F. A quantification acts on the predicate that immediately follows the colon. The meaning, therefore, can be interpreted literally. For instance, the predicate
means "for at least one a, a owes money to George", or "at least one person owes money to George". A predicate may contain more than one quantification. For instance, the predicate
means "it is not the case that for all a: for at least one b, a owes money to b". In plain English: "not everyone owes someone money".
Clause
Each part of a clause corresponds to an equivalent part in propositional logic: a predicate to an atom, and a connective to itself. Therefore, this rule can be deduced from propositional logic.
Thus conclude the rules of predicate logic.