Predicates and Quantified Statements
Set Notation
Universal and Existential Statements
Translating between Formal and Informal Language
Implicit
Quantification
Negation
of Universal and Existential Statements
Negation
of Universal Conditional Statements
Predicates and Quantified Statements top
Given an understanding of the logical analysis of compound
statements -those made of simple statements joined by the
connectives negation, conjunction, disjunction, conditional,
and the biconditional, we have the rudimentary tools. We
need only add an ability to quantify statements to extend our
understanding of logic to cover many of the everyday and the
majority of the mathematical situations. To this end we must
learn to analyze and understand the quantities "all"
and "some".
What is a predicate? In grammar, the predicate is the part of a sentence that gives information about the subject.
"John is a student at UNCW."
John is the subject and is a student at UNCW is the predicate. In logic we can obtain predicates by removing any nouns from a statement. "x
is a student at UNCW" and
"x is a student at y"
Definition
A predicate is a sentence that contains a finite number of
variables and becomes a statement when specific values are
substituted for the variables. The domain of a predicate variable
is the set of all values that may be substituted in place of the
variable.
Set Notation top
The sets in which predicate variables take their values are
denoted by upper case letters or described by words. The elements
of a set are denoted by lower case letters. So the notation x
Î A indicates that x is
an element of the set A, or simply x is in A.
Some common sets in mathematics are
Symbol |
Set |
R |
set of all real numbers |
Q |
set of all rational numbers, integer quotients |
Z |
set of all integers |
N |
set of nonnegative integers, the natural numbers |
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
substituted for x. The truth set of P(x) is
denoted
{x Î D | P(x)}
which is read "the set of all x in D such that P(x)."
Ex. 1
Let D = {0, 1, 2, 3, ...}, and P(x) be
"x is a factor of 12".
Then the truth set P(x) is ...Solution
Notation
Let P(x) and Q(x) be predicates and
suppose the common domain of x is D. The notation P(x)Þ Q(x) means that every
element in the truth set of P(x) is in the truth
set of Q(x). The notation P(x)Û Q(x) means that P(x)
and Q(x) have identical truth sets.
Ex. 2
Let P(x) be "x is a factor of 12,"
Q(x) be "x is a factor of 4," and R(x)
be "x < 5 and x ¹
3," and suppose the domain of x is Z^{+}.
Use Þ and Û
to indicate true relationships among P(x), Q(x),
and R(x). Solution
Universal and Existential Statements top
Quantifiers are words such as "some" or "all"
that can be added to predicates to tell for how many elements a
given predicate is true. The symbol "
denotes "for all" and is called the universal
quantifier.
Definition
Let Q(x) be a predicate and D the domain of x.
A universal statement is of the form
"" x Î D, Q(x)." It is
defined to be true if, and only if, Q(x) is true
for every x in D. It is defined to be false if, and
only if, Q(x) is false for at least one x in
D. A value for x for which Q(x) is
false is called a counterexample to the universal
statement.
Ex.
Let D = {0, 1, 2, 3}, and P(x) be "x^{2}
³ x." Show that
" x Î D, P(x)
is true.
Checking each case (method of exhaustion): 0^{2} ³ 0, 1^{2} ³ 1, 2^{2} ³ 2, 3^{2} ³ 3, we see that the statement is true.
The symbol $ denotes "there exists" and is called the existential quantifier.
Definition
Let Q(x) be a predicate and D the domain of x.
A existential statement is of the form
"$ x Î
D, such that Q(x)." It is defined to be
true if, and only if, Q(x) is true for at least one
x in D. It is defined to be false if, and only if, Q(x)
is false for all x in D.
Ex.
Show the truth of the statement
$ e Î Z such that e^{2} = e.
To show that e^{2} = e is true for at least one integer observe that 1^{2} = 1.
Translating between Formal and Informal
Language top
We can only approximate the translating of English sentencs to
predicate logic because of the diverse natures of teh two kinds
of language. The expressiveness of natural language is much
greater, but what a formal language does express is done with
precision. The first step is to identify the propositional
connectives conjunction, disjunction, negation, conditional,
..., then the quantifiers for all, and there
exist. Expressions that can be used in place of for all
are
for every, for arbitrary, for any, for each, and given any.
Expression that can be used in place of their exists are
there is a, we can find a, there is at least one, for some, and for at least one.
For particularly difficult cases it may be worth while to rephrase in a semi-formal version being sure to put subject in each sentence fragment. Do not expect the formal version to catch all the subtleties, and while there may be many correct solutions, there are also many incorrect ones. One's effort should be in the minimizing of the incorrect solutions.
E(x): x spoke English,
H(x): x spoke Hungarian.
Restating a. in a semi-formal
manner: "For all x, if x was a person in the class, then x
spoke English or x spoke Hungarian."
" x C(x) Þ (E(x) Ú H(x)).
We would write b. as
$ x C(x) Ù (E(x) Ú H(x)).
Another example reveals how to write equivalent universal statements by condensing the domain to include all values that make the hypothesis of the conditional true. Compare the statements, "" real numbers x, if x is an integer then x is rational." and "" integers x, x is rational." Both mean "All integers are rational." In fact,
" x Î U, if P(x) then Q(x)
can always be rewritten in the form
" x Î D, Q(x)
by narrowing U to be the domain D consisting of all values of the variable x that make P(x) true. Conversely, a statement of the form
" x Î D, Q(x)
can be rewritten as
" x, if x is in D then Q(x).
Implicit Quantification top
Consider the statement
If a number is an integer, then it is a rational number.
What quantifier should we use and what is the clue supporting this as the required quantifier?If x > 2 then x^{2} > 4.
Given in an algebra course this statement is understood to mean
" real numbers x, if x > 2 then x^{2} > 4.
In the same algebra course you might be asked to solve
(x - 2)^{2} = 25.
This predicate is existentially quantified as
Show (by finding a value) that $ a real number x such that (x -2)^{2} = 25.
The quantification, whether universal or existential, determines how the statement can be applied and the method to be used to establish its truth.
Negation of Universal and Existential Statements top
Consider the quantified statement "All fire trucks are red." Which of the
following statements more accurately reflects its negation?
Theorem 2.1.1
The negation of a statement of the form
" x in D, Q(x)
is logically equivalent to a statement of the form
$ x in D such that Ø Q(x).
Symbolically:
Ø (" x Î D, Q(x)) Û $ x Î D such that Ø Q(x).
The negation of the universal statement, "all are," is logically equivalent
to the existential statement, "some are not."
Clearly the answer to our fire
ruck question is b.
For what statement is "No fire trucks are red." a logical negation? Solution
Theorem 2.1.2
The negation of a statement of the form
$ x in D such that Q(x)
is logically equivalent to a statement of the form
" x in D, Ø Q(x).
Symbolically:
Ø ($ x Î D such that Q(x)) Û " x Î D, Ø Q(x).
The negation of the existential statement, "some are not ," is logically equivalent to the universal statement, "all are."
See examples 2.1.10-12 on pp. 84 & 85.
Negation of Universal Conditional Statements top
We have that
Ø (" x, P(x) Þ Q(x)) Û $ x such that Ø (P(x) Þ Q(x)),
by Theorem 2.1.1. But the negation of an if-then statement is logically equivalent to an and statement.
Ø (P(x) Þ Q(x)) Û P(x) Ù Ø Q(x).
So,
Ø (" x, P(x) Þ Q(x)) Û $ x such that P(x) Ù Ø Q(x).