# MATH 3066 ALGEBRA AND LOGIC Second Assignment

1. A positive well-formed formula (positive w?) in the Propositional Calculus isa well-formed formula that avoids all use of the negation symbol ? .(a) Use induction on the length of a w? to prove that if W = W (P1 , . . . , Pn )is a positive w? in terms of propositional variables P1 , . . . , Pn , thenV (P1 ) = . . . = V (Pn ) = Timplies V (W ) = T .(5 marks)(b) Prove that if W = W (P1 , . . . , Pn ) is any w? in the Propositional Calculussuch that V (P1 ) = . . . = V (Pn ) = T implies V (W ) = T , then W islogically equivalent to a positive w?.(optional, bonus marks)2. Use the rules of deduction in the Predicate Calculus to ?nd formal proofs forthe following sequents (without invoking sequent or theorem introduction):(a)(?x)(?y)(?z) K(y, x, z) ? (?z)(?y)(?x) K(y, x, z)(b)(?x)(G(x) ? F (x))(c)(?x)(?y)(?z) R(x, z) ? R(y, z)(d)(?x)(?y)(?z) R(x, y) ? R(y, z) ? R(x, z) ,(?x) ? F (x) ? (?x) ? G(x)? (?x)(?y) R(x, y)(?x)(?y)(?z) R(x, z) ? R(z, y)(?x) R(x, x)(21 marks)3. Consider the following well-formed formulae in the Predicate Calculus:(?x)(?y) R(x, y)(?x)(?y) R(x, y) ? ? R(y, x)(?x)(?y) R(x, y) ? (?z) R(z, x) ? R(y, z)Prove that any model in which W1 , W2 and W3 are all true must have at least3 elements. Find one such model with 3 elements.(6 marks)4. Let R = Z[x] andI = 2Z + xZ[x] ,the subset of R consisting of polynomials with integer coe?cients with evenconstant terms. Verify that I is an ideal of R. Show that I not a principalideal.(8 marks)5. Let R = Z3 [x]/(x2 ? x ? 1)Z3 [x], so we may writeR = { 0 , 1 , 2 , x , x + 1 , x + 2 , 2x , 2x + 1 , 2x + 2 } ,where we identify equivalence classes with remainders after division by thepolynomial x2 ? x ? 1. Then R is a commutative ring with identity. Constructthe multiplication table for R and use it to explain why R is a ?eld. Now ?nda primitive element, that is, an element a ? R such that all nonzero elementsof R are powers of a.(8 marks)6. In each case below, if it helps, you may identify the ring with remainders afterdivision by x2 + x + 1, so that the elements become linear expressions of theform a + bx where a, b come from Z3 in part (a) or from R in part (b).(a) Explain why R = Z3 [x]/(x2 + x + 1)Z3 [x] is not a ?eld.(b) Prove that F = R[x]/(x2 + x + 1)R[x] is isomorphic to C, the ?eld ofcomplex numbers.