Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MATH3066 ALGEBRA AND LOGIC
Assignment
This assignment comprises 60 marks and is worth 20% of the overall assessment.
It should be completed and uploaded into Canvas before midnight on Thursday 28
March 2024. 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) ∨ ∼ (P ∧ R )
(5 marks)
2. Use the rules of deduction in the Propositional Calculus to find formal proofs
for the following sequents, but without using sequent or theorem introduction.
(a) ∼ Q ⇒ P , Q ⇒ ∼ R , R ` P
(b) (P ∨ Q) ⇒ (P ∧ Q) ` P ⇒ Q
(c) ∼ P ⇒ (Q ∧R) , Q ⇒ S , ∼ S ∨ ∼ R ` P
(12 marks)
3. Use truth values to determine which one of the following is a theorem (in the
sense of always being true):
W1 ≡
(
P ⇒ (Q ⇒ R)) ⇒ ((P ⇒ Q) ⇒ R)
or
W2 ≡
((
P ⇒ Q) ⇒ R
)
⇒
(
P ⇒ (Q ⇒ R)) .
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. For the formal proof, you may use, if you wish,
Sequent Introduction (SI) or Sequent Introduction (with Substitution) (SI(S))
with regard to the valid sequent Q ` P ⇒ Q.
(12 marks)
4. In this exercise we investigate truth tables related to well-formed formulae
produced using only the double arrow. It is easily shown that the double arrow
⇔ is both associative and commutative up to logical equivalence, in the sense
that
(P ⇔ Q)⇔ R ≡ P ⇔ (Q⇔ R) and P ⇔ Q ≡ Q⇔ P .
You are not asked to prove these facts, which you can use freely. You may also
use freely, without proof, the easy fact that if X is a theorem (always having
truth value T ) and Y is any well-formed formula then
X ⇔ Y ≡ Y .
Let k be a positive integer and P1, . . . , Pk be distinct propositional variables.
Write
Wx = Pi1 ⇔ Pi2 ⇔ . . .⇔ Pi`−1 ⇔ Pi` ,
where
x = (i1, . . . , i`)
is a sequence of ` distinct positive integers drawn from {1, . . . , k}. In this for-
mula for Wx, it is understood, by associativity, that, up to logical equivalence,
any bracketing may be used (so the brackets may be regarded as invisible).
Also Wx is interpreted as Pi1 if ` = 1, and Pi1 ⇔ Pi2 if ` = 2.
(a) Show that if W is a well-formed formula using propositional variables
P1, . . . , Pk, where the only connective used is the double arrow ⇔, then
either W is a theorem (always having truth value T ) or
W ≡ Wx
for some x.
(b) Show that there are exactly 2k truth tables associated with P1, . . . , Pk
using only the connective ⇔ to build well-formed formulae.
(16 marks)
5. For any positive integer n, an idempotent in Zn is an element e such that e2 = e.
For example 0 and 1 are always idempotents in Zn if n ≥ 2, and 3 and 4 are
idempotents in Z6.
(a) Find the idempotents in each of Z12, Z24, Z36 and Z60. (If you simply
list them correctly, you receive full marks without needing to provide a
justification.)
(b) Use part (a) or otherwise to evaluate 2100 and 3100 in each of Z12, Z24,
Z36 and Z60. Show your working.
(c) Suppose that it is 10:24 am on a Monday. What time and day will it be
after 2100 minutes have elapsed? Show your working.