ITEC 122 2008fall ibarland

home—info—lectures—exams—archive

hw02
Quantifiers

Although you are welcome to typeset your work nicely (using Microsoft Word or LaTeX or whatever to get nice logic symbols), it's probably much easier to write formulas by hand.

1. (4pts) TeachLogic exercises I: #24 (algebra).
   Justify each step by using one of the rules of Rosen's §1.2 tables 6,7,8. (Alternately, you can use the set of rules from the TeachLogic project.)
   (Your answers will be in the same format as the problems in Rosen section 1.2, examples 5,6. and TeachLogic: propositional algebra.)

2. Logic and eBay You might think to yourself, after the problem on Logiconian web pages from the previous homework, “great, maybe we can use propositional logic for web queries, but no search-engine I've ever seen lets me type ‘∧’ or ‘∨’.” Different search engines on the web have their own syntax for specifying searches.

   Aside: 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 search engines allow full Boolean queries. Some interpret a list of several words in a row as an implicit conjunction (AND), while others might as an implicit disjunction (OR).

   Read over the search syntax for the search language of eBay®.

   1. (1pt) Write an eBay 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].
   2. (1pt) A hard-of-hearing friend was told about the superbowl playoff, which they mis-heard as something about a superb bowl for pilaf. Excited at such a concept, they immediately tried searching eBay for such a useful bowl! What would you guess the natural eBay query is for auctions which either contain “pilaf”, or contain both “bowl” and “superb” (not necessarily next to each other)?
   3. (2pts)
      1. How many eBay auctions contain “pilaf”?                  (Probably not too many.)
      2. How many eBay auctions contain “bowl” or “superb” (anywhere in the page)?                  (Probably quite a few.)
      3. Based on the previous two answers, what is the most number of auctions which could contain both “pilaf” and (“bowl” or “superb”)?                  What is the fewest?                 
   4. (3pts) Re-write ((superb∧bowl)∨pilaf) in conjunctive normal form (CNF). How many pages match this query?                 

   Aside: 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 discrete math student on their programming staff, and thus didn't think deeply about their syntax.

3. Logic and Email: In Microsoft's mail program Entourage, a user can set up different folders for filing their messages. Moreover, there is even a way to set up rules, so that incoming messages get auto-filed into a certain folder. For example, I have a rule set up so that all mail from and to certain mailing lists ("[ap-compsci]" and "[sigcse-members]") are automatically moved into a specific mail folder (see picture).

   
   

   Near the top-right of that image, notice that the rule is applied ("executed") for incoming messages which meets any of my four criteria. That is, Entourage combines the four criteria (call them a, b, c, d) and executes the rule whenever the propositional logic formula (a∨b∨c∨d) is true.

   1. (2pts) There are three more options which Entourage can use, to combine the four criteria into one bigger one (see picture).
      For each of the three other options, give a propositional logic formula (involving a, b, c, d) which determines whether Entourage will apply the rule.
   2. (1pt) What is a formula which cannot be expressed in Entourage?

4. (3pts) Logic and iTunes: Besides the mail program above, many other programs also let users combine several small conditions (formulas) by connecting those conditions with AND, or by connecting those conditions with OR. iTunes is one such example: the screen-shot at right specifies songs which “Match any of the following rules” (OR); it could also be set to “Match all of the following rules” (AND).

   
   

   In iTunes, one can create “smart playlists” — really, a formula which determines whether a particular song gets should be added to a playlist. For example, the image shown specifies a smart-playlist which contains all songs which “have a five-star-rating, OR have not been played in over a year”. After creating this smart-playlist, we name it “high-priority”; the second screen-shot lets you glimpse songs 12-19 on the playlist “high-priority”.
   

   1. After the preceding problem (3b) about email queries, you might initially think that there is no way to express a formula for all songs which “(have a five-star-rating, or have not been played in over a year), and are not ABBA”. However, there is an indirect way of doing it: iTunes allows options of the form “the song is on the playlist ________”. Use this option, along with existing playlists, to make a playlist which contains exactly those songs which have (have a five-star-rating, or have not been played in over a year), and are not ABBA.

   2. Suppose you want to make a query of the form (a∧(b∨(c∧(d∨e)))). What is the minimum number of playlists you'll need to create?

   3. What happens if you try to make a smart-playlist named "weird-list", which consists of: All songs whose playlist is equal to "weird-list" (?!). That would be an odd playlist, but it's one you can imagine creating. Do you think Abba's "SOS" should be included in "weird-list"?

   4. Even worse: What happens if you try to make a smart-playlist named "twisted", which consists of: All songs whose playlist is not equal to "twisted". Yikes! If you made such a playlist, should it include Abba's "SOS"?

   5. How, do you think, does iTunes prevent itself from creating such odd playlists?
      (If you want to confirm your guess, you can download iTunes for Windows or Mac.)

      To verify for yourself: does iTunes also prevent a pair of playlists with a mutual dependency?

5. (4pts) Rosen p.47 #6 (5ed: p.40 #6).
   To save writing:
   • Use “all people” as the domain, rather than “students in your school”;
   • write “N.D.” for “North Dakota”.
   
   Your sentences should be concise and natural English. For example, for (a), the formula “∃x.N(x)” should be translated to “Somebody has visited N.D.” rather than the (much more awkward) “There exists a person x such that x has visited N.D.”.
   1. ∃x.N(x)
   2. ∀x.N(x)
   3. ¬∃x.N(x)
   4. ∃x.¬N(x)
   5. ¬∀x.N(x)
   6. ∀x.¬N(x)
6. (4pts) Rosen p.47 #8. (5ed: p.40 #8)
   Your sentences should be concise and natural English.
   1. ∀x.(R(x)→H(x))
   2. ∀x.(R(x)∧H(x))
   3. ∃x.(R(x)→H(x))
   4. ∃x.(R(x)∧H(x))
7. (5pts) Rosen 6ed: p47, #10 (= Rosen 5ed: p40, #10): (raining cats and dogs ... and ferrets.)
   1. “A student in the class has a cat, a dog, and a ferret.”
   2. “All students in the class have a cat, a dog, or a ferret.”
   3. “Some student in the class has a cat and a dog, but not a ferret.”
   4. “No student in the class has a cat, a dog, and a ferret.”
   5. “For each of the three types of animal, there is a student who has one of that type.”
8. (6pts) Rosen p.47 #12. (5ed: p.41 #12)
   Let Q(x) be the statement “x+1 > 2x”. If the domain is the set of integers Z = {…,-2,-1,0,+1,+2,…}, what are these truth values?
   1. true or false?: Q(0)
   2. true or false?: Q(-1)
   3. true or false?: Q(1)
   4. true or false?: ∃x . Q(x)
   5. true or false?: ∀x . Q(x)
   6. true or false?: ∃x . ¬Q(x)
   7. true or false?: ∀x . ¬Q(x)

home—info—lectures—exams—archive

©2008, Ian Barland, Radford University Last modified 2008.Oct.10 (Fri)

Please mail any suggestions (incl. typos, broken links) to iba�rlandrad�ford.edu