MATH5301 Elementary Analysis. Homework 1
1.1 Prove the following tautologies writing the true-false table.
(a) A∨ ∼ A
(b) (A ∨ B) ⇒ A
(c) (A ∧ B) ⇒ A
(d) (A ⇒ B) ⇔ (∼ B ⇒∼ A)
(e) ∼ (A ∨ B) ⇔ (∼ A∧ ∼ B)
(f) ((A ⇒ B) ⇒ A) ⇒ A
(g) (A ⇒ (B ⇒ C)) ⇒ ((A ⇒ B) ⇒ (A ⇒ C))
These tautologies are sometimes called the axioms of logical system. Translate each of these statements in the human
language.
1.2 Prove the following identities for the set operations.
(a) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
(b) (A \ B) ∪ C = ((A ∪ C) \ B) ∪ (B ∩ C)
1.3 Write the following statements using the quantifiers.
(a) Even elements of the sequence {an} may be arbitrary large.
(b) The sequence {an} contains arbitrary large even elements.
(c) The sequence {an} contains infinitely many even elements.
1.4 Show that
(a) ∃x : (p(x) ∨ q(x)) ⇔ (∃x : p(x)) ∨ (∃x : q(x))
(b) (∀xp(x) ∨ ∀xq(x)) ⇒ ∀x(p(x) ∨ q(x))
(c) Why there is no left arrow implication on the previous line?
1.5 Show that one needs only one logic operation to construct all the 16 binary operations on statements A and B.
Define A ? B via the following table:
A B A ? B
0 0 1
0 1 0
1 0 0
1 1 0
.
Show that one can construct ∼ A, A ∨ B and A ∧ B using only operation ?. Then show that any other binary
operation can be obtained from {∼, ∨, ∧}.
1.6 How many subsets does the set A = {a, p, p, l, e} have?
