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: $\neg$.

Connective

A connective is one of the following symbols: $\land ,\;\lor$.

Quantifier

A quantifier is one of the following symbols: $\forall ,\;\exists$.

Variable

An variable is denoted by a string of letters without spaces, starting with a lowercase letter. For instance:

$a$

$thisIsAnotherVariable$

Quantification

A quantification is denoted by a quantifier followed by a variable. It may be preceded by a negation. For instance:

$\exists \,a$

$\neg \,\forall \,x$

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:

$P(a)$

$Married(a,b)$

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:

$P(a)$

$\neg \,Married(a)$

$\forall \,a:(\neg \,Q(a,b,c))$

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:

$P(a)$

$\exists \,a:(\neg \,P(a)\land \forall \,b:(Q(a,b)))$

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. $\forall \,a$ means "for all a" and $\exists \,a$ 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

$OwesMoney(a,b)$

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

$\exists \,a:(OwesMoney(a,George))$

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

$\neg \,\forall \,a:(\exists \,b:(OwesMoney(a,b))))$

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.