Homework 3

Note: Put your solution for Task 9 in the Carmen Dropbox. It’s code, afterall, and the grader should be able to execute it.


Task 1 (5 pts)

Build truth tables for the following formulas:

  1. \((\neg A \wedge B) \vee C\)
  2. \((A \leftrightarrow \neg B) \vee B\)

Task 2 (5 pts)

Express the following statements in propositional logic:

  1. \(B\) and \(C\) are both true should \(A\) be true.
  2. \(B\) is known to be true when \(A\) is true and not otherwise.
  3. At most one of \(R\), \(S\), and \(T\) can be true.
  4. The grass is wet if either it rained or the sprinkler was on. (Create propositional symbols, and give their definitions.)

Task 3 (10 pts)

We have a knowledge base that contains:

a. \((R \rightarrow S) \wedge Q\)

b. \((J \wedge Q) \rightarrow P\)

c. \(Q \rightarrow Z\)

d. \(P \rightarrow \neg Q\)

e. \((R \rightarrow S) \rightarrow (\neg H \rightarrow J)\)

Derive each of the following using inference rules for propositional logic. Indicate the rule used (i.e., MP for modus ponens) and the propositions used with the rule. You can use propositions you have already proved but were not in the initial knowledge base.

  1. \(Z\)
  2. \(\neg P\)
  3. \(\neg (J \wedge Q)\)
  4. \(\neg J\)

Task 5 (5 pts)

Rewrite the following statements in first-order logic, stating definitions for the predicates you use. (Note, one of these is exceedingly hard; make an attempt…)

  1. James is a dolphin.
  2. Dolphins are mammals.
  3. Mammals have hair and three middle ear bones.
  4. Not all dolphins live in the ocean.
  5. Some mammals have sweat glands and specialized teeth.
  6. This sentence cannot be proved.

Task 6 (10 pts)

Assume we have the following Prolog database:

parent(tom, liz).
parent(tim, bob).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).


mother(X) :- parent(X, _), female(X).
  1. Write Prolog queries for the following questions:
    1. Who is Ann’s parent?
    2. Is Jim Bob’s child?
    3. Who is Jim’s grandparent?
  2. Write a rule that describes a child, so that child(X, Y) means X is the child of Y. Don’t allow a person to be his or her own child.
  3. Define an ancestor rule. An ancestor is a parent of a person, a grandparent, a great-grandparent, etc. Naturally, this rule is recursive (like the member predicate in the notes).
  4. Define a “has no parents” rule. Use negation (“negation as failure”).

Task 7 (5 pts)

Do the following unify, and if so, what are values for the variables that make the unification work? Note: Each pair of terms has new variable assignments.

  1. parent(tom, liz) and parent(tom, X)
  2. parent(X, liz) and parent(liz, X)
  3. parent(X, Y) and parent(Y, X)
  4. head(X, [a, b, c]) and head(b, [a, b, c])
  5. head(foo(Y), X) and head(foo(Z), [foo(w)])
  6. foo(bar(a, b), baz(c)) and foo(bar(X), baz(Y))

Task 8 (10 pts)

Draw a resolution tree for mother(X), refering back to the database above. Note that there is a particular order by which Prolog creates subgoals (that is, the order that facts/rules are written in the knowledge base). You only need to show the tree until the first time the predicate is proved.

Task 9 (50 pts)

Extend the Prolog program at the bottom of this page to support the following interactions. (The user types the stuff after the |:)

?- consult('nldb.pl').
%    library(error) compiled into error 0.00 sec, 18,352 bytes
%   library(lists) compiled into lists 0.01 sec, 46,096 bytes
%  library(readln) compiled into readln 0.01 sec, 60,696 bytes
% nldb.pl compiled 0.01 sec, 78,560 bytes

?- run.
|: quit.
Ok we're done! 

?- run.
|: anteater is bigger than ant.
Ok, I learned that ant is smaller than anteater 
|: ant is smaller than foot.
Ok, I learned that ant is smaller than foot 
|: what is bigger than ant?
These are bigger: 
anteater, foot.
|: what is smaller than anteater?
These are smaller: 
|: what is smaller than ant?
These are smaller: 

|: godzilla is bigger than anteater.
Ok, I learned that anteater is smaller than godzilla 
|: what is bigger than ant?
These are bigger: 
anteater, foot, godzilla.
|: what is smaller than godzilla?
These are smaller: 
anteater, ant.
|: today is thursday.
Ok, I learned that today is a/an thursday 
|: socrates is mortal.
Ok, I learned that socrates is a/an mortal 
|: what is socrates?
socrates is a/an: 
|: what is today?
today is a/an: 
|: what is xyz?
I'm not sure! Care to tell me? 
|: is xyz abc?
|: xyz is abc.
Ok, I learned that xyz is a/an abc 
|: is xyz abc?
|: what is 15?
|: what is 2 + 2?
|: what is 2 - 3 * 5?
|: what is 2 * 3 - 2?
|: what is 4 / 3?
|: wow, you are very smart!
|: quit.
Ok we're done! 


Start with this code. Pay special attention to the “TODO” comments.

:- use_module(library(readln)).

% these allow us to use assertz with these two predicates
:- dynamic(learned_isa/2).
:- dynamic(learned_smaller/2).

% strip_puncation/2 & read_sentence/1 from The Art of Prolog 2nd Ed. (Sterling & Shaprio)

strip_punctuation([], []).
strip_punctuation([Word|Tail], [Word|Result]) :-
    \+(member(Word, ['.', ',', '?', '!'])),
    strip_punctuation(Tail, Result).
strip_punctuation([_|Tail], Result) :-
    strip_punctuation(Tail, Result).

read_sentence(Input) :-
    strip_punctuation(Input1, Input).

reply([Head|Tail]) :- write(Head), write(' '), reply(Tail).
reply([]) :- nl.

% TODO: code reply_list/1

run :- read_sentence(Input), run(Input), !.

run(['quit']) :- reply(['Ok we\'re done!']).

run(Input) :-
    !, run(NextInput).

process_sentence([what, is, bigger, than, Object]) :-
    % TODO: code findall using Object and creating Things
    reply(['These are bigger:']),

process_sentence([what, is, smaller, than, Object]) :-
    % TODO: finish predicate

process_sentence([what, is | Math]) :-
    math(Math, Z),

process_sentence([what, is, Object]) :-
    % TODO: finish predicate

process_sentence([what, is, _]) :-
    reply(['I''m not sure! Care to tell me?']).

process_sentence([is, Subject, Object]) :-
    % TODO: put a line of code here

% TODO: handle case where "is xyz abc" says "No"
% (i.e., above predicate failed)

process_sentence([Subject, is, Object]) :-
    assertz(learned_isa(Subject, Object)),
    reply(['Ok, I learned that', Subject, 'is a/an', Object]).

% TODO: handle "x is bigger than y" and "x is smaller than y"
% similarly to how "is" is handled above,
% using assertz(learned_smaller(...))

process_sentence(_) :-

% right-associative math

% default math case (an atom)
math(X, Z) :-
    Z = X.

% default math case (a list)
math([X], Z) :-
    Z = X.

math([X, + | Tail], Z) :-
    % TODO: finish predicate

% TODO: code rest of math

isa(X, Y) :- learned_isa(X, Y).

% TODO: code transitive isa

smaller(X, Y) :- learned_smaller(X, Y).

% TODO: code transitive smaller
AI Su13 material by Joshua Eckroth is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License. Source code for this website available at GitHub.