COSC 50 –DISCRETE STRUCTURE I
COSC 50-DISCRETE STRUCTURE I
1st Semester, AY 2022-2023
AIDA M. PENSON
Instructor
Let’s Start! COSC 50 –DISCRETE STRUCTURE I
COSC 50 –DISCRETE STRUCTURE I
Objectives:
▪ Explain material from logical equivalence;
▪ Identify the validity of arguments using truth table and
explain the formal proof of invalidity
COSC 55 –DISCRETE STRUCTURE II
COSC 50 –DISCRETE STRUCTURE I
Lesson 1: Material Equivalence
Let’s Start! COSC 55 –DISCRETE STRUCTURE II
COSC 50 –DISCRETE STRUCTURE I
Material Equivalence
Two propositions are materially equivalent if and only if they have the
same truth value for every assignment of truth values to the atomic
propositions. That is, they have the same truth values on every row of a
truth table.
COSC 55 –DISCRETE STRUCTURE II
COSC 50 –DISCRETE STRUCTURE I
Material Equivalence
Prove that “¬S → R” and “S v R” are materially equivalent.
s r ̃s ¬s → r svr
T T F T T
T F F T T
F T T T T
F F T F F
COSC 55 –DISCRETE STRUCTURE II
COSC 50 –DISCRETE STRUCTURE I
Material Equivalence
COSC 55 –DISCRETE STRUCTURE II
COSC 50 –DISCRETE STRUCTURE I
Material Equivalence
We can prove these two statements are materially equivalent with a truth
table
S q ¬p ¬q pvq ¬p . ¬q ¬(p v q)
T T F F T F F
T F F T T F F
F T T F T F F
F F T T T
T F
COSC 55 –DISCRETE STRUCTURE II
COSC 50 –DISCRETE STRUCTURE I
Material Equivalence
There is a fifth truth functional connective called “material equivalence” or the
“biconditional” that is defined as true when the atomic propositions share the same
truth value, and false when the truth values different.
The biconditional is represented using the symbol “≡” which is called a “tribar.”
p q p≡q
T T T
T F F
F T F
F F T
COSC 55 –DISCRETE STRUCTURE II
COSC 50 –DISCRETE STRUCTURE I
Let’s try this!
Construct a truth table to determine whether the following pairs of statements
are materially equivalent
1. A → B and ¬A ˅ B
A B ¬A A→B ¬A ˅ B
T T F T T
T F F F F
F T T T T
F F T T T
COSC 05 –DISCRETE STRUCTURE I
COSC 50 –DISCRETE STRUCTURE I
Lesson 2: Logical Equivalence
Let’s Start! COSC 55 –DISCRETE STRUCTURE II
COSC 50 –DISCRETE STRUCTURE I
Logical Equivalence
COSC 55 –DISCRETE STRUCTURE II
COSC 50 –DISCRETE STRUCTURE I
Testing by 1st method (Matching truth table)
Prove : ¬(P∨Q) and [(¬P)∧(¬Q)] are equivalent
P Q ¬P ¬Q P vQ ¬(P vQ) ¬P ˄ ¬Q
T T F F T F F F
T F F T T F F F
F T T F T F F F
F F T T F T T T
COSC 55 –DISCRETE STRUCTURE II
COSC 50 –DISCRETE STRUCTURE I
Testing by 2nd method (bi-conditionality)
Prove : [¬(P∨Q)] ↔ [(¬P)∧(¬Q)] are equivalent
P Q ¬P ¬Q P vQ ¬(P vQ) ¬P ˄ ¬Q [¬(P∨Q)] ↔ [(¬P)∧(¬Q)]
T T F F T F F T
T F F T T F F T
F T T F T F F T
F F T T F T T T
COSC 55 –DISCRETE STRUCTURE II
COSC 55 –DISCRETE STRUCTURE II
COSC 55 –DISCRETE STRUCTURE II
COSC 50 –DISCRETE STRUCTURE I
• Contrapositive: ¬Q→¬P
COSC 50 –DISCRETE STRUCTURE I
COSC 50 –DISCRETE STRUCTURE I
P Q
Conditional Statement − “If you do your homework, you will not be punished.”
Inverse: ¬P→¬Q
If you do not do your homework, you will be punished.
Converse: Q→P
If you will not be punished, you do your homework
Contrapositive: ¬Q→¬P
If you are punished, you did not do your homework
COSC 50 –DISCRETE STRUCTURE I
COSC 50 –DISCRETE STRUCTURE I
Let’s try this!
If a figure is a quadrilateral, then it is a polygon
Inverse:
If a figure is not a quadrilateral, then it is not a polygon
Converse:
T T
If it is a polygon, then a figure is a quadrilateral
T F
T
Contrapositive:
F
FIf it is
F not a polygon, then a figure is a not quadrilateral
COSC 05 –DISCRETE STRUCTURE I
COSC 50 –DISCRETE STRUCTURE I
Lesson 3:
Testing for Argument Validity
Let’s Start! COSC 55 –DISCRETE STRUCTURE II
COSC 50 –DISCRETE STRUCTURE I
In Mathematics and Logic, ARGUMENT is not a dispute. It is a sequence of
statements ending in a conclusion.
Example:
If Socrates is a man, then Socrates is mortal.
Socrates is a man.
Therefore, Socrates is mortal.
COSC 55 –DISCRETE STRUCTURE II
COSC 50 –DISCRETE STRUCTURE I
COSC 55 –DISCRETE STRUCTURE II
COSC 50 –DISCRETE STRUCTURE I
Logical Form
An argument form is valid if, no matter what statements are substituted for the
premises statement variables, if the premises are all true, then the conclusion is
also true. The truth of the conclusion must follow necessarily from the truth of
the premises.
COSC 50 –DISCRETE STRUCTURE I
COSC 50 –DISCRETE STRUCTURE I
COSC 50 –DISCRETE STRUCTURE I
COSC 50 –DISCRETE STRUCTURE I
1st premise
COSC 50 –DISCRETE STRUCTURE I
COSC 50 –DISCRETE STRUCTURE I
P→Q ˅ ¬R
Q→P ∧ R
2nd premise Conclusion
P→R 1st premise
P Q R ¬Q ¬R Q v ¬R P ∧ R P → Q ˅ ¬R Q → P ∧ R P→R
T T T F F T T T T T
T T F F T T F T F F
T F T T F F T F T T
T F F T T T F T T F
F T T F F T F T F T
F T F F T T F T F T
F F T T F F F T T T
F F F T T T F T T T
COSC 50 –DISCRETE STRUCTURE I
COSC 50 –DISCRETE STRUCTURE I
Let’s try this!
Construct a truth table to determine whether the following pairs of statements
are materially equivalent
1. A → B and ¬A ˅ B
A B ¬A A→B ¬A ˅ B
T T F T T
T F F F F
F T T T T
F F T T T
COSC 50 –DISCRETE STRUCTURE I
COSC 55 –DISCRETE STRUCTURE II
COSC 55 –DISCRETE STRUCTURE II
