VE203-Assignment 1 Solved

Exercise 1.1

(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.

(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.

                                         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)         Write the truth table for φ.

(ii)        Write φ in disjunctive normal form.

(iii)       Write φ in conjunctive normal form.



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)             Show that {∧,∨,¬} is functionally complete.

(ii)           Show that {∧,¬} is functionally complete. (iii) (1point) Show that {∨,¬} is functionally complete.

(iv) Show that {∨,∧} is not functionally complete.



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)         Give the truth tables for A | B and A ↓ B.

(ii)       Prove that A ↓ A ⇔ ¬A and (A ↓ B) ↓ (A ↓ B) ⇔ A ∨ B.

(iii)      Deduce that {↓} is functionally complete.

(iv)      Represent the exclusive or ⊕ solely through ↓.

1

(v)       Prove that {|} is functionally complete.

(vi)      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)       2A ∩ 2B = 2A∩B.

(ii)     (2A ∪ 2B) ⊂ 2A∪B.



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)         Prove that X △ Y = (X ∪ Y ) − (X ∩ Y ).

(ii)       Prove that (M − X) △ (M − Y ) = X △ Y .

(iii)      Show that the symmetric difference is associative, i.e., (X △ Y ) △ Z = X △ (Y △ Z).

(iv)      Prove that X ∩ (Y △ Z) = (X ∩ Y ) △ (X ∩ Z).

(v)       Show that X △ Y = Z △ W iff X △ Z = Y △ W.

(vi)      Indicate the region of X △ Y △ Z in a Venn diagram.



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)          ϱ(A,B) = 0 iff A = B;

(ii)        ϱ(A,B) = ϱ(B,A);

(iii)       ϱ(A,C) ≤ ϱ(A,B) + ϱ(B,C).



2


 
[1] According 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.