CMSC250, Spring 2004 Homework 4 Answers

Due Wednesday, February 25 at the beginning of your discussion section.

You must write the solutions to the problems single-sided on your own lined paper, with all sheets stapled together, and with all answers written in sequential order or you will lose points.

  1. Complete the following proofs using the method described in class (line numbers, rules, etc).
    1. P1 $ \forall x \in D \ P(x) \to (T(x) \vee Q(x))$
      P2 $ \forall y \in D \ Q(y) \vee (R(y) \wedge P(y))$
      P3 $ \forall z \in D \ (T(z) \wedge R(z)) \to S(z)$
      % latex2html id marker 903 $ \therefore$ $ \forall w \in D \ \sim Q(w) \to S(w)$
      • Answer:



        Line Statement Rule Lines Used
        1 $ Q(a) \vee (R(a) \wedge P(a))$ $ \forall$ instantiation P2
        2 $ \ \vline \ \sim Q(a)$ Assume --
        3 $ \ \vline \ R(a) \wedge P(a)$ Disjunctive syllogism 1, 2
        4 $ \ \vline \ P(a)$ Conjunctive simplification 3
        5 $ \ \vline \ T(a) \vee Q(a)$ $ \forall$ modus ponens 4, P1
        6 $ \ \vline \ R(a)$ Conjunctive simplification 3
        7 $ \ \vline \ T(a)$ Disjunctive syllogism 2, 5
        8 $ \ \vline \ T(a) \wedge R(a)$ Conjunctive addition 6, 7
        9 $ \ \vline \ S(a)$ $ \forall$ modus ponens P3, 8
        10 $ \sim Q(a) \to S(a)$ CCW w/out contra 2-9
        11 $ \forall w \in D \ \sim Q(w) \to S(w)$ $ \forall$ generalization 10



        Another way:



        Line Statement Rule Lines Used
        1 $ Q(a) \vee (R(a) \wedge P(a))$ $ \forall$ instantiation P2
        2 $ \ \vline \ \sim (\sim Q(a) \to S(a))$ Assume --
        3 $ \ \vline \ \sim Q(a) \wedge \sim S(a)$ Definition of $ \to$ 2
        4 $ \ \vline \ \sim Q(a)$ Conjunctive simplification 3
        5 $ \ \vline \ \sim S(a)$ Conjunctive simplification 3
        6 $ \ \vline \ \sim (T(a) \wedge R(a))$ $ \forall$ modus tollens 5, P3
        7 $ \ \vline \ \sim T(a) \vee \sim R(a)$ DeMorgan's law 6
        8 $ \ \vline \ R(a) \wedge P(a)$ Disjunctive syllogism 1, 4
        9 $ \ \vline \ R(a)$ Conjunctive simplification 8
        10 $ \ \vline \ P(a)$ Conjunctive simplification 8
        11 $ \ \vline \ \sim T(a)$ Disjunctive syllogism 7, 9
        12 $ \ \vline \ \sim T(a) \wedge \sim Q(a)$ Conjunctive addition 4, 11
        13 $ \ \vline \ \sim (T(a) \vee Q(a))$ DeMorgan's law 12
        14 $ \ \vline \ \sim P(a)$ $ \forall$ modus tollens P1, 13
        15 $ \ \vline \ \sim P(a) \wedge P(a)$ Conjunctive addition 14, 10
        16 $ \sim Q(a) \to S(a)$ CCW w/ contra 2-15
        17 $ \forall w \in D \ \sim Q(w) \to S(w)$ $ \forall$ generalization 16


    2. P1 $ \forall t \in D \ (A(t) \to B(t)) \to (C(t) \vee D(t))$
      P2 $ \exists u \in D \ \sim A(u) \wedge (D(u) \to E(u))$
      P3 $ \forall v \in D \ \sim E(v) \to (C(v) \to A(v))$
      % latex2html id marker 1115 $ \therefore$ $ \exists h \in D \ \sim B(h) \vee E(h)$
      • Answer:



        Line Statement Rule Lines Used
        1 $ \sim A(a) \wedge (D(a) \to E(a))$ $ \exists$ instantiation P2
        2 $ \sim A(a)$ Conjunctive simplification 1
        3 $ \sim A(a) \vee B(a)$ Disjunctive addition 2
        4 $ A(a) \to B(a)$ Definition of $ \to$ 3
        5 $ C(a) \vee D(a)$ $ \forall$ modus ponens P1, 4
        6 $ D(a) \to E(a)$ Conjunctive simplification 1
        7 $ \ \vline \ \sim (\sim B(a) \vee E(a))$ Assume --
        8 $ \ \vline \ B(a) \wedge \sim E(a)$ Double negation, DeMorgan's law 7
        9 $ \ \vline \ \sim E(a)$ Conjunctive simplification 8
        10 $ \ \vline \ \sim D(a)$ Modus tollens 6, 9
        11 $ \ \vline \ C(a)$ Disjunctive syllogism 5, 10
        12 $ \ \vline \ C(a) \wedge \sim A(a)$ Conjunctive addition 2, 11
        13 $ \ \vline \ \sim (\sim C(a) \vee A(a))$ Double negation, DeMorgan's law 12
        14 $ \ \vline \ \sim (C(a) \to A(a))$ Definition of $ \to$ 13
        15 $ \ \vline \ E(a)$ $ \forall$ modus tollens, Double negation P3, 14
        16 $ \ \vline \ E(a) \wedge \sim E(a)$ Conjunctive addition 15, 9
        17 $ \sim B(a) \vee E(a)$ Closing cond world w/ contra 7-16
        18 $ \exists h \in D \ \sim B(h) \vee E(h)$ $ \exists$ generalization 17



        Another way:



        Line Statement Rule Lines Used
        1 $ \sim A(a) \wedge (D(a) \to E(a))$ $ \exists$ instantiation P2
        2 $ \sim A(a)$ Conjunctive simplification 1
        3 $ D(a) \to E(a)$ Conjunctive simplification 1
        4 $ \sim A(a) \vee B(a)$ Disjunctive addition 2
        5 $ A(a) \to B(a)$ Definition of $ \to$ 4
        6 $ C(a) \vee D(a)$ $ \forall$ modus ponens P1, 5
        7 $ \ \vline \ C(a)$ Assume --
        8 $ \ \vline \ C(a) \wedge \sim A(a)$ Conjunctive addition 7, 2
        9 $ \ \vline \ \sim (C(a) \to A(a))$ Definition of $ \to$ 8
        10 $ \ \vline \ E(a)$ $ \forall$ modus tollens 9, P3
        11 $ C(a) \to E(a)$ Closing cond world w/out contra 7-10
        12 $ E(a)$ Dilemma 6, 3, 11
        13 $ \sim B(a) \vee E(a)$ Disjunctive addition 12
        14 $ \exists h \in D \ \sim B(h) \vee E(h)$ $ \exists$ generalization 13


    3. P1 $ \forall w \in D \ J(w) \to M(w)$
      P2 $ \forall x \in D \ M(x) \to ((N(x) \to \sim J(x)) \wedge \sim K(x))$
      P3 $ \forall y \in D \ N(y) \vee \sim L(y)$
      P4 $ \forall z \in D \ (J(z) \wedge K(z)) \vee (L(z) \wedge M(z))$
      % latex2html id marker 1359 $ \therefore$ $ \forall q \in D \ \sim J(q)$
      • Answer:



        Line Statement Rule Lines Used
        1 $ N(a) \vee \sim L(a)$ $ \forall$ instantiation P3
        2 $ (J(a) \wedge K(a)) \vee (L(a) \wedge M(a))$ $ \forall$ instantiation P4
        3 $ \ \vline \ J(a)$ Assume --
        4 $ \ \vline \ M(a)$ $ \forall$ modus ponens P1, 3
        5 $ \ \vline \ (N(a) \to \sim J(a)) \wedge \sim K(a)$ $ \forall$ modus ponens P2, 4
        6 $ \ \vline \ N(a) \to \sim J(a)$ Conjunctive simplification 5
        7 $ \ \vline \ \sim N(a)$ Modus tollens, double neg 6, 3
        8 $ \ \vline \ \sim L(a)$ Disjunctive syllogism 1, 7
        9 $ \ \vline \ \sim K(a)$ Conjunctive simplification 5
        10 $ \ \vline \ \sim J(a) \vee \sim K(a)$ Disjunctive addition 9
        11 $ \ \vline \ \sim (J(a) \wedge K(a))$ double neg, DeMorgan's law 10
        12 $ \ \vline \ L(a) \wedge M(a)$ Disjunctive syllogism 2, 11
        13 $ \ \vline \ L(a)$ Conjunctive simplification 12
        14 $ \ \vline \ L(a) \wedge \sim L(a)$ Conjunctive addition 8, 13
        15 $ \sim J(a)$ CCW w/ contra 3-14
        16 $ \forall q \in D \ \sim J(q)$ $ \forall$ generalization 15



        Another way:



        Line Statement Rule Lines
        1 $ M(a) \to ((N(a) \to \sim J(a)) \wedge \sim K(a))$ $ \forall$ instantiation P2
        2 $ \sim M(a) \vee ((N(a) \to \sim J(a)) \wedge \sim K(a))$ Definition of $ \to$ 1
        3 $ \ \vline \ \sim M(a)$ Assume --
        4 $ \ \vline \ \sim J(a)$ $ \forall$ modus tollens P1, 3
        5 $ \sim M(a) \to \sim J(a)$ CCW w/out contra 3-4
        6 $ \ \vline \ (N(a) \to \sim J(a)) \wedge \sim K(a)$ Assume --
        7 $ \ \vline \ N(a) \to \sim J(a)$ Conjunctive simp 6
        8 $ \ \vline \ \sim K(a)$ Conjunctive simp 6
        9 $ \ \vline \ \sim J(a) \vee \sim K(a)$ Disjunctive addition 8
        10 $ \ \vline \ \sim (J(a) \wedge K(a))$ DeMorgan's law 9
        11 $ \ \vline \ (J(a) \wedge K(a)) \vee (L(a) \wedge M(a))$ $ \forall$ instantiation P4
        12 $ \ \vline \ L(a) \wedge M(a)$ Disjunctive syllogism 10, 11
        13 $ \ \vline \ L(a)$ Conjunctive simp 12
        14 $ \ \vline \ N(a) \vee \sim L(a)$ $ \forall$ instantiation P3
        15 $ \ \vline \ N(a)$ Disjunctive syllogism 13, 14
        16 $ \ \vline \ \sim J(a)$ Modus ponens 15, 7
        17 $ [ (N(a) \to \sim J(a)) \wedge \sim K(a) ] \to \sim J(a)$ CCW w/out contra 6-16
        18 $ \sim J(a)$ Dilemma 2, 5, 17
        19 $ \forall q \in D \ \sim J(q)$ $ \forall$ generalization 18


  2. Translate each of the following into formal language using the sets and predicates given.
    1. Exactly two people completely understand quantum physics. ($ U =$ {universal set}, $ P(m) = m$ is a person, $ Q(n) = n$ completely understands quantum physics.)
      • Answer:
        $ \exists a,b \in U \ P(a) \wedge Q(a) \wedge P(b) \wedge Q(b) \wedge a\neq b \wedge \forall x \in U \ (P(x) \wedge Q(x)) \to (a=x \vee b=x)$
    2. I own at least three cats. ($ C =$ {all cats}, $ N(x) =$ I own $ x$.)
      • Answer: $ \exists a,b,c \in C \ N(a) \wedge N(b) \wedge N(c) \wedge a\neq b \wedge b\neq c \wedge c\neq a$
    3. No more than two people own both a kangaroo and a polar bear. ($ P =$ {all people}, $ K(p) = p$ owns a kangaroo, $ B(p) = p$ owns a polar bear.)
      • Answer:
        $ \forall p, q, r \in P \ (K(p) \wedge K(q) \wedge K(r) \wedge B(p) \wedge B(q) \wedge B(r)) \to (p = q \vee q = r \vee r = p)$

  3. For each of the following, decide if the argument is valid or invalid, and write ``invalid'' or ``valid'' as appropriate. If it is invalid, draw an Euler diagram to verify this fact. If it is valid, draw an Euler diagram that shows the premises and conclusion all to be true.
      • All shortshops can steal bases.
      • Some shortstops can hit home runs.
      • Therefore, some shortstops can steal bases and hit home runs.
        • Answer: VALID
          \includegraphics[scale=.6]{hw4eu1}
      • All CS professors are intelligent.
      • All CS professors like music.
      • Therefore, all intelligent people like music.
        • Answer: INVALID
          \includegraphics[scale=.6]{hw4eu2}
      • Some textbooks are cheap.
      • Some textbooks are useful.
      • Therefore, some textbooks are cheap and useful.
        • Answer: INVALID
          \includegraphics[scale=.6]{hw4eu3}

  4. In this problem, you are given a number of situations in English. For each situation, you must determine which symbolic expression(s) from the given list are true in that situation.

    Let $ L$ be the set of people {Kate, Lisa, John}, let $ M$ be the set of musical instruments {piano, trumpet, accordian}, and let the predicate $ P(x,y)$ mean ``person $ x$ plays instrument $ y$.''

    Symbolic expressions to choose from:

    (1)
    $ \forall x \in L \ \exists y \in M \ P(x, y)$
    (2)
    $ \exists x \in L \ \forall y \in M \ P(x, y)$
    (3)
    $ \forall y \in M \ \exists x \in L \ P(x, y)$
    (4)
    $ \exists y \in M \ \forall x \in L \ P(x, y)$

    You may assume that in each situation, each person plays only the instruments listed for him or her, and no others. In other words, if its not listed, they don't play it!

    Remember, for each situation, write down the corresponding numbers of all the symbolic expressions that apply to that situation.

    Situations:

    1. John plays piano, Kate plays trumpet, and Lisa plays accordian.
      • Answer: 1 and 3.
    2. John plays piano, Kate plays piano and trumpet, and Lisa plays piano and accordian.
      • Answer: 1, 3, and 4.
    3. John plays trumpet, Kate plays piano, trumpet, and accordian, and Lisa doesn't play anything.
      • Answer: 2 and 3.
    4. John plays trumpet, Kate plays piano and trumpet, and Lisa plays trumpet.
      • Answer: 1 and 4.
    5. John plays trumpet, Kate doesn't play anything, and Lisa plays piano and accordian.
      • Answer: 3.
    6. John plays accordian, Kate plays piano and accordian, and Lisa plays piano.
      • Answer: 1.
    7. John plays piano, trumpet, and accordian, Kate plays trumpet and accordian, and Lisa plays accordian.
      • Answer: 1, 2, 3, and 4.
    8. John plays piano and trumpet, Kate plays piano and accordian, and Lisa plays piano, trumpet, and accordian.
      • Answer: 1, 2, 3, and 4.

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002 (1.62)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -nonavigation -antialias_text -antialias hw4ans

The translation was initiated by Phillip Kirlin on 2004-02-25

Phillip Kirlin 2004-02-25

Web Accessibility