2695 words - 11 pages

Predicate Logic

Example:

All men are mortal.

Socrates is a man.

··· Socrates is mortal.

Note: We need logic laws that work for statements involving quantities like “some” and “all”.

In English, the predicate is the part of the sentence that tells you

something about the subject.

1

More on predicates

Example: Nate is a student at UT.

What is the subject? What is the predicate?

Example: We can form two diﬀerent predicates.

Let P(x) be “x is a student at UT”.

Let Q(x, y) be “x is a student at y”.

Deﬁnition: A predicate is a property that a variable or a ﬁnite

collection of variables can have. A predicate becomes a proposition

when speciﬁc values are assigned to the variables. P(x1, x2, ..., ...view middle of the document...

Ways to read ∀xP (x):

For every x, P(x)

For every x, P(x) is true

For all x, P(x)

4

More on the universal quantiﬁer

Deﬁnition: A counterexample for ∀xP (x) is any t ∈ U , where

U is the universe, such that P(t) is false.

Some Examples

Example: P(x, y): x + y = 8

Assign x to be 1, and y to be 7. We get proposition P(1, 7) which is

true.

Proposition P(2, 5) is false since 2 + 5 = 8.

Example: ∀x[x ≥ 0]

U = N (non-negative integers)

We could re-write this proposition as: ∀x ∈ N, x ≥ 0

Is the proposition true?

What if the universe is R?

Example: ∀x∀y[x + y > x]

Is this proposition true if:

1. If U = N?

2. If U = R?

Example: ∀x∀y[x > y]

True if:

universe for x = the non-negative integers

universe for y = the non-positive integers

5

The Existential Quantiﬁer: ∃

Deﬁnition: The symbol ∃ is call the existential quantiﬁer and

represents the phrase “there exists” or “for some”. The existential

quantiﬁcation of P(x) is the statement “P(x) for some values x in

the universe”, or equivalently, “There exists a value for x such that

P(x) is true”, which is written ∃xP (x).

Note: If P(x) is true for at least one element in the domain, then

∃xP (x) is true. Otherwise it is false.

Note: Let P(x) be a predicate and c ∈ U (U = domain).

The following implications are true:

∀xP (x) → P (c)

P (c) → ∃xP (x)

Example: ∃x [x is prime] where U = Z

Is this proposition true or false?

Example: ∃x[x2 < 0] where U = R

True or false?

Exercises: True or false? Prove your answer.

1. ∃n[n2 = n] where U = Z.

2. ∃n[n2 = n] where U = {4, 5, 6, 7}.

6

Translating Quantiﬁed Statements

Translate the following into English.

1. ∀x[x2 ≥ 0] where U = R.

2. ∃t[(t > 3) ∧ (t3 > 27)] where U = R.

3. ∀x[(2|x) ∨ (2 |x)] where U = N

Translate the following into logic statements.

1. There is an integer whose square is twice itself.

2. No school buses are purple.

3. If a real number is even, then its square is even.

Note: Let U = {1, 2, 3}.

Proposition ∀xP (x) is equivalent to P (1) ∧ P (2) ∧ P (3).

Proposition ∃xP (x) is equivalent to P (1) ∨ P (2) ∨ P (3).

7

Bound and Free Variables

Deﬁnition: All variables in a predicate must be bound to turn a

predicate into a proposition. We bind a variable by assigning it a

value or quantifying it. Variables which are not bound are free.

Note: If we bind one variable in a predicate P (x, y, z) with 3

variables, say by setting z = 4, we get a predicate with 2 variables:

P (x, y, 4).

Example: Let U = N.

P (x, y, z) : x + y = z ← 3 free variables

Let Q(y, z) = P (2, y, z) : 2 + y = z ← 2 free variables

8

Examples with Quantiﬁers

Example: U = Z

N(x): x is a non-negative integer

E(x): x is even

O(x): x is odd

P(x): x is prime

Translate into logical notation.

1. There exists an even integer.

2. Every integer is even or odd.

3. All prime integers are non-negative.

4. The only even prime is 2.

5. Not all integers are odd.

6. Not all primes are odd.

7. If an integer is not odd, then it is even.

9

Examples with Nested Quantiﬁers

Note about nested...

Beat writer's block and start your paper with the best examples