Chapter 1: (Part 2):

The Foundations: Logic and Proofs

 Propositional Equivalence
(Section 1.2)

 Predicates & Quantifiers

(Section 1.3)

© by Kenneth H. Rosen, Discrete Mathematics & its Applications, Sixth Edition, Mc Graw-Hill, 2007
 1

Propositional Equivalences (1.2)

 A tautology is a proposition which is always true .

Classic Example: P V P

 A contradiction is a proposition which is always

false .
Classic Example: P  P

 A contingency is a proposition which neither a

tautology nor a contradiction.
Example: (P V Q)  R
CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 2

Propositional Equivalences (1.2) (cont.)

 Two propositions P and Q are logically equivalent if

P  Q is a tautology. We write:

PQ

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 3

Propositional Equivalences (1.2) (cont.)

 Example:
(P  Q)  (Q  P)  (P  Q)

 Proof:
 The left side and the right side must have the same truth
values independent of the truth value of the component
propositions.

 To show a proposition is not a tautology: use an

abbreviated truth table
 try to find a counter example or to disprove the assertion.
 search for a case where the proposition is false

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 4

Propositional Equivalences (1.2) (cont.)

 Case 1: Try left side false, right side true

Left side false: only one of PQ or Q P need be

false.

1a. Assume PQ = F.

Then P = T , Q = F. But then right side PQ = F.
Wrong guess.

1b. Try Q P = F. Then Q = T, P = F. Then

PQ = F. Another wrong guess.
CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 5

Propositional Equivalences (1.2)

 Case 2. Try left side true, right side false
If right side is false, P and Q cannot have the same truth
value.
2a. Assume P =T, Q = F.
Then PQ = F and the conjunction must be false so the left
side cannot be true in this case. Another wrong guess.
2b. Assume Q = T, P = F.
Again the left side cannot be true. We have exhausted all
possibilities and not found a counterexample. The two
propositions must be logically equivalent.

Note: Because of this equivalence, if and only if or iff is

also stated as is a necessary and sufficient condition for.
CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 6
Equivalence Name
PTP Identity Laws
PVFP
PVTT Domination Laws
PFF
PVPP Idempotent Laws
PPP
 ( P)  P Double Negation
Law

PVQQVP Commutative Law

PQQP

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 7
Equivalence Name
(P V Q) V R Associative Law
 P V (Q V R)
P V (Q  R) Distributive Law
 (P V Q)  (P V R)
(P  Q)  P V Q De Morgan’s Laws
(P V Q)  P  Q
P  Q  P V Q Implication
Equivalence
P  Q  Q  P Contrapositive Law

Note: equivalent expressions can always be substituted for each other in a more
complex expression - useful for simplification.

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 8

Propositional Equivalences (1.2) (cont.)

 Normal or Canonical Forms

 Unique representations of a proposition

 Examples: Construct a simple proposition of two

variables which is true only when

 P is true and Q is false: P  Q

 P is true and Q is true: P  Q

 P is true and Q is false or P is true and Q is true:

(P  Q) V (P  Q)

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 9

Propositional Equivalences (1.2) (cont.)

 A disjunction of conjunctions where

 every variable or its negation is represented once in each

conjunction (a minterm)

 each minterms appears only once

Disjunctive Normal Form (DNF)

 Important in switching theory, simplification in the design

of circuits.

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 10

Propositional Equivalences (1.2) (cont.)

 Method: To find the minterms of the DNF.

 Use the rows of the truth table where the proposition is 1

or True

 If a zero appears under a variable, use the negation of

the propositional variable in the minterm

 If a one appears, use the propositional variable.

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 11

Propositional Equivalences (1.2) (cont.)

 Example: Find the DNF of (P V Q) R

P Q R (P V Q) R
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 0
CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 12

Propositional Equivalences (1.2) (cont.)

 There are 5 cases where the proposition is true, hence 5
minterms. Rows 1,2,3, 5 and 7 produce the following
disjunction of minterms:

(P V Q) R
 (P  Q  R) V (P  Q  R) V (P  Q  R)
V (P  Q  R) V (P  Q  R)

 Note that you get a Conjunctive Normal Form (CNF) if

you negate a DNF and use DeMorgan’s Laws.

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 13

Predicates & Quantifiers (1.3)

 A generalization of propositions - propositional
functions or predicates: propositions which contain
variables

 Predicates become propositions once every variable

is bound- by

 assigning it a value from the Universe of Discourse U

or

 quantifying it
CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 14

Predicates & Quantifiers (1.3) (cont.)

 Examples:

 Let U = Z, the integers = {. . . -2, -1, 0 , 1, 2, 3, . . .}

 P(x): x > 0 is the predicate. It has no truth value until the

variable x is bound.

 Examples of propositions where x is assigned a value:

 P(-3) is false,
 P(0) is false,
 P(3) is true.

 The collection of integers for which P(x) is true are the

positive integers.
CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 15

Predicates & Quantifiers (1.3) (cont.)

 P(y) V P(0) is not a proposition. The variable y
has not been bound. However, P(3) V P(0) is a
proposition which is true.

 Let R be the three-variable predicate R(x, y z):

x+y=z

 Find the truth value of

R(2, -1, 5), R(3, 4, 7), R(x, 3, z)

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 16

Predicates & Quantifiers (1.3) (cont.)

 Quantifiers

 Universal

P(x) is true for every x in the universe of discourse.

Notation: universal quantifier
x P(x)

‘For all x, P(x)’, ‘For every x, P(x)’

The variable x is bound by the universal quantifier

producing a proposition.

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 17

Predicates & Quantifiers (1.3) (cont.)

 Example: U = {1, 2, 3}

x P(x)  P(1)  P(2)  P(3)

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 18

Predicates & Quantifiers (1.3) (cont.)

 Quantifiers (cont.)
 Existential

 P(x) is true for some x in the universe of discourse.

Notation: existential quantifier
x P(x)

‘There is an x such that P(x),’ ‘For some x, P(x)’, ‘For

at least one x, P(x)’, ‘I can find an x such that P(x).’

Example: U={1,2,3}
x P(x)  P(1) V P(2) V P(3)
CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 19

Predicates & Quantifiers (1.3) (cont.)

 Quantifiers (cont.)

 Unique Existential

P(x) is true for one and only one x in the universe of

discourse.

Notation: unique existential quantifier

!x P(x)

‘There is a unique x such that P(x),’ ‘There is one and

only one x such that P(x),’ ‘One can find only one x
such that P(x).’
CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 20

Predicates & Quantifiers (1.3) (cont.)

 Example: U = {1, 2, 3, 4}

P(1) P(2) P(3) !xP(x)

0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1 How many
1 0 1 0 minterms are
1 1 0 0 in the DNF?
1 1 1 0
CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 21

Predicates & Quantifiers (1.3) (cont.)

REMEMBER!

A predicate is not a proposition until all variables

have been bound either by quantification or
assignment of a value!

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 22

Predicates & Quantifiers (1.3) (cont.)

 Equivalences involving the negation operator
(x P(x ))  x P(x)
(x P(x))  x P(x)

 Distributing a negation operator across a quantifier

changes a universal to an existential and vice
versa.

 (x P(x))  (P(x1)  P(x2)  …  P(xn))

 P(x1) V P(x2) V … V P(xn)
 x P(x)

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 23

Predicates & Quantifiers (1.3) (cont.)

 Multiple Quantifiers: read left to right . . .

 Example: Let U = R, the real numbers,

P(x,y): xy= 0
x y P(x, y)
x y P(x, y)
x y P(x, y)
x y P(x, y)

The only one that is false is the first one.

What’s about the case when P(x,y) is the predicate
x/y=1?
CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 24

Predicates & Quantifiers (1.3) (cont.)

 Multiple Quantifiers: read left to right . . .
 Example: Let U = {1,2,3}. Find an expression equivalent
to x y P(x, y) where the variables are bound by
substitution instead:

Expand from inside out or outside in.

Outside in:

y P(1, y)  y P(2, y)  y P(3, y)

[P(1,1) V P(1,2) V P(1,3)] 
[P(2,1) V P(2,2) V P(2,3)] 
[P(3,1) V P(3,2) V P(3,3)]
CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 25

Predicates & Quantifiers (1.3) (cont.)

 Converting from English (Can be very difficult!)

“Every student in this class has studied calculus”

transformed into:

“For every student in this class, that student has studied

calculus”

C(x): “x has studied calculus”

x C(x)

This is one way of converting from English!

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 26

Predicates & Quantifiers (1.3) (cont.)

 Multiple Quantifiers: read left to right . . . (cont.)

 Example:

F(x): x is a fleegle
S(x): x is a snurd
T(x): x is a thingamabob

U={fleegles, snurds, thingamabobs}

(Note: the equivalent form using the existential quantifier is also

given)

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 27

Predicates & Quantifiers (1.3) (cont.)

 Everything is a fleegle
x F( x)
  (x F(x))

 Nothing is a snurd.
x  S(x)
  (x S( x))

 All fleegles are snurds.

x [F(x)S(x)]
 x [F(x) V S(x)]
 x  [F(x)  S(x)]
  (x [F(x) V S(x)])
CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 28

Predicates & Quantifiers (1.3) (cont.)

 Some fleegles are thingamabobs.
x [F(x)  T(x)]
 (x [F(x) V T(x)])

 No snurd is a thingamabob.
x [S(x) T(x)]
 (x [S(x )  T(x)])

 If any fleegle is a snurd then it's also a thingamabob

x [(F(x)  S(x))  T(x)]
 (x [F(x)  S(x)  T( x)])

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 29

Predicates & Quantifiers (1.3) (cont.)

 Extra Definitions:

 An assertion involving predicates is valid if it is true for

every universe of discourse.

 An assertion involving predicates is satisfiable if there is a

universe and an interpretation for which the assertion is
true. Else it is unsatisfiable.

 The scope of a quantifier is the part of an assertion in

which variables are bound by the quantifier

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 30

Predicates & Quantifiers (1.3) (cont.)

 Examples:

Valid: x S(x)  [x S( x)]

Not valid but satisfiable: x [F(x)  T(x)]

Not satisfiable: x [F(x)  F(x)]

Scope: x [F(x) V S( x)] vs. x [F(x)] V x [S(x)]

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 31

Predicates & Quantifiers (1.3) (cont.)

 Dangerous situations:

 Commutativity of quantifiers
x y P(x, y) y x P( x, y)?
YES!
x y P(x, y)  y x P(x, y)?
NO!
DIFFERENT MEANING!

 Distributivity of quantifiers over operators

x [P(x)  Q(x)]  x P( x)  x Q( x)?
YES!
x [P( x)  Q( x)] [x P(x)  x Q( x)]?
NO!
CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 32

Sets (1.6)

 A set is a collection or group of objects or elements

or members. (Cantor 1895)

 A set is said to contain its elements.

 There must be an underlying universal set U, either

specifically stated or understood.

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 33

Sets (1.6) (cont.)

 Notation:

 list the elements between braces:

S = {a, b, c, d}={b, c, a, d, d}
(Note: listing an object more than once does not change the set.
Ordering means nothing.)

 specification by predicates:
S= {x| P(x)},
S contains all the elements from U which make the predicate P
true.

 brace notation with ellipses:

S = { . . . , -3, -2, -1},
the negative integers.
CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 34

Sets (1.6) (cont.)

 Common Universal Sets
 R = reals
 N = natural numbers = {0,1, 2, 3, . . . }, the counting
numbers
 Z = all integers = {. . , -3, -2, -1, 0, 1, 2, 3, 4, . .}
 Z+ is the set of positive integers

 Notation:
x is a member of S or x is an element of S:
x  S.
x is not an element of S:
x  S.
CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 35

Sets (1.6) (cont.)

 Subsets
 Definition: The set A is a subset of the set B, denoted
A  B, iff
x [x  A  x  B]
 Definition: The void set, the null set, the empty set,
denoted , is the set with no members.

Note: the assertion x   is always false. Hence

x [x    x  B]
is always true(vacuously). Therefore,  is a subset of
every set.

Note: A set B is always a subset of itself.

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 36

Sets (1.6) (cont.)

 Definition: If A  B but A  B the we say A is a proper

subset of B, denoted A  B (in some texts).

 Definition: The set of all subset of a set A, denoted P(A),

is called the power set of A.

 Example: If A = {a, b} then

P(A) = {, {a}, {b}, {a,b}}

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 37

Sets (1.6) (cont.)

 Definition: The number of (distinct) elements in A,
denoted |A|, is called the cardinality of A.

If the cardinality is a natural number (in N), then the

set is called finite, else infinite.

 Example: A = {a, b},

|{a, b}| = 2,
|P({a, b})| = 4.
A is finite and so is P(A).
Useful Fact: |A|=n implies |P(A)| = 2n

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 38

Sets (1.6) (cont.)

 N is infinite since |N| is not a natural number. It is called a transfinite
cardinal number.

 Note: Sets can be both members and subsets of other sets.

 Example:
A = {,{}}.
A has two elements and hence four subsets:
, {}, {{}}. {,{}}
Note that  is both a member of A and a subset of A!

 Russell's paradox: Let S be the set of all sets which are not members
of themselves. Is S a member of itself?

 Another paradox: Henry is a barber who shaves all people who do

not shave themselves. Does Henry shave himself?

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions
 39

Sets (1.6) (cont.)

 Definition: The Cartesian product of A with B, denoted
A x B, is the set of ordered pairs {<a, b> | a  A  b  B}
Notation: n
 Ai   a1 , a 2 ,...,a n  a i  Ai 
i 1
Note: The Cartesian product of anything with  is . (why?)

 Example:
A = {a,b}, B = {1, 2, 3}
AxB = {<a, 1>, <a, 2>, <a, 3>, <b, 1>, <b, 2>, <b, 3>}
What is BxA? AxBxA?

 If |A| = m and |B| = n, what is |AxB|?

CS 210, Ch.1 (part 2): The foundations: Logic & Proof, Sets, and Functions