Description
Exercise 1.1 De Morgan’s Rules
i) Let a, b be statements. Write out the truth tables to prove de Morgan’s rules:
¬(a ∧ b) ⇔ ¬a ∨ ¬b, ¬(a ∨ b) ⇔ ¬a ∧ ¬b.
(2 Marks)
ii) Let M be a set and A, B ⊂ M. Prove the following equalities by writing out the sets in terms of predicates
and applying de Morgan’s rules.
(A ∩ B)
c = A
c ∪ B
c
, (A ∪ B)
c = A
c ∩ B
c
.
(2 Marks)
Exercise 1.2 Disjunctive Normal Form
Suppose that a truth table in n propositional variables is specified. Show that a compoud proposition with
this truth table can be formed by taking the disjunction of conjunctions of the variables or their negations,
with one conjunction for each combination of values for which the compound proposition is true. The resulting
compound proposition is said to be in disjunctive normal form.
(2 Marks)
Exercise 1.3 Functional Completeness
A collection of logical operators is called functionally complete if every compound proposition is logically equivalent to a compound proposition involving only these logical operators.
i) Show that {∧, ∨, ¬} is a functionally complete collection of logical operators. (Hint: use the disjunctive
normal form.)
ii) Show that {∧, ¬} is a functionally complete collection of logical operators. (Hint: use a de Morgan law.)
iii) Show that {∨, ¬} is a functionally complete collection of logical operators.
(3 Marks)
Exercise 1.4 Exclusive Disjunction
In daily language, the phrase “A or B” is generally taken to mean “A or B, but not both A and B.” The
corresponding binary operation is called the exclusive or, written as ⊕ in logic or XOR in logic gate design. It
is defined by the truth table
A B A ⊕ B
T T F
T F T
F T T
F F F
i) Express ⊕ by logical conjunction, disjunction and negation, i.e., through the operations {∧, ∨, ¬}.
(2 Marks)
ii) As shown in Exercise 3, any binary operation can be represented through {∧, ∨, ¬}. For technical reasons,
it is preferable in computer design to represent logical operations using {∧, ⊕, ¬} instead. Write ∨ using
{∧, ⊕, ¬}.
(2 Marks)
iii) Explain why ii) proves that {∧, ⊕, ¬} is functionally complete.
(1 Mark)
Exercise 1.5 Functional Completeness with a Single Operator
In computer design, the logical operations NAND and NOR play an important role. 1
In logic, NAND is
represented by the Scheffer stroke | while NOR is represented by the Peirce arrow ↓. They are defined as
A | B :≡ ¬(A ∧ B), A ↓ B :≡ ¬(A ∨ B).
i) Give the truth tables for A | B and A ↓ B.
(1 Mark)
ii) Prove that A ↓ A ≡ ¬A and (A ↓ B) ↓ (A ↓ B) ≡ A ∨ B.
(2 Marks)
iii) Deduce that {↓} is a functionally complete collection of logical operators.
(1 Mark)
iv) Represent the exclusive or ⊕ solely through ↓.
(1 Mark)
v) Prove that {|} is a functionally complete collection of logical operators.
(1 Mark)
Exercise 1.6 The Symmetric Difference
Let S be a set and X, Y, Z ⊂ S. We define the symmetric difference
X △ Y := (X ∪ Y ) \ (X ∩ Y ).
i) If X = {x: A(x)} and Y = {x: B(x)} show that
x ∈ X △ Y ⇔ A(x) ⊕ B(x).
In the following proofs, it may be easiest to use truth tables and properties of the exclusive disjunction
rather than any laws of set theory.
(1 Mark)
ii) Prove that X △ Y = (X \ Y ) ∪ (Y \ X).
(2 Marks)
iii) Prove that Xc △ Y
c = X △ Y .
(2 Marks)
1According to https://en.wikipedia.org/wiki/Logical NOR, “The computer used in the spacecraft that first carried humans to
the moon, the Apollo Guidance Computer, was constructed entirely using NOR gates with three inputs.” A reference for this claim
is is given in that article. See also https://en.wikipedia.org/wiki/Flash memory for a fiscussion of NAND and NOR flash memory.
