Predicate Logic

Instructor

Li Hui

Concepts and Representation of Predicates

Propositional logic takes atomic propositions as its basic unit and studies the logical and inferential relationships among compound propositions. However, some inferential relationships are difficult to express precisely using propositional logic.

A typical example is the Socratic syllogism:

  1. All humans are mortal,

  2. Socrates is human,

  3. Therefore, Socrates is mortal.

Clearly, the conclusion follows reasonably from the premises, i.e., the reasoning is valid.

Symbolizing the syllogism:

  • \(p\): All humans are mortal

  • \(q\): Socrates is human

  • \(r\): Socrates is mortal

Premises: \(p\), \(q\); Conclusion: \(r\). We need to show that \({p, q}{\vDash}r\) is valid.

Note: The logical relationships among these propositions are not reflected between atomic propositions themselves, but among the components that make up the atomic propositions, i.e., at a deeper structural level.

\(p\) is a judgment about all humans, which includes \(q\). Both \(q\) and \(r\) are judgments about one individual, Socrates. These logical relationships are obscured when expressed as propositions.

In studying certain inferences, it is necessary to further analyze atomic propositions and decompose their components: individuals, predicates, and quantifiers.

Studying their formal structure, logical relationships, and rules of inference is precisely the subject of predicate logic (first-order logic).

Individuals and Predicates

Definition: A word representing a subject or object component is called an individual (term). Individuals can be concrete or abstract.

Example: Tiananmen Gate, panda, thought, 2, etc. are all individuals.

Individual constants: Words representing specific, definite individuals. Denoted by lowercase letters \(a, b, c, {\cdots}\).

Individual variables: Words representing unspecified individuals. Denoted by lowercase letters \(x, y, z, {\cdots}\).

Every individual appearing in a proposition is an individual constant.

  • I am a teacher.

  • Xiao Ming likes cats.

Definition: A word representing a property of one individual or a relation among multiple individuals is called a predicate.

A predicate representing the property of one individual is called a unary predicate; a predicate representing a relation among \(n\) individuals is called an \(n\)-ary predicate.

  • “I am a teacher” represents a property of one individual.

  • “Wednesday is between Monday and Friday” represents a relation among multiple individuals.

Predicates also have constants and variables.

Predicate constants: Predicates representing specific properties or relations.

Predicate variables: Predicates representing abstract or generic properties or relations.

Predicates are generally denoted by uppercase letters \(P, Q, R{\cdots}\).

Definition: An atomic proposition represented using a predicate \(P\) and \(n\) ordered individual constants \(a_{1}, a_{2}, {\cdots}, a_{n}\) in the form \(P(a_{1}, a_{2}, {\cdots}, a_{n})\) is called the predicate form of the atomic proposition.

 

In predicate logic, how does one symbolize an atomic proposition?

2 is an even number can be symbolized as \(P(a)\), where \(P\): \({\cdots}\) is an even number, \(a\): 2.

Xiao Wang likes the little tabby cat can be symbolized as: \(F(a, b)\), where \(F\): \({\cdots}\) likes \({\cdots}\), \(a\): Xiao Wang, \(b\): little tabby cat.

Shanghai is located between Beijing and Guangzhou can be symbolized as: \(G(a, b, c)\), where \(G\): \({\cdots}\) is between \({\cdots}\) and \({\cdots}\), \(a\): Shanghai, \(b\): Beijing, \(c\): Guangzhou.

Zhang San is a college student, Li Si is a college student.

(Symbolized in propositional logic) \(p\): Zhang San is a college student, \(q\): Li Si is a college student.

(Symbolized in predicate logic) \(S(a)\): Zhang San is a college student, \(S(b)\): Li Si is a college student. Where \(S\): \({\cdots}\) is a college student, \(a\): Zhang San, \(b\): Li Si.

In the propositional logic symbolization, \(p\) and \(q\) have no connection. In the predicate logic symbolization, \(S(a)\) and \(S(b)\) both reflect the fact that both are college students.

A given predicate can form different propositions with different individual constants.

Zhang San is a college student, Li Si is a college student.

These are two different propositions, but they share a common form, namely \(S(x)\), where \(x\) is an individual variable. When \(x\) takes the value \(a\) or \(b\), the above two propositions are represented respectively.

Here \(S(x)\) is merely an abstract common form of certain concrete propositions and does not represent any proposition itself.

Definition: A symbol string \(P(x_{1}, x_{2}, {\cdots}, x_{n})\) composed of a predicate \(P\) and \(n\) (\(n{\geq}1\)) individual variables \(x_{1}, x_{2}, {\cdots}, x_{n}\) is called an \(n\)-ary predicate.

\(n=1\), unary predicate, e.g.: \(P(x)\): \(x\) likes animals.

\(n=2\), binary predicate, e.g.: \(Q(x, y)\): \(x\) and \(y\) are classmates.

\(n=3\), ternary predicate, e.g.: \(R(x, y, z)\): \(x+y=z\).

Sometimes the predicate form of an atomic proposition is called a 0-ary predicate; \(P(a), F(a, b), G(a, b, c)\), etc. are all 0-ary predicates.

Since all propositions in propositional logic can be expressed as 0-ary predicates, propositions can be regarded as special predicates.

Domains and Quantifiers

An \(n\)-ary predicate is not itself a proposition; only when all individual variables in it are replaced by specific individuals with definite values does it become a proposition. The range of specific individuals that an individual variable can be replaced by, and the range within which it can take values, greatly affects its truth value.

The range of values of an individual variable is called the domain of discourse (or universe of discourse).

\(P(x, y)\): \(x^{2}+y^{2}=0\)

If the domain for \(x\) and \(y\) is all positive numbers, then for any values of \(x, y\), \(P(x, y)\) is false;

If the domain for \(x\) and \(y\) is all real numbers, then except for \(P(0, 0)\), which is a true proposition, all other cases are false propositions.

\(S(x)\): \(x\) is a student at the University of Chemical Technology

If the domain of \(x\) is the set of all faculty and students at the University of Chemical Technology, then \(S(x)\) is a true proposition when \(x\) takes the value of some student, and false for all other values.

If the domain of \(x\) is the set of all students at the University of Chemical Technology, then \(S(x)\) is a true proposition for any value of \(x\).

In addition to individuals and predicates, propositions sometimes contain words that express quantity; these are called quantifiers.

In predicate logic, quantifiers are divided into three types:

  1. Universal quantifier: Words expressing “all”, “every”, and “for any”, denoted by the symbol \(\forall\).

  2. Existential quantifier: Words expressing “there exist some”, “there is one”, and “there is at least one”, denoted by the symbol \(\exists\).

  3. Unique existential quantifier: Words expressing “there exists a unique” and “there is exactly one”, denoted by the symbol \({\exists}!\).

The quantifiers \({\forall}\), \({\exists}\), and \({\exists}!\) cannot be used alone.

An individual variable (such as \(x\)) must also be placed after the quantifier, forming \({\forall}x\), \({\exists}x\), and \({\exists}!x\), meaning “for all \(x\)”, “there exists at least one \(x\)”, and “there exists exactly one \(x\)”, respectively.

They can be placed before an \(n\)-ary predicate as a component, further constraining the values the individual variable takes within the domain of discourse.

\({\forall}xP(x)\) means every individual in the domain satisfies \(P(x)\);

\({\exists}xQ(x)\) means at least one individual in the domain satisfies \(Q(x)\);

\({\exists}!xR(x)\) means exactly one individual in the domain satisfies \(R(x)\).

Symbolize the following propositions, identifying the quantifiers, individuals, and predicates.

  1. All college students can speak English.

  2. Some college students can speak English.

Solution:

  1. The proposition is symbolized as \({\forall}xE(x)\), where the domain of \(x\) is all college students and \(E(x)\): \(x\) can speak English.

  2. The proposition is symbolized as \({\exists}xE(x)\), where the domain of \(x\) is all college students and \(E(x)\): \(x\) can speak English.

  1. Every natural number is an integer.

  2. Some tigers are white.

  3. There exists a unique even prime number.

Solution:

  1. The proposition is symbolized as \({\forall}xI(x)\), where the domain of \(x\) is the set of natural numbers and \(I(x)\): \(x\) is an integer.

  2. The proposition is symbolized as \({\exists}xW(x)\), where the domain of \(x\) is all tigers and \(W(x)\): \(x\) is white.

  3. The proposition is symbolized as \({\exists}!xR(x)\), where the domain of \(x\) is the set of even numbers and \(R(x)\): \(x\) is a prime number.

Definition: The domain formed by combining the domains of all individuals in a propositional function is called the universal domain of discourse of the propositional function.

Example: Teachers are older than students.

Here, \(P(x, y)\): \(x\) is older than \(y\); the domain of \(x\) is the set of all teachers; the domain of \(y\) is the set of all students. Universal domain: the union of the sets of teachers and students.

By convention, when a proposition does not specify the domain for its individuals, the universal domain of discourse may be used.

The true range of values for each individual variable can be restricted using a predicate, called a characteristic predicate.

Using the same examples with characteristic predicates:

  1. All college students can speak English. \({\forall}x(S(x){\rightarrow}E(x))\), where \(S(x)\): \(x\) is a college student, \(E(x)\): \(x\) can speak English.

  2. Some college students can speak English. \({\exists}x(S(x){\wedge}E(x))\), where \(S(x)\): \(x\) is a college student, \(E(x)\): \(x\) can speak English.

  3. Every natural number is an integer. \({\forall}x(N(x){\rightarrow}I(x))\), where \(N(x)\): \(x\) is a natural number, \(I(x)\): \(x\) is an integer.

  4. Some tigers are white. \({\exists}x(M(x){\wedge}W(x))\), where \(M(x)\): \(x\) is a tiger, \(W(x)\): \(x\) is white.

  5. There exists a unique even prime number. \({\exists}!x(Q(x){\wedge}R(x))\), where \(Q(x)\): \(x\) is an even number, \(R(x)\): \(x\) is a prime number.

Adding a quantifier to an \(n\)-ary predicate is called quantification of the \(n\)-ary predicate.

In predicate formulas with quantifiers and characteristic predicates, the pairing is: the universal quantifier should be followed by a conditional with the characteristic predicate as antecedent; the existential quantifier should be followed by a conjunction with the characteristic predicate as one conjunct. That is:

  • A proposition of the form “all \(A\) are \(B\)” is expressed as \({\forall}x(A(x){\rightarrow}B(x))\)

  • A proposition of the form “some \(A\) are \(B\)” is expressed as \({\exists}x(A(x){\wedge}B(x))\)

Given \(L(x): x+3>7\), let the domain of discourse be respectively:

(1)\(\{-3, -2, -1, 0, 1, 2\}\) (2)\(\{-5, 0, 3, 5, 6\}\) (3)\(\{10, 15, 24, 30\}\)

Examine the truth values of \({\forall}xL(x)\) and \({\exists}xL(x)\).

Solution: When the domain is (1), \({\forall}xL(x)\) is \(F\) and \({\exists}xL(x)\) is \(F\); when the domain is (2), \({\forall}xL(x)\) is \(F\) and \({\exists}xL(x)\) is \(T\); when the domain is (3), \({\forall}xL(x)\) is \(T\) and \({\exists}xL(x)\) is \(T\).

Predicate Formulas

Let \(P\) be an \(n\)-ary predicate and \(x_{1}, x_{2}, {\cdots}, x_{n}\) be individual variables or constants; then \(P(x_{1}, x_{2}, {\cdots}, x_{n})\) is called an atomic predicate formula.

In particular, when \(n=0\), the atomic predicate formula \(P(x_{1}, x_{2}, {\cdots}, x_{n})\) reduces to a propositional constant or propositional variable \(P\); thus propositional constants and propositional variables are also atomic predicate formulas.

A compound predicate formula is formed by connecting atomic predicate formulas using quantifiers and connectives.

A predicate formula is defined recursively as follows:

  1. An atomic predicate formula is a predicate formula;

  2. If \(A\) is a predicate formula, then \({\lnot}A\) is also a predicate formula;

  3. If \(A, B\) are predicate formulas, then \(A{\wedge}B, A{\vee}B, A{\rightarrow}B\), and \(A{\leftrightarrow}B\) are also predicate formulas;

  4. If \(A\) is a predicate formula and \(x\) is an individual variable, then \({\forall}xA\) and \({\exists}xA\) are also predicate formulas;

  5. Only symbol strings composed of atomic predicate formulas, logical connectives, quantifiers, and parentheses, obtained by finitely many applications of rules (1)–(4), are predicate formulas.

Example: \[{\forall}x((R(x){\rightarrow}P(x)){\wedge}S(x))\] \[{\forall}x(P(x, y){\rightarrow}{\exists}yQ(y))\] \[{\exists}x{\exists}y(D(y){\vee}E(x, y)){\rightarrow}{\forall}xC(x)\] \[P(x, y, z)\] \[P(a, 2){\wedge}Q(x)\] \[{\exists}yL(x, y){\rightarrow}R(x)\] are all predicate formulas.

Symbolization of Propositions

Expressing a proposition described in natural language as a predicate formula is called symbolization (translation) of propositions in predicate logic.

Let the domain of discourse be the set of real numbers. Symbolize the following propositions.

  1. Every real number is either rational or irrational.

  2. For every real number \(x\), there exists a real number \(y\) such that \(x+y=0\).

Solution:

  1. Let \(U(x)\): \(x\) is rational, \(V(x)\): \(x\) is irrational. Symbolization: \({\forall}x(U(x){\vee}V(x))\).

  2. Let \(E(x, y)\): \(x+y=0\). Symbolization: \({\forall}x{\exists}yE(x, y)\) (i.e., \({\forall}x{\exists}y(x+y=0)\)).

The general steps for translating a proposition in predicate logic are:

  1. Identify all atomic propositions and connectives in the proposition.

  2. Decompose each atomic proposition into its individuals, predicates, and quantifiers.

  3. Determine the domain of discourse for each individual; if discussing within the universal domain, provide the corresponding characteristic predicate.

  4. Translate the proposition according to the representation rules for predicate formulas.

Symbolize the following propositions:

  1. Every (quantifier) train (individual) is faster (part of predicate) than some (quantifier) cars (individual — other part of predicate).

Solution: \(F(x)\): \(x\) is a train, \(G(y)\): \(y\) is a car, \(H(x, y)\): \(x\) is faster than \(y\).

Symbolization: \({\forall}x(F(x){\rightarrow}{\exists}y(G(y){\wedge}H(x, y))\).

  1. Some cars are faster than all trains.

Solution: \(F(x)\): \(x\) is a train, \(G(y)\): \(y\) is a car, \(H(x, y)\): \(x\) is faster than \(y\).

Symbolization: \({\exists}y(G(y){\wedge}{\forall}x(F(x){\rightarrow}H(y, x))\)

  1. There is no number greater than all numbers.

Solution: \(F(x)\): \(x\) is a number, \(G(x, y)\): \(x\) is greater than \(y\).

Symbolization: \({\lnot}{\exists}x(F(x){\wedge}{\forall}y(F(y){\rightarrow}G(x, y))\)

  1. There exists a liquid that can dissolve all metals.

Solution: \(F(x)\): \(x\) is a liquid, \(G(y)\): \(y\) is a metal, \(H(x, y)\): \(x\) can dissolve \(y\).

Symbolization: \({\exists}x(F(x){\wedge}{\forall}y(G(y){\rightarrow}H(x, y))\).

Scope and Binding of Variables

Given a predicate formula \(A\), the part of the form \({\forall}xP(x)\) or \({\exists}xP(x)\) is called the \(x\)-binding part of the predicate formula \(A\); \(P(x)\) is called the scope of the corresponding quantifier \({\forall}\) or \({\exists}\).

Any occurrence of \(x\) within the \(x\)-binding part of a predicate formula \(A\) is called a bound occurrence of \(x\), and \(x\) is called a bound variable.

When an occurrence of \(x\) in a predicate formula is not a bound occurrence, it is called a free occurrence of \(x\), and the variable that occurs freely is called a free variable.

Identify the scope of each quantifier and the binding status of variables in the following predicate formulas.

  1. \({\exists}x(P(x){\wedge}Q(x))\)

Solution: The scope of \({\exists}x\) is \(P(x){\wedge}Q(x)\); \(x\) is a bound variable.

  1. \({\forall}x(P(x){\rightarrow}{\exists}yQ(x, y, z)){\wedge}R(x)\)

Solution: The scope of \({\forall}x\) is \(P(x){\rightarrow}{\exists}yQ(x, y, z)\), the scope of \({\exists}y\) is \(Q(x, y, z)\); \(x\) and \(y\) are bound variables. \(z\) is a free variable, and \(x\) in \(R(x)\) is a free variable.

In the entire predicate formula, \(x\) has both bound and free occurrences; \(y\) has a bound occurrence; \(z\) has a free occurrence.

  1. \({\exists}x{\forall}y(P(x, y){\rightarrow}(Q(x){\wedge}R(y)))\)

Solution: The scope of \({\exists}x\) is \({\forall}y(P(x, y){\rightarrow}(Q(x){\wedge}R(y)))\); the scope of \({\forall}y\) is \(P(x, y){\rightarrow}(Q(x){\wedge}R(y))\); \(x\) and \(y\) are bound variables.

In the entire predicate formula, \(x\) and \(y\) have bound occurrences.

  1. \({\forall}x(P(x, y){\wedge}Q(y)){\rightarrow}{\exists}yR(x, y)\)

Solution: The scope of \({\forall}x\) is \(P(x, y){\wedge}Q(y)\); \(x\) is a bound variable, \(y\) is a free variable. The scope of \({\exists}y\) is \(R(x, y)\); \(x\) is a free variable, \(y\) is a bound variable.

In the entire predicate formula, both \(x\) and \(y\) have both free and bound occurrences.

  1. \({\forall}xP(y, z){\rightarrow}{\exists}yQ(y)\)

Solution: The scope of \({\forall}x\) is \(P(y, z)\); \(y\) and \(z\) are free variables. The scope of \({\exists}y\) is \(Q(y)\); \(y\) is a bound variable.

In the entire predicate formula, \(z\) has a free occurrence; \(y\) has both free and bound occurrences.

In a predicate formula, an individual variable may appear as a free variable, as a bound variable, or simultaneously as both a free variable and a bound variable.

A variable in a predicate formula may have both bound and free occurrences. To avoid the confusion this causes, bound variables may be renamed so that each individual variable appears in only one form in a predicate formula — either as a free occurrence or as a bound occurrence.

The name symbol used for a bound variable in a predicate formula is unimportant; therefore, changing the symbol of a variable does not change the meaning of the predicate formula.

  • \({\forall}xP(x)\) and \({\forall}yP(y)\) have the same meaning.

  • \({\exists}xQ(x)\) and \({\exists}yQ(y)\) have the same meaning.

Rules for renaming bound variables:

  1. When renaming a bound variable, the renaming scope covers every bound occurrence of that individual variable within the quantifier’s scope; all other parts of the predicate formula remain unchanged.

  2. The replacement symbol must not have appeared in the scope; ideally it should be a symbol that has not appeared anywhere in the predicate formula.

For the predicate formula: \[({\forall}x(P(x){\rightarrow}(R(x){\vee}Q(x))){\wedge}{\exists}xR(x)){\rightarrow}{\exists}zS(x, z)\] rename the bound variables.

It can be renamed as: \[({\forall}y(P(y){\rightarrow}(R(y){\vee}Q(y))){\wedge}{\exists}wR(w)){\rightarrow}{\exists}zS(x, z)\]

Rename the following predicate formula: \[{\forall}x(P(x){\rightarrow}R(x, y)){\wedge}Q(x, y)\] It can be renamed as: \[{\forall}z(P(\boxed{z}){\rightarrow}R(\boxed{z}, y)){\wedge}Q(x, y)\] But it cannot be renamed as: \[{\forall}y(P(y){\rightarrow}R(y, y)){\wedge}Q(x, y)\] \[{\forall}z(P(z){\rightarrow}R(x, y)){\wedge}Q(x, y)\]

Free variables in a predicate formula may also be renamed; this is called free variable substitution.

Rules for free variable substitution:

  1. A free variable in a predicate formula may be substituted, and the substitution must be applied simultaneously to all occurrences of that free variable.

  2. The substituting symbol may be an individual constant or an individual variable; the symbol chosen must not have appeared in the original predicate formula.

For the predicate formula \[({\forall}x(R(x, y){\vee}S(x)){\rightarrow}Q(x)){\wedge}{\exists}zP(x, y, z)\] we may substitute the free variable \(x\) with the free variable \(w\), obtaining the predicate formula: \[({\forall}x(R(x, y){\vee}S(x)){\rightarrow}Q(w)){\wedge}{\exists}zP(w, y, z)\]

But it cannot be substituted as: \[({\forall}x(R(x, y){\vee}S(x)){\rightarrow}Q(w)){\wedge}{\exists}zP(x, y, z)\] because this violates substitution rule (1).

Or substituted as:\[({\forall}x(R(x, y){\vee}S(x)){\rightarrow}Q(y)){\wedge}{\exists}zP(y, y, z)\] because this violates substitution rule (2).

The binding of quantifiers over variables depends on the order in which the quantifiers appear; this order generally cannot be changed arbitrarily.

  • \({\forall}x{\exists}y(x+y=0)\) means “for every real number \(x\), there exists a real number \(y\) such that \(x+y=0\)”; this is a true proposition.

  • \({\exists}y{\forall}x(x+y=0)\) means “there exists a real number \(y\) such that for every real number \(x\), \(x+y=0\)”; this is a false proposition. They have different meanings.

Interpretation of Predicate Formulas

A predicate formula consists purely of abstract symbols. It acquires genuine meaning only after being given an interpretation, and a definite truth value only after a valuation is assigned.

For example: \(S(x){\wedge}{\exists}xQ(x)\) by itself has no meaning.

An interpretation includes: defining the domain, specifying the concrete meanings of predicate symbols and operation symbols, etc. It is a mapping from abstract symbols to concrete properties, relations, and operations on the domain, and is commonly denoted by \(I\).

The same predicate formula can have different meanings under different interpretations.

After an interpretation of a predicate formula is given, substituting each individual variable in the formula with a specific individual from its domain and each propositional variable with a definite proposition is called a valuation of the predicate formula.

Once a predicate formula is valuated, it becomes a proposition with a definite truth value.

Given the following interpretations \(I\), discuss the truth values of \(S(x)\), \({\exists}xS(x)\), and \(S(x){\wedge}{\exists}xS(x)\).

  1. \(I_1\): Domain \(D_{1}=\{3, 4\}\); \(S(x)\) means \(x\) is a prime number.

  2. \(I_2\): Domain \(D_{2}=\{3, 4\}\); \(S(x)\) means \(x\) is an even number.

  3. \(I_3\): Domain \(D_{3}=\{3, 5\}\); \(S(x)\) means \(x\) is a prime number.

  4. \(I_4\): Domain \(D_{4}=\{3, 5\}\); \(S(x)\) means \(x\) is an even number.

Truth table of \(S(x)\), \({\exists}xS(x)\), and \(S(x){\wedge}{\exists}xS(x)\):

  \[ \begin{array}{ccccc} Interpretation & x & S(x) & {\exists}xS(x) & S(x){\wedge}{\exists}xS(x) \\ I_1 & 3 & T & T & T \\ I_1 & 4 & F & T & F \\ I_2 & 3 & F & T & F \\ I_2 & 4 & T & T & T \\ I_3 & 3 & T & T & T \\ I_3 & 5 & T & T & T \\ I_4 & 3 & F & F & F \\ I_4 & 5 & F & F & F \\ \end{array} \]

Given an interpretation \(I\) of predicate formula \(A\), let \(x_{1}, x_{2}, {\cdots}, x_{n}\) be the individual variables appearing in \(A\).

If \(A\) is true when \(x_{1}, x_{2}, {\cdots}, x_{n}\) are assigned values \(t_{1}, t_{2}, {\cdots}, t_{n}\), then \(A\) is said to be true at \(t_{1}, t_{2}, {\cdots}, t_{n}\).

When \(A\) is true for every valuation of \(x_{1}, x_{2}, {\cdots}, x_{n}\) under interpretation \(I\), then \(A\) is said to be true under interpretation \(I\).

  • Given interpretation \(I\): Domain \(D=\{3, 4, 5\}\); \(S(x)\): \(x\) is greater than \(2\); \(T(x)\): \(x\) is less than \(6\). Then \(S(x){\wedge}T(x)\): is true at \(x=3\), \(x=4\), and \(x=5\), so \(S(x){\wedge}T(x)\) is true under interpretation \(I\).

  • Given interpretation \(I\): Domain \(D=\{-5, -4, 1, 2\}\); \(Q(x)\): \(x\) is greater than \(3\). Then: \(Q(x)\) is false at \(-5, -4, 1, 2\). \(Q(x)\) is false under interpretation \(I\).

  • Given interpretation \(I\): Domain \(D_x=\{1, 2, 3\}\), \(D_y=\{1, 4, 5\}\); \(Q(x, y)\): \(x<y\). Then: \(Q(x, y)\) is false at \(\{1,1\}\), \(\{2,1\}\), \(\{3,1\}\), and true elsewhere.

If a predicate formula \(A\) is true under every interpretation \(I\), then \(A\) is called a tautology.

If a predicate formula \(A\) is false under every interpretation \(I\), then \(A\) is called a contradiction; otherwise \(A\) is called a satisfiable formula.

 

\(P(x){\vee}{\lnot}P(x)\) is a tautology, \(Q(x){\wedge}{\lnot}Q(x)\) is a contradiction, and \(P(x){\vee}{\exists}xQ(x)\) is a satisfiable formula.

Is the predicate formula \[({\forall}xF(x){\rightarrow}G(x)){\rightarrow}({\forall}xF(x){\rightarrow}{\forall}xG(x))\] a tautology?

 

Solution: Let the domain \(D=\{2, 4, 6, 8\}\); \(F(x)\): \(x\) is divisible by 2; \(G(x)\): \(x\) is divisible by 4.

Then \({\forall}xF(x)\) has truth value \(T\), \({\forall}xG(x)\) has truth value \(F\), so \({\forall}xF(x){\rightarrow}{\forall}xG(x)\) has truth value \(F\).

\(G(4)\) has truth value \(T\), so \({\forall}xF(x){\rightarrow}G(4)\) has truth value \(T\).

Hence \(({\forall}xF(x){\rightarrow}G(4)){\rightarrow}({\forall}xF(x){\rightarrow}{\forall}xG(x))\) has truth value \(F\).

Therefore, \(({\forall}xF(x){\rightarrow}G(x)){\rightarrow}({\forall}xF(x){\rightarrow}{\forall}xG(x))\) is not a tautology.

Is the predicate formula \({\forall}xA(x){\rightarrow}A(y)\) a tautology?

For any given domain \(D\), suppose \({\forall}xA(x)\) is true under that interpretation; then for any \(d{\in}D\), \(A(d)\) is true, and therefore \(A(y)\) is true.

Hence \({\forall}xA(x){\rightarrow}A(y)\) is a tautology.

 

Is the predicate formula \({\forall}x(P(x){\rightarrow}Q(x))\) a satisfiable formula?

Define interpretation \(I\): the domain \(D\) is the set of integers; \(P(x)\): \(x\) is an integer; \(Q(x)\): \(x\) is a rational number.

Under interpretation \(I\), \({\forall}x(P(x){\rightarrow}Q(x))\) is true, so \({\forall}x(P(x){\rightarrow}Q(x))\) is a satisfiable formula.

Equivalences and Tautological Implications

Let \(A\) and \(B\) be predicate formulas. If \(A{\leftrightarrow}B\) is a tautology, then \(A\) and \(B\) are said to be logically equivalent, written \(A{\Leftrightarrow}B\).

\(A{\Leftrightarrow}B\) means that under any interpretation and valuation, \(A\) and \(B\) have the same truth value.

  • \({\forall}x{\lnot}{\lnot}P(x){\Leftrightarrow}{\forall}xP(x).\)

Let \(A\) and \(B\) be predicate formulas. If \(A{\rightarrow}B\) is a tautology, then \(A\) is said to tautologically imply \(B\), written \(A{\Rightarrow}B.\)

\(A{\Rightarrow}B\) means that under any interpretation, every valuation that makes \(A\) true also makes \(B\) true.

  • \({\exists}xP(x){\Rightarrow}{\exists}x{\lnot}{\lnot}P(x).\)
  1. Extension of Tautologies from Propositional Calculus

Since propositional constants and propositional variables are permitted in predicate calculus, predicate formulas may still contain propositional formulas; any tautological propositional formula remains a tautology in predicate calculus.

In a tautology of propositional calculus, replacing each occurrence of a propositional variable with the same predicate formula does not affect its validity, and the result is a tautology in predicate calculus.

Equivalence from propositional calculus: \[{\lnot}(A{\vee}B){\Leftrightarrow}({\lnot}A{\wedge}{\lnot}B)\] Replacing \(A\) with \({\forall}xP(x)\) and \(B\) with \({\exists}xQ(x)\) yields the predicate calculus equivalence: \[{\lnot}({\forall}xP(x){\vee}{\exists}xQ(x)){\Leftrightarrow}({\lnot}{\forall}xP(x){\wedge}{\lnot}{\exists}xQ(x))\]

In this sense, both equivalences and tautological implications from propositional calculus hold in predicate calculus.

 

\[{\forall}xP(x, y){\vee}{\exists}xQ(x){\Leftrightarrow}{\exists}xQ(x){\vee}{\forall}xP(x, y)\] \[{\forall}x(P(x){\rightarrow}Q(x)){\Leftrightarrow}{\forall}x({\lnot}P(x){\vee}Q(x))\] \[{\forall}xP(x){\wedge}({\forall}xP(x){\rightarrow}{\exists}xQ(x)){\Rightarrow}{\exists}xQ(x)\]

  1. Conversion Laws for Quantifiers

\[{\lnot}{\forall}x{\lnot}A(x){\Leftrightarrow}{\exists}xA(x)\] \[{\lnot}{\exists}x{\lnot}A(x){\Leftrightarrow}{\forall}xA(x)\] \[{\lnot}{\forall}xA(x){\Leftrightarrow}{\exists}x{\lnot}A(x)\] \[{\lnot}{\exists}xA(x){\Leftrightarrow}{\forall}x{\lnot}A(x)\]

  1. Expansion and Contraction Laws for Quantifier Scope

Let \(B\) be a predicate formula not containing the individual variable \(x\), then:

\[{\forall}x(A(x){\vee}B){\Leftrightarrow}{\forall}xA(x){\vee}B\] \[{\forall}x(A(x){\wedge}B){\Leftrightarrow}{\forall}xA(x){\wedge}B\] \[{\exists}x(A(x){\vee}B){\Leftrightarrow}{\exists}xA(x){\vee}B\] \[{\exists}x(A(x){\wedge}B){\Leftrightarrow}{\exists}xA(x){\wedge}B\]

  1. Distributive Laws for Quantifiers

\[{\forall}x(A(x){\wedge}B(x)){\Leftrightarrow}{\forall}xA(x){\wedge}{\forall}xB(x)\] \[{\exists}x(A(x){\vee}B(x)){\Leftrightarrow}{\exists}xA(x){\vee}{\exists}xB(x)\]

  1. Elimination of Quantifiers

Under a given interpretation \(I\), if the domain is a finite set \(D=\{a_{1}, a_{2}, {\cdots}, a_{n}\}\), by the definition of quantifiers: \[{\forall}xA(x){\Leftrightarrow}A(a_{1}){\wedge}A(a_{2}){\wedge}{\cdots}{\wedge}A(a_{n})\] \[{\exists}xA(x){\Leftrightarrow}A(a_{1}){\vee}A(a_{2}){\vee}{\cdots}{\vee}A(a_{n})\] where \(A(a_{i})(i=1, 2, {\cdots}, n)\) is the formula obtained by substituting \(a_{i}\) for all free occurrences of \(x\) in \(A(x)\).

  1. Tautological Implications Involving Quantifiers

\[{\forall}xA(x){\vee}{\forall}xB(x){\Rightarrow}{\forall}x(A(x){\vee}B(x))\] \[{\exists}x(A(x){\wedge}B(x)){\Rightarrow}{\exists}xA(x){\wedge}{\exists}xB(x)\] \[{\forall}x(A(x){\rightarrow}B(x)){\Rightarrow}{\forall}xA(x){\rightarrow}{\forall}xB(x)\] \[{\exists}xA(x){\rightarrow}{\forall}xB(x){\Rightarrow}{\forall}x(A(x){\rightarrow}B(x))\] The converses of these tautological implications do not hold.

  1. Use of Multiple Quantifiers

\[{\forall}x{\forall}yA(x, y){\Leftrightarrow}{\forall}y{\forall}xA(x, y), \, \, {\exists}x{\exists}yA(x, y){\Leftrightarrow}{\exists}y{\exists}xA(x, y)\] \[{\forall}x{\forall}yA(x, y){\Rightarrow}{\exists}y{\forall}xA(x, y), \, \, {\forall}y{\forall}xA(x, y){\Rightarrow}{\exists}x{\forall}yA(x, y)\] \[{\exists}y{\forall}xA(x, y){\Rightarrow}{\forall}x{\exists}yA(x, y), \, \, {\exists}x{\forall}yA(x, y){\Rightarrow}{\forall}y{\exists}xA(x, y)\] \[{\forall}x{\exists}yA(x, y){\Rightarrow}{\exists}y{\exists}xA(x, y), \, \, {\forall}y{\exists}xA(x, y){\Rightarrow}{\exists}x{\exists}yA(x, y)\]

The order of quantifiers matters; their meanings differ and cannot be interchanged arbitrarily.

 

Example: \(G(x, y):x+y>2\), where the domain of discourse is the set of real numbers.

Proposition \({\forall}x{\exists}yG(x, y)\): For any real number \(x\), there exists a real number \(y\) such that \(x+y>2\).

Proposition \({\exists}y{\forall}xG(x, y)\): There exists a real number \(y\) such that for any real number \(x\), \(x+y>2\).

\(A(x, y)\): \(x\) and \(y\) share the same surname; the domain of \(x\) is the set of people in Village A, and the domain of \(y\) is the set of people in Village B.

\({\forall}x{\forall}yA(x, y)\): All people in Village A and Village B share the same surname.

\({\forall}y{\forall}xA(x, y)\): All people in Village B and Village A share the same surname.

Thus:\[{\forall}x{\forall}yA(x, y){\Leftrightarrow}{\forall}y{\forall}xA(x, y)\]

\({\exists}x{\exists}yA(x, y)\): There are people in Village A and Village B who share the same surname.

\({\exists}y{\exists}xA(x, y)\): There are people in Village B and Village A who share the same surname.

Thus:\[{\exists}x{\exists}yA(x, y){\Leftrightarrow}{\exists}y{\exists}xA(x, y)\]

\({\forall}x{\exists}yA(x, y)\): For every person in Village A, there is someone in Village B who shares the same surname.

\({\exists}y{\forall}xA(x, y)\): There is a person in Village B such that all people in Village A share the same surname with them.

\({\forall}y{\exists}xA(x, y)\): For every person in Village B, there is someone in Village A who shares the same surname.

\({\exists}x{\forall}yA(x, y)\): There is a person in Village A such that all people in Village B share the same surname with them.

Theorem (Substitution Rule): Let \(A\) be a formula containing subformula \(A_{1}\). If formula \(B_{1}\) replaces \(A_{1}\) in formula \(A\) to obtain formula \(B\), and \(A_{1}{\Leftrightarrow}B_{1}\), then \(A{\Leftrightarrow}B\).

Since \(A_{1}\) and \(B_{1}\) are logically equivalent, replacing \(A_{1}\) with \(B_{1}\) does not change the truth value of \(A\); therefore \(A\) and \(B\) are equivalent.

Theorem (Renaming Rule): Let \(x\) be a bound variable within the scope of a quantifier, and let \(y\) be an individual variable that does not appear within that scope. Then: \[{\forall}xA(x){\Leftrightarrow}{\forall}yA(y)\] \[{\exists}xA(x){\Leftrightarrow}{\exists}yA(y)\] Theorem (Substitution of Free Variables Rule): Let \(A\) be a predicate formula. Replace all occurrences of some free variable in \(A\) with an individual variable not appearing in \(A\), leaving the rest of \(A\) unchanged, to obtain predicate formula \(B\). Then \(A{\Leftrightarrow}B\).

If the domain \(D=\{a, b\}\), find the truth value of \({\forall}x{\exists}y(A(x){\rightarrow}B(y))\).

Given: \[ \begin{array}{cccc} A(a)&A(b)&B(a)&B(b)\\ T&F&T&T\\ \end{array} \]  

\({\forall}x{\exists} y(A(x){\rightarrow}B(y))\)

\[{\Leftrightarrow}{\forall}x((A(x){\rightarrow}B(a)){\vee}(A(x){\rightarrow}B(b)))\] \[{\Leftrightarrow}((A(a){\rightarrow}B(a)){\vee}(A(a){\rightarrow}B(b))){\wedge}((A(b){\rightarrow}B(a)){\vee}(A(b){\rightarrow}B(b)))\] \[{\Leftrightarrow}((T{\rightarrow}T){\vee}(T{\rightarrow}T)){\wedge}((F{\rightarrow}T){\vee}(F{\rightarrow}T))\] \[{\Leftrightarrow}T\] When the domain contains many or infinitely many elements, this method becomes impractical.

Prove: \[{\forall}x(A(x){\rightarrow}B){\Leftrightarrow}{\exists}xA(x){\rightarrow}B.\]

Proof: \[{\forall}x(A(x){\rightarrow}B)\] \[{\Leftrightarrow}{\forall}x({\lnot}A(x){\vee}B)\] \[{\Leftrightarrow}{\forall}x{\lnot}A(x){\vee}B\] \[{\Leftrightarrow}{\lnot}{\exists}xA(x){\vee}B\] \[{\Leftrightarrow}{\exists}xA(x){\rightarrow}B\]

Prove: For any \(A(x)\) and \(B(x)\), \[{\exists}x(A(x){\rightarrow}B(x)){\Leftrightarrow}{\forall}xA(x){\rightarrow}{\exists}xB(x).\] Proof:\[{\exists}x(A(x){\rightarrow}B(x))\] \[{\Leftrightarrow}{\exists}x({\lnot}A(x){\vee}B(x))\] \[{\Leftrightarrow}{\exists}x{\lnot}A(x){\vee}{\exists}xB(x)\] \[{\Leftrightarrow}{\lnot}{\forall}xA(x){\vee}{\exists}xB(x)\] \[{\Leftrightarrow}{\forall}xA(x){\rightarrow}{\exists}xB(x)\]

Prove: \[{\forall}xP(x){\wedge}{\exists}xQ(x){\Leftrightarrow}{\forall}x{\exists}y(P(x){\wedge}Q(y)).\] Proof:\[{\forall}xP(x){\wedge}{\exists}xQ(x)\] \[{\Leftrightarrow}{\forall}xP(x){\wedge}{\exists}yQ(y)\] \[{\Leftrightarrow}{\forall}x(P(x){\wedge}{\exists}yQ(y))\] \[{\Leftrightarrow}{\forall}x{\exists}y(P(x){\wedge}Q(y))\]

Prove: For any \(A(x)\) and \(B(x)\), \[{\exists}xA(x){\rightarrow}{\forall}xB(x){\Rightarrow}{\forall}x(A(x){\rightarrow}B(x))\] Proof:\[{\exists}xA(x){\rightarrow}{\forall}xB(x)\] \[{\Leftrightarrow}{\lnot}{\exists}xA(x){\vee}{\forall}xB(x)\] \[{\Leftrightarrow}{\forall}x{\lnot}A(x){\vee}{\forall}xB(x)\] \[{\Rightarrow}{\forall}x({\lnot}A(x){\vee}B(x))\] \[{\Leftrightarrow}{\forall}x(A(x){\rightarrow}B(x))\] Therefore\[{\exists}xA(x){\rightarrow}{\forall}xB(x){\Rightarrow}{\forall}x(A(x){\rightarrow}B(x))\]

Prenex Normal Form

A predicate formula is called a prenex normal form if all quantifiers appear at the front of the formula and their scopes extend to the end of the entire predicate formula.

A prenex normal form has the following structure: \[Q_{1}x_{1}Q_{2}x_{2}{\cdots}Q_kx_kB\] where each \(Q_{i}{\in}\{{\forall}, {\exists}\}\) \((1{\le}i{\le}k)\), and \(B\) is a predicate formula containing no quantifiers.

If a predicate formula \(A\) contains no quantifiers, \(A\) is also regarded as a prenex normal form. E.g.: \({\lnot}A(x){\vee}B(x)\).

Example: \[{\forall}x{\exists}y{\exists}z({\lnot}P(x){\rightarrow}(Q(y){\rightarrow}R(z, y)))\] \[{\forall}x{\forall}y(S(x, w){\vee}T(y))\] \[U(x, y)\] are prenex normal forms.

whereas \[{\forall}xF(x, y){\rightarrow}{\exists}yG(y)\] \[{\forall}x{\exists}zC(x, z){\wedge}V(z)\] are not prenex normal forms.

Theorem (Prenex Normal Form Existence Theorem): Every predicate formula has a logically equivalent prenex normal form.

The steps to convert a predicate formula into prenex normal form are:

  1. Push negation connectives inward so that they directly precede atomic predicate formulas.

  2. Apply the renaming and substitution rules so that all bound variable symbols are distinct and no bound variable shares a symbol with any free variable.

  3. Use logical equivalences to move quantifiers one by one to the front of the predicate formula.

Transform the predicate formula \({\forall}xP(x){\rightarrow}{\exists}xQ(x)\) into prenex normal form.

(Method 1) \[{\forall}xP(x){\rightarrow}{\exists}xQ(x)\] \[{\Leftrightarrow}{\lnot}{\forall}xP(x){\vee}{\exists}xQ(x)\] \[{\Leftrightarrow}{\exists}x{\lnot}P(x){\vee}{\exists}xQ(x)\] \[{\Leftrightarrow}{\exists}x({\lnot}P(x){\vee}Q(x))\]

(Method 2) \[{\forall}xP(x){\rightarrow}{\exists}xQ(x)\] \[{\Leftrightarrow}{\forall}xP(x){\rightarrow}{\exists}yQ(y)\] \[{\Leftrightarrow}\lnot{\forall}xP(x){\vee}{\exists}yQ(y)\] \[{\Leftrightarrow}{\exists}x({\lnot}P(x)){\vee}{\exists}yQ(y)\] \[{\Leftrightarrow}{\exists}x({\lnot}P(x){\vee}{\exists}yQ(y))\] \[{\Leftrightarrow}{\exists}x{\exists}y({\lnot}P(x){\vee}Q(y))\] \[{\Leftrightarrow}{\exists}x{\exists}y(P(x){\rightarrow}Q(y))\]

Thus, the prenex normal form of a predicate formula is not unique.

Transform the predicate formula \({\lnot}({\forall}xP(x, y){\wedge}{\forall}xQ(x, z)){\rightarrow}{\exists}yR(y, x)\) into prenex normal form.

Solution:\[{\lnot}({\forall}xP(x, y){\wedge}{\forall}xQ(x, z)){\rightarrow}{\exists}yR(y, x)\] \[{\Leftrightarrow}({\lnot}{\forall}xP(x, y){\vee}{\lnot}{\forall}xQ(x, z)){\rightarrow}{\exists}yR(y, x)\] \[{\Leftrightarrow}({\exists}x{\lnot}P(x, y){\vee}{\exists}x{\lnot}Q(x, z)){\rightarrow}{\exists}yR(y, x)\] \[{\Leftrightarrow}{\exists}x({\lnot}P(x, y){\vee}{\lnot}Q(x, z)){\rightarrow}{\exists}yR(y, x)\] \[{\Leftrightarrow}{\exists}u({\lnot}P(u, y){\vee}{\lnot}Q(u, z)){\rightarrow}{\exists}vR(v, x)\] \[{\Leftrightarrow}{\exists}u(\lnot({\lnot}P(u, y){\vee}{\lnot}Q(u, z)){\lor}{\exists}vR(v, x))\] \[{\Leftrightarrow}{\exists}u{\exists}v(\lnot({\lnot}P(u, y){\vee}{\lnot}Q(u, z)){\lor}R(v, x))\] \[{\Leftrightarrow}{\exists}u{\exists}v(({\lnot}P(u, y){\vee}{\lnot}Q(u, z)){\rightarrow}R(v, x))\]

A prenex normal form is called a prenex disjunctive normal form if its quantifier-free part is a disjunctive normal form, and a prenex conjunctive normal form if its quantifier-free part is a conjunctive normal form.

  • \({\forall}x{\exists}y(P(x, y){\wedge}Q(x))\) is a prenex conjunctive normal form.

  • \({\forall}x{\exists}y{\exists}z((R(x, y, z){\wedge}S(x)){\vee}Q(x))\) is a prenex disjunctive normal form.

Theorem: Every predicate formula can be transformed into a logically equivalent prenex disjunctive normal form or prenex conjunctive normal form.

The steps to convert into prenex disjunctive or conjunctive normal form are:

  1. Convert all connectives in the predicate formula to \({\lnot}\), \({\wedge}\), and \({\vee}\).

  2. Transform the formula into prenex normal form.

  3. Use distributive laws to further transform the formula into prenex disjunctive or conjunctive normal form.

Find the prenex disjunctive normal form and prenex conjunctive normal form of \({\exists}xA(x){\rightarrow}{\exists}yB(y)\).

Solution:\[{\exists}xA(x){\rightarrow}{\exists}yB(y)\] \[{\Leftrightarrow}{\lnot}{\exists}xA(x){\vee}{\exists}yB(y)\] \[{\Leftrightarrow}{\forall}x{\lnot}A(x){\vee}{\exists}yB(y)\] \[{\Leftrightarrow}{\forall}x({\lnot}A(x){\vee}{\exists}yB(y))\] \[{\Leftrightarrow}{\forall}x{\exists}y({\lnot}A(x){\vee}B(y))\]

Find the prenex disjunctive normal form and prenex conjunctive normal form of \({\forall}x(F(x){\vee}H(y)){\rightarrow}{\forall}yG(x, y)\).

Solution: \[{\forall}x(F(x){\vee}H(y)){\rightarrow}{\forall}yG(x, y)\] \[{\Leftrightarrow}{\lnot}{\forall}x(F(x){\vee}H(y)){\vee}{\forall}yG(x, y)\] \[{\Leftrightarrow}{\exists}x{\lnot}(F(x){\vee}H(y)){\vee}{\forall}yG(x, y)\] \[{\Leftrightarrow}{\exists}v{\lnot}(F(v){\vee}H(y)){\vee}{\forall}wG(x, w)\] \[{\Leftrightarrow}{\exists}v({\lnot}(F(v){\vee}H(y)){\vee}{\forall}wG(x, w))\] \[{\Leftrightarrow}{\exists}v{\forall}w({\lnot}(F(v){\vee}H(y)){\vee}G(x, w))\] \[{\Leftrightarrow}{\exists}v{\forall}w(({\lnot}F(v){\wedge}{\lnot}H(y)){\vee}G(x, w))\]

Prenex disjunctive normal form: \({\exists}v{\forall}w(({\lnot}F(v){\wedge}{\lnot}H(y)){\vee}G(x, w))\)

Prenex conjunctive normal form: \({\exists}v{\forall}w({\lnot}F(v){\vee}G(x, w)){\wedge}({\lnot}H(y){\vee}G(x, w))\)

Find the prenex disjunctive normal form of \({\forall}x{\exists}y(P(x, y){\wedge}Q(x)){\wedge}{\forall}x({\exists}zR(z, x){\rightarrow}S(w))\).

Solution:\[{\forall}x{\exists}y(P(x, y){\wedge}Q(x)){\wedge}{\forall}x({\exists}zR(z, x){\rightarrow}S(w))\] \[{\Leftrightarrow}{\forall}x{\exists}y(P(x, y){\wedge}Q(x)){\wedge}{\forall}x({\lnot}{\exists}zR(z, x){\vee}S(w))\] \[{\Leftrightarrow}{\forall}x{\exists}y(P(x, y){\wedge}Q(x)){\wedge}{\forall}x({\forall}z{\lnot}R(z, x){\vee}S(w))\] \[{\Leftrightarrow}{\forall}x({\exists}y(P(x, y){\wedge}Q(x)){\wedge}{\forall}z({\lnot}R(z, x){\vee}S(w)))\]

\[{\Leftrightarrow}{\forall}x{\exists}y((P(x, y){\wedge}Q(x)){\wedge}{\forall}z({\lnot}R(z, x){\vee}S(w)))\] \[{\Leftrightarrow}{\forall}x{\exists}y{\forall}z((P(x, y){\wedge}Q(x)){\wedge}({\lnot}R(z, x){\vee}S(w)))\] \[{\Leftrightarrow}{\forall}x{\exists}y{\forall}z((P(x, y){\wedge}Q(x){\wedge}{\lnot}R(z, x)){\vee}(P(x, y){\wedge}Q(x){\wedge}S(w)))\]

Example: Find the prenex conjunctive normal form of \({\forall}x({\exists}y(A(x, y){\wedge}B(x)){\rightarrow}{\exists}zC(y, z))\).

Solution:\({\forall}x({\exists}y(A(x, y){\wedge}B(x)){\rightarrow}{\exists}zC(y, z))\) \[{\Leftrightarrow}{\forall}x({\lnot}{\exists}y(A(x, y){\wedge}B(x)){\vee}{\exists}zC(y, z))\] \[{\Leftrightarrow}{\forall}x({\forall}y({\lnot}A(x, y){\vee}{\lnot}B(x)){\vee}{\exists}zC(y, z))\] \[{\Leftrightarrow}{\forall}x({\forall}\boxed{w}({\lnot}A(x, \boxed{w}){\vee}{\lnot}B(x)){\vee}{\exists}zC(y, z))\] \[{\Leftrightarrow}{\forall}x{\forall}w{\exists}z({\lnot}A(x, w){\vee}{\lnot}B(x){\vee}C(y, z))\]

Predicate Logic Reasoning

Rules of Inference

For a predicate formula \(A(x)\), if there is no free occurrence of \(x\) within the scope of a quantifier \({\forall}y\) or \({\exists}y\), then \(A(x)\) is said to be free for the variable \(y\).

By definition, if \(y\) is not a bound variable in \(A(x)\), then \(A(x)\) is certainly free for \(y\).

  1. \(A(x)={\forall}yP(y){\vee}Q(x, y)\)

  2. \(A(x)={\forall}yP(y){\rightarrow}(Q(x){\wedge}Q(y))\)

  3. \(A(x)={\forall}yP(\boxed{x}, y){\rightarrow}Q(x, y)\)

  4. \(A(x)={\forall}y(P(y){\vee}Q(\boxed{x}, y))\)

  5. \(A(x)={\forall}y(P(y){\vee}{\forall}xQ(x, y))\)

(1), (2) and (5) are free for \(y\); (3) and (4) are not free for \(y\).

Universal Instantiation Rule

Also known as the universal specification rule, abbreviated as US (Universal Specification).

\[ \frac{\forall xA(x)}{\therefore A(y)}\, \, or\, \, \frac{\forall xA(x)}{\therefore A(c)} \]

where \(c\) is any individual constant in the domain.

Here it is required that \(A(x)\) is free for \(y\).

\(y\) or \(c\) replaces all free occurrences of \(x\) in \(A(x)\).

When using these two rules, attention must be paid to the conditions under which they hold; otherwise, errors in inference may result.

Let the domain of individuals be the set of real numbers, \(L(x, y)\) denotes \(x<y\), then \({\exists}x{\exists}yL(x, y)\) is interpreted as “for any real number \(x\), there exists a real number \(y\) such that \(x<y\)”, which is a true proposition.

If the following inference is made:

  1. \({\forall}x{\exists}yL(x, y)\qquad\) Premise introduction

  2. \({\exists}yL(y, y)\qquad\) US rule (1)

The result states “there exists a real number \(y\) such that \(y<y\)”, which is clearly an incorrect inference.

The reason is that \({\exists}yL(x, y)\) is not free for \(y\).

Universal Generalization Rule (UG)

Also known as the universal quantifier introduction rule, abbreviated as UG (Universal Generalization) rule. \[ \frac{A(x)}{\therefore {\forall}yA(y)} \]

Pay attention to the conditions of this rule to avoid errors in inference.

Pay attention to the conditions of this rule to avoid errors in inference.

Let the domain of individuals be the set of real numbers, \(L(x, y)\) denotes \(x<y\). The following inference is made:

  1. \({\forall}x{\exists}yL(x, y)\qquad\) Premise introduction

  2. \({\exists}yL(z, y)\qquad\qquad\) US rule

The conclusion “for any real number \(y\), there exists a real number \(y\) such that \(y<y\)” is clearly incorrect.

The reason is that the bound occurrence of \(y\) in \({\exists}yL(z, y)\) was used to replace \(z\).

The reason is that the bound occurrence of \(y\) in \({\exists}yL(z, y)\) was used to replace \(z\).

Existential Specification Rule (ES)

Also known as the existential quantifier elimination rule, abbreviated as ES (Existential Specification) rule.

\[ \frac{\exists xA(x)}{\therefore A(y)}\, \, or\, \, \frac{\exists xA(x)}{\therefore A(c)} \]

where \(c\) is a specific individual constant, and an individual constant \(c\) or individual variable \(y\) that has not previously appeared in \(A(x)\) is used to replace \(x\).

When \(A(x)\) contains other free variables, this rule should not be applied; otherwise, incorrect inferences may result.

Let the domain of individuals be the set of real numbers, \(L(x, y)\) denotes \(x<y\). If the following derivation is made:

  1. \({\forall}x{\exists}yL(x, y)\qquad\) Premise introduction

  2. \({\exists}yL(z, y)\qquad\,\,\,\) US rule (1)

Existential Generalization Rule (EG)

Also known as the existential quantifier introduction rule, abbreviated as EG (Existential Generalization) rule.

The reason is that \({\exists}yL(z, y)\) contains the free variable \(z\), so the ES rule should not be applied.

Existential Generalization Rule (EG)

Also known as the existential quantifier introduction rule, abbreviated as EG (Existential Generalization) rule.

\[ \frac{A(c)}{\therefore {\exists}yA(y)}\, \, or\, \, \frac{A(x)}{\therefore {\exists}yA(y)} \]

where \(c\) is a specific individual constant, \(A(x)\) is free for \(y\), the individual variable \(y\) replacing \(c\) has not previously appeared in \(A(x)\), and \(y\) must not be an individual variable already in \(A(x)\).

When applying this rule, these conditions must be observed; otherwise, errors in inference may occur.

Let the domain of individuals be the set of real numbers, \(L(x, y)\) denotes \(x<y\). If the following inference is made:

  1. \({\exists}xL(x, 0)\qquad\qquad\) Premise introduction

Let the domain of \(x, y\) be the set of real numbers, \(F(x)\) denotes “\(x\) is a positive number”, \(G(x)\) denotes “\(x\) is a negative number”. The following inference is made:

  1. \({\exists}xF(x)\qquad\) Premise introduction

  2. \(F(c)\qquad\qquad\) ES rule (1)

  3. \({\exists}yG(y)\qquad\) Premise introduction

  4. \(G(c)\qquad\qquad\) ES rule (3)

  1. \({\exists}x(F(x){\wedge}G(x))\qquad\) EG rule (5)

The conclusion “there exists a real number \(x\) that is both positive and negative” is clearly incorrect.

The reason is that after introducing the individual constant \(c\) in step (2), the same individual constant is introduced again at step (4) when applying the ES rule, resulting in an incorrect conclusion.

  1. \({\exists}yG(y)\qquad\) Premise introduction

  2. \(G(c)\qquad\qquad\) ES rule (3)

  3. \(F(c){\wedge}G(c)\qquad\) T rule (2)(4)

Let the domain of individuals be the set of positive real numbers, \(F(x): x>0\),

\(G(x): x>2\). The following inference is made:

  1. \({\forall}xF(x)\qquad\) Premise introduction

Let the domain of individuals be the set of positive real numbers, \(F(x): x>0\),

\(G(x): x>2\). The following inference is made:

Is this inference correct?

  1. \({\exists}yG(y)\qquad\) Premise introduction

  2. \(F(c)\qquad\) US rule (1)

  3. \(G(c)\qquad\) ES rule (2)

  4. \(F(c){\wedge}G(c)\qquad\) T rule (2)

Is this inference correct?

  1. \(F(c){\wedge}G(c)\qquad\) T rule (2)

  2. \({\forall}xF(x)\qquad\) Premise introduction

  3. \({\exists}yG(y)\qquad\) Premise introduction

  4. \(G(c)\qquad\) ES rule (1)

  5. \(F(c)\qquad\) US rule (2)

  6. \(F(c){\wedge}G(c)\qquad\) T rule (2)

This is correct.

Note: When eliminating quantifiers, apply \(\exists\) before \(\forall\).

Inference Applications

The inference methods of predicate logic are similar to those of propositional logic. Reasoning is carried out using known basic equivalences, basic implications, the \(P\) rule, \(T\) rule, \(CP\) rule, and the quantifier introduction and elimination rules.

Inference methods are also divided into direct proof and indirect proof.

Proof of the inference: \[{\forall}x(A(x){\vee}B(x)), {\exists}x(A(x){\rightarrow}C(x)){\vDash}{\exists}x(B(x){\vee}C(x))\]

Proof:

  1. \({\exists}x(A(x){\rightarrow}C(x))\qquad\) P

  2. \(A(c){\rightarrow}C(c)\qquad\) ES(1)

  3. \({\forall}x(A(x){\vee}B(x))\qquad\) P

  4. \(A(c){\vee}B(c)\qquad\) US(3)

  5. \({\lnot}B(c){\rightarrow}A(c)\qquad\) T(4)

  6. \({\lnot}B(c){\rightarrow}C(c)\qquad\) T(2)(5)

  7. \(B(c){\vee}C(c)\qquad\) T(6)

  8. \({\exists}x(B(x){\vee}C(x))\qquad\) EG(7)

Premises: \({\forall}x(F(x){\rightarrow}G(x))\); \(F(c)\),

Conclusion: \(G(c)\) All giant pandas come from Sichuan Province, China. Huanhuan is a giant panda, so Huanhuan comes from Sichuan Province, China.

Let \(F(x)\): \(x\) is a giant panda; \(G(x)\): \(x\) comes from Sichuan Province, China;

\(c\): Huanhuan.

  1. \({\forall}x(F(x){\rightarrow}G(x))\qquad\) P

  2. \(F(c){\rightarrow}G(c)\qquad\) US(1)

  3. \(F(c)\qquad\qquad\) P

  4. \(G(c))\qquad\) T(2)(3)

Proof of the inference: \[{\forall}x(P(x){\vee}Q(x)), {\lnot}{\forall}xP(x){\vDash}{\exists}xQ(x).\]

Take \({\lnot}{\exists}xQ(x)\) as an additional premise. The proof is as follows:

  1. \({\lnot}{\forall}xP(x)\qquad\) P

  2. \({\exists}x{\lnot}P(x)\qquad\) T(1)

  3. \({\lnot}P(a)\qquad\, \, \, \, \, \,\) ES(2)

  4. \({\lnot}{\exists}xQ(x)\qquad\) P (additional premise)

  5. \({\forall}x{\lnot}Q(x)\qquad\) T(4)

  6. \({\lnot}Q(a)\, \, \, \, \, \qquad\) US(5)

  1. \({\lnot}P(a){\wedge}{\lnot}Q(a)\qquad\) T(3)(6)

  2. \({\lnot}(P(a){\vee}Q(a))\qquad\) T(7)

  3. \({\forall}x(P(x){\vee}Q(x))\qquad\) P

  4. \(P(a){\vee}Q(a)\qquad\, \, \, \, \, \, \, \, \,\) US(9)

  5. \((P(a){\vee}Q(a)){\wedge}{\lnot}(P(a){\vee}Q(a))\quad\) \(\qquad\qquad\qquad\qquad\qquad\) T(8)(10)

Proof of the Socratic syllogism: All men are mortal, Socrates is a man, therefore Socrates is mortal. \[{\forall}x(P(x){\vee}Q(x)), {\lnot}{\forall}xP(x){\vDash}{\exists}xQ(x).\]

Proof of the inference \[{\forall}x(H(x){\rightarrow}M(x)){\vDash} {\forall}x{\forall}y(H(y){\wedge}N(x, y)){\rightarrow}{\exists}y(M(y){\wedge}N(t, y))\]

Taking \({\forall}x{\forall}y(H(y){\wedge}N(x, y))\) as an additional premise, the proof sequence is as follows:

  1. \({\forall}x{\forall}y(H(y){\wedge}N(x, y))\) P (additional premise)

  2. \({\forall}y(H(y){\wedge}N(t, y))\qquad\) US(1)

  3. \(H(b){\wedge}N(t, b)\qquad\qquad\) US(2)

  1. \({\forall}x(H(x){\rightarrow}M(x))\, \,\) P

  2. \(H(b){\rightarrow}M(b)\qquad\) US(4)

  3. \(H(b)\qquad\qquad\qquad\) T(3)

  4. \(M(b)\qquad\qquad\qquad\) T(5)(6)

  5. \(N(t, b)\qquad\qquad\qquad\) T(3)

  6. \(M(b){\wedge}N(t, b)\qquad\) T(7)(8)

  7. \({\exists}y(M(y){\wedge}N(t, y)\) EG(9)

  8. \({\forall}x{\forall}y(H(y){\wedge}N(x, y)){\rightarrow}{\exists}y(M(y){\wedge}N(t, y))\qquad\qquad\) CP(1)(10)

Proof of the Socratic syllogism: All men are mortal, Socrates is a man, therefore Socrates is mortal.

Proof: Let \(F(x)\): \(x\) is a man, \(G(x)\): \(x\) is mortal, \(c\): Socrates.

Premises: \({\forall}x(F(x){\rightarrow}G(x)), F(c)\)

Conclusion: \(G(c)\)

The proof sequence is as follows:

  1. \({\forall}x(F(x){\rightarrow}G(x))\qquad\) P

  2. \(F(c){\rightarrow}G(c)\qquad\quad\quad\) US(1)

  3. \(F(c)\qquad\qquad\qquad\quad\, \, \,\) P

  4. \(G(c)\qquad\qquad\qquad\quad\, \, \,\) T(2)(3)