Discrete Structures

Lecture # 5

PMAS- Arid Agriculture University, Rawalpindi

Recap

1. Application of Predicates
2. Simplification
3. Conditional Statements and Implications
4. Truth Tables
5. Translation NLP to Symbols
6. Laws of Implication
7. Negation of Implication
8. Inverse of Implication
9. Converse of Implication
10.Contrapositive
 Bi-Conditional Statement

If p and q are statement variables, the bi-

condition of p and q is “p if and only if q” and
is denoted as “p ↔ q”

The word “if and only if” are sometimes

abbreviated “iff”.

The double headed arrow “↔” is bi-conditional

operator.
Truth Table for Bi-Conditional Statement p ↔ q

p q p↔q
F F T
F T F
T F F
T T T
 Bi-Conditional Statement p ↔ q -- Example

1. 1 + 1 = 3 if and only if earth is flat True

2. Sky is blue if and only if 1 = 0

False

3. Milk is white if and only if birds lay eggs True

4. 33 is divisible by 4 iff horse has four legs

False

5. x > 5 iff x2 > 25 False

Bi-Conditional Statement – Logical Equivalence

p ↔ q ≡ (p  q) ∧ (q  p)

p q p↔q pq qp (p  q) ∧ (q  p)

T T T
T F F
F T F
F F T
Bi-Conditional Statement – Logical Equivalence

p ↔ q ≡ (p  q) ∧ (q  p)

p q p↔q pq qp (p  q) ∧ (q  p)

T T T T T
T F F F T
F T F T F
F F T T T
Bi-Conditional Statement – Logical Equivalence

p ↔ q ≡ (p  q) ∧ (q  p)

p q p↔q pq qp (p  q) ∧ (q  p)

T T T T T T
T F F F T F
F T F T F F
F F T T T T
Rephrasing Bi-Conditional

p ↔ q is also expressed as:

“p is necessary and sufficient for q”

“If p then q, and conversely”

“p is equivalent to q”
 Bi-Conditional – Examples

1. If it is hot outside you buy an ice cream cone, and if you buy
an ice cream cone it is hot outside.
• Sol: You buy an ice cream cone if and only if it is hot
outside.

2. For you to win the contest it is necessary and sufficient that

you have the only winning ticket.
• Sol: You win the contest if and only if you hold the only
winning ticket.

3. If you read the news paper every day, you will be informed and
conversely.
• Sol: You will be informed if and only if you read the news
paper every day.
Truth Table for (p  q) ↔ (~q  ~p) ≡ t

p q ~p ~q p  q ~q  ~p (p  q) ↔ (~q  ~p)
T T
T F
F T
F F
Truth Table for (p  q) ↔ (~q  ~p) ≡ t

p q ~p ~q p  q ~p  ~q (p  q) ↔ (~q  ~p)
T T F F T
T F F T F
F T T F T
F F T T T
Truth Table for (p  q) ↔ (~q  ~p) ≡ t

p q ~p ~q p  q ~p  ~q (p  q) ↔ (~q  ~p)
T T F F T T
T F F T F F
F T T F T T
F F T T T T
Truth Table for (p  q) ↔ (~q  ~p) ≡ t

p q ~p ~q p  q ~p  ~q (p  q) ↔ (~q  ~p)
T T F F T T T
T F F T F F T
F T T F T T T
F F T T T T T
Truth Table for (p ↔ q) ↔ (r ↔ q)

p q r p↔q r↔q (p ↔ q) ↔ (r ↔ q)
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F
Truth Table for (p ↔ q) ↔ (r ↔ q)

p q r p↔q r↔q (p ↔ q) ↔ (r ↔ q)
T T T T
T T F T
T F T F
T F F F
F T T F
F T F F
F F T T
F F F T
Truth Table for (p ↔ q) ↔ (r ↔ q)

p q r p↔q r↔q (p ↔ q) ↔ (r ↔ q)
T T T TDF T
T T F T F
T F T F F
T F F F T
F T T F T
F T F F F
F F T T F
F F F T T
Truth Table for (p ↔ q) ↔ (r ↔ q)

p q r p↔q r↔q (p ↔ q) ↔ (r ↔ q)
T T T T T T
T T F T F F
T F T F F T
T F F F T F
F T T F T F
F T F F F T
F F T T F F
F F F T T T
Truth Table for p ∧ ~r ↔ q ∨ r

p q r ~r p∧ q ∨ r p ∧ ~r ↔ q ∨ r
~r
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F
Truth Table for p ∧ ~r ↔ q ∨ r

p q r ~r p∧ q ∨ r p ∧ ~r ↔ q ∨ r
~r
T T T F
T T F T
T F T F
T F F T
F T T F
F T F T
F F T F
F F F T
Truth Table for p ∧ ~r ↔ q ∨ r

p q r ~r p∧ q ∨ r p ∧ ~r ↔ q ∨ r
~r
T T T F F
T T F T T
T F T F F
T F F T T
F T T F F
F T F T F
F F T F F
F F F T F
Truth Table for p ∧ ~r ↔ q ∨ r

p q r ~r p∧ q ∨ r p ∧ ~r ↔ q ∨ r
~r
T T T F F T
T T F T T T
T F T F F T
T F F T T F
F T T F F T
F T F T F T
F F T F F T
F F F T F F
Truth Table for p ∧ ~r ↔ q ∨ r

p q r ~r p∧ q ∨ r p ∧ ~r ↔ q ∨ r
~r
T T T F F T F
T T F T T T T
T F T F F T F
T F F T T F F
F T T F F T F
F T F T F T F
F F T F F T F
F F F T F F T
Truth Table for ~p ↔ q ≡ p ↔ ~q

p q ~p ~q ~p ↔ q p ↔ ~q
T T F F
T F F T
F T T F
F F T T
Truth Table for ~p ↔ q ≡ p ↔ ~q

p q ~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 F
Truth Table for ~p ↔ q ≡ p ↔ ~q

p q ~p ~q ~p ↔ q p ↔ ~q
T T F F F F
T F F T T T
F T T F T T
F F T T F F
Truth Table for ~(p ⊕ q) ≡ p ↔ q

p q p⊕q ~(p ⊕ q) p↔q

T T
T F
F T
F F
Truth Table for ~(p ⊕ q) ≡ p ↔ q

p q p⊕q ~(p ⊕ q) p↔q

T T F
T F T
F T T
F F F
Truth Table for ~(p ⊕ q) ≡ p ↔ q

p q p⊕q ~(p ⊕ q) p↔q

T T F T
T F T F
F T T F
F F F T
Truth Table for ~(p ⊕ q) ≡ p ↔ q

p q p⊕q ~(p ⊕ q) p↔q

T T F T T
T F T F F
F T T F F
F F F T T
Laws of Logic

1. Commutative Law: p  q  q  p

2. Implication Law: p  q  ~q ∨ p  ~(~p ∧ q)

3. Exportation Law: (p ∧ q)  r  p  (q  r)

4. Equivalence Law: p  q  (p  q)  (q  p)

5. Reductio ad Absurdum: p  q  (p ∧ ~q)  c

 Applications

Prove that p ∧ ~q  r  ~(p ∧ ~q) ∨ r

Solution.

p ∧ ~q  r  (p ∧ ~q)  r Order of Operation

 ~(p ∧ ~q) ∨ r Implication Law

 Applications

Prove that (p  r)  (q  r)  [~(~p ∨ r) ∨ (~q ∨ r)] ∧

[~(~q ∨ r) ∨ (~p ∨ r)]

Solution.
(p  r)  (q  r)  (~p ∨ r)  (~q ∨ r) Implication

º [(~p ∨ r)  (~q ∨ r)] ∧ [(~q ∨ r)  (~p ∨ r)] Equivalence

of bi-conditional

º [~(~p ∨ r) ∨ (~q ∨ r)] ∧ [~(~q ∨ r) ∨ (~p ∨ r)] Implication

Law
 Applications

Prove that ~(p  q)  p  t

Solution.
~(p  r)  p  ~[~(p ∧ ~q)]  p Implication Law
º (p ∧ ~q)  p Double Negation
º ~(p ∧ ~q) ∨ p Implication Law
º (~p ∨ q) ∨ p De Morgan’s Law
º (q ∨ ~q) ∨ p Commutative Law of ∨
º q ∨ (~p ∨ p) Associative law of ∨
º q∨t Negation Law
ºt Universal Bound
Law