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.
(2 points)
M − (A ∩ B) = (M − A) ∪ (M − B),
M − (A ∪ B) = (M − A) ∩ (M − B).
Exercise 1.2 Given φ = (A → (B → C)) → (B → (A → C)), (i) (2 points) Write the truth table for φ.
(ii) (2 points) Write φ in disjunctive normal form. (iii) (2 points) Write φ in conjunctive normal form.
(6 points)
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 000000000011111111 010000111100001111 100011001100110011 110101010101010101
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) (1 point) Show that {∧, ∨, ¬} is functionally complete. (ii) (1 point) Show that {∧, ¬} is functionally complete. (iii) (1 point) Show that {∨, ¬} is functionally complete.
(iv) (1 point) Show that {∨, ∧} is not functionally complete. (4 points)
Exercise 1.4 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) (1point) Give the truth tables for A|B and A↓B.
(ii) (2points)ProvethatA↓A⇔¬Aand(A↓B)↓(A↓B)⇔A∨B. (iii) (1 point) Deduce that {↓} is functionally complete.
(iv) (1 point) Represent the exclusive or ⊕ solely through ↓.
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 discussion of NAND and NOR flash memory.
1
- (v) (1 point) Prove that {|} is functionally complete.
- (vi) (1 point) Is the Scheffer stroke | acting on logical statements is associative? That is, is it correct that (A|B)|C ⇔A | (B | C)?
(7 points)
Exercise 1.5 For any sets A and B, show that (i) (1 point) 2A ∩ 2B = 2A∩B .
(ii) (1point)(2A∪2B)⊂2A∪B. (2 points)
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)ProvethatX△Y =(X∪Y)−(X∩Y). (ii) (1point)Provethat(M−X)△(M−Y)=X△Y.
(iii) (1 point) Show that the symmetric difference is associative, i.e., (X △ Y ) △ Z = X △ (Y △ Z). (iv) (1point)ProvethatX∩(Y △Z)=(X∩Y)△(X∩Z).
(v) (1point)ShowthatX△Y =Z△W iffX△Z=Y △W.
(vi) (1 point) Indicate the region of X △ Y △ Z in a Venn diagram.
(6 points)
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) (1 point) ρ(A, B) = ρ(B, A);
(iii) (2points)ρ(A,C)≤ρ(A,B)+ρ(B,C). (4 points)
2
