module TruthTable::QM

implements Quine-McCluskey algorithm. It minimize the boolean function given by tbl.

For example, the 3-inputs majority function is given as follows.

tbl = {
#  P      Q      R
  [false, false, false] => false,
  [false, false, true ] => false,
  [false, true,  false] => false,
  [false, true,  true ] => true,
  [true,  false, false] => false,
  [true,  false, true ] => true,
  [true,  true,  false] => true,
  [true,  true,  true ] => true,
}
TruthTable::QM.qm(tbl)
#=>
[[true, true, :x], [true, :x, true], [:x, true, true]]  # P&Q | P&R | Q&R
# P     Q           P         R           Q     R

For another example, the implication function is given as follows.

tbl = {
#  P      Q
  [false, false] => true,
  [false, true ] => true,
  [true,  false] => false,
  [true,  true ] => true,
}
TruthTable::QM.qm(tbl)
#=>
[[false, :x], [:x, true]]  # ~P | Q
# ~P               Q

tbl is a hash to represent a boolean function. If the function has N variables, all key of tbl must be an array of N elements.

A element of the key array and a value of the hash should be one of follows:

• false, 0

• true, 1

• :x

0 is same as false.

1 is same as false.

:x means “don't care”.

For example, 3-inputs AND function can be given as follows.

tbl = {
  [false, :x,    :x   ] => false,
  [:x,    false, :x   ] => false,
  [:x,    :x,    false] => false,
  [true,  true,  true ] => true,
}

:x can be used for a value of tbl too. It means that the evaluated result of minimized boolean function is not specified: it may be evaluated to true or false.

tbl = {
  [false, false] => false,
  [false, true ] => true,
  [true,  false] => false,
  [true,  true ] => :x
}

If tbl doesn't specify some combination of input variables, it assumes :x for such combination. The above function can be specified as follows.

tbl = {
  [false, false] => false,
  [false, true ] => true,
  [true,  false] => false,
}

#qm returns an array of arrays which represents the minimized boolean function.

The minimized boolean function is a disjunction of terms such as “term1 | term2 | term3 | …”.

The inner array represents a term. A term is a conjunction of input variables and negated input variables: “P & ~Q & ~R & S & …”.

# File truthtable/qm.rb, line 121
def qm(tbl)
  return [] if tbl.empty?
  tbl = intern_tbl(tbl)
  prime_implicants = find_prime_implicants(tbl)
  essential_prime_implicants, chart = make_chart(prime_implicants, tbl)
  additional_prime_implicants = search_minimal_combination(chart)
  (essential_prime_implicants.keys + additional_prime_implicants).sort.reverse.map {|t|
    extern_term(t)
  }
end