Do problems 1-19 (inclusive), less the practice-problems (which already have a solution). Due 2004.Jan.27 (Tue), either at the start of class or under the instructor's door (DH3117) by 17:00, to avoid the late penalty. Rice Students: If you like, you can play WaterWorld on OwlNet, in /home/scheme/bin/waterworld. To run Waterworld on your home computer, download (from owlnet) the directory /home/scheme/plt/203/collects/waterworld/, and (from drscheme) add it as a teachpack.

Propositional Logic [practice] 0pts Your friend Tracy argues: "It is bad to be depressed. Watching the news makes me feel depressed. Thus it's good to avoid watching the news." Regardless of whether the premises and conclusion are true, show that the argument is not, by showing it doesn't hold for all domains. Replace "depressed" and "watching news" with expressions which leave the premises true, but the conclusion false (or at least, what most reasonable people would consider false). Lots of possible counterexamples. "It is bad to be depressed. Doing homework makes me depressed; so it's good to not do my homework." Or, "It is bad for people to be in physical pain. Childbirth causes pain. Therefore childbirth needs be avoided by all people." If the original conclusion is really correct, Tracy needs to elucidate some of his unspoken assumptions. The flaw seems to be along the lines of, "avoiding bad in the short run may not always be good in the long run" (or equivalently, sometimes you have to choose the lesser of two evils). No, you weren't asked to name a specific flaw, and reasonable people can differ on precisely what the flaw is. (And, formal logic is not particularly helpful here.) Nonetheless, uncovering hidden assumptions in arguments often helps understand the real issues involved. For fun, pick up the front page of the daily newspaper, and see how many arguments use faulty rules of inference and/or rely on unspoken premises (which not all might agree with). In particular, political issues as spun to the mainstream press are often riddled with error, even though there are usually reasonable arguments on both sides which policy-makers and courts debate. [practice] 0pts An acquaintance says the following to you: "Chris claims knowledge is more important than grades. But she spent yesterday doing an extra-credit assignment which she already knew how to do. Therefore, she's a hypocrite and deserves no respect." Regardless of whether the premises and conclusion are true, show that the argument is not, by showing it doesn't hold for all domains. Replace "knowledge" and "grades" with expressions which give you true premises, but a false conclusion (or at least, what most reasonable people would consider false). Exaggerate "knowledge" to something more important, and "grades" to something less important. "Terry claims that encouraging human-rights is more important than playing Tetris. But Terry played Tetris yesterday (rather than volunteering with Amnesty International)." Most people wouldn't condemn Terry as a hypocrite just because of this; even the most dedicated of people are entitled to some free time. If your friend wants to prove Terry hypocritical, they'll have to provide further evidence or arguments. (1pt) Choose just one of the following informal arguments. For your choice, give a different conclusion -- a counterexample -- which is equally well justified by the provided argument, yet is false (or at least, clearly more false than the original). For this exercise, strive for realistic counterexample, rather than exagguratedly trivial as on the previous exercises. Since 18-to-20 year olds aren't particularly mature, the minimum drinking age needs be (at least) 21. Talking on a cell phone while driving increases the likelihood of an accident. Interestingly, hands-free phones does not significantly help. It's just the distraction of a phone conversation that causes the problem. If two companies offer two entirely equivalent products, then most everybody will buy the cheaper one. In the free market, if a company doesn't offer good service, individual customers will become fed up and take their business elsewhere. If there are two versions of a free web browser, and they run equally quickly, users will use the one with better features/interface. Anybody who really wants to break into your house while you're gone will be able to. (For instance, using a towel to muffle sound, break the corner of a back window, reach in and unlatch the window, and climb through.) So there's no point in locking your front door. One the age of maturity: Voting, being drafted to combat, smoking -- all are activities (arguably) at least as much maturity, yet they don't have a minimum age of 21. There may be other reasons why drinking has a higher threshold, but they aren't acknowledged by the original argument. Cell phones: The argument doesn't acknowledge the "phone" part of the conversation at all, so it leads equally well to: "A conversation between driver and passenger is just as dangerous." ¶ In reality, phone conversations are presumably more dangerous than those with a passenger; a good argument leads to trying to identify/hypothesize the difference. ¶ I suspect it would be the that a passenger is aware of the road conditions, and routinely pauses the conversation when the driver needs to pay extra attention (while passing, etc.) This hypothesis is certainly testable, though psychologists have their work cut out for them actually trying to measure this effect formally. ¶ (Experiments have controlled for the personality-type which tends to have a cell phone in the first place.) People by cheapest of two equivalent products: Counterexample: generics. Aspirin, Mouthwash, etc. Some are essentially identical to the name-brand product, yet people will prefer the name-brand. Partly, out of confidence -- while some generics are the same as their counterpart, you don't always know that; it's more efficient to buy a brand-name than to be constantly questioning your selections. ¶ Other interesting counterexamples are artificial diamonds (atom-for-atom equivalent to a real diamond), and indistinguishable copies of famous artwork. ¶ In my personal experience: While many generics are as effective as their counterparts, don't dally with bargain dental floss -- it's not worth it! --ian On businesses' having their customers' best interest in mind: Car or house sales -- where an individual doesn't do routine business. Car dealers routinely use deceptive tactics, and closing on a house often includes "junk fees" -- perhaps part of a realtor's deserved profit, but certainly not labeled as such. As a counterexample, there are browsers available which block pop-ups as a simple preference. However, several leading browsers don't include this feature (or didn't until recently). Despite not having additional features of significance, many people tend to stick with the browser they have; perhaps it's not worth their time to always be hunting for a better one. Thus inferior products can still enjoy market use. By this same "it won't stop a determined burglar" reasoning, you should leave your front door unlocked (over even wide open). Clearly, while a determined burglar admittedly can be hard to foil, there may well be many less-determined burglars (or neighborhood hooligans) who would be stopped by a lock, since they're not willing to break a window. [practice] 0pts Let p, q, and r be the following propositions: p: You get an A on the final exam q: You do every exercise in the book. r: You get an A in this class. Write the following formulas using p, q, and r and logical connectives. You get an A in this class, but you do not do every exercise in the book. To get an A in this class, it is necessary for you to get an A on the final. Getting an A on the final and doing every exercise in the book is sufficient for getting an A in this class. r ∧ ¬q r → p p ∧ q → r (1pt) Translate the following English sentences into propositional logic. Your answers should be WFFs. If the Astros win the series ("AW"), then pigs will fly ("PF"). Pigs will not fly, and/or bacon will be free ("BF"). The Astros will win the series, or bacon will be free (but not both). AW → PF. ¬PF ∨ BF. Note that this is equivalent to PF → BF; here, we happen choose the phrasing which more closely mirrors the original problem statement. AW ∨ BF ∧ ¬ AW ∧ BF . Alternatively, AW ∧ ¬BF ∨ ¬AW ∧ BF This is the "exclusive or" (sometimes called "xor"). [practice] 0pts It just so happens that all the web pages in Logiconia which contain the word "Poppins" also contain the word "Mary". Write a formula (a query) expressing this. Use the proposition Poppins to represent the concept "the web page contains 'Poppins'" (and similar for Mary). Poppins → Mary (1pt) It further happens to be the case that: If a Logicanian page contains the word "weasel", then it also contains either "words" or "eyed"; and whenever a Logiconian page contains the word "mongoose", it does not also contain the word "weasel"; and finally, all Logiconian pages contain the word "Logiconia", rather patriotically. Write a formula expressing all this. (Your formula will involve six propositions -- weasel, etc.. Try to find a formula which mirrors the wording of the English above.) If a web page in Logiconia does not contain "weasel", does it contain "mongoose"? Let's go meta for a moment: What can you conclude about this web page? (Yes, this one you're looking at now -- the one with the homework problems.) Why? weasel → words ∨ eyed ∧ mongoose → ¬weasel ∧ Logiconia No, a Logiconian web page may contain neither of those words. This web page contains both words; you may conclude that this web page isn't Logiconian! (If you are buying into the truth of what this page says about Logiconian pages.) (3pts) Different search engines on the web have their own syntax for specifying searches. Note that a formula may be true for some web pages, and false for others. The search engine is concerned with finding all web pages which satisfy the formula. This is called a query, in database lingo. Some allow full Boolean queries. Some interpret a list of several words in a row as an implicit conjunction, others as an implicit disjunctions. Read over the search syntax for the search language of eBay®. Write a query for auctions which contain "border", do not contain "common", and contain at least one of "foreign" or "foriegn" [sic -- misspellings are a great way to find underexposed auctions]. An hard-of-hearing friend was told about the superbowl playoff, but instead heard something about a superb bowl for pilaf. Excited at such a concept, what would you guess the natural query is for auctions which either contain "pilaf", or contain both "superb" and "bowl" (in either order)? Test your previous answer on eBay. How many matches do you get? How many do you get if you swap the order of "superb" and "bowl"? How about for each of "pilaf" and "superb bowl" as separate queries? Re-write superb ∧ bowl ∨ pilaf in conjunctive normal form (CNF). Confirm that this query transliterates to a more reliable ebay query. Apparently, eBay expects their users to: (a) realize their query isn't working, (b) realize that some equivalent query can work, and (c) be adept at Boolean algebra to find the working equivalent query. More likely, they didn't have a comp280/409/412 graduate on their programming staff, and thus didn't think deeply about their syntax. eBay uses sequencing for conjunction, parentheses for disjunction, and a preceding minus sign for negation. border -common (foreign,foreign) The expected ebay query for pilaf ∨ superb ∧ bowl would (just transliterating) (pilaf,superb bowl). The numbers depend on the moment you made the query, but I got: 5 matches for (pilaf,superb bowl) 11 matches for (pilaf,bowl superb) 5 matches for pilaf 84 matches for superb bowl By distributing the ∨ over ∧, superb ∧ bowl ∨ pilaf ≡ superb ∨ pilaf ∧ bowl ∨ pilaf, which can be expressed as (superb,pilaf) (bowl,pilaf), we get a search returning 88 results. Hmm, we should get 5+84, from above. An inspection shows that ebay's results are a bit weird; in fact Pilaf and pilaf both return different results, even though both sets of matches have the word "pilaf" in varying cases. Their search-code is perhaps as confused as their query syntax? Note that there are other problematic queries: It's not entirely clear how to directly encode the query ¬a ∧ b, since our first guess would be to take a b and put a - in front, but that gives us -a b, which is the query for ¬a ∧ b. Here, DeMorgan's law is needed to get an equivalent formula that can be expressed in ebay's syntax. [practice] 0pts

A sample WaterWorld board Consider the particular board shown in the above figure. Y-safe, Y-has-0, and ¬Y-has-2 are among the formulas which are true for this board but not for all boards. (That is, they are not domain axioms or tautologies.) Give two other such formulas. V-safe might or might not be true for this board. Give two other such formulas. There are many simple answers, such as Y-has-1, ¬W-has-1, … There are many simple answers, such as A, N-has-1, J-has-3, … For each, there are also many such formulas composed with connectives such as ∧ and ∨. (4pts) In that same board, is location W safe? What is your informal reasoning? (List all your small steps.) Similarly for location P. X has exactly one neighboring pirate, so exactly one of W and Y must have a pirate. Y does not have a pirate. Therefore W does. We use this fact to continue: Q has exactly one neighboring pirate, so exactly one of P, R, and W must have a pirate. W contains a pirate (by the previous step). Therefore, P and R do not, so P is safe. (1pt) Give a domain axiom of WaterWorld which is not explicitly shown in the WaterWorld domain axioms. (Just show one that's omitted in the ellipses.) Z-has-0 → Y-safe is one domain axiom; another is Q-has-2 → P-unsafe ∧ R-unsafe ∧ W-safe ∨ P-unsafe ∧ R-safe ∧ W-unsafe ∨ P-safe ∧ R-unsafe ∧ W-unsafe or even Q-has-0 ∨ Q-has-1 ∨ Q-has-2 ∨ Q-has-3 ∨ (3pts) Give one WFF which meets all three conditions: true in all WaterWorld boards ("A theorem of WaterWorld") not already listed as one of the WaterWorld domain axioms, and not a tautology of propositional logic (can be made false in some truth assignment, though it may not be a truth assignment which satisfies the waterworld axioms). This can either be a wimpy obvious formula, or can be some pattern you've noticed when playing, that requires several steps of inference. One way to do this is to include weaker formulas. For example, instead of Q-has-2 implying that exactly two neighbors are unsafe, you can imply (just) at least two neighbors are unsafe: Q-has-2 → P-unsafe ∧ R-unsafe ∨ P-unsafe ∧ W-unsafe ∨ R-unsafe ∧ W-unsafe The reason we added the last requirement is so that you don't weaken the formula so much as to be a tautology: Q-has-2 → P-unsafe ∨ P-safe, or more trivially P-unsafe ∨ P-safe, or even just ! A more interesting theorem to deduce is B-has-1 ∧ G-has-1 ∧ H-has-1 → J-unsafe.

Reasoning with Truth Tables (1pt) Write the truth-table for "xnor", the negation of exclusive-or, What is a more common name for this Boolean function? Truth table for xnor abxnor

This the "equals" (for Booleans). (If you said something like "logical equivalence" or "the both-or-neither function", that is a point off, as it's a roundabout way of expressing the simple idea "equals". Granted, it takes some practice to internalize Booleans as values, and that equality is as valid for them as for any other value.) This function is also represented by the connective "↔", and can also called "if-and-only-if". (4pts) Using truth-tables, show that a ∨ c ∧ b → c ∧ c → a is equivalent to b → c ∧ a, but that these are not equivalent to a ∨ c ∧ b → c. We'll name the three formulas of interest. Let χ = a ∨ c ∧ b → c ∧ c → a, υ = b → c ∧ a, and ω = a ∨ c ∧ b → c. A truth table for three functions. abcχυωnotewffy, wffz differwffy, wffz differ

Sure enough, the first two functions χ and υ are the same on each line of the truth table, and hence equivalent to each other. But they differ from the third function ω for a couple couple of truth settings. (4pts) Consider the following conditional code, which returns a boolean value.


int  i;
bool a,b;

…

if (a && (i > 0))
   return b;
else if (a && i <= 0)
   return false;
else if (a || b)
   return a;
else
   return (i > 0);

Simplify it by filling in the following blank with a single Boolean formula (not using a conditional if). For the graders' sake, please use either Java or scheme syntax, and in the former case please parenthesize to make your formula unambiguous (rather than rely having me having memorized Java's 13 levels (with ?:) of operator precedence).


int  i;
bool a,b;

…

return ________________;

When simplifying, you should treat i > 0 as proposition, with i <= 0 as its negation. One possible answer is

(    ( a &&  b) 
                          || (!a && !b)) && (i > 0)

in Java, or in scheme, (and (or (and a b) (and (not a) (not b))) (> i 0)). While our particular syntax for logic formulas doesn't contain an if-and-only-if connective, programming languages do: boolean=? or ==. Using this could shorten our answer: ((a == b) && (i > 0)) in Java, or in Scheme (and (boolean=? a b) (> i 0)). [practice] 0pts When writing a complicated conditional that involves multiple pieces of data, it is easy to incorrectly oversimplify. One strategy for avoid mistakes is to write such code in a two-step process. First, write a conditional with a case for every possible combination, as in a truth table. Second, simplify the conditional. Using this approach, we might obtain the following code after the first step. Simplify this code.


list merge_sorted_lists(list list1, list list2)
{
   if (is_empty(list1) && is_empty(list2))
      return empty_list;
   else if (is_empty(list1) && !is_empty(list2))
      return list2;
   else if (!is_empty(list1) && is_empty(list2))
      return list1;
   else if (!is_empty(list1) && !is_empty(list2)) {
      if (first_element(list1) < first_element(list2))
         return make_list(first_element(list1),
                          merge_sorted_lists(rest_elements(list1),list2));
      else if (first_element(list1) >= first_element(list2))
         return make_list(first_element(list2),
                          merge_sorted_lists(list1,rest_elements(list2)));
   }
}


list merge_sorted_lists(list list1, list list2)
{
   if (is_empty(list1))
      return list2;
   else if (is_empty(list2))
      return list1;
   else {
      if (first_element(list1) < first_element(list2))
         return make_list(first_element(list1),
                          merge_sorted_lists(rest_elements(list1),list2));
      else
         return make_list(first_element(list2),
                          merge_sorted_lists(list1,rest_elements(list2)));
   }
}

Alternatively, we could test the emptiness of the lists in the other order.

Reasoning with Equivalences (6pts) Using algebraic identities (.ps), show that a ∨ c ∧ b → c ∧ c → a is equivalent to b → c ∧ a. This is an algebraic hand-evaluation: a series of formulas joined by ≡. Don't write just portions of previous formulas and mysteriously re-introduce the dropped parts later. For each step, mention which identity you used. It is also helpful if you underline the formula you are rewriting in the next step. You can use commutativity and associativity without using a separate line, but mention when you use it. Some issues to think about (w/o turning in): in a previous exercise we showed this same fact by using truth tables. Which approach appeals more to you? If trying to show equivalent to formulas with 10 propositions (instead of just 3) equivalent, which approach might you try? What about the rest of the previous problem -- showing two formulas non-equivalent -- it is possible to approach this with boolean algebra rather than truth tables. How? Is there some hybrid approach, that would convince you of the non/equivalence of formulas? 1a ∨ c ∧ b → c ∧ c → a 2≡a ∨ c ∧ c → a ∧ b → c. Commutativity of ∧ 3≡a ∨ c ∧ c → a ∧ b → c. Associativity of ∧ (It's okay to combine this with the previous step.) 4≡a ∨ c ∧ ¬c ∨ a ∧ b → c →-to-or 5≡a ∨ c ∧ a ∨ ¬c ∧ b → c Commutativity of ∨ 6≡a ∨ c ∧ a ∨ a ∨ c ∧ ¬c ∧ b → c Distributivity of ∧ over ∨ 7≡a ∨ a ∨ c ∧ ¬c ∧ b → c Commutativity of ∧, Absorption 8≡a ∨ ¬c ∧ ¬¬c ∨ a ∧ b → c Commutativity of ∧, Commutativity of ∨, Double complementation 9≡a ∨ ¬c ∧ a ∧ b → c Absorption with φ being ¬c 10≡a ∧ b → c Commutativity of ∨, Absorption 11≡b → c ∧ a Commutativity of ∧

Ta-dum! We could have saved some repeated-writing by showing as a lemma that a ∨ c ∧ c → a is equivalent to a, and then applying a few commutes rules and the lemma to get the result. (This is allowed, since in Boolean algebra we can replace formulas with equivalent formulas. This is not allowed in all formal systems.) (6pts) Using algebraic identities (.ps), rewrite the formula a → b ∨ c ∧ ¬b to one with fewer connectives. 1a → b ∨ c ∧ ¬b 2≡¬a ∨ b ∨ c ∧ ¬b Definition of →, Eliminating nested ∨. 3≡¬b ∧ a ∨ ¬b ∧ b ∨ ¬b ∧ c Distributivity of ∧ over ∨ 4≡¬b ∧ a ∨ ∨ ¬b ∧ c Complement of ∧ 5≡¬b ∧ a ∨ ¬b ∧ c Dominance of ∨ 6≡¬b ∧ ¬a ∨ c Distributivity of ∧ over ∨ 7≡¬a ∨ c ∧ ¬b Commutativity of ∧ 8≡a → c ∧ ¬b Definition of →

Ugh, that sure was tedious, and also (when done by hand) error-prone. [practice] 0pts Using algebraic identities (.ps), and the definition NORφψ ≡ ¬φ ∨ ψ, express the function ∧ in terms of NOR only. (That is, give a formula only using the connective NOR -- no ∧, ∨, ¬ -- which has the same truth-table as φ ∧ ψ.) First we show that we can write negation in terms of NOR, or more specifically, ¬θ ≡ NORθθ. Checking this on a truth table is pretty easy (there are only two rows to check). But for this question we need to use algebraic manipulation. This can be derived in a couple of simple steps: 1¬θ 2≡¬θ ∧ ¬θ Idempotency of ∧ 3≡¬θ ∨ θ DeMorgan's law 4≡NORθθ definition of NOR

We use this lemma to show our ultimate goal: 1δ ∧ κ 2≡¬¬δ ∧ κ Double Complementation 3≡¬¬δ ∨ ¬κ DeMorgan's law 4≡¬NORδδ ∨ ¬κ Lemma, with θδ 5≡¬NORδδ ∨ NORκκ Lemma, θκ where θ=κ 6≡NORNORδδNORκκ definition of NOR, where φ=NORδδ, and ψ=NORκκ

Note that we judiciously used new meta-variables δ and κ rather than re-using φ and ψ (which would still be correct, but would make the graders need to pay much closer attention to the scope of those variables).

Reasoning with Inference Rules For proofs on this homework, Remember that each step must be justified by one of: "premise", a listed inference rule (.ps) (a previous line number and, if ambiguous, substitutions for the inference rule's metavariables), or a WaterWorld domain axiom. Postponed -- this problem postponed until the next homework; it uses one of the less obvious inference rules which we haven't discussed yet, but will touch upon in lecture Tuesday, 2004.jan.27. Fill in the blank reasons in the following proof that ∨ commutes, that is, χ ∨ υ ⊢ υ ∨ χ. 1χ ∨ υ premise 2subproof:χ ⊢ υ ∨ χ 2.a χ premise for subproof 2.b υ ∨ χ ∨Intro 3subproof:υ ⊢ υ ∨ χ 3.a υ premise for subproof 3.b υ ∨ χ ____________ 4υ ∨ χ ____________

1χ ∨ υ premise 2subproof:χ ⊢ υ ∨ χ 2.a χ premise 2.b υ ∨ χ ∨Intro 3subproof:υ ⊢ υ ∨ χ 3.a υ premise 3.b υ ∨ χ ∨Intro 4υ ∨ χ ∨Elim, by lines 1,2,3, where φ=χ and ψ=υ and θ=υ ∨ χ