CMSC 250 KEY Quiz #2 Monday, Sept. 17, 2001

Write all answers legibly in the space provided. The number of points possible for each question is indicated in square brackets - the total number of points on the quiz is 30, and you will have exactly 15 minutes to complete this quiz. You may not use calculators, textbooks or any other aids during this quiz.
  1. [10 pnts.] Use a Truth Table to determine if the following is a valid argument.

    $\sim r \vee q$
    $ p \rightarrow r $
    $ q \rightarrow r$
    $ --------------$
    therefore $\sim ( p \wedge q )$
     
    Circle One: Valid (Invalid)
     

    p q r $\sim r$ $\sim r \vee q$ $ p \rightarrow r $ $ q \rightarrow r$ $p \wedge q$ $\sim ( p \wedge q )$  
    1 1 1 0 1 1 1 1 0 Critical-Invalid
    1 1 0 1 1 0 0 1 0  
    1 0 1 0 0 1 1 0 1  
    1 0 0 1 1 0 1 0 1  
    0 1 1 0 1 1 1 0 1 Critical
    0 1 0 1 1 1 0 0 1  
    0 0 1 0 0 1 1 0 1  
    0 0 0 1 1 1 1 0 1 Critical

  2. [8 pnts.] Draw the simplest diagram (fewest number of gates) which will represent the expression given by the following truth table.

    p q r Output
    1 1 1 0
    1 1 0 0
    1 0 1 0
    1 0 0 0
    0 1 1 1
    0 1 0 1
    0 0 1 0
    0 0 0 1

    Expression in Reduced form :

    \begin{displaymath} \sim p \wedge (q \vee \sim r) \end{displaymath}

    Expression in non-Reduced form :

    \begin{displaymath} (\sim p \wedge q \wedge r) \vee (\sim p \wedge q \wedge \sim r) \vee (\sim p \wedge \sim q \wedge \sim r) \end{displaymath} 

    
       |***|
P  ----|NOT|-----------------+
       |***|                 |
                             +----|***|
                                  |AND| ---
Q  -------------+            +----|***|  
                +---|**|     |
                    |OR|-----+ 
       |***|    +---|**|
R  ----|NOT|----+
       |***|

  3. [12 pnts.] Use the handout of the ``Logical Equivalence Rules'' and the ``Rules of Inference'' to prove the following. It is a Valid Argument - you need to prove it without using a truth table.

    P1 $\sim (q \vee \sim p) $
    P2 $ \sim z \rightarrow \sim s$
    P3 $(p \wedge \sim q) \rightarrow s$
    P4 $ \sim z \vee r $
      $ --------------$
      therefore $r$

    Line # Logical Statement Name of Rule Line Numbers Used
    1 $\sim q \wedge \sim \sim p$ DeMorgan's Law P1
    2 $\sim q \wedge p$ Double Negative 1
    3 $p \wedge \sim q$ Commutative 2
    4 $s$ Modus Ponens P3, 2
    5 $\sim \sim s$ Double Negative 4
    6 $\sim \sim z$ Modus Tollens P2, 5
    7 $r$ Disjunctive Syllogism P4, 6
      OR    
    1 $\sim q \wedge \sim \sim p$ DeMorgan's P1
    2 $\sim \sim p \wedge \sim q$ Commutative 1
    3 $p \wedge \sim q$ Double Negative 2
           
    4 $s$ Modus Ponens P3, 3
    5 $\sim \sim z \vee \sim s$ Definition of Implication P2
    6 $z \vee \sim s$ Double Negative 5
    7 $\sim \sim s$ Double Negative 4
    8 $z$ Disjunctive Syllogism P4, 7
    9 $\sim \sim z \rightarrow r$ Definition of Implication P4
    10 $z \rightarrow r$ Double Negative 9
    11 $r$ Modus Ponens 10, 8

About this document ...

This document was generated using the LaTeX2HTML translator Version 99.1 release (March 30, 1999)

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 -show_section_numbers -split 0 -no_navigation -no_footnode quiz2k

The translation was initiated by John Arras on 2001-10-10

John Arras
2001-10-10