Mathematical Foundation of Computer Science

DHARM

108 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

and negation (~). Other connectors like implication (→), equivalence (⇔) that are also used to
form a compound statement they are all represented using basic connectors ( ∧, ∨, ~).
Theorem 6.1
(i) (A → B) ⇔ (~ A ∨ B) (ii) (A ⇔ B) ⇔ (A ∧ B) ∨ (~ A ∧ ~ B)
(iii) (A ⊕ B) ⇔ (A ∧ ~B) ∨ (~ A ∧ B) (iv) (A ↔ B) ⇔ (A → B) ∧ (B → A)
(v) (A ∧ B) ⇔ ~ ( ~A ∨ ~ B) (vi) (A ∨ B) ⇔ ~ ( ~ A ∧ ~ B)
The equivalence of illustrated formulas (i) — (vi) can be proved by the truth table.
(for the truth table see section 5.4.5)
For example, verify the equivalence between the LHS and RHS of the Implication
formula shown in (i). Construct the truth table and compare the truth values of both the
formulas shown in column 3 and 5. We observe that for all possible interpretations of
propositional variables A and B truth values of both the formulas are same.

AB(A → B) ~ A (~ A ∨ B)

FFTTT

FTTTT

TFFFF

TTTFT

12345 ← Column number

Fig. 5.7

Similarly verify other equivalence formulas.

(ii) (A ⇔ B) ⇔ (A ∧ B) ∨ (~ A ∧ ~ B)

(Equivalence formula)

A B (A ⇔ B) (A ∧ B) (~ A ∧ ~ B) (A ∧ B) ∨ (~ A ∧∧∧∧∧~ B)

FF T F T T

FT F F F F

TF F F F F

TT T T F T

Fig. 5.8

(iii)(A ⊕ B) ⇔ (A ∧ ~ B) ∨ (~ A ∧ B)

(Exclusive-OR formula)

A B (A ⊕ B) (A ∧ ~ B) (~ A ∧ B) (A ∧ ~ B) ∨∨∨∨∨ (~ A ∧ B)

FF F F F F

FT T F T T

TF T T F T

TT F F F F

Fig. 5.9