THE UNIVERSITY OF SYDNEY
MATH3066 ALGEBRA AND LOGIC
Semester 1 First Assignment 2023
This assignment comprises 60 marks and is worth 20% of the overall assessment.
It should be completed and uploaded into Canvas before midnight on Friday 31
March 2023. Acknowledge any sources or assistance. This must be your own work.
Breaches of academic integrity, including copying solutions, sharing answers and
attempts at contract cheating, attract severe penalties.
1. Construct a truth table for the following well-formed formula W in the propo-
sitional variables P , Q and R and find all counterexamples.
W ≡ (P ∨ Q) ⇒ ∼ (Q ∧ R )
(5 marks)
2. Find a well-formed formula W in the propositional variables P , Q and R, using
at most two instances of binary connectives, having the following truth table:
P Q R | W
|
T T T | F
T T F | F
T F T | F
T F F | T
F T T | T
F T F | T
F F T | T
F F F | T
Justify your answer. Prove that it is impossible to represent W using at most
one instance of a binary connective.
(10 marks)
3. Use the rules of deduction in the Propositional Calculus to find formal proofs
for the following sequents. You have access to the 10 basic rules, and use of
definition of the double arrow for the last sequent, but should not use sequent
or theorem introduction.
(a) (P ∨ Q) ⇒ R ` (P ⇒ R) ∧ (Q ⇒ R)
(b) P ⇒ Q , ∼ (∼ R ∧ S) ` (Q⇒ S) ⇒ (P ⇒ R)
(c) P ⇔ Q ` (P ∨ Q) ⇔ (P ∧ Q)
(15 marks)
4. Use truth values to determine which one of the following is a theorem (in the
sense of always being true).
(a)
(
P ∧ (Q ∨ ∼ P )) ⇒ Q (b) (Q ∧ (Q ∨ ∼ P )) ⇒ P
For the one that isn’t a theorem, produce a counterexample. For the one
that is a theorem, provide a formal proof also using rules of deduction in the
Propositional Calculus (but avoiding derived rules).
(10 marks)
5. Consider well-formed formulae Wn, for each positive integer n, defined as fol-
lows, where P1, P2, P3, . . . are propositional variables:
W1 = ∼ P1 and Wk+1 = ∼ (∼Wk ∨ Pk+1) for each k ≥ 1 .
Prove, for each positive integer n, that Wn has truth value T if and only if
P1, . . . , Pn all have truth value F .
(5 marks)
6. Prove that every well-formed formula in the Propositional Calculus is equivalent
to a well-formed formula where the only connectives used are ∼ and ⇒ . You
may use without proof the fact that if two well-formed formulae are logically
equivalent, then replacing one by the other as subwffs in any given well-formed
formula retains logical equivalence.
(8 marks)
7. Consider the following equations over Z:
112 = 2(39) + 34 ,
39 = 34 + 5 ,
34 = 6(5) + 4 ,
5 = 4 + 1 .
(a) Use these equations to find integers α and β such that
112α+ 39β = 1 .
(b) Use the previous part to find the multiplicative inverse of 39 in Z112 and
the multiplicative inverse of 34 in Z39.
(7 marks)