CSci 4511 - Homework 3

Homework 3 -- due date Thursday March 14

This homework will be graded out of 100 points. It will count 6% of the grade. You can submit the homework with a 10% late penalty up to Sunday March 17.

Written questions

  1. [30 points] Decide if the following sentences are valid, unsatisfiable, or neither. To do it, use the truth tables and equivalency rules from Chapter 7.
    1. Small ⇒ Small
    2. Small ⇒ Light
    3. (Small ⇒ Light) ⇒ (¬ Small ⇒ ¬ Light)
    4. Small ∨ Light ∨ ¬ Light
    5. ((Small ∧ Dense)⇒ ¬ Light) ⇔ ((Small ⇒ Dense) ∨ (¬ Light ⇒ Dense))
    6. (Small ⇒ Dense) ⇒ ((Small ∧ Light) ⇒ Dense)
    7. Small ∨ Cute ∨ (Small ⇒ Cute)
    8. (Small ∧ Cute) ∨ ¬ Cute
    9. ((Snow ⇒ Wet) ∧ (Wet ⇒ Cold)) ⇒ (Snow ⇒ Cold)
    10. ((Snow ∨ Wet ) ∧ ( ¬ Wet ∨ Cold)) ⇒ ( Snow ∨ Cold )
  2. [15 points] For each of the following propositional calculus formulas, state briefly if it is a correct representation in propositional calculus of the sentence "If the dog sleeps and the house is warm, then the night is quiet." or not and explain why. The propositions used in the sentences should have an obvious interpretation.
    1. DogSleeps ∧ HouseWarm ∧ NightQuiet
    2. (DogSleeps ∨ HouseWarm) ⇒ NightQuiet
    3. (DogSleeps ∧ HouseWarm) ⇒ NightQuiet
    4. NightQuiet ⇒ (DogSleeps ∧ HouseWarm)
    5. ¬ DogSleeps ∨ (¬ NightQuiet ∨ HouseWarm)
  3. [25 points] Convert the following set of propositional clauses to CNF
    1. (Sunny ⇒ Warm) ⇒ Warm
    2. (Sunny ⇒ Sunny) ⇒ Rain
    3. (Rain ⇒ Wet) ⇒ ¬ (Wet ⇒ Warm)
    and prove by resolution with refutation "Rain".

Programming questions

Use the python or lisp aima software to anser the following questions. Submit source files showing your function calls and any changes you make (do nto submit all the aima files!) and a file showing the output obtained.
  1. [5 points] Create a minimax agent and play it against itself in a tic-tac-toe game.
  2. [5 points] Play the alpha-beta agent against itself in a tic-tac-toe game.
  3. [5 points] Show if alpha-beta does any pruning when playing against itself in a tic-tac-toe game.
  4. [15 points] Study the effect of the order in which players play the game on their ability to win in a tic-tac-toe game.
    1. Play the alpha-beta agent against a random agent. Collect the results when playing 10 games.
    2. Repeat the same but this time making the random agent playing first. Collect the results when playing 10 games.
    3. Compute the average winning rate for the two setups. Can you make any conclusion from the results?
Copyright: © 2019 by the Regents of the University of Minnesota
Department of Computer Science and Engineering. All rights reserved.
Comments to: Maria Gini
Changes and corrections are in red.