MATH6005 Graduate Assignment A, 2021 ANU
Question 1
(A) Construct a circuit diagram corresponding to the input-output table below.
| X | Y | Z | output |
| 1 1 1 1 0 0 0 0 |
1 1 0 0 1 1 0 0 |
1 0 1 0 1 0 1 0 |
0 1 0 1 0 0 1 0 |
AssignmentTutorOnline
(B) Determine whether the following statement is true or false, and explain your reasoning:
Every compound statement is logically equivalent to one in which the
only symbols used are statement variables, ‘(’, ‘)’, ‘→’ and ‘¬’.
(C) Determine whether the following statement is true or false, and explain your reasoning:
Every compound statement is logically equivalent to one in which the
only symbols used are statement variables, ‘(’, ‘)’, ‘∧’ and ‘∨’.
Question 2
(A) Each of the variables in the following predicates is quantified over Z+:
| p(x): x is prime o(t): t = 1 |
d(t; x): t divides x q(t; x): t = x. |
Using only quantifications, parentheses, logical connectives, variables and the predicates d(t; x) and o(t) and q(t; x), write something in place of : : : in the following
to make a true statement.
∀x ∈ Z+ [p(x) 
: : : ]:
(B) Using only quantifications, parentheses, logical connectives, variables and the predicates d(t; x) and o(t) and q(t; x) defined in part (A),write something in place of
: : : in the following to make a true statement.
∀x ∈ Z+ [¬p(x) : : : ]:
(C) Let g∶ Z → Z be a function. Consider the following two statements, both assuming
the universe of real numbers.
| Statement 1∶ Statement 2∶ |
∀x ∃y([x ≤ y] ∧ [g(x) ≥ g(y)]) ∃y ∀x([x ≤ y] ∧ [g(x) ≥ g(y)]) |
Without knowing any more about the function g, are you able to determine whether
or not Statement 1 is true? How about Statement 2? Explain your answers.
Page 3 of 5.
MATH6005 Graduate Assignment A, 2021 ANU
Question 3
(A) Establish or refute the validity of the following argument:
If the Raiders are playing a home match, the traffic will be bad.
If the traffic is bad, we will be late to the Tina Arena concert.
∴ If we are late to the Tina Arena concert, it will be because the Raiders are playing
a home match.
(B) Establish or refute the validity of the following argument:
Vika is a mathematics major or Vika is a computer science major.
If Vika is a computer science major, then Vika is required to take MATH1005.
∴ Vika is a mathematics major or Vika is required to take MATH1005.
(C) Sharky, a leader of the underworld, was killed by one of his own band of four minions. Detective Sharp interviewed the minions and determined that all were lying
except for one. The detective’s notes from the interviews included the following:
Socko said Lefty killed Sharky.”
Fats saidMuscles didn’t kill Sharky.”
Lefty said Muscles was shooting dice with Socko when Sharky was killed.”
Muscles said Lefty didn’t kill Sharky.”
Who killed Sharky? Justify your answer.
Question 4 A relation R on a set S is said to be transitive if, and only if,
∀x; y; z ∈ S x R y ∧ y R z Ô⇒ x R z:
Relations R1, R2, and R3 are defined on the power set P(a; b; c; d; e; f) by the rules
below. In each case, prove or disprove that the relation is transitive.
(A) A R1 B ⇔ A/B = ∅.
(B) A R2 B ⇔ there exists a bijective function f ∶ A → B.
(C) A R3 B ⇔ there exists an injective function f ∶ A/B → B/A.
Page 4 of 5.
MATH6005 Graduate Assignment A, 2021 ANU
Question 5 Review the definition of countable and uncountable sets given in lectures. Prove or disprove each of the following statements:
(A) Every subset of a countable set is countable.
(B) If A and B are disjoint sets and both A and B are countable, then A∪B is countable.
(C) If A ⊆ R and
∀a; b ∈ A ((a then A is uncountable.
End of Questions for Assignment A
Page 5 of 5.