2021-11-29, 6:44 PMCSCI 479 Fall 2021 - Assignment 5
Page 1 of 3http://csci.viu.ca/~liuh/479/assignments/A5.html
CSCI 479 Fall 2021 - Assignment 5
Due: 5:30pm, 3 December 2021, Friday
Questions:
1. Decide whether each of the following propositional logic sentences is valid, unsatisfiable, or neither.
Explain briefly.
i. P ⇒ Q
ii. (P ∨ Q) ⇒ P
iii. (P ∧ Q) ⇒ P
iv. (¬P ∨ Q) ⇒ P
v. (¬P ∨ Q) ⇒ (P ⇒ Q)
vi. P ⇒ ¬P
vii. P ⇔ ¬P
viii. P ⇒ (P ⇒ Q)
ix. P ⇒ (Q ⇒ P)
x. (P ⇒ P) ⇔ (¬Q ⇒ ¬P)
2. Represent the following sentences in first-order logic, using a consistent vocabulary (which you must
define) that includes constants, function symbols, and predicate symbols.
You may use multiple FOL sentences to code one of the following sentences, and I'd assume the final
result is a conjunction of these FOL sentences unless you tell me otherwise.
Natural language sentences may naturally have ambiguities in the meaning. If you believe that there is
ambiguity in a sentence, write down your own interpretation of the sentence along with your FOL
sentence(s).
i. Sign Language, Lillan and Kaput are languages.
ii. There are other language(s) besides Sign Language, Lillan and Kaput.
iii. Everybody can speak/use at least one language.
iv. Everybody, except Marvin, can speak/use at least one language.
v. Nobody can speak/use all languages.
vi. Both Lillan and Kaput are Country Lilliput's official language. And Country Lilliput doesn't have
other official languages besides Lillan and Kaput.
vii. In order to be a politician in Country Lilliput, you have to be a citizen of Country Lilliput and
speak both Lillan and Kaput.
viii. Not all citizens of Lilliput who speak both Lillan and Kaput are politicians.
ix. Every politician in Lilliput has some Lilliput citizens supporting him/her.
x. No politician in Lilliput is supported by all Lilliput citizens.
3. Find the Most General Unifier to unify each of the following pairs of FOL sentences, assuming that
P is a predicate symbol and F is a function symbol;
strings in quotation marks are constants; and
all variables are universally quantified.
If any pair can not be unified, explain why.
i. P (X, Y, Z) and P ('A', F('A'), 'B')
ii. P (X, F(X), Y) and P ('D', Z, 'G')
iii. P (X, F(X), Y) and P ('D', 'G', Z)
iv. P (X, F(X), F(X)) and P (Y, F(Y), F('A'))
v. P (X, F(X), F(X)) and P (Y, F('G'), Z)
2021-11-29, 6:44 PMCSCI 479 Fall 2021 - Assignment 5
Page 2 of 3http://csci.viu.ca/~liuh/479/assignments/A5.html
4. In the following training data set, Status is the target class label, and the values in column Count
indicate how many data items share the same Department, Age, Salary and Status values.
Department Age Salary Status Count
Sales 31 ... 35 46K ... 50K Senior 25
Sales 26 ... 30 26K ... 30K Junior 45
Sales 31 ... 35 31K ... 35K Junior 40
Systems 21 ... 25 46K ... 50K Junior 22
Systems 31 ... 35 66K ... 70K Senior 5
Systems 26 ... 30 46K ... 50K Junior 6
Systems 41 ... 45 66K ... 70K Senior 5
Marketing 36 ... 40 46K ... 50K Senior 7
Marketing 31 ... 35 41K ... 45K Junior 14
Secretary 46 ... 50 36K ... 40K Senior 2
Secretary 26 ... 30 26K ... 30K Junior 8
Secretary 26 ... 30 36K ... 40K Junior 1
i. Construct and draw a decision tree based on the above given training dataset.
ii. Choose a pair of attributes along a path in your decision tree, and justify why you picked one
attribute before the other.
iii. Given a data item having the values Department = "Secretary", Age = "26 ... 30" and Salary =
"36K ... 40K", what would the Status of this data item be when your decision tree is used to
perform the prediction?
iv. Convert your decision tree into an equivalent set of rules.
v. Does your constructed decision tree have over-fitting problem? Why or why not?
5. Given the following partial order plan (where clearly S is the start step and F is the final step) with
numbers in the boxes indicating the duration of the steps, determine the earliest possible start time and
the latest possible start time of each step, and list the steps in the critical path of the plan.
2021-11-29, 6:44 PMCSCI 479 Fall 2021 - Assignment 5
Page 3 of 3http://csci.viu.ca/~liuh/479/assignments/A5.html
Submission
You can hand in a hard copy before the due date/time.
Alternatively or if you would like to submit one day late, use the following command on otter in the directory
where your assignment file is:
~liuh/bin/submit 479 A5 .
The submit script currently accepts files with the extension name of .txt or .pdf.
To check what file(s) you have submitted for this assignment, use the following command on otter:
~liuh/bin/checksubmit 479 A5