CS 3505

Discrete Mathematical Structures

Faria Jameel
[email protected]
Consultation hours: 12.30pm-1.30pm Mon-Thu
Grading

 Assignments (1): 10 marks

 Test: 10 marks
 Midterm: 25
 Final: 35
 Project: 10
 Presentation: 5
 Class Participation: 5

Policies
 No late homework accepted.
 Written solutions must be your own

12/22/2020
Expectations

 This is really a fun course!

 This class contains some of the most beautiful math you’ll ever learn.
 It’s even useful, beyond giving you techniques to use solving the puzzles
in Games Magazine.

Hints for success

 Read the textbook.
 Lectures really do help!
 Set up study groups.
 Do revise at home.

12/22/2020
Propositional Logic
 Statement (Proposition)

A Statement is a sentence that is either True or False

Examples: 2+2=4 True

3x3=8 False

787009911 is a prime

Non-examples: x+y>0

x2+y2=z2

They are true for some values of x and y

but are false for some other values of x and y.
 Logic Operators

 :: NOT ~p is true if p is false

 :: AND  :: OR

P Q P Q P Q P Q
T T T T T T
T F F T F T
F T F F T T
F F F F F F
 Compound Statement

p = “it is hot” q = “it is sunny”

It is hot and sunny

It is not hot but sunny

It is neither hot nor sunny

Propositional Logic - negation

Suppose p is a proposition.
The negation of p is written p and has meaning:
“It is not the case that p.”

 Maths is NOT Aliya’s favorite class.

p p
Truth table for negation:
T F Notice that
F T p is a
proposition!
12/22/2020
Propositional Logic - conjunction

Conjunction corresponds to English “and.”

p  q is true exactly when p and q are both true.

 Eg Vivien is curious AND clever.

p q pq

Truth table for conjunction: T T T

T F F
F T F
F F F
12/22/2020
Propositional Logic - disjunction

Disjunction corresponds to English “or.”

p  q is when p or q (or both) are true.

 Ex. Atif is brave OR nuts.

p q pq

Truth table for disjunction: T T T

T F T
F T T
F F F
12/22/2020
Propositional Logic - implication

Implication: p  q corresponds to English “if p then q,” or “p

implies q.”
 If it is raining then it is cloudy.
 If there are 200 people in the room, then I am the Easter
Bunny.
 If p then 2+2=4.

p q pq

Truth table for implication: T T T

T F F
F T T
F F T
12/22/2020
 Exclusive-Or

coffee “or” tea  exclusive-or

How to construct a compound statement for exclusive-or?

Idea 1: Look at the true rows

p q pq
T T F Want the formula to be true
exactly when the input belongs
T F T
to a “true” row.
F T T
F F F

The input is the second row exactly if this sub-formula is satisfied

And the formula is true exactly when the input is the second row or the third row.
 Exclusive-Or

coffee “or” tea  exclusive-or

How to construct a compound statement for exclusive-or?

Idea 2: Look at the false rows

p q pq
T T F Want the formula to be true
exactly when the input does
T F T
not belong to a “false” row.
F T T
F F F

The input is the first row exactly if this sub-formula is satisfied

And the formula is true exactly when the input is not in the 1st row and the 4th row.
 Logical Equivalence

Idea 3: Guess and check

p q
T T F T F F
T F T T T T
F T T T T T
F F F F T F

Logical equivalence: Two statements have the same truth table

As you see, there are many different ways to write the same logical formula.
One can always use a truth table to check whether two statements are equivalent.
 Writing Logical Formula for a Truth Table

Digital logic:

Given a digital circuit, we can construct the truth table.

Now, suppose we are given only the truth table (i.e. the specification),
how can we construct a circuit (i.e. formula) that has the same function?
 Writing Logical Formula for a Truth Table

Use idea 1 or idea 2. Idea 1: Look at the true rows

and take the “or”.

p q r output
T T T F
T T F T
T F T T
T F F F
F T T T
F T F T
F F T T
F F F F

The formula is true exactly when the input is one of the true rows.
 Writing Logical Formula for a Truth Table

Idea 2: Look at the false rows,

negate and take the “and”.

p q r output
T T T F
T T F T
T F T T
T F F F
F T T T
F T F T
F F T T
F F F F

The formula is true exactly when the input is not one of the false row.
 DeMorgan’s Laws
Logical equivalence: Two statements have the same truth table

Statement: Tom is in the football team and the basketball team.

Negation: Tom is not in the football team or not in the basketball team.

De Morgan’s Law

Statement: The number 783477841 is divisible by 7 or 11.

Negation: The number 783477841 is not divisible by 7 and not divisible by 11.

De Morgan’s Law
 DeMorgan’s Laws
Logical equivalence: Two statements have the same truth table

De Morgan’s Law

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

De Morgan’s Law
 Simplifying Statement

DeMorgan

Distributive law

See textbook for more identities.

 Tautology, Contradiction
A tautology is a statement that is always true.

A contradiction is a statement that is always false. (negation of a tautology)

In general it is “difficult” to tell whether a statement is a contradiction.

It is one of the most important problems in CS – the satisfiability problem.
 Checkpoint

Key points to know.

1. Write a logical formula from a truth table.

2. Check logical equivalence of two logical formulas.

3. DeMorgan’s rule and other simple logical rules (e.g. distributive).

4. Use simple logical rules to simplify a logical formula.

 Logical Form

• Initial terms in logic: sentence, true, false

• Statement (proposition) is a sentence that is true or false but not both

• Compound statement is a statement built out of simple statements

using logical operations: negation, conjunction, disjunction
 Logical Form

• Truth table

• Precedence of logical operations

• English words to logic:

– It is not hot but it is sunny
– It is neither hot nor sunny

• Statement form (propositional form) is an expression made up of

statement variables and logical connectives (operators)

• Exclusive OR: XOR

 Logical Form

• Truth table for (~p  q)  (q  ~r)

• Two statements are called logically equivalent if and only if (iff) they have
identical truth tables

• Double negation

• Non-equivalence: ~(p  q) vs ~p  ~q

• De Morgan’s Laws:

– The negation of and AND statement is logically equivalent to the OR

statement in which component is negated

– The negation of an OR statement is logically equivalent to the AND

statement in which each component is negated
 Logical Form

• Applying De-Morgan’s Laws:

– Write negation for

• The bus was late or Tom’s watch was slow

• -1 < x <= 4

• Tautology is a statement that is always true regardless of the truth

values of the individual logical variables

• Contradiction is a statement that is always false regardless of the

truth values of the individual logical variables
 Logical Equivalence
• Commutative laws: p  q = q  p, p  q = q  p

• Associative laws: (p  q)  r = p  (q  r), (p  q)  r = p  (q  r)

• Distributive laws: p  (q  r) = (p  q)  (p  r)
p  (q  r) = (p  q)  (p  r)

• Identity laws: p  t = p, p  c = p

• Negation laws: p  ~p = t, p  ~p = c

• Double negative law: ~(~p) = p

• Idempotent laws: p  p = p, p  p = p

• De Morgan’s laws: ~(p  q) = ~p  ~q, ~(p  q) = ~p  ~q

• Universal bound laws: p  t = t, p  c = c

• Absorption laws: p  (p  q) = p, p  (p  q) = p

• Negation of t and c: ~t = c, ~c = t
 Exercises

• Simplify: ~(~p  q)  (p  q)

• Write truth table for: (p  (~p  q))  ~(q  ~r)

• Simplify: p XOR p, (p XOR p) XOR p

• Is XOR associative?

• Is XOR distributive with respect to AND?

Propositional Logic -

A tautology is a proposition that’s always TRUE.

A contradiction is a proposition that’s always FALSE.

p p p  p p  p
T F T F
F T T F

12/22/2020
Propositional Logic -

if NOT (blue AND NOT red) OR red then…

(p  q)  q  p  q

(p  q)   (p  q)  DeMorgan’s

q q
 (p  q)  Double negation
q
 p  (q  Associativity
q)
 p  q Idempotent

12/22/2020
Propositional Logic - proof

 Show that [p  (p  q)]  q is a tautology.

 We use  to show that [p  (p  q)]  q  T.
[p  (p  q)]  q
 [p  (p  q)]  substitution
q
 [(p  p)  (p  q)]  
for
distributive
q
 [ F  (p  q)]  q uniqueness
 (p  q)  q identity
 (p  q)  q substitution
 (p  q)  q for 
DeMorgan’s
 p  (q  q ) associative
 p  T excluded middle
 T domination
12/22/2020
 Tautologies, contradictions, contingencies

DEF: A compound proposition is called a tautology if no matter what

truth values its atomic propositions have, its own truth value is T.
EG: p  ¬p (Law of excluded middle)

The opposite to a tautology, is a compound proposition that’s always

false –a contradiction.
EG: p  ¬p

On the other hand, a compound proposition whose truth value isn’t

constant is called a contingency.
EG: p  ¬p

L3 32
 Tautologies and contradictions

The easiest way to see if a compound proposition is

tautology/contradiction is to use a truth table.

p p p p p p p p
F T T F T F
T F T T F F

L3 33
 Tautology example (1.2.8.a)
Part 1

Demonstrate that
[¬p (p q )]q
is a tautology in two ways:

1. Using a truth table – show that [¬p (p q )]q is always true

2. Using a proof (will get to this later).

L3 34
 Tautology by truth table

p q ¬p p q ¬p (p q ) [¬p (p q )]q

T T

T F

F T

F F

L3 35
 Tautology by truth table

p q ¬p p q ¬p (p q ) [¬p (p q )]q

T T F

T F F

F T T

F F T

L3 36
 Tautology by truth table

p q ¬p p q ¬p (p q ) [¬p (p q )]q

T T F T

T F F T

F T T T

F F T F

L3 37
 Tautology by truth table

p q ¬p p q ¬p (p q ) [¬p (p q )]q

T T F T F

T F F T F

F T T T T

F F T F F

L3 38
 Tautology by truth table

p q ¬p p q ¬p (p q ) [¬p (p q )]q

T T F T F T

T F F T F T

F T T T T T

F F T F F T

L3 39
 Tautologies, contradictions and programming

Tautologies and contradictions in your code usually correspond to poor

programming design. EG:

• while(x <= 3 || x > 3)

x++;
• if(x > y)
if(x == y)
return “never got here”;

L3 40
 Which is true?

Which is false?

“The sentence below is false.”

“The sentence above is true.”