class LogicTools::Node
Represents a node of a tree representing a logical expression.
Public Instance Methods
Tells if self
covers tree
# File lib/logic_tools/logictree.rb, line 300 def cover?(tree) # By default: equality comparison. return self == tree end
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
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
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
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
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
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
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
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
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
Tells if self
includes tree
.
# File lib/logic_tools/logictree.rb, line 294 def include?(tree) # By default: equality comparison. return self == tree end
Tells if the node is a parent.
Default: false
.
# File lib/logic_tools/logictree.rb, line 90 def is_parent? return false end
Gets the operator.
Default: nil
(none).
# File lib/logic_tools/logictree.rb, line 97 def op nil end
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
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
Gets number of children.
Default: 0
(none).
# File lib/logic_tools/logictree.rb, line 104 def size 0 end
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
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
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
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
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