Version 0 of Disjunctive Normal Form

Updated 2005-04-27 06:55:14 by suchenwi

if 0 {Richard Suchenwirth 2005-04-24 - In Integers as Boolean functions it was shown how from a logical expression f, a non-negative integer n(f) can be computed that represents the expression. Now how about the opposite direction - given an integer, which expression does it represent? A simple answer is to provide the "disjunctive normal form", where the truth table is constructed, and all rows that are true are joined with "or". For example, decimal 11 is binary 1011. From its logarithm to base 4 we see that it has an "arity" of 2, i.e. it matches a truth table of two variables, into which it is filled, least significant bit first:

 b a  f(11)
 0 0  1
 0 1  1
 1 0  0
 1 1  1

By specifying the cases where f(11)=1, we get the full disjunctive normal form (disjunction is just a fancy word for "or" i.e. "|"):

 (!a & !b) | (a & !b) | (a & b)

However, the first two elements of this disjunction are a bit redundant, as obviously the value of a doesn't really matter in them - they cancel themselves out:

  (!a & !b) | (a & !b) == !b

So f(11) reduces to

 !b | (a & b)

And another simplification is possible: if !b doesn't hold, b must be true, so the second element boils down to

 !b | a

Here's the code:}

 proc disjunctiveNormalForm n {
    if {$n <= 0} {return 0} ;# never true
    set res {}
    set rows [1-bits $n]
    foreach row $rows {
        set element [conjunction [int2bits $row [arity $n]] $rows]
        if {$element ne {}} {lappend res ($element)} 
    }
    if [llength $res] {
        join [lsort -u $res] " | "
    } else {return 1} ;# always true - tautology
 }
 proc arity n {expr {$n>0? int(log($n)/log(4))+1 : 1}}

 proc 1-bits n {
    #-- set bits in an integer, e.g. 1-bits 11 -> {0 1 3}
    set res {}
    set row 0
    while {$n} {
        if {$n%2} {lappend res $row}
        set n [expr {$n/2}]
        incr row
    }
    set res
 }
 proc int2bits {n width} {
    set bit 1
    for {set i 0} {$i<$width} {incr i} {
        lappend res [expr {!!($n & $bit)}]
        incr bit $bit
    }
    set res
 }
 proc bits2int bits {
    set res 0
    set value 1
    foreach bit $bits {
        set res [expr {$res+$bit*$value}]
        incr value $value
    }
    set res
 }

if 0 {Building up the conjunctive element for a row, we test each bit if the contrary case is also contained in the rows, and only add its form if it isn't:}

 proc conjunction {bits rows} {
    set res {}
    set i 0
    foreach bit $bits {
        set contrary [lreplace $bits $i $i [not $bit]]
        if ![in $rows [bits2int $contrary]] {
            lappend res [expr {$bit? "": "!"}]$[letter $i]
        }
        incr i
    }
    join $res " & "
 }
 proc not bit {expr {!$bit}}

#-- A simple map generates variable names for 0..25:

 interp alias {} letter {} \
    lindex {a b c d e f g h i j k l m n o p q r s t u v w x y z}

#-- Handy shortcut for element inclusion in a list

 proc in {list element} {expr {[lsearch -exact $list $element]>=0}}

#--Testing:

 for {set i 0} {$i<16} {incr i} {puts $i:[disjunctiveNormalForm $i]}

if 0 {results in:

 0:0
 1:(!$a)
 2:($a)
 3:1
 4:(!$a & $b)
 5:(!$a)
 6:(!$a & $b) | ($a & !$b)
 7:(!$a) | (!$b)
 8:($a & $b)
 9:(!$a & !$b) | ($a & $b)
 10:($a)
 11:(!$b) | ($a)
 12:($b)
 13:(!$a) | ($b)
 14:($a) | ($b)
 15:1

---

Category Mathematics | Arts and crafts of Tcl-Tk programming }