CS534 Assignment 3 Solved

Homework Objective: The goal of this assignment is to help you master the materials of Lecture 4 and 5. Homework Deliverables: Submit your answers and solutions in a zip file that includes all the write-ups in a

pdf file and your python codes to Canvas.

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:

1. Gershwin wrote “The Man I Love.”
2. Gershwin did not write “Eleanor Rigby.”
3. Either Gershwin or McCartney wrote “The Man I Love.”
4. Joe has written at least one song.
5. Joe owns a copy of *Revolver*.
6. Every song that McCartney sings on *Revolver* was written by McCartney.
7. Gershwin did not write any of the songs on *Revolver*.
8. Every song that Gershwin wrote has been recorded on some album. (Possibly different songs are recorded

   on different albums.)

9. There is a single album that contains every song that Joe has written.
10. Joe owns a copy of an album that has Billie Holiday singing “The Man I Love.”
11. 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.)

12. 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:

1. 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.
2. 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:

a. Run the perceptron learning rule on these data, show the final equation, and draw the final perceptron architecture. Include your Python code in the submission.

▪ Reference:https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.Perceptron.html
b. Run the decision tree learning rule on these data (x1, x2, …, x6), and show the resulting decision tree.

Include your Python code in the submission.
▪ Reference:https://scikit-learn.org/stable/modules/tree.html#classification
c. Comment on your prediction results by using both algorithms if there is an unseen A15: <1, 1, 0, 0, 1, 1>.

The true T of A15 is 1. Include your Python code in the submission