Homework #9 1. Show that if a language L and its complement are both recursively enumerable, then 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,Walt,Wanda,Larry 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. 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) 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)) 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.