Predicate Calculus
Predicate
Universal Quantifier
Existential Quantifier
De Morgans Laws
Other Rules for Quantifiers
Analogy Between Sets and Statements
SSK3003
Discrete Structures
Predicate
An open sentence p(x) is a declarative sentence
that becomes a statement when x is given a
particular value chosen from a universe of
values. An open sentence is also known as a
predicate.
SSK3003
Discrete Structures
Example Predicate
Let p(x) = If x > 4, then x + 10 > 14 be an open sentence.
Let x U, where U = {1, 2, 3, 4, }. Find the truth value of
each statement formed when these values are substituted for
x in p(x).
p(1) is TRUE because 1 > 4 is FALSE.
p(2) is TRUE because 2 > 4 is FALSE.
p(3) is TRUE because 3 > 4 is FALSE.
SSK3003
Discrete Structures
Example Predicate (2)
p(x) = If x > 4, then x + 10 > 14
p(4) is TRUE because 4 > 4 is FALSE.
p(5) is TRUE because 5 > 4 and 5 + 10 > 14
are TRUE.
p(6) is TRUE because 6 > 4 and 6 + 10 > 14
are TRUE.
In fact, p(x) is TRUE for all values of x U.
SSK3003
Discrete Structures
Universal Quantifier
The statement
For all x U, p(x)
is symbolized by
x U p(x).
The above statement is TRUE if and only if p(x) is TRUE for every
x U.
The symbol is called the universal quantifier.
SSK3003
Discrete Structures
Example: Universal Quantifier
Let U = {1, 2, 3, 4, 5, 6}. Determine the truth value of the
statement
x U [(x 4)(x 8) > 0].
Let p(x) = (x 4)(x 8) > 0.
p(1) is TRUE because (1 4)(1 8) > 0 is TRUE.
p(2) is TRUE because (2 4)(2 8) > 0 is TRUE.
p(3) is TRUE because (3 4)(3 8) > 0 is TRUE.
SSK3003
Discrete Structures
Example: Universal Quantifier
(2)
p(x) = (x 4)(x 8) > 0.
p(4) is FALSE because (4 4)(4 8) > 0 is FALSE.
Therefore, the statement
x U [(x 4)(x 8) > 0]
is FALSE because 4 U and p(4) is FALSE.
SSK3003
Discrete Structures
Existential Quantifier
The statement
There exists an x U such that p(x)
is symbolized by
x U p(x).
The above statement is TRUE if and only there is at
least one element x U such that p(x) is TRUE.
The symbol is called the existential quantifier.
SSK3003
Discrete Structures
Example: Existential Quantifier
Let U = {1, 2, 3, 4, 5, 6, 7, 8}. Determine the truth value of
x U [(x 3)(x + 2) = 0].
Let p(x) = (x 3)(x + 2) = 0.
p(1) is FALSE because (1 3)(1 + 2) = 0 is FALSE.
p(2) is FALSE because (2 3)(2 + 2) = 0 is FALSE.
p(3) is TRUE because (3 3)(3 + 2) = 0 is TRUE.
SSK3003
Discrete Structures
Example: Existential Quantifier
(2)
Therefore, the statement
x U [(x 3)(x + 2) = 0]
is TRUE because we found 3 U such that p(3) is
TRUE.
SSK3003
Discrete Structures
10
De Morgans Laws
The rules for the negation of quantified
statements are
~[x U p(x)] [x U ~ p(x)]
~[x U p(x)] [x U ~ p(x)].
These rules are called De Morgans laws.
SSK3003
Discrete Structures
11
Example De Morgans Laws
Write the negation of
a) All university students like football.
b) There exists a university student who
does not like football.
b) There is a mathematics textbook that is both
short and clear.
c)
Every mathematics textbook is either not
short or not clear.
SSK3003
Discrete Structures
12
Other Rules for Quantifiers
Other rules for statements containing
quantifiers are
~[x y p(x,y)] x y [~ p(x,y)]
~[x y p(x,y)] x y [~ p(x,y)]
~[x y p(x,y)] x y [~ p(x,y)]
~[x y p(x,y)] x y [~ p(x,y)]
x y p(x,y) y x p(x,y)
x y p(x,y) y x p(x,y)
x y p(x,y) y x p(x,y)
SSK3003
Discrete Structures
13
Example: Other Rules for
Quantifiers
Let U for both variables be the nonnegative
integers 0, 1, 2, 3, 4, . Determine the truth
value of
a) x y [2x = y]
b) y x [2x = y]
SSK3003
Discrete Structures
14
Example:Other Rules for
Quantifiers (a)
a) x y [2x = y]
b)The statement says that for every nonnegative
integer x, there is a nonnegative integer y such
that 2x = y. This is TRUE because, once having
chosen any nonnegative number x, we can let y
be the double of x.
SSK3003
Discrete Structures
15
Example Other Rules for
Quantifiers (b)
b) y x [2x = y]
The statement says that there exists a
nonnegative integer y such that, for all
nonnegative integers x, 2x = y. For it to be TRUE,
we would need to find a specific value of y that
can be fixed and for which, no matter what
nonnegative integer x we choose, 2x = y. Since
this is not possible, the statement is FALSE.
SSK3003
Discrete Structures
16
Analogy Between Sets and
Statements
Let p(x) = x S, and q(x) = x T. Then
Union:
x [x
S T p(x) v q(x)]
Intersection:
x [x
S T p(x) ^ q(x)]
Complement:
x [x
S ~ p(x)]
Symmetric Difference:
x [x
S T p(x) q(x)]
Subset
(S T) x [p(x) q(x)]
Equal
(S = T) x [p(x) q(x)]
SSK3003
Discrete Structures
17
Example: Sets and Statements
Let U = {1, 2, 3, 4, 5, 6}, let S = {x U: x < 3}, and let T = {x U: x divides 6}.
Show S T.
We need to show that where x S is TRUE then
x T is TRUE.
By definition of S, x S is TRUE if and only if x is 1, 2, or 3.
However, 1, 2, and 3 all divide 6 so x T is also TRUE.
Therefore, S T.
SSK3003
Discrete Structures
18
Summary Section
Statements containing variables are called
predicates and can be made into logical
statements with quantifiers. The quantifiers are
the symbols (for all) and (there exists).
These symbols refer to the particular universal
set for the variables in the predicate.
SSK3003
Discrete Structures
19
Summary Section
Important rules of predicate calculus include
the following
~[x U p(x)] [x U ~ p(x)]
~[x U p(x)] [x U ~ p(x)]
x y p(x,y) y x p(x,y)
x y p(x,y) y x p(x,y)
x y p(x,y) y x p(x,y)
SSK3003
Discrete Structures
20
Logic Circuits
Logic Circuits
NOT, AND and OR Gates
NAN and NOR Gates
XOR Gate
SSK3003
Discrete Structures
21
Logic Circuits
Logic circuits can be found in computers,
telephones, digital clocks, and television sets
plus a great many more devices. In a logic circuit
current flows through gates to an output line.
The input current to the gate has only two states,
ON (1) or OFF (0). The output depends upon the
type of gate in the circuit.
SSK3003
Discrete Structures
22
NOT, AND and OR Gates
SSK3003
Discrete Structures
23
Example NOT, AND and OR Gates
Draw a logic circuit for three inputs, p, q, and r
and output (~ p) ( q r ).
We will begin with the AND gate.
SSK3003
Discrete Structures
24
Example NOT, AND and OR Gates
(2)
Next we will add in the OR and NOT gates.
SSK3003
Discrete Structures
25
Example Logical Statement (2)
SSK3003
Discrete Structures
26
NAND and NOR Gates
SSK3003
Discrete Structures
27
XOR Gate
SSK3003
Discrete Structures
28
Summary Section
Logic circuits contain NOT, AND, OR, NAND, NOR
and XOR gates.
Logic circuits frequently can be simplified
using the Table of Logical Equivalences.
SSK3003
Discrete Structures
29
