L5.pdf

CMPUT 272 (Stewart)

University of Alberta

Lecture 5

Reading: Epp 1.1, 1.2, 3.1, 3.2, 3.3 Predicate Logic Definition. A set is an unordered collection of distinct elements. Examples and Notation: S = {1, 2, 5, 10, 4}

set-roster notation

1 ∈ S, 5 ∈ S, 3 ∈ /S

element

{1, 5} ⊆ S, {1, 5, 3} 6⊆ S

subset

{} = ∅

empty set

R

real numbers

Z

integers

Z+

positive integers

Znonneg

nonnegative integers

N = {0, 1, 2, . . .}

natural numbers

Q

rational numbers

P = {x ∈ Z | x > 1 and the only positive divisors of x are 1 and x} set-builder notation

1

Predicate Logic • propositional logic with the addition of predicates, quantifiers, =, 6= • allows us to express facts about all or some elements of sets

Definition. A predicate is a sentence that contains one or more variables where • each variable is associated with a nonempty set, called its domain or universe of discourse, and • the sentence becomes a statement when each variable is replaced by an element of its domain.

Example: Predicate: x lives in Alberta. Let the domain of x be the set of all people. Statement: Mary lives in Alberta. (Mary is an element of the domain.) Predicate symbol: Let A stand for “lives in Alberta”. Predicate: A(x) is formal notation for “x lives in Alberta”. Statement: A(Mary) is formal notation for “Mary lives in Alberta”.

Definition. The truth set of a predicate P (x) on domain D is {x ∈ D | P (x) is true}.

2

Quantifiers are combined with predicates to say something about all or some elements of a domain. ∀

Universal Quantifier: ∀x ∈ D, Q(x)

“For all ... ”

universal statement

• Truth value – T if and only if Q(x) is T for every x ∈ D ∗ To show that a universal statement is true, show that the quantified statement is true for every element of the domain. – F if and only if Q(x) is F for at least one x ∈ D ∗ To show that a universal statement is false, give a counterexample. • Relation between ∀ and ∧: If D = {x1 , x2 , . . . xn } then ∀x ∈ D, Q(x)

∃

Existential Quantifier: ∃x ∈ D such that Q(x)

Q(x1 ) ∧ Q(x2 ) ∧ · · · ∧ Q(xn )

means

“There exists ... ”

existential statement

• Truth value – T if and only if Q(x) is T for at least one x ∈ D ∗ To show that an existential statement is true, give an example. – F if and only if Q(x) is F for all x ∈ D ∗ To show that an existential statement is false, show that the quantified statement is false for every element of the domain. • Relation between ∃ and ∨: If D = {x1 , x2 , . . . xn } then ∃x ∈ D such that Q(x)

means

Q(x1 ) ∨ Q(x2 ) ∨ · · · ∨ Q(xn )

Note: Q(x) (the quantified statement) can be a complicated logical expression involving many predicates, quantifiers, and logical connectives. 3

These two statements always have the same truth value: ∼ ∀x ∈ D, Q(x) ∃x ∈ D such that ∼ Q(x) and so do these: ∼ ∃x ∈ D such that Q(x) ∀x ∈ D, ∼ Q(x)

For u and v representing elements of a domain, u = v means that u and v represent the same element of the domain, and u 6= v means that u and v denote two distinct elements of the domain.

4

Translating between English and predicate logic ∀: all, every, each ∃: there exists, there is at least one, some Combine predicates and quantified statements with ∧, ∨, ∼, →, ↔ Examples: 1. A(x): x lives in Alberta C(x): x is a student in this class P : the set of all people S: the set of all students in this class Every student in this class lives in Alberta. ∀x ∈ S, A(x) ∀x ∈ P, (C(x) → A(x)) Some student in this class lives in Alberta. ∃x ∈ S such that A(x) ∃x ∈ P such that (C(x) ∧ A(x)) No student in this class lives in Alberta. ∀x ∈ S, ∼ A(x) ∀x ∈ P, (C(x) →∼ A(x)) ∀x ∈ P, (C(x) ∧ A(x)) Every person is in this class and lives in Alberta. ∃x ∈ P such that (C(x) → A(x)) There is a person such that if he is in this class then he lives in Alberta. 5

2. Write the following statements in symbolic form using the predicates: P (x): x > 0 Q(x): x is even R(x): x is divisible by 5 There exists a positive integer that is even. ∃x ∈ Z such that (P (x) ∧ Q(x)) ∃x ∈ Z+ such that Q(x)

If an integer is even, then it is not divisible by 5. ∀x ∈ Z, (Q(x) →∼ R(x))

No even integer is divisible by 5. ∀x ∈ Z, (Q(x) →∼ R(x)) ∼ ∃x ∈ Z such that (Q(x) ∧ R(x))

There exists an even integer that is divisible by 5. ∃x ∈ Z such that (Q(x) ∧ R(x))

If x is a positive, even integer then x is divisible by 5. ∀x ∈ Z, ((P (x) ∧ Q(x)) → R(x))

6

At least one integer is even. ∃x ∈ Z such that Q(x)

At least two integers are even. ∃x, y ∈ Z such that (Q(x) ∧ Q(y) ∧ x 6= y)

At most one integer is even. ∀x, y ∈ Z, (Q(x) ∧ Q(y) → x = y)

Exactly one integer is even. ∃x ∈ Z such that (Q(x) ∧ ∀y ∈ Z, (Q(y) → x = y))

7

Using mathematical notation as predicates Stating the domain only once when variables have the same domain Multiple Quantifiers: Order is important! Domain is important! Examples: • ∀x ∈ Z, ∃y ∈ Z such that x + y = 0

T

• ∃y ∈ Z such that ∀x ∈ Z, x + y = 0

F

• ∀x ∈ Z+ , ∃y ∈ Z+ such that x + y = 0

F

• ∀q ∈ Z, ∃p ∈ P such that p > q infinitely many prime numbers exist (known since Euclid’s time)

• ∀a, b, c, n ∈ Z, ((a, b, c > 0 ∧ n > 2) → an + bn 6= cn ) Fermat’s last theorem, proved by Andrew Wiles in 1994

• ∀n ∈ N, ((n > 2 ∧ n even) → (∃p, q ∈ P such that n = p + q)) Goldbach’s conjecture (1742): Every even integer greater than 2 can be written as the sum of two primes. Unproven; holds up to 4 · 1018 .

8