{"id":80585,"date":"2018-02-20T23:50:30","date_gmt":"2018-02-20T23:50:30","guid":{"rendered":"https:\/\/writemyessayfree.com\/algebra-and-logic"},"modified":"2017-08-18T07:41:24","modified_gmt":"2017-08-18T07:41:24","slug":"algebra-and-logic","status":"publish","type":"post","link":"https:\/\/www.benedictsol.com\/blogs\/algebra-and-logic\/","title":{"rendered":"ALGEBRA AND LOGIC"},"content":{"rendered":"

This assignment comprises a total of 60 marks and is worth 15% of the overall<\/p>\n

assessment. It should be completed, accompanied by a signed cover sheet, and a<\/p>\n

hardcopy handed in at the lecture on Wednesday 25 May. Acknowledge any sources<\/p>\n

or assistance. An electronic copy or scan should also be downloaded using Turnitin<\/p>\n

from the Blackboard portal.<\/p>\n

    \n
  1. Let W<\/li>\n<\/ol>\n

    1<\/p>\n

    and W<\/p>\n

    be w\ufb00s such that the following sequent can be proved using<\/p>\n

    the 10 rules of deduction in the Propositional Calculus:<\/p>\n

    2<\/p>\n

    W<\/p>\n

    1<\/p>\n

    \u22a2 W<\/p>\n

    2<\/p>\n

    .<\/p>\n

    Let W be another w\ufb00 in the Propositional Calculus. Use Sequent Introduction<\/p>\n

    to prove the following sequents:<\/p>\n

    (a) ~ W<\/p>\n

    2<\/p>\n

    \u22a2 ~ W<\/p>\n

    1<\/p>\n

    (b) W \u2228 W<\/p>\n

    1<\/p>\n

    \u22a2 W \u2228 W<\/p>\n

    Decide which of the following sequents can be proved, providing a proof or<\/p>\n

    counterexample in each case:<\/p>\n

    (c) W<\/p>\n

    2<\/p>\n

    \u21d2 W \u22a2 W<\/p>\n

    1<\/p>\n

    \u21d2 W (d) W<\/p>\n

    1<\/p>\n

    \u21d2 W \u22a2 W<\/p>\n

      \n
    1. Use the rules of deduction in the Predicate Calculus (but avoiding derived<\/li>\n<\/ol>\n

      rules) to \ufb01nd formal proofs for the following sequents:<\/p>\n

      (a) (\u2203x) F(x) \u22a2 ~ (\u2200x) ~ F(x)<\/p>\n

      (b) ~ (\u2200x) ~ F(x) \u22a2 (\u2203x) F(x)<\/p>\n

      (c) (\u2200x)<\/p>\n

      &nbsp;<\/p>\n

      ~ F(x) \u21d2 G(x)<\/p>\n

      _<\/p>\n

      \u22a2<\/p>\n

      &nbsp;<\/p>\n

      (\u2203x) ~ G(x)<\/p>\n

      (d) (\u2203z)(\u2203y)(\u2200x) K(x, y, z) \u22a2 (\u2200x)(\u2203y)(\u2203z) K(x, y, z)<\/p>\n

      (e) (\u2203x)<\/p>\n

      _<\/p>\n

      G(x) \u2227 (\u2200y)<\/p>\n

      &nbsp;<\/p>\n

      F(y) \u21d2 H(y, x)<\/p>\n

      ,<\/p>\n

      (\u2200x)<\/p>\n

      _<\/p>\n

      G(x) \u21d2 (\u2200y)<\/p>\n

      &nbsp;<\/p>\n

      L(y) \u21d2~ H(y, x)<\/p>\n

      _<\/p>\n

      _<\/p>\n

      _<\/p>\n

      _<\/p>\n

      _<\/p>\n

      \u21d2<\/p>\n

      &nbsp;<\/p>\n

      (\u2203y)F(y)<\/p>\n

      _<\/p>\n

      2<\/p>\n

      2<\/p>\n

      \u21d2 W<\/p>\n

      (9 marks)<\/p>\n

      \u22a2 (\u2200x)<\/p>\n

      &nbsp;<\/p>\n

      F(x) \u21d2~ L(x)<\/p>\n

      _<\/p>\n

      (20 marks)<\/p>\n

        \n
      1. Find faults in the following arguments, with brief explanations:<\/li>\n<\/ol>\n

        (a) First faulty argument:<\/p>\n

        1 (1) (\u2200x)<\/p>\n

        &nbsp;<\/p>\n

        F(x) \u21d2 G(x)<\/p>\n

        _<\/p>\n

        A<\/p>\n

        2 (2) (\u2203x) F(x) A<\/p>\n

        3 (3) F(a) A<\/p>\n

        1 (4) F(a) \u21d2 G(a) 1 \u2200 E<\/p>\n

        1, 3 (5) G(a) 3, 4 MP<\/p>\n

        1, 3 (6) (\u2200x) G(x) 5 \u2200 I<\/p>\n

        1, 2 (7) (\u2200x) G(x) 2, 3, 6 \u2203 E<\/p>\n

        (b) Second faulty argument:<\/p>\n

        1 (1) (\u2200x)(\u2203y) H(x, y) A<\/p>\n

        1 (2) (\u2203y) H(a, y) 1 \u2200 E<\/p>\n

        1 (3) (\u2203y) H(b, y) 1 \u2200 E<\/p>\n

        4 (4) H(a, b) A<\/p>\n

        5 (5) H(b, a) A<\/p>\n

        4, 5 (6) H(a, b) \u2227 H(b, a) 4, 5 \u2227 I<\/p>\n

        4, 5 (7) (\u2203y)<\/p>\n

        &nbsp;<\/p>\n

        H(a, y) \u2227 H(y, a)<\/p>\n

        4, 5 (8) (\u2203x)(\u2203y)<\/p>\n

        &nbsp;<\/p>\n

        H(x, y) \u2227 H(y, x)<\/p>\n

        1, 4 (9) (\u2203x)(\u2203y)<\/p>\n

        &nbsp;<\/p>\n

        H(x, y) \u2227 H(y, x)<\/p>\n

        1 (10) (\u2203x)(\u2203y)<\/p>\n

        &nbsp;<\/p>\n

        H(x, y) \u2227 H(y, x)<\/p>\n

        _<\/p>\n

        6 \u2203 I<\/p>\n

        _<\/p>\n

        7 \u2203 I<\/p>\n

        _<\/p>\n

        3, 5, 8 \u2203 E<\/p>\n

        _<\/p>\n

        2, 4, 9 \u2203 E<\/p>\n

        Now \ufb01nd models to demonstrate that the following sequents are not valid, with<\/p>\n

        brief explanations:<\/p>\n

        (c) (\u2200x)<\/p>\n

        &nbsp;<\/p>\n

        F(x) \u21d2 G(x)<\/p>\n

        _<\/p>\n

        , (\u2203x) F(x) \u22a2 (\u2200x) G(x)<\/p>\n

        (d) (\u2200x)(\u2203y) H(x, y) \u22a2 (\u2203x)(\u2203y)<\/p>\n

        &nbsp;<\/p>\n

        H(x, y) \u2227 H(y, x)<\/p>\n

          \n
        1. Solve the following equations simultaneously over Z<\/li>\n<\/ol>\n

          7<\/p>\n

          _<\/p>\n

          and explain why no solution<\/p>\n

          exists in Z<\/p>\n

          11<\/p>\n

          :<\/p>\n

          5x + 2y = 4<\/p>\n

          3x \u2013 y = 3<\/p>\n

          (9 marks)<\/p>\n

          (4 marks)<\/p>\n

            \n
          1. In this exercise we work with polynomials over Z<\/li>\n<\/ol>\n

            3<\/p>\n

            . Consider the ring<\/p>\n

            R = {0, 1, 2, x, x + 1, x + 2, 2x, 2x + 1, 2x + 2}<\/p>\n

            of remainders with addition and multiplication modulo the quadratic<\/p>\n

            p(x) = x<\/p>\n

            where all coe\ufb03cients come from Z<\/p>\n

            2<\/p>\n

            + 2x + 2 = x<\/p>\n

            3<\/p>\n

            2<\/p>\n

            \u2013 x \u2013 1 ,<\/p>\n

            .<\/p>\n

            (a) Verify that p(x) has no linear factors, so is irreducible. (Hence R is a \ufb01eld.)<\/p>\n

            (b) Calculate in R the following powers of x:<\/p>\n

            x<\/p>\n

            2<\/p>\n

            , x<\/p>\n

            3<\/p>\n

            , x<\/p>\n

            (c) Explain why x is primitive in R, but x<\/p>\n

            4<\/p>\n

            , x<\/p>\n

            5<\/p>\n

            , x<\/p>\n

            2<\/p>\n

            6<\/p>\n

            , x<\/p>\n

            is not primitive.<\/p>\n

            (d) Find both square roots of 2 in R.<\/p>\n

            (e) Solve over R the following quadratic equation in a:<\/p>\n

            a<\/p>\n

            2<\/p>\n

              \n
            1. Suppose that a, b, c \u2208 R with a 6 = 0 and b<\/li>\n<\/ol>\n

              \u2013 2xa + x \u2013 1 = 0 .<\/p>\n

              r(x) = ax<\/p>\n

              2<\/p>\n

              is an irreducible quadratic polynomial. Prove that<\/p>\n

              2<\/p>\n

              7<\/p>\n

              , x<\/p>\n

              8<\/p>\n

              .<\/p>\n

              \u2013 4ac < 0, so that<\/p>\n

              + bx + c<\/p>\n

              R[x]\/r(x)R[x]<\/p>\n

              ~<\/p>\n

              =<\/p>\n

              C .<\/p>\n

              [Hint: use the Fundamental Homomorphism Theorem. You may assume without<\/p>\n

              proof that an appropriate evaluation map is a ring homomorphism.]<\/p>\n

              (9 marks)<\/p>\n

              (9 marks)<\/p>\n","protected":false},"excerpt":{"rendered":"

              This assignment comprises a total of 60 marks and is worth 15% of the overall assessment. It should be completed, accompanied by a signed cover sheet, and a hardcopy handed in at the lecture on Wednesday 25 May. Acknowledge any Read More …<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-80585","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/www.benedictsol.com\/blogs\/wp-json\/wp\/v2\/posts\/80585","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.benedictsol.com\/blogs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.benedictsol.com\/blogs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.benedictsol.com\/blogs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.benedictsol.com\/blogs\/wp-json\/wp\/v2\/comments?post=80585"}],"version-history":[{"count":0,"href":"https:\/\/www.benedictsol.com\/blogs\/wp-json\/wp\/v2\/posts\/80585\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.benedictsol.com\/blogs\/wp-json\/wp\/v2\/media?parent=80585"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.benedictsol.com\/blogs\/wp-json\/wp\/v2\/categories?post=80585"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.benedictsol.com\/blogs\/wp-json\/wp\/v2\/tags?post=80585"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}