CIS 1103
DISCRETE STRUCTURES 1
FORMAL LOGIC
PART 2
MORE CONDITIONAL STATEMENTS
Recall:
Conditional statement: If p, then q: p → q
Converse: Reverse of the conditional statement
Converse: If q, then p: q → p
Inverse: Negation of the conditional statement
Inverse: If not p, then not q : ¬ p → ¬ q
Contrapositive: Negation of the converse
Contrapositive: If not q, then not p: ¬ q → ¬ p
MORE CONDITIONAL STATEMENTS
Facts:
1. Implication and contrapositive are equivalent. [p → q = ¬q → ¬p ]
2. Converse and inverse are equivalent. [q → p = ¬ p → ¬ q]
3. Neither converse nor inverse is equivalent to implication.
Truth Table
p q ¬p ¬q p→q q→p ¬q → ¬p ¬p → ¬q
T T F F T T T T
T F F T F T F T
F T T F T F T F
F F T T T T T T
MORE CONDITIONAL STATEMENTS: EXAMPLE
Given:
Consider the statement “If it rains today, then I will stay at home”
Tasks:
1. Find the p proposition and q proposition.
2. Find the converse of p → q : q → p.
3. Find the contrapositive of p → q : ¬ q → ¬ p.
4. Find the inverse of p → q : ¬ p → ¬ q.
LOGIC OPERATORS: BICONDITIONAL (↔)
Let p and q be propositions.
The biconditional statement p ↔ q is the proposition “p
if and only if q.”
The biconditional statement p ↔ q is True when p and q
have the same truth values, and is False otherwise.
Biconditional statements are also called bi-implications.
LOGIC OPERATORS: BICONDITIONAL (↔)
Truth Table
p q p↔q
T T T
T F F
F T F
F F T
BICONDITIONAL STATEMENT: EXAMPLE
Given:
Let p be a proposition “You get promoted” and let q be a proposition
“You have connections”
Tasks:
a) Determine the p ↔ q of the given propositions.
b) Determine the four cases that can be formulated from p ↔ q and
give the corresponding truth values for each case.
c) Identify the important implications of p ↔ q.
PRECEDENCE OF OPERATORS
Operator Precedence
¬ 1
Λ 2
V 3
→ 4
↔ 5
PRECEDENCE OF OPERATORS: EXAMPLES
1) ¬p Λ q means (¬p) Λ q
2) p Λ q → r means (p Λ q) → r
LOGICAL OPERATORS IN C
Operator Meaning Example
&& Logical AND. If c = 5 and d = 2, then expression
True only if all operands are true. ((c == 5) && (d > 5)) equals 0.
Logical OR. If c = 5 and d = 2, then expression
|| True only if either one operand is true. ((c == 5) || (d >5)) equals to 1.
Logical NOT. If c = 5, then expression
! True only if the operand is 0. !(c == 5) equals to 0.
LOGICAL FORMULAS TO ENGLISH SENTENCES
Compound propositions:
Logical formulas that can be constructed
using the logical operators or connectives.
LOGICAL FORMULAS TO ENGLISH SENTENCES: EXAMPLE
Given:
Consider the following propositions:
Proposition p: Alice is smart.
Proposition q: Alice is honest.
Logical formulas:
a) ¬p Λ q
b) p v (¬p Λ q)
c) p → ¬q
Task:
Translate each logical formula into an English sentence
TRUTH TABLE
It is a visual tool, in the form of a diagram with rows & columns,
that shows the truth or falsity of a compound premise.
In logic, it is a chart that shows the truth value of one or more
compound propositions for every possible combination of truth
values of the propositions making up the compound ones.
It can be used to test the validity of arguments.
Every proposition is assumed to be either true or false and the
truth or falsity of each proposition is said to be its truth value.
TRUTH TABLE
Each row of the table represents a possible combination of truth
values for the compound propositions of the compound, and
there should be enough rows to cover all possible
combinations.
If the compound contains just two component propositions,
there will be four possibilities and thus four rows to the table.
The truth value of the compound is indicated on each row under
the truth functional operator.
TRUTH TABLE: EXAMPLE 1
Given:
Consider the following compound proposition:
(p v ¬q) → (p Λ q).
Task:
Construct the truth table of the compound proposition.
TRUTH TABLE: EXAMPLE 2
Given:
Consider the following statement:
(¬ p Λ ¬ q) v (r Λ q) .
Task:
Construct the truth table of the compound statement.
DE MORGAN’S LAWS
Statement 1:
The negation of an AND proposition is logically equivalent to
the OR proposition in which each component is negated.
Symbolically: ¬(p Λ q) ≡ ¬p v ¬q
Statement 2:
The negation of an OR proposition is logically equivalent to
the AND proposition in which each component is negated.
Symbolically: ¬(p v q) ⇔ ¬p Λ ¬q)
DE MORGAN’S LAWS: EXAMPLE
Given:
Consider the following De Morgan’s Laws:
1. ¬(p Λ q) ≡ ¬p v ¬q
2. ¬(p v q) ⇔ ¬p Λ ¬q
Task:
Construct the truth table that will show the proof that each of the
De Morgan’s Laws is true.
DE MORGAN’S LAWS: IMPORTANT NOTES
De Morgan's Laws describe how mathematical
statements and concepts are related through their
opposites.
In set theory, De Morgan's Laws relate the
intersection and union of sets through complements.
DE MORGAN’S LAWS: IMPORTANT NOTES
In propositional logic, De Morgan's Laws relate conjunctions
and disjunctions of propositions through negation.
De Morgan's Laws are also applicable in computer
engineering for developing logic gates.
Interestingly, regardless of whether De Morgan's Laws apply to
sets, propositions, or logic gates, the structure is always the
same.
TAUTOLOGY
It is a statement form where its truth values in all rows in
the truth table are always true.
It is a proposition form that is always true regardless of
the truth values of the individual propositions substituted
for its proposition variables.
Note:
A proposition whose form is a tautology is called a
tautological proposition.
TAUTOLOGY: EXAMPLE
Given:
[(A→B) ∧ A] → B
Task:
Determine if the given statement above is a tautology
using truth table.
CONTRADICTION
It is a statement form where its truth values in all rows in the truth
table are always false.
It is a proposition form that is always false regardless of the truth
values of the individual propositions substituted for its proposition
variables.
Note:
A proposition whose form is a contradiction is called a
contradictory proposition.
CONTRADICTION: EXAMPLE
Given:
(A ∨ B) ∧ [(¬A) ∧ (¬B)]
Task:
Determine if the given statement above is a contradiction
using truth table.
CONTINGENCY
It is a statement form that is neither tautology nor
contradiction.
It is a formula which has both some true and some
false values for every value of its propositional
variables.
CONTINGENCY: EXAMPLE
Given:
(A ∨ B) ∧ (¬A)
Task:
Determine if the given statement above is a
contingency using truth table.
LOGICAL EQUIVALENCE
Two compound propositions p and q are logically equivalent if
their truth tables are the same.
Namely, p and q are logically equivalent if p ↔ q is a tautology.
If p and q are logically equivalent, we write p ≡ q.
p ≡ q if and only if p ↔ q is a tautology.
LOGICAL EQUIVALENCE: EXAMPLE 1
Given:
Consider the following two compound propositions:
p → q and q v ¬p
Tasks:
a) By using truth table, prove that the two compound
propositions are logically equivalent.
b) Using the same truth table, prove that the bi-implication of
the two given compound propositions is a tautology.
LOGICAL EQUIVALENCE: EXAMPLE 2
Given:
Consider the following two compound propositions:
p ⊕ q and ¬(p ↔ q)
Tasks:
a) By using truth table, prove that the two compound
propositions are logically equivalent.
b) Using the same truth table, prove that the bi-implication of
the two given compound propositions is a tautology.
LOGIC EQUIVALENCES
Given any statement variables p, q, and r, a tautology t and a
contradiction c, the following logical equivalences hold.
1. Commutative Laws: p q q p and p q q p
2. Associative Laws: (p q) r p (q r) and
(p q) r p (q r)
3. Distributive Laws: p (q r) (p q) (p r) and
p (q r) (p q) (p r)
4. Identity Laws: p t p and p c p
5. Negation Laws: p ~p c and p ~p t
LOGIC EQUIVALENCES
6. Double Negative Law: ~(~p) p
7. Idempotent Laws: p p p and p p p
8. De Morgan’s Laws: ~(p q) ~p ~q and
~(p q) ~p ~q
9. Universal Bound Laws: p c c and p t t
10. Absorption Laws: p (p q) p and
p (p q) p
11. Negation of t and c ~t c and ~c t
LOGIC EQUIVALENCES: EXAMPLE 1
Use the Logical Equivalence Laws to verify if the following is a
logical equivalence (simplifying statement forms):
~(~p q) (p q ) p
Solution:
~(~p q) (p q ) (~(~p) ~q) (p q ) by De Morgan’s laws
(p ~q) (p q ) by the double negative law
p (~q q ) by the distributive law
p ( q ~q ) by the commutative law
pc by the negation law
p by the identity law
PAIRWISE: EXERCISE 1
A logical equivalence is derived using the Logical Equivalence Laws.
Supply a reason for each step.
1) (p ~q) (p q) p (~q q) by (a)
p (q ~q) by (b)
pt by (c)
p by (d)
Therefore, (p ~q) (p q) p.
2) (p ~q) (~p ~q) (~q p) (~q ~p) by (a)
~q (p ~p) by (b)
~q c by (c)
~q by (d)
Therefore, (p ~q) (~p ~q) ~q.
ASSIGNMENT
Use Logical Equivalence Laws to verify the logical equivalences
of the following:
1) (p ~q) p p
2) p (~q p) p
3) ~(p ~q) (~p ~q) ~p
4) ~((~p q) (~p ~q)) (p q) p
5) (p (~(~p q))) (p q) p
Reflection: In not more than 5 sentences, write your comments regarding
the complexity or significance of the assignment. Did you answer it
independently? or needed help and from whom?
MORE PRACTICE: EXERCISE 2
Use Logical Equivalence Laws to verify the logical equivalences
of the following:
1) (p ~q) q p q
2) ~p (p q) ~p q
3) [ ~ (p q) (p q)] T
4) ~ (p (~p q)) (~p ~q)
LOGICAL EQUIVALENCES
