Version 3 of Disjunctive Normal Form

Updated 2005-04-27 07:46:02 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" [L1 ], 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

---

Bug report: arity isn't computed correctly for higher integers. I get

 % disjunctiveNormalForm 168
 ($a & !$d) | ($a & $b & !$d) | ($a & $c & !$d)

which should however be

 ($a & $b) | ($a & $c)

Hints welcome! :)

---

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