Sir Penguin
26-11-2004, 08:01:23
Submitted either 2 minutes before it's due, or 72 hours and 2 minutes before it's due, depending on whether or not the prof decided to give us an extension (either way, he apparently forgot to tell us).
Part 2 uses 2 more rules than Dr. Horspool said he needed, but Part 3 uses 1 less. :coolgrin: I haven't tested it extensively though, so I'm not convinced that it's completely correct.
% ass5.pl - Source file for C SC 330 Assignment 5.
% Author: Neil MacMillan, #0229199
% Part 1 - check if an expression is in Disjunctive Normal Form
% match a literal
isLiteral(X) :- atom(X).
isLiteral(not(X)) :- atom(X).
% match a conjunction
isConjunct(X) :- isLiteral(X).
isConjunct(and(X,Y)) :- isConjunct(X),isConjunct(Y).
% match a disjunction
dnf(X) :- isConjunct(X).
dnf(or(X,Y)) :- dnf(X),dnf(Y).
% Part 2 - cancel double-negations in a boolean expression
cancel_negations(not(not(X)),X1) :- cancel_negations(X,X1).
cancel_negations(or(X,Y),or(X1,Y1)) :- cancel_negations(X,X1),cancel_negations(Y,Y1).
cancel_negations(not(or(X,Y)),not(or(X1,Y1))) :- cancel_negations(X,X1),cancel_negations(Y,Y1).
cancel_negations(and(X,Y),and(X1,Y1)) :- cancel_negations(X,X1),cancel_negations(Y,Y1).
cancel_negations(not(and(X,Y)),not(and(X1,Y1))) :- cancel_negations(X,X1),cancel_negations(Y,Y1).
cancel_negations(X,X) :- isLiteral(X).
% Part 3 - apply DeMorgan's law to a boolean expression
deMorgan(not(and(X,Y)), or(X1,Y1)) :-
cancel_negations(not(X),X2),
deMorgan(X2,X1),
cancel_negations(not(Y),Y2),
deMorgan(Y2,Y1).
deMorgan(not(or(X,Y)), and(X1,Y1)) :-
cancel_negations(not(X),X2),
deMorgan(X2,X1),
cancel_negations(not(Y),Y2),
deMorgan(Y2,Y1).
deMorgan(not(not(X)), X1) :-
cancel_negations(X,X2),
deMorgan(X2,X1).
deMorgan(and(X,Y), and(X1,Y1)) :-
cancel_negations(X,X2),
deMorgan(X2,X1),
cancel_negations(Y,Y2),
deMorgan(Y2,Y1).
deMorgan(or(X,Y), or(X1,Y1)) :-
cancel_negations(X,X2),
deMorgan(X2,X1),
cancel_negations(Y,Y2),
deMorgan(Y2,Y1).
deMorgan(X,X) :- isLiteral(X).
SP
Part 2 uses 2 more rules than Dr. Horspool said he needed, but Part 3 uses 1 less. :coolgrin: I haven't tested it extensively though, so I'm not convinced that it's completely correct.
% ass5.pl - Source file for C SC 330 Assignment 5.
% Author: Neil MacMillan, #0229199
% Part 1 - check if an expression is in Disjunctive Normal Form
% match a literal
isLiteral(X) :- atom(X).
isLiteral(not(X)) :- atom(X).
% match a conjunction
isConjunct(X) :- isLiteral(X).
isConjunct(and(X,Y)) :- isConjunct(X),isConjunct(Y).
% match a disjunction
dnf(X) :- isConjunct(X).
dnf(or(X,Y)) :- dnf(X),dnf(Y).
% Part 2 - cancel double-negations in a boolean expression
cancel_negations(not(not(X)),X1) :- cancel_negations(X,X1).
cancel_negations(or(X,Y),or(X1,Y1)) :- cancel_negations(X,X1),cancel_negations(Y,Y1).
cancel_negations(not(or(X,Y)),not(or(X1,Y1))) :- cancel_negations(X,X1),cancel_negations(Y,Y1).
cancel_negations(and(X,Y),and(X1,Y1)) :- cancel_negations(X,X1),cancel_negations(Y,Y1).
cancel_negations(not(and(X,Y)),not(and(X1,Y1))) :- cancel_negations(X,X1),cancel_negations(Y,Y1).
cancel_negations(X,X) :- isLiteral(X).
% Part 3 - apply DeMorgan's law to a boolean expression
deMorgan(not(and(X,Y)), or(X1,Y1)) :-
cancel_negations(not(X),X2),
deMorgan(X2,X1),
cancel_negations(not(Y),Y2),
deMorgan(Y2,Y1).
deMorgan(not(or(X,Y)), and(X1,Y1)) :-
cancel_negations(not(X),X2),
deMorgan(X2,X1),
cancel_negations(not(Y),Y2),
deMorgan(Y2,Y1).
deMorgan(not(not(X)), X1) :-
cancel_negations(X,X2),
deMorgan(X2,X1).
deMorgan(and(X,Y), and(X1,Y1)) :-
cancel_negations(X,X2),
deMorgan(X2,X1),
cancel_negations(Y,Y2),
deMorgan(Y2,Y1).
deMorgan(or(X,Y), or(X1,Y1)) :-
cancel_negations(X,X2),
deMorgan(X2,X1),
cancel_negations(Y,Y2),
deMorgan(Y2,Y1).
deMorgan(X,X) :- isLiteral(X).
SP