Transcript 3.1-2 - the College of Science and Engineering

Predicates and Quantified Statements
x is an even number
x is a student in Discrete Math
x+y=5
x is the son of z
These are not statements. Why?
When the variable(s) takes specific values, they become
propositions. The sets were the variable takes values is
called the domain D.
Each sentence describe properties hold by the
variable(s) involve in it.
These sentences are called Predicates or Open Statements.
Notation for Predicates
P(x): x is an even number
Possible domains: N, Z, R
Q(y): y is a student in Discrete Math
Possible domains: TAMUCC, College of Science
R(x, y): x + y =5
Possible domains: N, Z, Q, R
S(x, z): x is the son of z
Possible domains: People in CC, TX, USA, the world
True Set
P(x): x is an even number
If D is the domain, { x Î D / P(x)} represents
all the elements in the domain that make P(x)
true.
If D={1,2,3,4} The true set is { 2,4}
If D=N, the true set is {0,2,4,6,8,…}
Let Q(n) be the predicate “n is a factor of 8.”
Find the truth set of Q(n) if
a. the domain of n is the set Z+ of all positive
integers
{1, 2, 4, 8}
b. the domain of n is the set Z of all integers.
{1, 2, 4, 8,−1,−2,−4,−8}
Quantifiers
Consider P(x): x is an even number with domain
all integers
How to make a predicate a proposition?
1. By substituting the variable by a specific
value: P(3), P(4), etc.
2. All integers satisfy P(x)
"x Î D, P(x)
1. Some integers satisfy P(x) $x Î D, P(x)
To make a predicate into a proposition two
components are needed: the quantifier and the
domain (where the variable takes values)
P(x): x is an even number
All integers satisfy P(x)
Quantifiers Domain
Some integers satisfy P(x)
Equivalent Expressions for “All”
P(x): x is an even number
All integers satisfy P(x)
–
–
–
–
–
for every x, P(x)
for arbitrary x, P(x)
for any x, P(x)
for each x, P(x)
given any x, P(x)
Let D = {1, 2, 3, 4, 5}, and consider the statement
Show that this statement is true.
• Let D = {-1, 0.25, 0.5, 1}, and consider the statement
Show that this statement is false. (counterexample)
Equivalent Expressions for “Some”
P(x): x is an even number
Some integers satisfy P(x)
•
•
•
•
•
there is an a, P(a),
we can find a, P(a),
there is at least one a, P(a)
for some a, P(a),
for at least one a, P(a)
Let D = {-1, 0.25, 0.5, 1}, and consider the statement
Î D, P(x)
Show that this$x
statement
is false.
From Formal to Informal
Rewrite the following formal statements in a
variety of equivalent but more informal ways.
Do not use the symbol ∀ or ∃.
a.
b.
c.
Solutions
a. All real numbers have nonnegative squares.
Or: Every real number has a nonnegative square.
Or: Any real number has a nonnegative square.
Or: The square of each real number is
nonnegative.
b. All real numbers have squares that are not equal
to −1.
Or: No real numbers have squares equal to −1.
(The words none are or no . . . are are equivalent
to the words all are not.)
c. There is a positive integer whose square is
equal to itself.
Or: We can find at least one positive integer
equal to its own square.
Or: Some positive integer equals its own
square.
Or: Some positive integers equal their own
squares.
Rewrite the following statement informally, without quantifiers or
variables.
∀x ∈ R, if x > 2 then x2 > 4.
Solution:
If a real number is greater than 2 then its square is greater than
4.
Or: Whenever a real number is greater than 2, its square is
greater than 4.
Or: The square of any real number greater than 2 is greater
than 4.
Or: The squares of all real numbers greater than 2 are
greater than 4.
Equivalent Forms of Universal and Existential Statements
Observe that the two statements “∀ real numbers x, if x
is an integer then x is rational” and “∀ integers x, x is
rational” mean the same thing.
Both have informal translations “All integers are
rational.” In fact, a statement of the form
can always be rewritten in the form
by narrowing U to be the domain D consisting of all
values of the variable x that make P(x) true.
Exercise
Rewrite the statement "All squares are
rectangles" in the two forms
“∀x,
if ______ then ______” and
“∀ ______x, _______”
Solution:
∀x, if x is a square then x is a
rectangle.
∀ squares x, x is a rectangle.
On the other hand, a statement of the form
“∃x such that P(x) and Q(x)”
can be rewritten as
“∃x εD such that Q(x),”
where D is the set of all x for which P(x) is true.
A statement of the form
“∃x such that P(x) and Q(x)”
can be rewritten as
“∃x εD such that Q(x),”
where D is the set of all x for which P(x) is true.
A prime number is an integer greater than 1 whose
only positive integer factors are itself and 1.
Consider the statement “There is an integer that is
both prime and even.”
Let P (n) be “n is prime” and E(n) be “n is even.”
Use the notation P (n) and E (n) to rewrite this
statement in the following two forms:
a. ∃n such that ______ ∧ ______ .
b. ∃ ______ n such that ______.
NEGATION OF “ALL” “SOME”
All the students in Discrete Math are math majors
Statement in symbolic form
Let D be the Discrete Math students, M(x): x is a
math major
"x Î D, M(x)
Negation of the original statement
Some discrete math students are not math majors
$x Î D, ~ M(x)
Negation in symbolic form
Some students in Discrete Math wear glasses
Statement in symbolic form
D Discrete Math students, W(x): x wears glasses
$x Î D, W(x)
Negation of original statement
Any Discrete Math student does not wear glasses
Negation in symbolic form
"x Î D ~ W(x)
SUMMARY OF NEGATIONS FOR "ALL " "SOME"
~ ("x Î D,Q(x)) º $x Î D, ~ Q(x)
~ ( "x, P(x) ® Q(x)) º $x, ~ ( P(x) ® Q(x))
º $x, ( P(x) Ù ~ Q(x))
~ ($x Î D, Q(x)) º "x Î D, ~ Q(x)
~ ( $x, P(x) ÙQ(x)) º "x, ~ ( P(x)Ù Q(x))
º "x, (~ P(x)Ú ~ Q(x))
º "x, (P(x) ®~ Q(x))
Contrapositive, Converse, Inverse of a
Universal Implication
Consider a statement of the form
"x Î D, if P(x) then Q(x)
Contrapositive
Converse
Inverse
"x Î D, if ~ Q(x) then ~ P(x)
"x Î D, if Q(x) then P(x)
"x Î D, if ~ P(x) then ~ Q(x)
Example
Write a formal and an informal contrapositive,
converse, and inverse for the statement:
If a real number is greater than 2, then its
square is greater than 4.
Contrapositive: ∀x ∈ R, if x2 ≤ 4 then x ≤ 2.
If the square of a real number is less
than or equal to 4, then the number is less
than or equal to 2.
Converse: ∀x ∈ R, if x2 > 4 then x > 2.
If the square of a real number is greater
than 4, then the number is greater than 2.
Inverse: ∀x ∈ R, if x ≤ 2 then x2 ≤ 4.
If a real number is less than or equal to
2, then the square of the number is less
than or equal to 4.
Necessary, Sufficient, Only if
"x Î D, if P(x) then Q(x)
For all x, P(x) is a sufficient condition for Q(x)
For any x, Q(x) is a necessary condition for P(x)
For any x, P(x) only if Q(x)
Example
Rewrite the following statements as quantified
conditional statements. Do not use the word
necessary or sufficient.
a. Squareness is a sufficient condition for
rectangularity.
b. Being at least 35 years old is a necessary
condition for being President of the United
States.
Solution
a. A formal version of the statement is
∀x, if x is a square, then x is a rectangle.
In informal language:
If a figure is a square, then it is a rectangle.
b. A formal version
∀ people x, if x is younger than 35, then x cannot be President of
the United States.
Or, by the equivalence between a statement and its contrapositive:
∀ people x, if x is President of the United States, then x is at least
35 years old.
Informal version
Any president of the United States is at least 35 years old