CS 141 Introduction to AI Greenwald

TBA

5:00 PM, Mar 9, 2009

Homework 4: Propositional Logic

Due:

Contents

    1  Natural Deduction

    2  True or False

    3  Normal Form

    4  Subsets of Connectives

    5  Law of the Excluded Middle

Objectives

By the end of this homework, you will know:

  1. the law of the excluded middle

By the end of this homework, you will be able to:

  1. do proofs by natural deduction

  2. convert sentences of propositional logic to normal form

Practice

1  Natural Deduction

These practice problems were written by head TA Nick Schaden in 200?.

#1 Consider the following sequence of statements.

IF MICROSOFT’S STOCK PRICE FALLS, THEN STEVE IS HAPPY. IF THE FOOTBALL GAME IS ON, THEN GEORGE WILL CHOKE ON A PRETZEL. MICROSOFT’S STOCK PRICE DROPPED OR THE FOOTBALL GAME IS ON.

(a) Convert the above statements into a knowledge base in propositional logic.

(b) Using the rules of natural deduction and your knowledge base, derive the following theorem: STEVE IS HAPPY OR GEORGE WILL CHOKE ON A PRETZEL.

#2 Consider the following sequence of statements.

IF TODAY IS FRIDAY OR SATURDAY, THEN A BROWN STUDENT WILL STAY OUT LATE. IF A BROWN STUDENT STAYS OUT LATE, THEN S/HE WILL SLEEP IN THE NEXT DAY.

(a) Convert the above statements into a knowledge base in propositional logic.

(b) Using the rules of natural deduction and your knowledge base, derive the following theorem: IF A BROWN STUDENT DOES NOT SLEEP IN, THEN TODAY IS NOT SATURDAY.

#3 Using the rules of natural deduction, and the equivalence A \wedge \neg A \leftrightarrow \bot, derive the rule of contraposition:

\infer[(\mbox{\em Con})]{B \rightarrow \neg A}{A \rightarrow \neg B}

(b) Consider the following sequence of statements.

If today is Saturday, then Brown will not hold classes.
Brown is holding classes.
Convert the above statements into a knowledge base in propositional logic.

(c) Using the rules of natural deduction, the derived rule of contraposition, and your knowledge base, derive the theorem: TODAY IS NOT SATURDAY.

#4 Consider the following sequence of statements, which describe the workings of the security system for the computer science TA annex on the second floor.

IF THE SYSTEM IS ARMED AND MOTION IS DETECTED, THEN THE ALARM WILL SOUND. IF THE ALARM SOUNDS, THEN THE SYSTEM HAS BEEN ARMED OR THERE HAS BEEN A FIRE. REGARDLESS OF WHETHER THE SYSTEM IS ARMED, THE ALARM SHOULD GO OFF WHEN THERE IS A FIRE. MOTION IS CONSTANTLY DETECTED.

(a) Convert the above statements into a knowledge base using the symbols of propositional logic.

(b) Using the rules of natural deduction, the derived rule,

\infer[(\leftrightarrow I)]{A \leftrightarrow B}{A \rightarrow B & B \rightarrow A}

and your knowledge base, derive the following theorem: THE ALARM WILL SOUND IFF THE SYSTEM IS ARMED OR THERE IS A FIRE.

Problems

2  True or False

Task:

3  Normal Form

Task: Convert the following sentences of propositional logic to normal form. Show all work.

4  Subsets of Connectives

Task: Show that it is possible to define the meaning of ∨, →, ←, and ↔ in terms of ¬ and ∧. In other words, show that the subset { ¬, ∧ } suffices to express all the formulas of propositional logic. Are there other subsets of the set of connectives { ¬, ∨, ∧, →, ←, ↔ } that exhibit this property?

5  Law of the Excluded Middle

(a) Using truth tables, establish the soundness of the following variation of the resolution rule for propositional logic:

\infer{A \vee C}{A \vee B & \neg B \vee C}

(b) Derive this rule from the inference rules of natural deduction. You may take as an axiom P ∨ ¬ P, and you may also make use of the tautology A \wedge \neg A \leftrightarrow \bot. (Hint: First derive unit resolution.)

(c) Is the system of natural deduction refutation-complete for propositional logic? Why or why not?

(d) Can you derive P ∨ ¬ P using only resolution (1R, GR, or IGR)? If so, give a derivation; if not, explain why not. (Hint: Is resolution complete?)

Last modified: Tuesday, March 3rd, 2009 6:22:07pm