Course Review Exercises Course Review Exercises

    1. Determine whether (p q) p logically implies p.
    2. Is ((p q) p)        p a tautology? Explain.

    1. Determine whether (p q) r   and  p (q r ) are equivalent.
    2. Is ((p q) r)     (p (q r )) a tautology? Explain.

  1. (Ganong) I claim that there are infinitely many boolean expressions
    P1, P2, P3, Pn
    that are all tautologies in which

    the boolean constants true and false do not appear and r is the only boolean variable that does appear.

    Indicate why this claim is correct by writing down four different specific tautologies P1, P2, P3, P4 satisfying the given condition and indicating, by what you write (e.g., by a pattern in your four), that you know how to continue the list ad infinitum.

  2. Rewrite the following to include ``invisible'' parentheses and test the resulting expression for validity.
    pq r     q (p r) .
  3. (Dow) Fill in complete justifications (in the proof style of the ``model proof'') using (3.10) and less of this proof of
    ((p p)     (q q))         false .
    where the proof steps are given below.
    ((p p)     (q q))         false
    =

                        

    (true      (q q))         false
    =

                        

    ((q q)      true)         false
    =

                        

    (q q)          ( true     false)
    =

                        

    (q q)          ( false      false)
    =

                        

    true          ( false      false)
  4. Using the proof style of the text, prove (3.32):
    |- pq     p q      p .
    You may assume any result with lower number.
  5. Using the proof style of the text, prove (3.52):
    |- (p q)         (pq)     ( pq) .
    You may assume any result with lower number.
  6. Using the proof style of the text, prove
    |- (p q)         ((p r)   (p    (qr))) .
  7. (Dow)

    1. Is pq pr a theorem in our system? Justify your answer.
    2. Leibniz gives
      |- pq      pr
      |- (pq p)     (pr p)
       .
      Does this mean that ((pq p)     ((pr p) is a theorem? Explain.
    3. You are given that P and Q are expressions and that |- P Q. Determine whether each of the following statements are true or false. Justify your answer. Express yourself carefully, using semantic language or syntactic language as appropriate.

      1. If P is satisfiable, then Q is satisfiable.
      2. If P is a theorem, then Q is not satisfiable.
      3. If |- R, then |- (RP) (RQ).

  8. Prove in the style of the text, Transitivity, (3.82)(b),
    (p q)    (q r)          (p r) .
    You may use any lower numbered theorem in your proof.
  9. Use the method of Section 4.1 to prove
    |- (p q)     (r s)         (pr    q s).
    You may want to use the hint given for Problem 4.4 in the textbook.
  10. Apply the Deduction Theorem (i.e., method of assuming the antecedent) to prove
    |- (p q)        ((r p)    (r q)) .
  11. Prove
    |- (p q)     (r s)         (pr    q s)
    using Case Analysis and the Deduction Theorem. Begin by reducing the problem to showing
    |- (pr)        ((p q)     (r s)    (q s)) .
  12. Prove using the methods of the text that
    |-   ((a = 1)    (b = 2)    (a = b))        (1 = 4) .
  13. Determine whether each of the following as a theorem. If yes, give a proof. If no, give an interpretation for which it is false. Note that 0, 1, and 5 are constant symbols and 0 1.

    1. ("| (x = 0)(x = 1) : x2 = 5).
    2. ($| (x = 0)(x = 1) : x2 = 5).
    3. ("| (x = 0)(x = 1) : x2 = 1).
    4. ($| (x = 0)(x = 1) : x2 = 1).
    5. ("| x = y :x = 5)      y = 5.
    6. ($| x = y :x = 5)      y = 5.
    7. ("| (x = y)(y = 5) : (x = 5) (y = 5)).
    8. ($| (x = y)(y = 5) :(x = 5) (y = 5)).

  14. Fill in reasons in the following proof that
    |- (+i | 0 m-i m: 1 + (m-i))   =   (+i | 0 i m : 1+i)  .


    (+i | 0 m-i m: 1 + (m-i))
    =

                                  

    (+i | 0 m-i m: (+j | j = m-i: 1+j))
    =

                                  

    (+i,j | (0 m-i m)(j = m-i): 1+j)
    =

                                  

    (+i,j | (0 j m)(j = m-i): 1+j)
    =

                                  

    (+i,j | (0 j m)(i = m-j): 1+j)
    =

                                  

    (+j,i | (0 j m)(i = m-j): 1+j)
    =

                                  

    (+j | 0 j m: (+i | i = m-j:1+j))
    =

                                  

    (+j | 0 j m:1+j)
    =

                                  

    (+i | 0 i m:1+i)

  15. Prove
    |- (("| :Ax)    (Ay By))         By .
  16. Prove
    |-  ("| :x = 1) ("| :y = x) .
  17. Determine whether each of the following is a theorem. If yes, give a proof. If no, give an interpretation for which it is false.

    1. (By Ay)    (By ($x|:Ax)).
    2. (By Ay)    (($x|:Bx) ($x|:Ax)).

  18. Use Metatheorem Witness to prove this instance of (9.27),
    ("y|:By Ay)    (($x|:Bx) ($x|:Ax)) .
    Hint: Start by using (3.65) to obtain a form to which (9.30) applies, apply (9.30) and complete a proof.


File translated from TEX by TTH, version 2.60.
On 9 Jan 2001, 14:33.