You should turn in a file A5.pdf containing your answers.

1. (25 points) Suppose you have been assigned the problem of designing a computer program that will write poetry in the Haiku form. Each piece must consist of three lines of text. The first line must have 5 syllables. The second line must have 7 syllables, and the third line must have 5 syllables. An example is the following:

   Three lines of Python
   Though they might not be valid
   Can still be entered
   

   No rhyming is required. The sponsors have told you that they want a genetic algorithm for this task. The state space is given: each state will consist of three lists of words. All the words will come from a dictionary that will be given to your program at runtime. The dictionary will consist of the words as keys, and for each key, a list of its number of syllables and its grammatical part(s) of speech as the value for the key. For example, the word "jump" would have [1, ['verb', 'noun']] as its value in the dictionary. Design the following for this problem. For each item, explain in English something that could work to produce the poems. The poems do not have to be particularly "good". You do not need to express any of this in Python. But do explain why you think it would work.
   1. (8 points) a fitness function that takes into consideration the numbers of syllables in the words and, optionally, the words' formation of noun phrases, prepositional phrases, clauses and/or sentences;
   2. (5 points) a mutational operator;
   3. (7 points) a crossover operator;
   4. (5 points) a starting population.
   
    
   
2. (5 points) Make a truth table for the contrapositive rule. Your table should have five columns: one each for P, Q, ~P, ~Q, and ~Q -> ~P
    
   
3. (20 points) Do Exercise 1 at the end of Chapter 6 of the reading on logic.
    
   
4. (10 points) Do Exercise 4 at the end of Chapter 6 of the reading on logic.
    
   
5. (5 points) Find the resolvent for the two clauses:

        P v ~Q v R
        P v ~R v S
   

   
    
   
6. (35 points) Consider the following logic puzzle, which is one of many created by Lewis Carroll, the author of Alice in Wonderland.

     No birds, except ostriches, are 9 feet high.
     There are no birds in this aviary that belong to anyone but me.
     No ostrich lives on mince pies.
     I have no birds less than 9 feet high.
   

   Prove that these premises imply the following conclusion:

     Any bird in this aviary does not live on mince pies.
   

   In your proof, use the following symbols to represent statements.

   H:  Height of the bird is not less than nine feet.
   O:  The bird is an ostrich.
   M:  The bird lives on mince pies.
   I:  I own the bird.
   A:  The bird is in this aviary.
   

   1. (10 points) Show the premises as logical formulas represented using these symbols. As you encode each premise, you may translate it from being a generalization (e.g., "no birds...") to a statement about a particular bird ("the bird"). For example, the first premise can be translated to "If the bird is an ostrich, then the height of the bird is not less than nine feet."
   2. (3 points) Show the conclusion as a logical formula represented using these symbols.
   3. (2 points) Show the negation of the conclusion using these symbols.
   4. (10 points) Show all premises and the negation of the conclusion as a set of clauses.
   5. (10 points) Finally use the resolution method for your proof, and show for each resolution step which formulas are involved as parents and what the resolvent is.