Exercises for propositional logic i  (Page 3/5)

Translate the following English sentences into propositional logic. Your answers should be WFF s.

1. If the Astros win the series (

   $\mathrm{AW}$

   ), then pigs will fly (

   $\mathrm{PF}$

   ).

2. Pigs will not fly, and/or bacon will be free (

   $\mathrm{BF}$

   ).

3. The Astros will win the series, or bacon will be free, but not both.

[Practice problem $—$ solution provided.]

It just so happens that all the web pages in Logiconia which contain the word

Poppins

Mary

the web page contains 'Poppins'

• 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 five propositions: $\mathrm{weasel}$ , $\mathrm{words}$ , … Try to find a formula whichmirrors the wording of the English above.)

Given the above statements, if a web page in Logiconia does not contain

weasel

mongoose

Let's go meta for a moment: Is this web page Logiconian? (Yes, this one you're looking at now,the one with the homework problems.) Explain why or why not.

Different search engines on the web have their own syntax for specifying searches.

1. Read about the search syntax for the search language of eBay® . 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. Google£'s advanced search is typical for the online search engines. In particular, you can search for results containing all of $a$ , $b$ , …, at least one of $c$ , $d$ , …, and none of $e$ , $f$ , …. Describe how that corresponds to a Boolean formula.

3. Give an example of a Boolean formula which cannot be rewritten to conform to Google's advanced search interface.

[Practice problem $—$ solution provided.]

Consider the particular board shown in the above figure .

1. $\mathrm{Y-safe}$ , $\mathrm{Y-has-0}$ , and $\neg \mathrm{Y-has-2}$ are among the formulas which are true for this board but not for all boards.That is, they are neither domain axioms nor tautologies. Give two other such formulas.

2. $\mathrm{V-safe}$ might or might not be true for this board.Give two other such formulas.