Let’s get started with...

Logic!

MS 101 - Discrete Mathematics 1

 Logic
• Crucial for mathematical reasoning
• Important for program design
• Used for designing electronic circuitry

• (Propositional )Logic is a system based on

propositions.
• A proposition is a (declarative) statement
that is either true or false (not both).
• We say that the truth value of a proposition
is either true (T) or false (F).
• Corresponds to 1 and 0 in digital circuits
MS 101 - Discrete Mathematics 2
 The Statement/Proposition Game

“Elephants are bigger than mice.”

Is this a statement? yes

Is this a proposition? yes

What is the truth value

of the proposition? true

MS 101 - Discrete Mathematics 3

 The Statement/Proposition Game

“10 < 5”

Is this a statement? yes

Is this a proposition? yes

What is the truth value

of the proposition? false

MS 101 - Discrete Mathematics 4

 The Statement/Proposition Game

“y > 5”

Is this a statement? yes

Is this a proposition? no

Its truth value depends on the value of y,

but this value is not specified.
We call this type of statement a
propositional function or open sentence.
MS 101 - Discrete Mathematics 5
 The Statement/Proposition Game

“Today is February 9 and 100 < 50.”

Is this a statement? yes

Is this a proposition? yes

What is the truth value

of the proposition? false

MS 101 - Discrete Mathematics 6

 The Statement/Proposition Game

“Please do not fall asleep.”

Is this a statement? no
It’s a request.

Is this a proposition? no

Only statements can be propositions.

MS 101 - Discrete Mathematics 7

 The Statement/Proposition Game
“If the moon is made of cheese,
then I will be rich.”

Is this a statement? yes

Is this a proposition? yes

What is the truth value

of the proposition? probably true

MS 101 - Discrete Mathematics 8

 The Statement/Proposition Game
“x < y if and only if y > x.”
Is this a statement? yes
Is this a proposition? yes
… because its truth value
does not depend on
specific values of x and y.
What is the truth value
of the proposition? true
MS 101 - Discrete Mathematics 9
 Combining Propositions

As we have seen in the previous examples,

one or more propositions can be combined
to form a single compound proposition.

We formalize this by denoting propositions

with letters such as p, q, r, s, and
introducing several logical operators or
logical connectives.

MS 101 - Discrete Mathematics 10

 Logical Operators (Connectives)
We will examine the following logical operators:

• Negation (NOT, )
• Conjunction (AND, )
• Disjunction (OR, )
• Exclusive-or (XOR,  )
• Implication (if – then,  )
• Biconditional (if and only if,  )

Truth tables can be used to show how these

operators can combine propositions
CMSC 203 - Discrete Structures to 11

compound propositions.
 Negation (NOT)

Unary Operator, Symbol: 

P  P
true (T) false (F)
false (F) true (T)

MS 101 - Discrete Mathematics 12

 Conjunction (AND)
Binary Operator, Symbol: 
P Q P Q
T T T
T F F
F T F
F F F

MS 101 - Discrete Mathematics 13

 Disjunction (OR)
Binary Operator, Symbol: 
P Q P Q
T T T
T F T
F T T
F F F

MS 101 - Discrete Mathematics 14

 Exclusive Or (XOR)
Binary Operator, Symbol: 
P Q PQ
T T F
T F T
F T T
F F F

MS 101 - Discrete Mathematics 15

 Implication (if - then)
Binary Operator, Symbol: 
P Q PQ
T T T
T F F
F T T
F F T

MS 101 - Discrete Mathematics 16

Biconditional (if and only if)
Binary Operator, Symbol: 
P Q PQ
T T T
T F F
F T F
F F T

MS 101 - Discrete Mathematics 17

Statements and Operators
Statements and operators can be combined in any
way to form new statements.

P Q P Q (P)(Q)
T T F F F
T F F T T
F T T F T
F F T T T

MS 101 - Discrete Mathematics 18

Statements and Operations
Statements and operators can be combined in any
way to form new statements.

P Q PQ (PQ) (P)(Q)

T T T F F
T F F T T
F T F T T
F F F T T

MS 101 - Discrete Mathematics 19

 Exercises
• To take discrete mathematics, you must have
taken calculus or a course in computer science.
• When you buy a new car from Acme Motor
Company, you get $2000 back in cash or a 2%
car loan.
• School is closed if more than 2 feet of snow
falls or if the wind chill is below -100.

MS 101 - Discrete Mathematics 20

 Exercises
• To take discrete mathematics, you must have
taken calculus or a course in computer science.
– P: take discrete mathematics
– Q: take calculus
– R: take a course in computer science
•P Q R
• Problem with proposition R
– What if I want to represent “take CMSC201”?

MS 101 - Discrete Mathematics 21

 Exercises
• When you buy a new car from Acme Motor
Company, you get $2000 back in cash or a 2%
car loan.
– P: buy a car from Acme Motor Company
– Q: get $2000 cash back
– R: get a 2% car loan

•P Q R
• Why use XOR here? – example of ambiguity of
natural languages
MS 101 - Discrete Mathematics 22
 Exercises
• School is closed if more than 2 feet of snow
falls or if the wind chill is below -100.
– P: School is closed
– Q: 2 feet of snow falls
– R: wind chill is below -100

•QRP
• Precedence among operators:
, , , , 

MS 101 - Discrete Mathematics 23

 Equivalent Statements
P Q (PQ) (P)(Q) (PQ)(P)(Q)

T T F F T
T F T T T
F T T T T
F F T T T
The statements (PQ) and (P)  (Q) are logically
equivalent, since they have the same truth table, or put
it in another way, (PQ) (P)  (Q) is always true.
MS 101 - Discrete Mathematics 24
 Tautologies and Contradictions
A tautology is a statement that is always true.
Examples:
– R(R)
– (PQ)  (P)( Q)
A contradiction is a statement that is always false.
Examples:
– R(R)
– ((P  Q)  (P)  (Q))
The negation of any tautology is a contradiction, and
the negation of any contradiction is a tautology.

MS 101 - Discrete Mathematics 25

 Equivalence
Definition: two propositional statements
S1 and S2 are said to be (logically)
equivalent, denoted S1  S2 if
– They have the same truth table, or
– S1  S2 is a tautology
Equivalence can be established by
– Constructing truth tables
– Using equivalence laws (Table 5 in Section 1.2)

MS 101 - Discrete Mathematics 26

 Equivalence
Equivalence laws
– Identity laws, P  T  P,
– Domination laws, P  F  F,
– Idempotent laws, P  P  P,
– Double negation law,  ( P)  P
– Commutative laws, P  Q  Q  P,
– Associative laws, P  (Q  R) (P  Q)  R,
– Distributive laws, P  (Q  R) (P  Q)  (P  R),
– De Morgan’s laws,  (PQ)  ( P)  ( Q)
– Law with implication P Q PQ

MS 101 - Discrete Mathematics 27

 Exercises
• Show that P  Q   P  Q: by truth table
• Show that (P  Q)  (P  R)  P  (Q  R):
by equivalence laws (q20, p27):
– Law with implication on both sides
– Distribution law on LHS

MS 101 - Discrete Mathematics 28

 Summary, Sections 1.1, 1.2
• Proposition
– Statement, Truth value,
– Proposition, Propositional symbol, Open proposition
• Operators
– Define by truth tables
– Composite propositions
– Tautology and contradiction
• Equivalence of propositional statements
– Definition
– Proving equivalence (by truth table or equivalence
laws)
MS 101 - Discrete Mathematics 29
 Propositional Functions & Predicates
Propositional function (open sentence):
statement involving one or more variables,
e.g.: x-3 > 5.
Let us call this propositional function P(x),
where P is the predicate and x is the variable.
What is the truth value of P(2) ? false
What is the truth value of P(8) ? false
What is the truth value of P(9) ? true
When a variable is given a value, it is said to be
instantiated
Truth value depends on value of variable
MS 101 - Discrete Mathematics 30
 Propositional Functions
Let us consider the propositional function
Q(x, y, z) defined as:
x + y = z.
Here, Q is the predicate and x, y, and z are the
variables.
What is the truth value of Q(2, 3, 5) ? true
What is the truth value of Q(0, 1, 2) ? false
What is the truth value of Q(9, -9, 0) ? true
A propositional function (predicate) becomes a
proposition when all its variables are instantiated.
MS 101 - Discrete Mathematics 31
 Propositional Functions
Other examples of propositional functions
Person(x), which is true if x is a person
Person(Socrates) = T
Person(dolly-the-sheep) = F
CSCourse(x), which is true if x is a
computer science course
CSCourse(CMSC201) = T
CSCourse(MATH155) = F
How do we say
All humans are mortal
One CS course
MS 101 - Discrete Mathematics 32
 Universal Quantification
Let P(x) be a predicate (propositional function).

Universally quantified sentence:

For all x in the universe of discourse P(x) is true.

Using the universal quantifier :

x P(x) “for all x P(x)” or “for every x P(x)”

(Note: x P(x) is either true or false, so it is a

proposition, not a propositional function.)

MS 101 - Discrete Mathematics 33

 Universal Quantification
Example: Let the universe of discourse be all
people
S(x): x is a UMBC student.
G(x): x is a genius.
What does x (S(x)  G(x)) mean ?
“If x is a UMBC student, then x is a genius.” or
“All UMBC students are geniuses.”
If the universe of discourse is all UMBC students,
then the same statement can be written as
x G(x)
MS 101 - Discrete Mathematics 34
 Existential Quantification
Existentially quantified sentence:
There exists an x in the universe of discourse
for which P(x) is true.

Using the existential quantifier :

x P(x) “There is an x such that P(x).”
“There is at least one x such that P(x).”

(Note: x P(x) is either true or false, so it is a

proposition, but no propositional function.)

MS 101 - Discrete Mathematics 35

 Existential Quantification
Example:
P(x): x is a UMBC professor.
G(x): x is a genius.

What does x (P(x)  G(x)) mean ?

“There is an x such that x is a UMBC professor

and x is a genius.”
or
“At least one UMBC professor is a genius.”

MS 101 - Discrete Mathematics 36

 Quantification
Another example:
Let the universe of discourse be the real numbers.

What does xy (x + y = 320) mean ?

“For every x there exists a y so that x + y = 320.”

Is it true? yes

Is it true for the natural numbers? no

MS 101 - Discrete Mathematics 37

 Disproof by Counterexample
A counterexample to x P(x) is an object c so
that P(c) is false.

Statements such as x (P(x)  Q(x)) can be

disproved by simply providing a counterexample.

Statement: “All birds can fly.”

Disproved by counterexample: Penguin.

MS 101 - Discrete Mathematics 38

 Negation

(x P(x)) is logically equivalent to x (P(x)).

(x P(x)) is logically equivalent to x (P(x)).

See Table 2 in Section 1.3.

This is de Morgan’s law for quantifiers

MS 101 - Discrete Mathematics 39

 Negation
Examples
Not all roses are red
x (Rose(x)  Red(x))
x (Rose(x)  Red(x))

Nobody is perfect
x (Person(x)  Perfect(x))
x (Person(x)  Perfect(x))

MS 101 - Discrete Mathematics 40

 Nested Quantifier
A predicate can have more than one variables.
– S(x, y, z): z is the sum of x and y
– F(x, y): x and y are friends
We can quantify individual variables in different
ways
– x, y, z (S(x, y, z)  (x <= z  y <= z))
– x y z (F(x, y)  F(x, z)  (y != z)  F(y, z)

MS 101 - Discrete Mathematics 41

 Nested Quantifier
Exercise: translate the following English
sentence into logical expression
“There is a rational number in between every
pair of distinct rational numbers”

Use predicate Q(x), which is true when x

is a rational number
x,y (Q(x)  Q (y)  (x < y) 
u (Q(u)  (x < u)  (u < y)))

MS 101 - Discrete Mathematics 42

 Summary, Sections 1.3, 1.4
• Propositional functions (predicates)
• Universal and existential quantifiers,
and the duality of the two
• When predicates become propositions
– All of its variables are instantiated
– All of its variables are quantified
• Nested quantifiers
– Quantifiers with negation
• Logical expressions formed by
predicates, operators, and quantifiers
MS 101 - Discrete Mathematics 43