Homework #9



1.  Show that if a language L and its complement are both recursively
    enumerable,  then L is recursive.


    Solution:
        +------------------+
        |                  +---> "yes"
        |      +--+ "yes" /|
        |   +->|M1|------+ |
        |  /   +--+        |
        | /                |
    w-----                 |
        | \                +---> "no"
        |  \   +--+ "yes" /|
        |   +->|M2|------+ |                         |
        |      +--+        |
        |                  |
        +------------------+


        Since L, L complement are recursively enumerable,
        there exist M_L, M_{L complement} accepting them (these machines need
        not halt when rejecting).

        Forall w, either w in L or w in L complement, so at least one of
        M_L, M_{L complement} accepts w.  Thus M' always halts and decides
        whether w in L correctly; thus L is recursive.


2.  Translate the following sentences into first-order predicate calculus,
    drawing symbols from the following lists:


    Predicates			Variables		Constants
       shorter(2 parms)		   x,y,p1,p2,t1,t2	   YOU,Tom,Karen,Wilt
       taller(2 parms)
       person(1 parm)
       equal(2 parms)
       look_alike(2 parms)
       people(1 parm)
       time(1 parm)
       can_fool_at_time(3 parms)

    a) Walt is shorter than Wanda.
    b) There is no one taller than Larry.
    c) No two people look alike.
    d) You can fool some of the people all of the time, and all of the people
       some of the time, but you can't fool all of the people all of the time.


    Solution:

    a)  shorter(Walt,Wanda)
    b)  forall x [-taller(x,Larry)]
	  OR
	-exists x [taller(x,Larry)]
    c)  forall x,y [person(x) & person(y) & -equal(x,y) => -look_alike(x,y)]
    d)  exists p1, t1, forall p2, t2
         [(time(t2) => (people(p1) ^ can_fool_at_time(You, p1, t2))) ^
          (people(p2) => (time(t1) & can_fool_at_time(You, p2, t1))) ^
          (time(t1) ^ people(p1)) => -can_fool_at_time(You, p1, t1))]

   3.  Use truth tables to show that the following sentences are valid and thus
       that the equivalences hold.

       a) P ^ (Q ^ R)  <=>  (P ^ Q) ^ R
       b) P ^ (Q v R)  <=>  (P ^ Q) v (P ^ R)
       c) P <=> Q  <=>  (P ^ Q) v (-P ^ -Q)

       Solution:

       a) P Q R | (Q^R) (P^Q) P^(Q^R) (P^Q)^R LHS<=>RHS
	  ------+--------------------------------------
	  T T T |   T     T      T       T        T
	  T T F |   F     T      F       F        T
	  T F T |   F     F      F       F        T
	  T F F |   F     F      F       F        T
	  F T T |   T     F      F       F        T
	  F T F |   F     F      F       F        T
	  F F T |   F     F      F       F        T
	  F F F |   F     F      F       F        T

       b) P Q R | (QvR) P^(QvR) (P^Q) (P^R) ((P^Q)v(P^R)) LHS<=>RHS
	  ------+--------------------------------------------------
	  T T T |   T     T       T     T         T           T
	  T T F |   T     T       T     F         T           T
	  T F T |   T     T       F     T         T           T
	  T F F |   F     F       F     F         F           T
	  F T T |   T     F       F     F         F           T
	  F T F |   T     F       F     F         F           T
	  F F F |   F     F       F     F         F           T
	  
       c) P Q R | (P<=>Q) (P^Q) -P -Q (-P^-Q) ((P^Q)v(-P^-Q)) LHS<=>RHS
	  ------+------------------------------------------------------
	  T T T |    T      T    F  F    F          T             T
	  T T F |    T      T    F  F    F          T             T
	  T F T |    F      F    F  T    F          F             T
	  T F F |    F      F    F  T    F          F             T
	  F T T |    F      F    T  F    F          F             T
	  F T F |    F      F    T  F    T          F             T
	  F F T |    T      F    T  T    T          T             T
	  F F F |    T      F    T  T    T          T             T
   4.  Look at the following sentences and decide for each if it is valid,
       unsatisfiable, or satisfiable.  Verify with truth tables or using
       rules given in class.

       a) Smoke => Smoke
       b) Smoke => Fire
       c) ((Smoke ^ Heat) => Fire) <=> ((Smoke => Fire) | (Heat => Fire))

       Solution:
         a) VALID
         b) SATISFIABLE
         c) VALID


   5.  Jones, Smith, and Clark hold the jobs of programmer, software engineer,
       and manager (not necessarily in that order).  Jones owes the programmer
       $10.  The manager's spouse prohibits borrowing money.  Smith is not
       married.  Your task is to figure out which person has which job
       using the equivalence rules and inference rules given in class.

       Represent all of the facts in propositional logic.  You should have nine
       propositional symbols throughout the entire proof, one to represent each
       possible person/job assignment.  You do not need to represent the
       relation between owing and borrowing, or between being married and having
       a spouse; you can just use these to draw conclusions (e.g., from "Smith"
       is not married" and "the manager's spouse" we know that Smith cannot be
       the manager, or -SM).  A solution will be a conjunction of the form
       JP ^ SK ^ CM.  Justify every conclusion you draw.

       Solution:
	    /* Represent the fact that each person has one job */
          1) JP v JK v JM
          2) SP v SK v SM
          3) CP v CK v CM
	    /* Represent the each job is held by one person */
          4) JP v SP v CP
          5) JK v SK v CK
          6) JM v SM v CM
	    /* Represent the fact that each person has at most one job
	       by a series of disjunctions of the form show below */
	  7) {-JP v -JK}, {-JP v -JM},  etc.
	    /* Represent the fact that each job is held by at most one person
	       by a series of disjunctions of the form show below */
	  8) {-JP v -SP}, {-JP v -CP}, etc.
	    /* Jones owes the programmer $10 */
	  9) -JP
	    /* The manager's spouse prohibits borrowing money */
	 10) -JM
	    /* Smith is not married */
	 11) -SM
            /* Resolve 1 and 7 */
	 12) JK v JM
            /* Resolve 4 and 7 */
	 13) SP v CP
            /* Resolve 6 and 7 */
	 14) SM v CM
            /* Resolve 8 and 10 */
	 15) JK
            /* Resolve 9 and 12 */
	 16) CM
	    /* Recall from step 8 that we have the disjunction -JKv-SK,
	       resolve this and 15 */
	 17) -SK
	    /* Resolve 2 and 11 */
	 18) SP v SK
	    /* Resolve 17 and 18 */
	 19) SP
	    /* And Introduction applied to 15, 16, and 19 */
	 20) JK & SP & CM