3.
1 Predicates and Quantified Statements I
3.1 Predicates and Quantified Statements I 1/1
Predicates
Fact
Recall that some sentences are not statements: “She got an A the test”.
3.1 Predicates and Quantified Statements I 2/1
Predicates
Fact
Recall that some sentences are not statements: “She got an A the test”.
(It’s true or false depending on whom we refer to, so we can think of
“person” as a variable.)
Definition
1 A predicate is a sentence that contains a finite number of variables
and becomes a statement when specific values are substituted for the
variables.
Example
3.1 Predicates and Quantified Statements I 2/1
Predicates
Fact
Recall that some sentences are not statements: “She got an A the test”.
(It’s true or false depending on whom we refer to, so we can think of
“person” as a variable.)
Definition
1 A predicate is a sentence that contains a finite number of variables
and becomes a statement when specific values are substituted for the
variables.
Example
1 P(x) : “x is a factor of 8.” What if the domain is Z+ ? What about
Z?
3.1 Predicates and Quantified Statements I 2/1
Predicates
Fact
Recall that some sentences are not statements: “She got an A the test”.
(It’s true or false depending on whom we refer to, so we can think of
“person” as a variable.)
Definition
1 A predicate is a sentence that contains a finite number of variables
and becomes a statement when specific values are substituted for the
variables.
2 The domain of a predicate variable is the set of all values that may be
substituted in place of the variable.
Example
1 P(x) : “x is a factor of 8.” What if the domain is Z+ ? What about
Z?
3.1 Predicates and Quantified Statements I 2/1
The Truth Set of P(x)
Example
Let P(x) be the predicate x 2 − x > 0 with domain the set R.
1 Write P(2) and P( 12 ).
3.1 Predicates and Quantified Statements I 3/1
The Truth Set of P(x)
Example
Let P(x) be the predicate x 2 − x > 0 with domain the set R.
1 Write P(2) and P( 12 ).
2 Indicate which of the above statements are true and which are false.
3.1 Predicates and Quantified Statements I 3/1
The Truth Set of P(x)
Example
Let P(x) be the predicate x 2 − x > 0 with domain the set R.
1 Write P(2) and P( 12 ).
2 Indicate which of the above statements are true and which are false.
Definition
If P(x) is a predicate and x has domain D, the truth set of P(x) is the
set of all elements of D that make P(x) true when they are substituted for
x. The truth set of P(x) is denoted
{x ∈ D | P(x)}.
3.1 Predicates and Quantified Statements I 3/1
The Universal Quantifier: ∀
Definition
Let P(x) be a predicate and D the domain of x.
1 A universal statement is a statement of the form “∀x ∈ D, P(x).”
2 It is defined to be true if, and only if, P(x) is true for every x in D.
Example
3.1 Predicates and Quantified Statements I 4/1
The Universal Quantifier: ∀
Definition
Let P(x) be a predicate and D the domain of x.
1 A universal statement is a statement of the form “∀x ∈ D, P(x).”
2 It is defined to be true if, and only if, P(x) is true for every x in D.
Example
1 Let D = R. Then the statement ∀x ∈ D , x 2 + 1 > 0 is true.
3.1 Predicates and Quantified Statements I 4/1
The Universal Quantifier: ∀
Definition
Let P(x) be a predicate and D the domain of x.
1 A universal statement is a statement of the form “∀x ∈ D, P(x).”
2 It is defined to be true if, and only if, P(x) is true for every x in D.
3 It is defined to be false if, and only if, P(x) is false for at least one x
in D.
4 A value for x for which P(x) is false is called a counterexample to the
universal statement.
Example
1 Let D = R. Then the statement ∀x ∈ D , x 2 + 1 > 0 is true.
3.1 Predicates and Quantified Statements I 4/1
The Universal Quantifier: ∀
Definition
Let P(x) be a predicate and D the domain of x.
1 A universal statement is a statement of the form “∀x ∈ D, P(x).”
2 It is defined to be true if, and only if, P(x) is true for every x in D.
3 It is defined to be false if, and only if, P(x) is false for at least one x
in D.
4 A value for x for which P(x) is false is called a counterexample to the
universal statement.
Example
1 Let D = R. Then the statement ∀x ∈ D , x 2 + 1 > 0 is true.
2 Let D = R. Then the statement ∀x ∈ D , x 2 + x > 0 is false. Find a
counterexample.
3.1 Predicates and Quantified Statements I 4/1
The Existential Quantifier: ∃
Definition
Let P(x) be a predicate and D the domain of x.
1 An existential statement is a statement of the form “∃x ∈ D such
that P(x).”
2 It is defined to be true if, and only if, P(x) is true for at least one x
in D.
Example
3.1 Predicates and Quantified Statements I 5/1
The Existential Quantifier: ∃
Definition
Let P(x) be a predicate and D the domain of x.
1 An existential statement is a statement of the form “∃x ∈ D such
that P(x).”
2 It is defined to be true if, and only if, P(x) is true for at least one x
in D.
Example
1 Show that the statement “∃m ∈ Z+ such that m2 = m” is true.
3.1 Predicates and Quantified Statements I 5/1
The Existential Quantifier: ∃
Definition
Let P(x) be a predicate and D the domain of x.
1 An existential statement is a statement of the form “∃x ∈ D such
that P(x).”
2 It is defined to be true if, and only if, P(x) is true for at least one x
in D.
3 It is false if, and only if, P(x) is false for all x in D.
Example
1 Show that the statement “∃m ∈ Z+ such that m2 = m” is true.
3.1 Predicates and Quantified Statements I 5/1
The Existential Quantifier: ∃
Definition
Let P(x) be a predicate and D the domain of x.
1 An existential statement is a statement of the form “∃x ∈ D such
that P(x).”
2 It is defined to be true if, and only if, P(x) is true for at least one x
in D.
3 It is false if, and only if, P(x) is false for all x in D.
Example
1 Show that the statement “∃m ∈ Z+ such that m2 = m” is true.
2 Let D = {2, 4, 6}. Show that the statement “∃m ∈ E such that
m2 = m” is false.
3.1 Predicates and Quantified Statements I 5/1
Formal Versus Informal Language
Example
Rewrite the following formal statements in an equivalent informal way
(that is, use words instead of the symbols ∀ and ∃ and predicate
variables).
1 ∀x ∈ R, x 2 + 1 > 0.
2 ∃m ∈ Z+ such that m2 = m.
3.1 Predicates and Quantified Statements I 6/1
Formal Versus Informal Language
Example
Rewrite the following formal statements in an equivalent informal way
(that is, use words instead of the symbols ∀ and ∃ and predicate
variables).
1 ∀x ∈ R, x 2 + 1 > 0.
2 ∃m ∈ Z+ such that m2 = m.
Example
Rewrite each of the following statements formally. Use quantifiers and
variables.
1 All triangles have three sides.
2 Some programs are structured.
3.1 Predicates and Quantified Statements I 6/1
Universal Conditional Statements
Definition
The universal conditional statement is
∀x ∈ D, if P(x) then Q(x).
3.1 Predicates and Quantified Statements I 7/1
Universal Conditional Statements
Definition
The universal conditional statement is
∀x ∈ D, if P(x) then Q(x).
Example
Rewrite the following statement informally, without quantifiers or variables.
∀x ∈ R, if x > 2 then x 2 > 4.
3.1 Predicates and Quantified Statements I 7/1
Universal Conditional Statements
Definition
The universal conditional statement is
∀x ∈ D, if P(x) then Q(x).
Example
Rewrite the following statement informally, without quantifiers or variables.
∀x ∈ R, if x > 2 then x 2 > 4.
Example
Rewrite the following statement in the form
“∀ , if then .”
All bytes have eight bits.
3.1 Predicates and Quantified Statements I 7/1
Equivalent Forms of Universal and Existential Statements
Examples
1 “∀ midshipmen X , if X is a cyber major then X takes SM242.” and
“∀ cyber major midshipmen X , X takes SM242” are equivalent
universal statements.
3.1 Predicates and Quantified Statements I 8/1
Equivalent Forms of Universal and Existential Statements
Examples
1 “∀ midshipmen X , if X is a cyber major then X takes SM242.” and
“∀ cyber major midshipmen X , X takes SM242” are equivalent
universal statements.
2 “There is an integer that is both prime and even” and “There is a
prime number that is even” are equivalent existential statements. Can
you find another one equivalent with them?
3.1 Predicates and Quantified Statements I 8/1
