Introduction

In the propositional logic, the most basic elements are atoms (= simple propositions). Through atoms we build up formulas. Then we use formulas to express various complex ideas. An atom is treated as a single unit. However, there are many ideas that cannot be treated in this simple way. For example, consider the following deduction of statements:

Every man is mortal.

Since Confucius is a man, he is mortal.

The above reasoning is intuitively correct. However, if we denote:

P: Every man is mortal

Q: Confucius is a man

R: Confucius is mortal

then PÙQ ®R is not a tautology (= R is not a logical consequence of P and Q within the framework of the propositional logic). This is because the structure of P, Q, and R are not used in the propositional logic.

In this lecture we shall discuss how the above argument and similar arguments are proven to be valid in the 1^st order logic. The 1^st order logic has two more logical notions (called predicates, and quantifiers) compared to the propositional logic. Much of everyday and mathematical language can be symbolized by the 1^st order logic.

An n-place predicate is a function

y = P(x₁, x₂, …, x_i, …, x_n),

where y Î {true, false}, and x₁, x₂, …, x_n Î D = {a₁, a₂ , …, a_m}. D is a set of objects related to the situation under study. D is called the domain (or the domain of discourse). Every argument x_i can be a variable, a constant from D or a function with arguments and values in D.

In general, every x_i may have its own domain D_i. To simplify our discussion we shall assume one common domain for all arguments.

Examples.

Let the predicate GREATER (x, y) mean "x is greater than y", and x, y Î D = {1, 2, 3}. Then

GREATER (1, 3)= false,

GREATER (3, 1)= true,

GREATER (2, y)= false or true (depending on the value of y),

GREATER (plus(x, 1), x) = true. (meaning: x+1 > x)

In the last example plus (x, y) is a function symbol x + y. So the value of the 1^st argument is specified indirectly, through the function value.

Similarly, we can represent "x loves y" by the predicate LOVE(x, y). Then "John loves Marry" can be represented by LOVE (John, Marry). "John's father loves John " can be symbolized as LOVE (father (John), John).

Here GREATER, LOVE are predicate symbols (uppercase letters P, Q, R,... or expressive strings of uppercase letters), x and y are variabls, 1, 2, 3, John, and Marry are individual symbols or constants, and plus and father are function symbols.

An n-place predicate P(x₁, x₂, …, x_n,) is an atom in the 1^st order logic.

Atoms are connected by logical connectives (Ø, Ù, Ú, «, ®) to build up formulas.

In the 1^st order logic, two special symbols ∀ (universalquantifier) and ∃ (existentialquantifier) are used to characterize variables.

(∀x) is read as “for all x”, “for each x” or “for every x ”.

(∃x) is read as “there exists an x”, “for some x”, or “for at least one x”.

Examples.

Symbolize the following statements:

(a) Every rational number is a real number

(b) There exists a number that is prime

(c) For every number x, there exists a number y such that x<y.

Let

- P(x) denote “x is a prime number”,

- Q(x) denote “x is a rational number”,

- R(x) denote “x is a real number”,

- LESS (x, y) denote “x is less than y”.

Then the above statements can be denoted by such formulas:

(a^')

(b^')

(c^')

The scope of a quantifier in a formula is the part of the formula to which the quantifier applies. If a formula contains no brackets then a quantifier is applied only to the nearest predicate symbol on the right.

For example, the scope of both the universal and existential quantifiers in the formula .

stands for .

We have to distinguish between bound variables and free variables.

Definition: An occurrence of a variable in a formula is bound if and only if the occurrence is within the scope of a quantifier employing the variable, or is the occurrence in that quantifier. An occurrence of a variable in a formula is free if and only if this occurrence of the variable is not found.

Definition: A variable is free in a formula if at least one occurrence of it is free in the formula. A variable is bound in a formula if at least one occurrence of it is found.

Example.

(∀x)(A(x) Ú B(x)) è x is bound in this formula.

Bound occurrences of variable x

(∀x)A(x) Ú B(x) è x is bound and free in this formula.

Bound occurrences of variable x Free occurrence

The truth value of a predicate does not depend on the bound variable. That is a bound variable is a dummy variable. The predicate depends on the values of free variables (if any), on the domain D and the meaning of the predicate.

Let EVEN(x) stand for “x is an even number”, and LESSEQUAL(x, y) denote “x £ y”.

Then (∀x) EVEN(x) º (∀y) EVEN(y) = true if x, y Î D = {2, 6, 10}.

(∀x) EVEN(x) º (∀y) EVEN(y) = false if x, y Î D = {2, 5, 7}.

(∃x) EVEN(x) º (∃y) EVEN(y) = true if x, y Î D = {3, 6, 8}.

(∃x) EVEN(x) º (∃y) EVEN(y) = false if x, y Î D = {3, 7, 9, 11}.

(∃x)(∃y) LESSEQUAL(x,y) º (∃v)(∃w) LESSEQUAL(v,w) = true if x, y, v, w Î D = {3, 7, 9, 11}.

(∀x)(∃y) LESSEQUAL(x,y) º (∀v)(∃w) LESSEQUAL(v,w) = true if x, y, v, w Î D = {2, 6, 10}.

Note: a formula containing free variables cannot be evaluated.

Example

Translate the statement “Every man is mortal. Confucius is a man. Therefore, Confucius is mortal” into a formula.

Denote “x is a man” by MAN(x), and “x is mortal” by MORTAL (x). Then “every man is mortal” can be represented by

)

“Confucius is a man” by

MAN (Confucius)

The whole statement can now be represented by