cs534 - Homework Assignment 3 - Solved

Homework Objective: The goal of this assignment is to help you master the materials of Lecture 4 and 5.


 

Notes:  

1.      Each answer needs to be explained.

2.      The implementation should be in Python if You need.

 

Project Questions: 

 

Question 1. Consider the problem of deciding whether a propositional logic (PL) sentence is true in a given model. Write a recursive algorithm PL-True?(s, m) that returns true if and only if the sentence s is true in the model m (where m assigns a truth value for every symbol in s). The algorithm should run in time linear in the size of the sentence. The original algorithm can be found in the function pl_true() in logic4e.py.

 

If you have forgotten the concept of recursive algorithms that you have learned in your prerequisites, you can review this website (https://realpython.com/python-recursion/) to refresh your memory.

 

Question 2. Consider a first-order logical knowledge base that describes worlds containing people, songs, albums (e.g., “Meet the Beatles”) and disks (i.e., particular physical instances of CDs). The vocabulary contains the following symbols:

 

> CopyOf(d, a): Predicate. Disk d is a copy of album a. > Owns(p, d): Predicate. Person p owns disk d. > Sings(p, s, a): Album a includes a recording of song s sung by person p. > Wrote(p, s): Person p wrote song s. > McCartney, Gershwin, BHoliday, Joe, EleanorRigby, TheManILove, Revolver: Constants with the obvious meanings.  

 

Express the following statements in first-order logic:

 

a.       Gershwin wrote “The Man I Love.”

b.      Gershwin did not write “Eleanor Rigby.”

c.       Either Gershwin or McCartney wrote “The Man I Love.”

d.      Joe has written at least one song.

e.       Joe owns a copy of *Revolver*.

f.        Every song that McCartney sings on *Revolver* was written by McCartney.

g.      Gershwin did not write any of the songs on *Revolver*.

h.      Every song that Gershwin wrote has been recorded on some album. (Possibly different songs are recorded on different albums.)

i.        There is a single album that contains every song that Joe has written.

j.        Joe owns a copy of an album that has Billie Holiday singing “The Man I Love.”

k.      Joe owns a copy of every album that has a song sung by McCartney. (Of course, each different album is instantiated in a different physical CD.)

l.        Joe owns a copy of every album on which all the songs are sung by Billie Holiday.

 

 

Question 3. Consider the following dataset (x1, x2, .., x5) comprised of three binary input attributes (A1, A2, and A3) and one binary output:

 

  

 

a.       Use the Gini Index to learn a decision tree for these data. Show the computations made to determine the attribute to split at each node. Draw the final tree.

b.      Use the Information Gain to learn a decision tree for these data. Show the computations made to determine the attribute to split at each node. Draw the final tree.

 

Question 4. Consider the following set of examples (A1, A2, …, A14), each with six inputs (x1, x2, …, x6) and one target output T: