Discrete Structures (CMP-2111)

LECTURE 2
Previous Lecture Summery

• Introduction to the Course

• Propositions
• Logical Connectives
• Truth Tables
• Compound propositions
• Translating English to logic and logic to
English.
Today’s Lecture

• Logical Equivalences.
• De Morgan’s laws.
• Tautologies and Contradictions.
• Laws of Logic.
• Conditional propositions.
Logical Equivalence

Definition
Two Propositional Forms are called logically
equivalent if and only if they have identical truth
values for each possible substitution of propositions
for their propositional variables.

The logical equivalence of proposition forms P

and Q is written
P≡Q
Equivalence of Two Compound
Propositions P and Q

1. Construct the truth table for P.

2. Construct the truth table for Q using the
same proposition variables for identical
component propositions.
3. Check each combination of truth values of
the proposition variables to see whether the
truth value of P is the same as the truth
value of Q.
Equivalence Check

a. If in each row the truth value of P is the

same as the truth value of Q, then P and Q
are logically equivalent.

b. If in some row P has a different truth value

from Q, then P and Q are not logically
equivalent.
Example

• Prove that ¬ (¬p)≡ p

Solution

p ¬p ¬ (¬p)
T F T
F T F

As you can see the corresponding truth values of p

and ¬ (¬p) are same, hence equivalence is justified.
Example
Show that the proposition forms ¬(pq) and ¬p  ¬q
are NOT logically equivalent.

p q ¬p ¬q (pq) ¬(pq) ¬pv¬q

T T F F T F F
T F F T F T F
F T T F F T F
F F T T F T T
Here the corresponding truth values
differ and hence equivalence does not hold
De Morgan’s laws
De Morgan’s laws state that:
The negation of an and proposition is
logically equivalent to the or proposition in
which each component is negated.

The negation of an or proposition is logically

equivalent to the and proposition in which
each component is negated.
Symbolically (De Morgan’s Laws)

1. ¬(pq) ≡ ¬p¬q

2. ¬(pq) ≡ ¬p¬q
Applying De-Morgan’s Law
Question: Negate the following compound Propositions

1. John is six feet tall and he weights at least 200

pounds.

2. The bus was late or Tom’s watch was slow.

Solution

a) John is not six feet tall or he weighs less

than 200 pounds.

b) The bus was not late and Tom’s watch

was not slow.
Inequalities and De Morgan’s Laws

Question Use De Morgan’s laws to write the negation of


-1< x 4
Solution: The given proposition is equivalent to

-1 < x and x 4,
By De Morgan’s laws, the negation is

-1 ≥ x or x > 4.
Tautology and Contradiction

Definition A tautology is a proposition form that is

always true regardless of the truth values of the
individual propositions substituted for its proposition
variables. A proposition whose form is a tautology is
called a tautological proposition.

Definition A contradiction is a proposition form that is

always false regardless of the truth values of the
individual propositions substituted for its proposition
variables. A proposition whose form is a contradiction
is called a contradictory proposition.
Example
Show that the proposition form p¬p is a
tautology and the proposition form p¬p is a
contradiction.

p ¬p p ¬p p ¬p
T F T F
F T T F

Exercise: If t is a tautology and c is

contradiction, show that pT≡ Tand pc≡c?
 Laws of Logic

1. Commutative laws
pq ≡ qp ; pq ≡ qp

2. Associative laws
p  (q  r) ≡ (p q)  r ; p(q r) ≡ (pq)r

3. Distributive laws
p  (q  r ) ≡ (p  q)  (p  r)
p  (q  r) ≡ (p  q)  (p  r)
Laws of Logic

4. Identity laws
p  t ≡ p ; pc ≡ p

5. Negation laws
p¬p ≡ t ; p  ¬p ≡ c

6. Double negation law

¬(¬p) ≡ p

7. Idempotent laws
p  p ≡ p ; pp ≡ p
Laws of Logic

8. Universal bound laws

pt≡t ;pc≡ c

9. Absorption laws
p (pq) ≡ p ; p (p  q) ≡ p

10. Negation of t and c

¬t ≡ c ; ¬c ≡ t
Exercise

Using laws of logic, show that

⌐(⌐p  q) (p  q) ≡ p.
Solution
Take ⌐(⌐p  q) (p  q)
≡ (⌐(⌐p)  ⌐q) (p  q), (by De Morgan’s laws)
≡ (p  ⌐q) (p  q), (by double negative law)
≡ p (⌐q  q), (by distributive law)
contd…

≡ p (q  ⌐q), (by the commutative law)

≡ p  c, (by the negation law)

≡ p, (by the identity law)

Skill in simplifying proposition forms is useful in

constructing logically efficient computer programs
and in designing digital circuits.
 Lecture Summary

• Logical Equivalence
• Equivalence Check
• Tautologies and Contradictions
• Laws of Logic
• Simplification of Compound Propositions
Another Example
Prove that ¬[r ∨ (q ∧ (¬r →¬p))] ≡ ¬r ∧ (p∨ ¬q)

¬[r ∨ (q ∧ (¬r → ¬p))]

≡ ¬r ∧ ¬(q ∧ (¬r → ¬p)), De Morgan’s law
≡ ¬r ∧ ¬(q ∧ (¬¬r ∨ ¬p)), Conditional rewritten as disjunction
≡ ¬r ∧ ¬(q ∧ (r ∨¬p)), Double negation law
≡ ¬r ∧ (¬q ∨ ¬(r ∨ ¬p)), De Morgan’s law
≡ ¬r ∧ (¬q ∨ (¬r ∧ p)), De Morgan’s law, double negation
≡ (¬r ∧¬q) ∨ (¬r ∧ (¬r ∧ p)), Distributive law
≡ (¬r ∧¬q) ∨ ((¬r ∧ ¬r) ∧ p), Associative law
≡ (¬r ∧¬q) ∨ (¬r ∧ p), Idempotent law
≡ ¬r ∧ (¬q ∨ p), Distributive law
≡ ¬r ∧ (p ∨¬q), Commutative law
CONDITIONAL PROPOSITIONS

DEFINITION
IF P AND Q ARE PROPOSITIONS, THE CONDITIONAL OF Q BY
P IS IF P THEN Q OR P IMPLIES Q AND IS DENOTED BY P→Q.
IT IS FALSE WHEN P IS TRUE AND Q IS FALSE OTHERWISE IT
IS TRUE.

EXAMPLES
IF YOU WORK HARD THEN YOU WILL SUCCEED.
IF SARA LIVES IN ISLAMABAD, THEN SHE LIVES IN
PAKISTAN.
Implication (if - then)

• Binary Operator, Symbol: 

P Q PQ
T T T
T F F
F T T
F F T
Interpreting Conditional Statements
Examples
“The online user is sent a notification of a link error if
the network link is down”.
The statement is equivalent to
“If the network link is down, then the online user is sent a
notification of a link error.”
Using
p : The network link is down,
q : the online user is sent a notification of a link error.

The statement becomes (q if p)

p → q.
Examples
“When you study the theory, you understand the
material”.
The statement is equivalent to (using if for when)
“If you study the theory, then you understand the material.”
Using
p : you study the theory,
q : you understand the material.

The statement becomes (when p, q)

p → q.
Examples

“Studying the theory is sufficient for solving the

exercise”.

The statement is equivalent to

“If you study the theory, then you can solve the exercise.”
Using
p : you study the theory,
q : you can solve the exercise.

The statement becomes (p is sufficient for q)

p → q.
 ACTIVITY

• SHOW THAT
P→Q ≡ ¬P  Q

THIS SHOWS THAT A CONDITIONAL PROPOSITION IS SIMPLE A PROPOSITION

FORM THAT USES A NOT AND AN OR.

• SHOW THAT
¬(P→Q) ≡ P  ¬Q

THIS MEANS THAT NEGATION OF ‘IF P THEN Q’ IS LOGICALLY EQUIVALENT

TO ‘P AND NOT Q’.
SOLUTION

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

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

FROM THE ABOVE TABLE IT IS OBVIOUS THAT CONDITIONAL

PROPOSITION IS EQUIVALENT TO A “NOT OR PROPOSITION”
AND THAT ITS NEGATION IS NOT OF THE FORM ‘IF THEN’.
NEGATIONS OF SOME CONDITIONALS

PROPOSITION: IF MY CAR IS IN THE REPAIR SHOP, THEN I

CANNOT GET THE CLASS.
NEGATION: MY CAR IS IN THE REPAIR SHOP AND I CAN GET
THE CLASS.

PROPOSITION: IF SARA LIVES IN ATHENS, THEN SHE LIVES IN

GREECE.
NEGATION: SARA LIVES IN ATHENS AND SHE DOES NOT LIVE
IN GREECE.
 DEFINITION
THE CONTRAPOSITIVE OF A CONDITIONAL PROPOSITION OF THE FORM ‘IF P THEN
Q’ IS ‘IF ¬Q THEN ¬P’. SYMBOLICALLY, THE CONTRAPOSITIVE OF P→Q IS ¬Q→¬P.

A CONDITIONAL PROPOSITION IS LOGICALLY EQUIVALENT TO ITS CONTRA-

POSITIVE.

EXAMPLE
IF TODAY IS SUNDAY, THEN TOMORROW IS MONDAY.

CONTRAPOSITIVE:
IF TOMORROW IS NOT MONDAY, THEN TODAY IS NOT SUNDAY.
TRAPOSITION
 CONVERSE AND INVERSE OF THE
CONDITIONAL
SUPPOSE A CONDITIONAL PROPOSITION OF THE FORM
‘IF P THEN Q’ IS GIVEN.

1.THE CONVERSE IS ‘IF Q THEN P’.

2.THE INVERSE IS ‘IF ⌐P THEN ⌐Q’.

SYMBOLICALLY,
THE CONVERSE OF P→Q IS Q→P,
AND
THE INVERSE OF P→Q IS ⌐P→⌐Q.
THE BICONDITIONAL
DEFINITION GIVEN PROPOSITION VARIABLES P AND Q, THE
BICONDITIONAL OF P AND Q IS P IF AND ONLY IF Q AND IS
DENOTED P↔Q.
IT IS TRUE IF BOTH P AND Q HAVE THE SAME TRUTH VALUES
AND IS FALSE IF P AND Q HAVE OPPOSITE TRUTH VALUES.
THE WORDS IF AND ONLY IF ARE SOMETIME ABBREVIATED
IFF.

EXAMPLE THIS COMPUTER PROGRAM IS CORRECT IFF IT

PRODUCES THE CORRECT ANSWER FOR ALL POSSIBLE SETS
OF INPUT DATA.
TRUTH TABLE
p q p↔q
T T T
T F F
F T F
F F T

p q p→q q→p p↔q (p→q) (q→p)

T T T T T T
T F F T F F
F T T F F F
F F T T T T
Interpreting Necessary and sufficient conditions

“If a number is divisible by 10, then it is divisible by 2”.

The clause introduced by If A number is divisible by 10” is called
the hypothesis.  It is what we are given, or what we may assume.
The clause introduced by then It is divisible by 2 is called
the conclusion. It is the statement that "follows" from the
hypothesis.
When the If-then sentence is true, we say that the hypothesis is a
sufficient condition for the conclusion. Thus it is sufficient to know
that a number is divisible by 10, in order to conclude that it is
divisible by 2.
The conclusion is then called a necessary condition of that
hypothesis. For, if a number is divisible by 10,
it necessarily follows that it will be divisible by 2.
INTERPRETING NECESSARY AND SUFFICIENT
CONDITIONS
EXAMPLE: CONSIDER THE PROPOSITION

‘IF JOHN IS ELIGIBLE TO VOTE THEN HE IS AT LEAST 18

YEAR OLD’.

THE TRUTH OF THE CONDITION ‘JOHN IS ELIGIBLE TO VOTE’

IS SUFFICIENT TO ENSURE THE TRUTH OF THE CONDITION
‘JOHN IS AT LEAST 18 YEAR OLD’.

IN ADDITION, THE CONDITION ‘JOHN IS AT LEAST 18 YEAR

OLD’ IS NECESSARY FOR THE CONDITION ‘JOHN IS ELIGIBLE
TO VOTE’ TO BE TRUE. IF JOHN WERE YOUNGER THAN 18,
THEN HE WOULD NOT ELIGIBLE TO VOTE.
 NECESSARY AND SUFFICIENT
CONDITIONS
LET R AND S ARE TWO PROPOSITIONS

R IS A SUFFICIENT CONDITION FOR S MEANS ‘IF R THEN S’.

R IS A NECESSARY CONDITION FOR S MEANS ‘IF NOT R THEN NOT S’

R IS NECESSARY AND SUFFICIENT CONDITION FOR S MEANS ‘R IF

AND ONLY IF S’
Lecture Summary

• Logical Equivalence
• Equivalence Check
• Tautologies and Contradictions
• Laws of Logic
• Simplification of Compound Propositions