Supplement to the Classical Algebra text

Chapter 0: Logic and Proofs

EXERCISE SET 0

    1 - 6. Determine which of the following sentences are statements. What are the truth values of those that are statements?

  1. 7 > 5.
  2. 5 > 7.
  3. Is 5 > 7 ?
  4. 21/2 is an integer.
  5. Show that 21/2 is not an integer.
  6. If 5 is even then 6 = 7.

    7 - 12. Write down the truth tables for each expression.

  7. NOT ( NOT P )
  8. NOT ( P OR Q )
  9. P => ( Q OR R )
  10. ( P AND Q ) => R
  11. ( P OR NOT Q ) => R
  12. NOT P => ( Q <=> R )

  13. P UNLESS Q is defined as ( NOT Q ) => P. Show that this statement has the same truth table as P OR Q. Give an example in common English showing the equivalence of P UNLESS Q and P OR Q.
  14. Write down the truth table for the exclusive or connective XOR.
  15. Write down the truth table for the not or connective NOR.
  16. Write down the truth table for the not and connective NAND.

    17 - 21. Write each statement using P, Q, and connectives.

  17. P whenever Q.
  18. P is necessary for Q.
  19. P is sufficient for Q.
  20. P only if Q.
  21. P is necessary and sufficient for Q.

  22. Show that the statements  P AND ( Q AND R )  and  ( P AND Q ) AND R  have the same truth tables. This is the associative law for AND.
  23. Show that the statements  P AND ( Q OR R )  and  ( P AND Q ) OR ( P AND R )  have the same truth tables. This is a distributive law.
  24. Is  ( P AND Q ) => R  equivalent to  P => ( Q => R ) ? Give reasons.

    25 - 28. Let P be the statement`It is snowing.' and let Q be the statement `It is freezing.' Write each statement using P, Q, and connectives.

  25. If it is snowing, then it is freezing.
  26. It is freezing when it is snowing.
  27. It is freezing but not snowing.
  28. When it is not freezing it is not snowing.

    29 - 32. Let P be the statement `I can walk.' Q be the statement `I have broken my leg.' and R be the statement `I take the bus.' Express each statement as an English sentence.

  29. Q => NOT P
  30. P <=> NOT Q
  31. R => ( Q OR NOT P )
  32. R => ( Q <=> NOT P )

    33 - 36. Express each statement as a logical expression using quantifiers. State the universe of discourse.

  33. There is a smallest positive integer.
  34. There is no smallest positive real number.
  35. There exists an integer that is larger than the product of any two integers.
  36. Every pair of integers has a common divisor.

    37 - 40. Negate and simplify each expression.

  37. forall x  ( P(x) OR Q(x) )
  38. forall x  ( (P(x) AND Q(x) ) => R(x) )
  39. exists x  ( P(x) => Q(x) )
  40. exists x  forall y  ( P(x) AND Q(y) )

    41 - 44. If the universe of discourse is the real numbers, what does each statement mean in English? Are they true or false?

  41. forall x  forall y   (x >= y).
  42. exists x  exists y   (x >= y).
  43. exists y  forall x   (x >= y).
  44. forall x  exists y   (x >= y).

    45 - 48. Determine whether each pair of statements is equivalent. Give reasons.

  45. exists x  ( P(x) OR Q(x) )         (exists x  P(x) ) OR (exists x  Q(x) )
  46. exists x  ( P(x) AND Q(x) )         (exists x  P(x) ) AND (exists x  Q(x) )
  47. forall x  ( P(x) OR Q(x) )         (forall x  P(x) ) OR (forall x  Q(x) )
  48. forall x  ( P(x) OR Q(y) )         (forall x  P(x) ) OR Q(y)

  49. If A, B and C are sets, the statement A cap B subset C can be expressed as
    forall x    ( (x inA   AND   xinB )  =>   xinC ) .
    Express and simplify the negation of this expression, namely A cap B is not a subset of C, in terms of quantifiers.
  50. If A and B are sets, the statement A = B can be expressed as
    forall x    ( x inA  <=>  xinB ) .
    What does A not equals to B mean? Give different ways of expressing this using quantifiers. How would you go about showing that two sets are not the same?
  51. The definition of the limit of a function,  limx -> a f(x) = L,  can be expressed using quantifiers as
    forall epsilon> 0   exists delta> 0   forall x    ( 0 < | x - a | < delta  =>  | f(x) - L | < epsilon ) .
    Use quantifiers to express the negation of this statement, namely  limx -> a f(x)  is not equal to  L.
  52. Show that the statement  P => ( Q OR R )  is equivalent to the statement  ( P AND NOT Q ) => R .
    [ This explains the proof method 0.3.6 for  P => ( Q OR R ) . ]
  53. Show that the statement  P => (Q AND R)  is equivalent to the statement  (P => Q) AND (P => R) .
    [ This explains the proof method 0.3.7 for  P => ( Q AND R ) . ]
  54. Is the statement  P => ( Q => R )  equivalent to  ( P => Q ) => R ? Give reasons.
  55. Show that the statement  P AND Q AND R  is equivalent to the statement  ( NOT P AND NOT Q) => R) .

    56 - 60. Negate and simplify each expression.

  56. If I do my assignments then I will get a good mark in the course.
  57. If x > 3 then x2 > 9.
  58. If x < -3 then x2 > 9.
  59. If a number is divisible by 2 then it is not prime.
  60. If x >= 0 and y >= 0 then x y >= 0.

  61. Let a and b be real numbers. Prove that if a b = 0 then a = 0 or b = 0.
  62. Let A and B be sets. Prove that if x is not in A cap B then x is not in A or x is not in B.
© 1998 William J. Gilbert and Scott A. Vanstone, University of Waterloo

Supplement Contents   |   Previous Section