Sale!

ve203 Assignment 1

$30.00

ve203 Assignment 1

Q1. Let A and B be propositions. Use truth tables to prove the de Morgan rules:
¬(A ∧ B) ⇐⇒ (¬A ∨ ¬B) and ¬(A ∨ B) ⇐⇒ (¬A ∧ ¬B)
(2 marks)
Q2. Let M be a set and let A, B ⊆ M. Prove
M\(A ∩ B) = (M\A) ∪ (M\B) and M\(A ∪ B) = (M\A) ∩ (M\B)
(2 marks)
Q3. Which of the compound propositions are tautologies? Justify your answers.
(i) (A ⇒ (B ⇒ C)) ⇒ (B ⇒ (A ⇒ C))
(ii) ((A ∨ B) ∧ (A ∨ C)) ⇒ (B ∨ C)
(iii) (A ⇒ (¬B)) ⇒ (B ⇒ (¬A))

Category:

Description

5/5 - (4 votes)

ve203 Assignment 1

Q1. Let A and B be propositions. Use truth tables to prove the de Morgan rules:
¬(A ∧ B) ⇐⇒ (¬A ∨ ¬B) and ¬(A ∨ B) ⇐⇒ (¬A ∧ ¬B)
(2 marks)
Q2. Let M be a set and let A, B ⊆ M. Prove
M\(A ∩ B) = (M\A) ∪ (M\B) and M\(A ∪ B) = (M\A) ∩ (M\B)
(2 marks)
Q3. Which of the compound propositions are tautologies? Justify your answers.
(i) (A ⇒ (B ⇒ C)) ⇒ (B ⇒ (A ⇒ C))
(ii) ((A ∨ B) ∧ (A ∨ C)) ⇒ (B ∨ C)
(iii) (A ⇒ (¬B)) ⇒ (B ⇒ (¬A))
(3 marks)
Q4. 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)
Q5. Let A and B be propositions. Write compound expressions using only the propositions A and B, and the connectives ∨ and ¬ that are logically equivalent to each of the
following: A ∧ B, A ⇒ B and A ⇔ B.
(3 marks)
Q6. Let M be a set and let X, Y, Z ⊆ M. We define the symmetric difference:
X4Y := (X ∪ Y )\(X ∩ Y )
(i) Prove that X4Y = (X\Y ) ∪ (Y \X).
(ii) Prove that (M\X)4(M\Y ) = X4Y .
(iii) Show that the symmetric difference is associative, i.e., (X4Y )4Z = X4(Y 4Z).
(iv) Prove that X ∩ (Y 4Z) = (X ∩ Y )4(X ∩ Z).
(1+1+2+3 marks)
1
Q7. The logical operation associated to the symmetric difference 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) If X = {x | A(x)} and Y = {x | B(x)}, show that
x ∈ X4Y ⇔ A(x) ⊕ B(x)
(ii) Using only the propositions A and B, and the connectives ∧ and ¬, write a compound expression that is logically equivalent to A ⊕ B.
(iii) Show that
A ⊕ B
B ⊕ C
∴ ¬(A ⊕ C)
is a valid argument.
(2+1+2 marks)
Q8. Show that (∃x(P(x) ⇒ Q(x))) ⇐⇒ ((∀xP(x)) ⇒ (∃xQ(x))) is a tautology.
(2 marks)
Q9. Let M be a set and let A, B ⊆ M. Let T = (A ∩ B) ∪ ((M\A) ∩ (M\B)). Prove
that (M\A) ∩ B ⊆ M\T.
(2 marks)
Q10. 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) and A ↓ B :≡ ¬(A ∨ B).
(i) Give truth tables for A | B and A ↓ B.
(ii) Show that every connective of propositional logic can be defined using only the
connective |.
(iii) Show that every connective of propositional logic can be defined using only the
connective ↓.
(iv) Is A ↓ (B ↓ C) logically equivalent to (A ↓ B) ↓ C?
(v) Show that
(¬A) ↓ B
A | C
∴ B ↓ C
is a valid argument.
(2+4+4+1+4 marks)
2