THE UNIVERSITY OF SYDNEY MATH3066 ALGEBRA AND LOGIC Semester 1 2017 First Assignment This assignment is worth 15% of the overall assessment. Full marks may be obtained by achieving 60 marks (though 70 marks are available). It should be completed, accompanied by a signed cover sheet, and a hardcopy handed in at the lecture on Wednesday 26 April. Acknowledge any sources or assistance. An electronic copy or scan should also be downloaded using Turnitin from the Blackboard portal. 1. Build a combined truth table for the following wffs, where P , Q and R are propositional variables: (a) (P Q) R (b) Q ( P R ) Use your table to explain briefly why Q ( P R ) |= (P Q) R , but (P Q) R 6|= Q ( P R ) . (8 marks) 2. Use the rules of deduction in the Propositional Calculus (but avoiding derived rules) to find formal proofs for the following sequents: \u0001 (a) (P Q) R Q P R (b) (P Q) (R Q) (c) P Q, P R (R Q) P (d) (P Q) (R Q) (P R) Q RP (15 marks) 3. Use truth values to determine which one of the following wffs is a theorem (in the sense of always being true). \u0010 \u0010 \u0001\u0011 \u0001\u0011 (a) P Q R Q P R \u0010 \u0010 \u0001\u0011 \u0001\u0011 (b) P Q R Q P R For the one that isn't a theorem, produce all counterexamples. For the one that is a theorem, provide a formal proof also using rules of deduction in the Propositional Calculus. You are allowed (and encouraged) to use the derived rules TI, TI(S), SI and SI(S) with respect to the Law of Excluded Middle and the sequent that allows one to deduce any proposition from a contradiction. (12 marks) 4. Consider any wff W in the Propositional Calculus. Let #W be the number of symbols that occur in W (including all brackets). Let c(W ) be the number of occurrences of logical connectives (, , , , ) and v(W ) the number of occurrences of propositional variables in W . Prove, by induction on the length of a wff W , that #W = 3 c(W ) + v(W ) . (8 marks) 5. Let X, Y and Z be wffs built from propositional variables P1 , P2 , . . . , Pn (where n is a positive integer), and define the following wff (suppressing brackets in the usual way): WX,Y,Z := (X Y ) (Z X) . (i) Use the truth table for implication to explain why V ( P ) if V (Q) = F , V (P Q) = V (Q) if V (P ) = T . (ii) Use part (i), or otherwise, to deduce that V (Y ) if V (X) = T , V (WX,Y,Z ) = V (Z) if V (X) = F . (iii) Suppose that n 2 and Y and Z are built from variables P2 , . . . , Pn only. Denote the truth tables for Y and Z by TY and TZ respectively. Describe the truth table for WP1 ,Y,Z in terms of TY and TZ . (iv) Use part (iii), or otherwise, to prove, by induction on n, that every truth table arises as the truth table of a wff built only using the logical connectives and . (12 marks) 6. Solve the following equations simultaneously over Z11 and explain why no solution exists over Z13 : 3x y = 2 7x + 2y = 0 (5 marks) 7. Prove that the only integer solution to the equation x2 + 5y 2 = 3z 2 is (x, y, z) = (0, 0, 0). (10 marks)