For the final project in our Introduction to Artificial Intelligence (CS171) class, we were asked to write a function that converts a propositional logic expression to its Conjunctive Normal Form (CNF).
Following that, a couple of days ago, I was thinking about a more general function that would allow easy conversion to either Conjunctive or Disjunctive Normal Form (CNF or DNF). I suddenly realized how, despite their logical differences, ands and ors actually have similar structural functions when used in expressions. Each of the equalities given by inference rules such as the distribution laws and the De Morgan’s law, for instance, would still be equalities if all conjunctions were switched to disjunctions, and all disjunctions were switched to conjunctions. Of course, all instances of true should also be replaced with instances of false, and vice versa.
I had actually already noticed the similarity in structural function years ago when I first had to understand and memorize basic inference rules. Now, however, I am seeing the similarity in a different light: it does not only make memorization of the rules easier but also allows generalization in computer science. This makes me wonder about how ands and ors can be represented as objects.
I will not be publishing the entire code here, as I am quite positive that the same project will be asked of the next batch of students who will take the same class that I currently am taking. However, given a function that takes an expression in a form that no longer has equivalences and implications but only conjunctions and disjunctions, and where negations are only applied to literals, if an option argument for the function, which would be ‘and if the function is supposed to convert to CNF and ‘or if the function is supposed to convert to DNF, was introduced, and all the ‘ands were replaced with options, and all the ‘ors with (invert-operator option)s, where the following code:
(defun invert-operator (a)
(cond ((eql a 'and) 'or)
((eql a 'or) 'and)
(T NIL)))defines the invert-operator function, a more general solution to the problem can be arrived at.