Description

Exercise 1.1
(i) (1point) Let a,b be statements. Write out the truth tables to prove de Morgan’s rules:
¬(a ∧ b) ⇔ ¬a ∨ ¬b, ¬(a ∨ b) ⇔ ¬a ∧ ¬b.
(ii) (1point) 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.
M − (A ∩ B) = (M − A) ∪ (M − B), M − (A ∪ B) = (M − A) ∩ (M − B).
(2points)
Exercise 1.2 Given φ = (A → (B → C)) → (B → (A → C)),
(i) (2points) Write the truth table for φ.
(ii) (2points) Write φ in disjunctive normal form.
(iii) (2points) Write φ in conjunctive normal form.
(6points)
Exercise 1.3 The following shows the truth table for all 222 = 16 different binary logical operators φi, i = 0,…,15.
p q φ0 φ1 φ2 φ3 φ4 φ5 φ6 φ7 φ8 φ9 φ10 φ11 φ12 φ13 φ14 φ15
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Using infix notation, for example, φ13 can be represented as φ13 = →(p,q) = p → q.
A set S of logical operators is called functionally complete if every compound proposition is logically equivalent to a compound proposition involving only these logical operators in S. In this exercise, in order to show S is a functionally complete set, it suffices to verify that for all i = 0,…,15, φi over logical variables p and q can be represented using only operators in S.
(i) (1point) Show that {∧,∨,¬} is functionally complete.
(ii) (1point) Show that {∧,¬} is functionally complete. (iii) (1point) Show that {∨,¬} is functionally complete.
(iv) (1point) Show that {∨,∧} is not functionally complete.
(4points)
Exercise 1.4 In computer design, the logical operations NAND and NOR play an important role. 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) (1point) Give the truth tables for A | B and A ↓ B.
(ii) (2points) Prove that A ↓ A ⇔ ¬A and (A ↓ B) ↓ (A ↓ B) ⇔ A ∨ B.
(iii) (1point) Deduce that {↓} is functionally complete.
(iv) (1point) Represent the exclusive or ⊕ solely through ↓.
1
(v) (1point) Prove that {|} is functionally complete.
(vi) (1point) Is the Scheffer stroke | acting on logical statements is associative? That is, is it correct that (A|B)|C ⇔ A | (B | C)?
(7points)
Exercise 1.5 For any sets A and B, show that
(i) (1point) 2A ∩ 2B = 2A∩B.
(ii) (1point) (2A ∪ 2B) ⊂ 2A∪B.
(2points)
Exercise 1.6 Let M be a set and let X,Y,Z,W ⊂ M. We define the symmetric difference:
X △ Y := (X − Y ) ∪ (Y − X)
(i) (1point) Prove that X △ Y = (X ∪ Y ) − (X ∩ Y ).
(ii) (1point) Prove that (M − X) △ (M − Y ) = X △ Y .
(iii) (1point) Show that the symmetric difference is associative, i.e., (X △ Y ) △ Z = X △ (Y △ Z).
(iv) (1point) Prove that X ∩ (Y △ Z) = (X ∩ Y ) △ (X ∩ Z).
(v) (1point) Show that X △ Y = Z △ W iff X △ Z = Y △ W.
(vi) (1point) Indicate the region of X △ Y △ Z in a Venn diagram.
(6points)
Exercise 1.7 Let X be a finite set, define the distance/metric ϱ(A,B) of two sets A,B ∈ 2X by
ϱ(A,B) := |A △ B|.
Show that (2X,ϱ) is a metric space by verifying that for all A,B,C ∈ 2X,
(i) (1point) ϱ(A,B) = 0 iff A = B;
(ii) (1point) ϱ(A,B) = ϱ(B,A);
(iii) (2points) ϱ(A,C) ≤ ϱ(A,B) + ϱ(B,C).
(4points)
2