Ternary Logic (Lisp)
From LiteratePrograms
This is an implementation of ternary logic in Lisp, more exactly, the Ł3 system by Łukasiewisz.
The code is written in Emacs Lisp, but should be portable to any Lisp implementation. The functions error and message used in the test function might however not be provided by other implementations; implementing them to just print the message should however be easy. Also the function interactive should be defined to do nothing in that case (it tells Emacs that the function may be called interactively).
The code was successfully tested on XEmacs (beta) version 21.5.21 of February 2005 (+CVS-20050720).
Contents |
Description of the ternary logic
The ternary logic differs from the classical logic in that it knows three logical values; besides "true" (t) and "false" (f), there's a third, which can be interpreted as "unknown" (u). The logical relations "and", "or", "not" and "implication" are all extended to this three-valued system. The negation is quite straighforward:
| A | |
|---|---|
| f | t |
| u | u |
| t | f |
Also, the conjunction and disjunction offer no surprises. The implication at first looks a bit strange, but one readily verifies that it holds the rules that is always true, and if A is false, is also always true. One can understand the table better if one reads the implication as "B is as least as true as A". Note, however, that in the ternary case, is not the same as .
| A | B | |||
|---|---|---|---|---|
| f | f | f | f | t |
| f | u | f | u | t |
| f | t | f | t | t |
| u | f | f | u | u |
| u | u | u | u | t |
| u | t | u | t | t |
| t | f | f | t | f |
| t | u | u | t | u |
| t | t | t | t | t |
Implementation in Lisp
Lisp implements two-valued logic by treating nil as false and every other Lisp object as true. However, it also has a special symbol t, which explicitly denotes the value true. Like nil, t evaluates to itself.
To implement ternary logic, it's straightforward to add a third symbol u to represent the corresponding logical value. This leaves the question on how to interpret other Lisp objects. The decision taken here is to interpret them as u as well.
The ternary logical functions will get the names of their classic counterparts, but with a 3 added, i.e. and3, or3 and not3. In addition, an explicit implication function, implies3, a function testing for "unknownness", unknownp, and a function to "normalize" an expression by replacing anything which is not t or nil are defined.
Conjunction and disjunction
Lisp provides the built-in functions and and or, which only evaluate arguments until one is found to evaluate to nil (for and), or to something non-nil (for or). The result of the last evaluated argument is returned.
This behaviour cannot be carried over to the ternary case exactly, however one can translate this behaviour to two rules which can easily be applied to the ternary case:
- Evaluation of the arguments stops as soon as the final logical result of the expression is known.
- The value returned is the latest evaluated Lisp object representing the logical value of the result. Note that such an object exists in any case.
For and3 and or3 this results in the following behaviour:
- and3 evaluates all arguments until one of them returns nil, in which case nil is returned and no further arguments are evaluated. If no argument returns nil, the result of the last argument which did not return t, if any, is returned, otherwise t. All arguments are evaluated in this case.
- or3 evaluates all arguments until one of them returns t, in which case t is returned and no further arguments are evaluated. If no argument returns t, the result of the last non-nil argument, if any, is returned, otherwise nil. All arguments are evaluated in this case.
Looking at the behaviour of and3 and or3 as defined above, one recognises that it is completely equivalent, except that the roles of nil and t are exchanged. It therefore makes sense to have a single helper function containing the logic, called by both and3 and or3. Since in general not all arguments are to be evaluated, it must be defined as a macro. A macro doesn't directly evaluate to the result, but it evaluates to another expression which then in turn evaluates to the result. The important point here is that, unlike function arguments, macro arguments are not evaluated prior to evaluating the macro itself.
The macro doing the actual work is implemented by recursion. It takes three arguments: The first argument, val is the default value of the evaluated function, i.e. t for and3, and nil for or3. This value actually decides which of those two functions are evaluated. The second argument, old gives the result accumulated so far, and the third argument, new is the list of arguments not yet evaluated.
<<logic3.el>>= (defmacro andor3-helper (val old new) andor3-helper implementation)
In the function we'll need access to the first element of the list new, as well as the rest of it. Thus we just store those two values in local variables first and rest. Note that it doesn't harm if the list is empty (i.e. nil); in that case both first and rest will simply be nil as well.
<<andor3-helper implementation>>= (let ((first (eval (car new))) (rest (cdr new))) andor3-helper macro function body)
The macro function body is just a big cond statement:
<<andor3-helper macro function body>>= (cond conditions)
The first test is if the list of new values is empty, i.e. nil. In that case, evaluation has finished, and the result evaluated so far, old is the final result.
<<conditions>>= ((not new) old)
The next test is if the first new symbol is actually the default value. In that case, it doesn't change anything and can therefore safely be ignored. The expression we have to evaluate is therefore the same macro incvocation, but with the list new replaced by the list without the first argument, which we conveniently stored in rest.
<<conditions>>= ((equal first val) (list 'andor3-helper val old rest))
The next test is for the negation of the default value. If the first new value is not equal to that, the operation so far evaluated to first.
<<conditions>>= ((not (equal first (not val))) (list 'andor3-helper val first rest))
If all those conditions failed, we know that we found the opposite of the default value. In that case, we can simply ignore whatever we evaluated before and return that value.
<<conditions>>= ((not val))
Now we can implement and3 and or3. They are macros which just forward to the helper macro defined above, with the appropriate default value. The value evaluated so far is, of course, the same default value. Also, the functions contain documentation strings.
<<logic3.el>>= (defmacro and3 (&rest args) "Calculate 3-valued and. This function evaluates all arguments until one of them returns nil, in which case nil is returned and no further arguments are evaluated. If no argument returns nil, the result of the last argument which did not return t, if any, is returned, otherwise t. All arguments are evaluated in this case." (list 'andor3-helper t t args)) (defmacro or3 (&rest args) "Evaluate 3-valued or. This functions evaluates all arguments until one of them returns t, in which case t is returned and no further arguments are evaluated. If no argument returns t, the result of the last non-nil argument, if any, is returned, otherwise nil." (list 'andor3-helper nil nil args))
Negation
Negation is quite simple: t is mapped to nil, nil to t, and the rest is passed on unchanged. Since there's only one argument, which is evaluated unconditionally, a normal function can be used for this.
<<logic3.el>>= (defun not3 (arg) "Three-valued not. Returns t if arg is nil, and nil if arg is t. Otherwise, arg is returned unchanged." (or (not arg) (and (not (equal arg t)) arg)))
Implication
A short-circuit evaluation approach like in and3 and or3 is also used on implication. While Lisp (to my knowledge) does not provide an implication function for classical logic, one can argue that it would be an inconsistency to have one logical function evaluating more than necessary to determine the result, while the other only evaluate as much as needed. Also, one could consider the expression (or (not A) B) as the classical implication expression in Lisp, and that indeed doesn't evaluate B if A evaluates to nil.
The short-circuit evaluation demands an implementation as macro. Special care has been taken to evaluate the first argument only once.
<<logic3.el>>= (defmacro imply3 (arg1 arg2) "Three-valued implication. If arg1 is nil, imply3 evaluates to t, and arg2 is not evaluated. If arg1 is t, imply3 evaluates to arg2. If arg1 is neither nil nor t, imply3 evaluates to arg1 if arg2 is nil, and to t otherwise." (let ((val1 (eval arg1))) (cond ((not arg1) t) ((equal val1 t) arg2) ((not (eval arg2)) `',val1) (t t))))
Other definitions
Sometimes it's interesting to test if some value actually represents unknown. That's what the predicate unknownp does.
<<logic3.el>>= (defun unknown-p (arg) "Returns t if arg is neither nil nor t, nil otherwise." (and arg (not3 arg) t))
While the above functions work with any Lisp object other than t or nil as "unknown" value, it's nice to have a self-evaluation symbol just like t and nil for that. The obvious name choice is u.
<<logic3.el>>= (setq u 'u)
The following function maps any expression which is interpreted as u value to the symbol u defined above.
<<logic3.el>>= (defun normalize3 (arg) "Replace any arg which is not t or nil with u" (if (unknown-p arg) u arg))
Test code
The following function tests the definitions above.
<<logic3.el>>= (defun test-logic3 () "Test the 3-values logic routines." (interactive) (let ((one 1) (two 2)) (or (equal (mapcar (lambda (args) (list args '=> (eval (cons 'and3 args)) (eval (cons 'or3 args)))) '(() (nil) (1) (t) (nil nil) (nil 1) (nil t) (1 nil) (1 2) (1 t) (t nil) (t 1) (t t))) '((nil => t nil) ((nil) => nil nil) ((1) => 1 1) ((t) => t t) ((nil nil) => nil nil) ((nil 1) => nil 1) ((nil t) => nil t) ((1 nil) => nil 1) ((1 2) => 2 2) ((1 t) => 1 t) ((t nil) => nil t) ((t 1) => 1 t) ((t t) => t t))) (error "error in and3 or or3")) (or (equal (mapcar 'not3 '(nil 1 t)) '(t 1 nil)) (error "error in not3")) (or3 t (error "or3 evaluates after t")) (and3 nil (error "and3 evaluates after nil")) (or (and (not (unknown-p t)) (not (unknown-p nil)) (unknown-p 1)) (error "error in unknown-p")) (or (and (equal (imply3 nil (error "imply3 evaluates after nil")) t) (equal (imply3 one nil) 1) (equal (imply3 'one nil) 'one) (equal (imply3 one two) t) (equal (imply3 one t) t) (equal (imply3 t nil) nil) (equal (imply3 t one) 1) (equal (imply3 t 'one) 'one) (equal (imply3 t t) t)) (error "error in imply3")) (or (and (equal (normalize3 t) t) (equal (normalize3 nil) nil) (equal (normalize3 1) u) (equal (normalize3 u) u)) (error "error in normalize3")) (let ((a 0)) (and3 (setq a (+ 1 a)) (setq a (+ 2 a))) (or (equal a 3) (error "and3 evaluation error"))) (let ((a 0)) (and3 (setq a (+ 1 a)) t (setq a (+ 2 a))) (or (equal a 3) (error "and3 evaluation error"))) (let ((a 0)) (and3 (setq a (+ 1 a)) nil (setq a (+ 2 a))) (or (equal a 1) (error "and3 evaluation error"))) (let ((a 0)) (or3 (setq a (+ 1 a)) (setq a (+ 2 a))) (or (equal a 3) (error "or3 evaluation error"))) (let ((a 0)) (or3 (setq a (+ 1 a)) nil (setq a (+ 2 a))) (or (equal a 3) (error "or3 evaluation error"))) (let ((a 0)) (or3 (setq a (+ 1 a)) t (setq a (+ 2 a))) (or (equal a 1) (error "or3 evaluation error"))) (let ((a 0)) (imply3 (setq a (+ 1 a)) (setq a (+ 2 a))) (or (equal a 3) (error "imply3 evaluation error"))) (let ((a 0)) (imply3 (setq a (+ 1 a)) t) (or (equal a 1) (error "imply3 evaluation error")))) (message "No error found in logic3.el"))
| Download code |