class TruthTable

truth table and formula generator from Ruby block ↑

The truthtable library generates a truth table from a logical formula written in Ruby. The truth table can be converted to a logical formula.

Author ↑

Tanaka Akira <akr@fsij.org>

Feature ↑

Usage ↑

truthtable/qm.rb - Quine-McCluskey algorithm

Copyright (C) 2007 Tanaka Akira <akr@fsij.org>

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

  1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

  2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

  3. The name of the author may not be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE AUTHOR “AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Public Class Methods

new(&b) click to toggle source 
# File truthtable.rb, line 156
def initialize(&b)
  table = TruthTable.test(&b)
  @table = table
end
test(&b) click to toggle source 
# File truthtable.rb, line 144
def self.test(&b)
  r = []
  o = TruthTableObject.new
  begin
    result = !!b.call(o)
    inputs = o.plan
    order = o.order
    r << [inputs, result, order]
  end while o.next_plan
  r
end

Public Instance Methods

cnf() click to toggle source

obtains a formula in conjunctive normal form.

# File truthtable.rb, line 275
def cnf
  r = []
  @table.each {|inputs, output|
    return output.to_s if inputs.empty?
    next if output
    term = []
    each_input(inputs) {|name, input|
      if input
        term << "!#{name}"
      else
        term << name
      end
    }
    if term.length == 1
      r << term.join('|')
    else
      r << "(#{term.join('|')})"
    end
  }
  return "true" if r.empty?
  r.join(' & ')
end
dnf() click to toggle source

obtains a formula in disjunctive normal form.

# File truthtable.rb, line 255
def dnf
  r = []
  @table.each {|inputs, output|
    return output.to_s if inputs.empty?
    next if !output
    term = []
    each_input(inputs) {|name, input|
      if input
        term << name
      else
        term << "!#{name}"
      end
    }
    r << term.join('&')
  }
  return "false" if r.empty?
  r.join(' | ')
end
formula() click to toggle source

obtains a minimal formula using Quine-McCluskey algorithm.

# File truthtable.rb, line 299
def formula
  input_names = all_names
  input_names_ary = sort_names(input_names.keys)
  tbl = {}
  @table.each {|inputs, output|
    return output.to_s if inputs.empty?
    inputs2 = [:x] * input_names.length
    inputs.each {|name, input|
      inputs2[input_names[name]] = input ? 1 : 0
    }
    tbl[inputs2] = output ? 1 : 0
  }
  qm = QM.qm(tbl)
  r = []
  qm.each {|term|
    t = []
    num_dontcare = 0
    term.each_with_index {|v, i|
      if v == false
        t << ("!" + input_names_ary[i])
      elsif v == true
        t << input_names_ary[i]
      else # :x
        num_dontcare += 1
      end
    }
    if num_dontcare == term.length
      r << 'true'
    else
      r << t.join('&')
    end
  }
  return "false" if r.empty?
  r.join(' | ')
end
to_s() click to toggle source 
# File truthtable.rb, line 161
def to_s
  r = ''
  names = sort_names(all_names.keys)
  format = ''
  sep = ''
  names.each {|name|
    format << "%-#{name.length}s "
    sep << '-' * (name.length+1)
  }
  format << "| %s\n"
  sep << "+--\n"
  r << sprintf(format, *(names + ['']))
  r << sep
  @table.each {|inputs, output, order|
    h = {}
    each_input(inputs) {|name, input|
      h[name] = input
    }
    args = []
    names.each {|name|
      if h.has_key? name
        args << (h[name] ? 't' : 'f').center(name.length)
      else
        args << '?'.center(name.length)
      end
    }
    args << (output ? 't' : 'f')
    r << sprintf(format, *args)
  }
  r
end