CS331 writing assignment 2 PDF

Preview

Summary

WRITING ASSIGNMENT...

Description

CS331 (Spring 2017): Introduction to Artificial Intelligence Written Assignment #2 Date handed out: April 25, 2018Date due: May 2, 2018 at the start of class Total: 28 points The written portion of this assignment is to be done individually. Please hand in a pdf on Canvas. Assignments done on a word processor are preferred but not mandatory. For hand written assignments, if we cannot read your writing, we cannot mark your assignment. 1. (From 7.4 in the book) For each of the following statements, prove if it is true or false. a) 𝐹𝑎𝑙𝑠𝑒 ⊨ 𝑇𝑟𝑢𝑒 [2 points] True. To prove 𝐹𝑎𝑙𝑠 𝐹𝑎𝑙𝑠𝑒 𝑒 ⊨ 𝑇𝑟𝑢𝑒, we only need to prove False => True is valid, which is obviously true. p

q

p=>q

false

true

true

b) 𝑇𝑟𝑢𝑒 ⊨ 𝐹𝑎𝑙𝑠𝑒 [2 points] False. To prove 𝑇𝑟𝑢𝑒 ⊨ 𝐹𝑎𝑙𝑠 𝐹𝑎𝑙𝑠𝑒 𝑒,*only need to prove True => False is valid, which is obviously false. p

q

p=>q

true

false

false

c) (𝐴 ∧ 𝐵) ⊨ (𝐴 ⟺ 𝐵) [3 points]

True. A

B

𝐴∧𝐵

𝐴⟺𝐵

T

T

T

T

T

F

F

F

F

T

F

F

F

F

F

T

When 𝐴 ∧ 𝐵*is true, 𝐴 ⟺ 𝐵 is always true. d) 𝐴 ⟺ 𝐵 ⊨ 𝐴 ∨ 𝐵 [3 points] False. A

B

𝐴⟺𝐵

𝐴∧𝐵

T

T

T

T

T

F

F

F

F

T

F

F

F

F

T

F

When 𝐴 ⟺ 𝐵 is true, 𝐴 ∧ 𝐵*is not always true. 2. (From 7.10 in the book) Decide whether each of the following sentences is valid, unsatisfiable or neither. Verify your decisions using truth tables or the equivalence rules of Figure 7.11. a) 𝑆𝑚𝑜𝑘𝑒 ⇒ 𝐹𝑖𝑟𝑒 [2 points] Neither Smoke Fire

Smoke => Fire

T

T

T

T

F

F

F

T

T

F

F

T

b) (𝑆𝑚𝑜𝑘𝑒 ⟹ 𝐹𝑖𝑟𝑒) ⟹ ((𝑆𝑚𝑜𝑘𝑒 ∧ 𝐻𝑒𝑎𝑡) ⟹ 𝐹𝑖𝑟𝑒) [4 points] Valid Smoke Fire Hear 𝑆𝑚𝑜𝑘𝑒 ∧

𝑆𝑚𝑜𝑘𝑒 ∧ 𝐻𝑒𝑎𝑡) ⟹

𝐻𝑒𝑎𝑡

𝐹𝑖𝑟𝑒

𝑆𝑚𝑜𝑘𝑒 ⟹ 𝐹𝑖𝑟𝑒

The*whole* sentence*

T

T

T

T

T

T

T

T

T

F

F

T

T

T

T

F

T

T

F

F

T

T

F

F

F

T

F

T

F

T

T

F

T

T

T

F

T

F

F

T

T

T

F

F

T

F

T

T

T

F

F

F

F

T

T

T

3. (From Exercises 7.20 and 7.12 in the book). a) Convert the following sentences to CNF. [6 points] S1: 𝐴 ⟺ (𝐵 ∨ 𝐸)

S2:𝐸 ⇒𝐷 S3: 𝐶 ∧ 𝐹 ⇒ ¬𝐵 S4: 𝐸 ⇒ 𝐵 S5: 𝐵 ⇒ 𝐹 S6: 𝐵 ⇒ 𝐶

b) Use resolution to prove ¬𝐴 ∧ ¬𝐵. [6 points]

!...