class LogicTools::Node

Represents a node of a tree representing a logical expression.

Public Instance Methods

cover?(tree) click to toggle source

Tells if self covers tree

# File lib/logic_tools/logictree.rb, line 300
def cover?(tree)
    # By default: equality comparison.
    return self == tree
end
distribute(dop,node) click to toggle source

Creates a new tree where the current node is distributed over node according to the dop operator.

# File lib/logic_tools/logictree.rb, line 245
def distribute(dop,node)
    fop = dop == :and ? :or : :and
    if (node.op == dop) then
        # Same operator: merge self in node
        return NodeNary.make(dop, self, *node)
    elsif (node.op == fop) then
        # Opposite operator: can distribute
        # result = NodeNary.make(dop)
        # node.each do |child|
        #     result << NodeNary.make(dop,child,self).flatten
        # end
        # return result.flatten
        nchildren = node.map do |child|
            NodeNary.make(dop,child,self).flatten
        end
        return NodeNary.make(fop,*nchildren).flatten
    else
        # Unary operator: simple product
        return NodeNary.make(dop, self, node)
    end
end
each() click to toggle source

Iterate over the children.

# File lib/logic_tools/logictree.rb, line 174
def each
    # No block given? Return an enumerator.
    return to_enum(:each) unless block_given?
    # Block given? No child, so nothing to do anyway...
end
each_line() { |vars,eval| ... } click to toggle source

Iterates on each line of the truth table obtained from the tree rooted by current node.

Iteration parameters (for the current line of the truth table):

  • vars: the variables of the expression

  • val: the value of the expression

# File lib/logic_tools/logictree.rb, line 123
def each_line
    # No block given? Return an enumerator.
    return to_enum(:each_line) unless block_given?

    # Block given? Apply it.
    # Get the variables
    vars = self.get_variables
    # Compute the number of iterations
    nlines = 2**vars.size
    # Generates each bit value for the variables and the
    # correspong node value for iterating on it
    nlines.times do |line|
        vars.each_with_index do |var,i|
            val = line[vars.size-i-1]
            var.value = val
        end
        # Apply the block
        yield(vars,self.eval)
    end
end
each_maxterm() { |vars| ... } click to toggle source

Iterates over each maxterm of the tree rooted from current node.

Iteration parameters:

  • vars: the variables of the expression

# File lib/logic_tools/logictree.rb, line 160
def each_maxterm
    # No block given? Return an enumerator.
    return to_enum(:each_maxterm) unless block_given?

    # Block given? Apply it.
    each_line do |vars,val|
        unless val then
            vars.each { |var| var.value = !var.value }
            yield(vars)
        end
    end
end
each_minterm() { |vars| ... } click to toggle source

Iterates over each minterm of the tree rooted from current node.

Iteration parameters:

  • vars: the variables of the expression

# File lib/logic_tools/logictree.rb, line 148
def each_minterm
    # No block given? Return an enumerator.
    return to_enum(:each_minterm) unless block_given?

    # Block given? Apply it.
    each_line { |vars,val| yield(vars) if val }
end
eval_input(input) click to toggle source

Evalutes the tree on a binary input.

# File lib/logic_tools/logictree.rb, line 109
def eval_input(input)
    self.get_variables.each_with_index do |var,i|
        val = input[vars.size-i-1]
        var.value = val
    end
    return self.eval
end
flatten() click to toggle source

Creates a new tree where the and, or or not operator of the current node is flattened.

Default: simply duplicates the node.

# File lib/logic_tools/logictree.rb, line 222
def flatten
    return self.dup
end
flatten_deep() click to toggle source

Creates a new tree where all the and, or and not operators from the current node are flattened.

Default: simply duplicate.

# File lib/logic_tools/logictree.rb, line 230
def flatten_deep
    # print "flatten_deep #1 with self=#{self}\n"
    return self.dup
end
get_variables() click to toggle source

Gets a array containing the variables of the tree sorted by name.

# File lib/logic_tools/logictree.rb, line 82
def get_variables()
    result = self.get_variablesRecurse
    return result.flatten.uniq.sort
end
include?(tree) click to toggle source

Tells if self includes tree.

# File lib/logic_tools/logictree.rb, line 294
def include?(tree)
    # By default: equality comparison.
    return self == tree
end
is_parent?() click to toggle source

Tells if the node is a parent.

Default: false.

# File lib/logic_tools/logictree.rb, line 90
def is_parent?
    return false
end
op() click to toggle source

Gets the operator.

Default: nil (none).

# File lib/logic_tools/logictree.rb, line 97
def op
    nil
end
reduce() click to toggle source

Reduce the node by removing redundancy from it.

NOTE: this is not the same purpose a Enumerable::reduce.

# File lib/logic_tools/logictree.rb, line 238
def reduce
    # By default, no possible reduction.
    self.clone
end
simplify() click to toggle source

Generates an equivalent but simplified representation of the expression represented by the tree rooted by the current node.

Uses the Espresso method.

# File lib/logic_tools/logicsimplify_es.rb, line 729
def simplify()
    # Initialization

    # Step 1: generate the simplified cover.
    cover = self.to_cover.simplify

    # Step 2: generate the resulting tree from the resulting cover.
    return cover.to_tree
end
size() click to toggle source

Gets number of children.

Default: 0 (none).

# File lib/logic_tools/logictree.rb, line 104
def size
    0
end
to_cover(*variables) click to toggle source

Converts to a cover of a boolean space based of variables.

NOTE: the variables of the space are also extracted from self.

# File lib/logic_tools/logicconvert.rb, line 19
def to_cover(*variables)
    # Check the cases of trivial trees.
    if self.is_a?(NodeTrue) then
        if variables.empty? then
            cover = Cover.new("all")
            cover << Cube.new("-")
        else
            cover = Cover.new(*variables)
            cover << Cube.new("-"*variables.size)
        end
        return cover
    elsif self.is_a?(NodeFalse) then
        return Cover.new(*variables)
    end

    # Get the variables for converting them to indexes in the cubes
    vars = (variables + self.get_variables.map(&:to_s)).uniq
    # print "vars=#{vars}\n"
    # Converts the tree rooted by self to a sum of products
    # (reduced to limit the number of cubes and their sizes).
    tree = self.to_sum_product.reduce
    # print "tree=#{tree}\n"
    
    # Create an empty cover.
    cover = Cover.new(*vars)

    # Treat the trival cases.
    case tree.op 
    when :true then
        # Logic true
        cover << Cube.new("-" * cover.width)
        return cover
    when :false then
        # Logic false
        return cover
    when :variable then
        # Single variable
        str = "-" * cover.width
        index = vars.index(tree.variable.to_s)
        str[index] = "1"
        cover << Cube.new(str)
        return cover
    when :not then
        # Single complement of a variable
        str = "-" * cover.width
        index = vars.index(tree.child.variable.to_s)
        str[index] = "0"
        cover << Cube.new(str)
        return cover
    end

    # Treat the other cases.

    # Ensure we have a sum of product structure.
    tree = [ tree ] unless tree.op == :or

    # print "tree=#{tree}\n"

    # Fill it with the cubes corresponding to each product
    tree.each do |product|
        next if product.is_a?(NodeFalse)
        if product.is_a?(NodeTrue) then
            cover.add(Cube.new("-"*vars.size))
            next
        end
        product = [ product ] unless product.is_a?(NodeNary)
        # print "product=#{product}\n"
        # Generate the bit string of the cube
        str = "-"*vars.size
        product.each do |lit|
            if lit.is_a?(NodeNot) then
                index = vars.index(lit.child.variable.to_s)
                # The litteral is a not
                if str[index] == "1" then
                    # But it was "1" previously, contradictory cube:
                    # mark it for removal
                    str = nil
                    break
                else
                    # No contradiction, put a "0"
                    str[index] = "0"
                end
            else
                # print "lit=#{lit}\n"
                index = vars.index(lit.variable.to_s)
                # The litteral is a variable
                if str[index] == "0" then
                    # But it was "0" previously, contradictory cube:
                    # mark it for removal.
                    str = nil
                    break
                else
                    # No contradiction, put a "1"
                    str[index] = "1"
                end
            end
        end
        # Create and add the corresponding cube if any.
        cover.add(Cube.new(str)) if str
    end
    # print "cover=#{cover}\n"
    # Remove the duplicate cubes if any.
    cover.uniq!
    # Return the resulting cover.
    return cover
end
to_std_conjunctive() click to toggle source

Generates the equivalent standard conjunctive form.

# File lib/logic_tools/logictree.rb, line 181
def to_std_conjunctive
    # Generate each minterm tree
    minterms = []
    each_minterm do |vars|
        vars = vars.map do |var|
            var = NodeVar.new(var)
            var = NodeNot.new(var) unless var.eval
            var
        end
        # Create the term
        term = vars.size == 1 ? vars[0] : NodeAnd.new(*vars)
        # Add the term
        minterms << term
    end
    # Conjunct them
    return minterms.size == 1 ? minterms[0] : NodeOr.new(*minterms)
end
to_std_disjunctive() click to toggle source

Generates the equivalent standard disjunctive form.

# File lib/logic_tools/logictree.rb, line 200
def to_std_disjunctive
    # Generate each maxterm tree
    maxterms = []
    each_maxterm do |vars|
        vars = vars.map do |var|
            var = NodeVar.new(var)
            var = NodeNot.new(var) unless var.eval
            var
        end
        # Create the term
        term = vars.size == 1 ? vars[0] : NodeOr.new(*vars)
        # Add the term
        maxterms << term
    end
    # Disjunct them
    return maxterms.size == 1 ? maxterms[0] : NodeAnd.new(*maxterms)
end
to_sum_product(flattened = false) click to toggle source

Creates a sum fo product from the tree rooted by current node.

Argument flattened tells if the tree is already flattend

# File lib/logic_tools/logictree.rb, line 270
def to_sum_product(flattened = false)
    # print "NODE to_sum_product with tree=#{self}\n"
    return self.dup
end
to_sym() click to toggle source

Converts to a symbol.

There is exactly one symbol per possible tree.

# File lib/logic_tools/logictree.rb, line 282
def to_sym
    to_s.to_sym
end