Integers as Boolean functions

Richard Suchenwirth 2005-04-12 - Boolean functions, in which arguments and result are in the domain {true, false}, or {1, 0} as expr has it, and operators are e.g. {AND, OR, NOT} resp. {&&, ||, !}, can be represented by their truth table, which for example for {$a && $b} looks like:

As all but the last column just enumerate all possible combinations of the arguments, first column least-significant, the full representation of a&&b is the last column, a sequence of 0s and 1s which can be seen as binary integer, reading from bottom up: 1 0 0 0 == 8. So 8 is the associated integer of a&&b, but not only of this - we get the same integer for !(!a || !b), but then again, these functions are equivalent.

To try this in Tcl, here's a truth table generator that I borrowed from a little proving engine, but without the lsort used there - the order of cases delivered makes best sense when the first bit is least significant:

 proc truthtable n {
    # make a list of 2**n lists, each with n truth values 0|1
    set res {}
    for {set i 0} {$i < (1<<$n)} {incr i} {
        set case {}
        for {set j  0} {$j <$n} {incr j } {
            lappend case [expr {($i & (1<<$j)) != 0}]
        }
        lappend res $case
    }
    set res
 }

Now we can write n(f), which, given a Boolean function of one or more arguments, returns its characteristic number, by iterating over all cases in the truth table, and setting a bit where appropriate:

 proc n(f) expression {
    set vars [lsort -unique [regsub -all {[^a-zA-Z]} $expression " "]]
    set res 0
    set bit 1
    foreach case [truthtable [llength $vars]] {
        foreach $vars $case break
        set res [expr $res | ((($expression)!=0)*$bit)]
        incr bit $bit ;#-- <<1, or *2
    }
    set res
 }

Experimenting:

 % n(f) {$a && !$a} ;#-- contradiction is always false
 0
 % n(f) {$a || !$a} ;#-- tautology is always true
 3
 % n(f) {$a}        ;#-- identity is boring
 2
 % n(f) {!$a}       ;#-- NOT
 1
 % n(f) {$a && $b}  ;#-- AND
 8
 % n(f) {$a || $b}  ;#-- OR
 14
 % n(f) {!($a && $b)} ;#-- de Morgan's laws:
 7
 % n(f) {!$a || !$b}  ;#-- same value = equivalent
 7

So the characteristic integer is not the same as the Goedel number of a function, which would encode the structure of operators used there.

 % n(f) {!($a || $b)} ;#-- interesting: same as unary NOT
 1
 % n(f) {!$a && !$b}
 1

Getting more daring, let's try a distributive law:

 % n(f) {$p && ($q || $r)}
 168
 % n(f) {($p && $q) || ($p && $r)}
 168

Daring more: what if we postulate the equivalence?

 % n(f) {(($p && $q) || ($p && $r)) == ($p && ($q || $r))}
 255

Without proof, I just claim that every function of n arguments whose characteristic integer is 2^(2^n) - 1 is a tautology (or a true statement - all bits are 1). Conversely, postulating non-equivalence turns out to be false in all cases, hence a contradiction:

 % n(f) {(($p && $q) || ($p && $r)) != ($p && ($q || $r))}
 0

So again, we have a little proving engine, and simpler than last time.

In the opposite direction, we can call a Boolean function by its number and provide one or more arguments - if we give more than the function can make sense of, non-false excess arguments lead to constant falsity, as the integer can be considered zero-extended:

 proc f(n) {n args} {
    set row 0
    set bit 1
    foreach arg $args {
        set row [expr {$row | ($arg != 0)*$bit}]
        incr bit $bit
    }
    expr !!($n &(1<<$row))
 }

Trying again, starting at OR (14):

 % f(n) 14 0 0
 0
 % f(n) 14 0 1
 1
 % f(n) 14 1 0
 1
 % f(n) 14 1 1
 1

So f(n) 14 indeed behaves like the OR function - little surprise, as its truth table (the results of the four calls), read bottom-up, 1110, is decimal 14 (8 + 4 + 2). Another test, inequality:

 % n(f) {$a != $b}
 6
 % f(n) 6 0 0
 0
 % f(n) 6 0 1
 1
 % f(n) 6 1 0
 1
 % f(n) 6 1 1
 0

Trying to call 14 (OR) with more than two args:

 % f(n) 14 0 0 1
 0
 % f(n) 14 0 1 1
 0
 53 % f(n) 14 1 1 1
 0

The constant 0 result is a subtle indication that we did something wrong :)

Implication (if a then b, a -> b) can in expr be expressed as $a <= $b - just note that the "arrow" seems to point the wrong way. Let's try to prove "Modus Barbara" - "if a implies b and b implies c, then a implies c":

 % n(f) {(($a <= $b) && ($b <= $c)) <= ($a <= $c)}
 255

With less abstract variable names, one might as well write

 % n(f) {(($Socrates <= $human) && ($human <= $mortal)) <= ($Socrates <= $mortal)}
 255

But this has been verified long ago, by Socrates' death :^)

Lars H: A remark concerning the use of the word "proof" above. Strictly speaking, the above doesn't prove any implications; it verifies that the given formula is a tautology (evaluates to true for any assignment of true/false to its variables). While from one point of view these things are the same -- a formula is a theorem of standard propositional logic if and only if it is a tautology -- they are also quite different, because "proof" is a concept that has meaning only in relation to a particular theory, whereas "tautology" is defined with respect to a particular model. It is possible to deduce from the fact that a formula is a tautology that there is a proof of it, but that deduction relies on a result in the metatheory of propositional logic.

More formally, a proof in a theory T is defined to be a sequence of formulae where each formula is (i) a premise, (ii) an axiom of the theory T, or (iii) a formula that follows (using one of the rules of inference of T) from some previous formulae in the proof. If there is a proof in the theory under consideration that ends with B and has premises A1,...,An, then one writes A1,...,An|-B (this |- is really a \u22A2). A formula B is a theorem in a theory if |-B, i.e., if there is a proof of it without any additional assumptions.

CL applauds Lars' exposition of the distinction between model and theory.

The way back from an integer to a logical expression is shown on Disjunctive Normal Form.

Arts and Crafts of Tcl-Tk Programming

Category Mathematics