class LogicTools::Cover
Represents a cover of a boolean function.
Public Class Methods
Creates a new cover on a boolean space represented by a list of variables
.
# File lib/logic_tools/logiccover.rb, line 335 def initialize(*variables) @variables = *variables # Initialize the cover @cubes = [] # @sorted = false # Initialy, the cover is not sorted end
Public Instance Methods
Gets a cube by index
.
# File lib/logic_tools/logiccover.rb, line 410 def [](index) return @cubes[index] end
Adds a cube
to the cover.
Creates a new cube if cube
is not an instance of LogicTools::Cube
.
# File lib/logic_tools/logiccover.rb, line 370 def add(cube) # Check the cube. cube = Cube.new(cube) unless cube.is_a?(Cube) if cube.width != self.width then raise "Invalid cube width for #{cube}, expecting: #{self.width}" end # The cube is valid, add it. @cubes.push(cube) # # The cubes of the cover are therefore unsorted. # @sorted = false end
Generates the cofactor obtained when var
is set to val
.
# File lib/logic_tools/logiccover.rb, line 479 def cofactor(var,val) # if val != "0" and val != "1" then if val != 48 and val != 49 then raise "Invalid value for generating a cofactor: #{val}" end # Get the index of the variable. i = @variables.index(var) # Create the new cover. cover = Cover.new(*@variables) # Set its cubes. @cubes.each do |cube| cube = cube.to_s # cube[i] = "-" if cube[i] == val cube.setbyte(i,45) if cube.getbyte(i) == val # cover << Cube.new(cube) if cube[i] == "-" cover << Cube.new(cube,false) if cube.getbyte(i) == 45 end cover.uniq! return cover end
Generates the generalized cofactor from cube
.
# File lib/logic_tools/logiccover.rb, line 501 def cofactor_cube(cube) # Create the new cover. cover = Cover.new(*@variables) # Set its cubes. @cubes.each do |scube| scube = scube.to_s scube.size.times do |i| if scube.getbyte(i) == cube.getbyte(i) then # scube[i] = "-" scube.setbyte(i,45) # elsif (scube[i] != "-" and cube[i] != "-") then elsif (scube.getbyte(i)!=45 and cube.getbyte(i)!=45) then # The cube is to remove from the cover. scube = nil break end end if scube then # The cube is to keep in the cofactor. cover << Cube.new(scube,false) end end cover.uniq! return cover end
Generates the complement cover.
# File lib/logic_tools/logiccover.rb, line 623 def complement # First treat the case when the cover is empty: # the result is the tautology. if @cubes.empty? then result = Cover.new(*@variables) result << Cube.new("-"*self.width,false) return result end # Otherwise... # Look for a binate variable to split on. binate = self.find_binate unless binate then # The cover is actually unate, complement it the fast way. # Step 1: Generate the following boolean matrix: # each "0" and "1" is transformed to "1" # each "-" is transformed to "0" matrix = [] @cubes.each do |cube| line = " " * self.width matrix << line cube.each_byte.with_index do |bit,i| # line[i] = (bit == "0" or bit == "1") ? "1" : "0" line.setbyte(i, (bit == 48 or bit == 49) ? 49 : 48 ) end end # Step 2: finds all the minimal column covers of the matrix mins = minimal_column_covers(matrix) # Step 3: generates the complent cover from the minimal # column covers. # Each minimal column cover is converted to a cube using # the following rules (only valid because the initial cover # is unate): # * a minimal column whose variable can be reduced to 1 # is converted to the not of the variable # * a minimal column whose variable can be reduced to 0 is # converted to the variable # # +result+ is the final complement cover. result = Cover.new(*@variables) # print "mins=#{mins}\n" mins.each do |min| # +cbits+ is the bit string describing the cube built # from the column cover +min+. cbits = "-" * self.width min.each do |col| # if @cubes.find {|cube| cube[col] == "1" } then if @cubes.find {|cube| cube.getbyte(col) == 49 } then # cbits[col] = "0" cbits.setbyte(col,48) else # cbits[col] = "1" cbits.setbyte(col,49) end end result << Cube.new(cbits,false) end return result else # Compute the cofactors over the binate variables. # cf0 = self.cofactor(binate,"0") cf0 = self.cofactor(binate,48) # cf1 = self.cofactor(binate,"1") cf1 = self.cofactor(binate,49) # Complement them. cf0 = cf0.complement cf1 = cf1.complement # Build the resulting complement cover as: # (cf0 and (not binate)) or (cf1 and binate) result = Cover.new(*@variables) # Get the index of the binate variable. i = @variables.index(binate) cf0.each_cube do |cube| # cf0 and (not binate) # if cube[i] != "1" then if cube.getbyte(i) != 49 then # Cube's binate is not "1" so the cube can be kept # cube[i] = "0" cube.setbyte(i,48) result << cube end end cf1.each_cube do |cube| # cf1 and binate # if cube[i] != "0" then if cube.getbyte(i) != 48 then # Cube's binate is not "0" so the cube can be kept # cube[i] = "1" cube.setbyte(i,49) result << cube end end return result end end
Iterates over the cubes of the cover.
Returns an enumerator if no block is given.
# File lib/logic_tools/logiccover.rb, line 401 def each_cube(&blk) # No block given? Return an enumerator. return to_enum(:each_cube) unless block_given? # Block given? Apply it. @cubes.each(&blk) end
Iterates over the variables of the cube
Returns an enumberator if no block is given
# File lib/logic_tools/logiccover.rb, line 438 def each_variable(&blk) # No block given? Return an enumerator return to_enum(:each_variable) unless block_given? # Block given? Apply it. @variables.each(&blk) end
Tells if the cover is empty.
# File lib/logic_tools/logiccover.rb, line 353 def empty? return @cubes.empty? end
Evaluates the corresponding function's value for a binary input
.
input
is assumed to be an integer. Returns the evaluation result as a boolean.
# File lib/logic_tools/logiccover.rb, line 449 def eval_input(input) # Evaluates each cube, if one results in true the result is true. return !!@cubes.each.find {|cube| cube.eval_input(input) } end
Looks for a binate variable.
Returns the found binate variable or nil if not found.
NOTE: Can also be used for checking if the cover is unate.
# File lib/logic_tools/logiccover.rb, line 532 def find_binate # Merge the cube over one another until a 1 over 0 or 0 over 1 # is met. # The merging rules are to followings: # 1 over 1 => 1 # 1 over - => 1 # 1 over 0 => not unate # 0 over 0 => 0 # 0 over - => 0 # 0 over 1 => not unate merge = "-" * self.width @cubes.each do |cube| cube.each_byte.with_index do |bit,i| # if bit == "1" then if bit == 49 then # if merge[i] == "0" then if merge.getbyte(i) == 48 then # A 1 over 0 is found, a binate variable is found. return @variables[i] else # merge[i] = "1" merge.setbyte(i,49) end # elsif bit == "0" then elsif bit == 48 then # if merge[i] == "1" then if merge.getbyte(i) == 49 then # A 0 over 1 is found, a binate variable is found. return @variables[i] else # merge[i] = "0" merge.setbyte(i,48) end end end end # The cover is unate: no binate variable. return nil end
Checks if self
intersects with cube_or_cover
.
cube_or_cover
is either a full LogicTools::Cover
object or a single cube object (LogicTools::Cube
or bit string).
# File lib/logic_tools/logiccover.rb, line 809 def intersects?(cube_or_cover) if cube_or_cover.is_a?(Cover) then # Cover case: check intersect with each cube of +cube_or_cover+. # # NOTE: !! is for converting the result to boolean. return !!( cube_or_cover.each_cube.find do |cube| self.intersects?(cube) end ) else # Cube case. # # NOTE: !! is for converting the result to boolean. return !!( @cubes.find do |cube| cube.intersects?(cube_or_cover) end ) end end
Checks if self is a tautology.
# File lib/logic_tools/logiccover.rb, line 719 def is_tautology? # Look for a binate variable to split on. binate = self.find_binate # Gets its index i = @variables.index(binate) unless binate then # The cover is actually unate, check it the fast way. # Does it contain a "-" only cube? If yes, this is a tautology. @cubes.each do |cube| # return true unless cube.each_bit.find { |bit| bit != "-" } return true unless cube.each_byte.find { |bit| bit != 45 } end # No "-" only cube, this is not a tautology return false # # Other techniques: actually general, not necessarily on # unate cover! Therefore WRONG place! # The cover is actually unate, check it the fast way. # Does it contain a "-" only cube? If yes, this is a tautology. # @cubes.each do |cube| # # return true unless cube.each_bit.find { |bit| bit != "-" } # return true unless cube.each_bit.find { |bit| bit != 45 } # end # # Is there a "1" only or "0" only column? If yes, this is not # # a tautology. # self.width.times do |col| # fbit = @cubes[0][col] # # next if fbit == "-" # next if fbit == 45 # next if (1..(@cubes.size-1)).each.find do |bit| # bit != fbit # end # return false # Not a tautology. # end # # Check the upper bound of the number of minterms: # # if < 2**width, not a tautology. # num_minterms = 0 # @cubes.each do |cube| # # num_minterms += 2 ** cube.each_bit.count {|b| b == "-"} # num_minterms += 2 ** cube.each_bit.count {|b| b == 45} # end # return false if num_minterms < 2**self.width # # Last check: the truth table. # (2**self.width).times do |input| # return false if self.eval_input(input) == 0 # end else # Compute the cofactors over the binate variables. # cf0 = self.cofactor(binate,"0") cf0 = self.cofactor(binate,48) # cf1 = self.cofactor(binate,"1") cf1 = self.cofactor(binate,49) # Check both: if there are tautologies, self is also a # tautology return ( cf0.is_tautology? and cf1.is_tautology? ) end end
Duplicate the cover while improving a bit the result (for faster processing later).
# File lib/logic_tools/logiccover.rb, line 424 def simpler_clone # Clone. cover = self.clone # But remove duplicate cubes. cover.uniq! # And sort the cubes to group together cubes with a shorter # distance. cover.sort! { |c0,c1| c0.distance(c1) - 1 } return cover end
Generates an equivalent but simplified cover.
Param:
deadline
-
the deadline for irredudant in seconds.
volume
-
the “volume” above which the cover is split before being solved.
Uses the Espresso method.
# File lib/logic_tools/logicsimplify_es.rb, line 618 def simplify(deadline = Float::INFINITY, volume = Float::INFINITY) # Compute the cost before any simplifying. @first_cost = cost(self) info do "Cost before simplifying: #{@first_cost} " + "(with #{@cubes.size} cubes)" end # If the cover is too big, split before solving. if (self.size > 2) and (self.size * (self.width ** 2) > volume) then return split_simplify(deadline,volume) end # Step 1: # The on set is a copy of self [F]. on = self.simpler_clone # Initialization # # print "on=#{on}\n" # print "#1 #{Time.now}\n" # And the initial set of don't care: dc [D]. dc = Cover.new(*on.each_variable) # At first dc is empty # print "#2 #{Time.now}\n" # Step 2: generate the complement cover: off [R = COMPLEMENT(F)]. off = on.complement # off = irredundant_partial(off) # quickly simlify off. # print "off=#{off}\n" info { "off with #{off.size} cubes." } # # Process the cover by pieces if the off and the on are too big. # If on and off are too big together, split before solving. if (on.size > 2) and (on.size*off.size > volume) then return split_simplify(deadline,volume) end # print "#3 #{Time.now}\n" # Step 3: perform the initial expansion [F = EXPAND(F,R)]. on = expand(on,off,deadline) # print "expand:\non=#{on}\n" # Remove the duplicates. on.uniq! # print "#4 #{Time.now}\n" # Step 4: perform the irredundant cover [F = IRREDUNDANT(F,D)]. on = irredundant(on,dc,deadline) # print "irredundant:\non=#{on}\n" # print "#5 #{Time.now}\n" # Step 5: Detect the essential primes [E = ESSENTIAL(F,D)]. essentials = essentials(on,dc) # print "essentials=#{essentials}\n" # print "#6 #{Time.now}\n" # Step 6: remove the essential primes from on and add them to dc on = on - essentials dc = dc + essentials # Optimiation loop # Computes the cost after preprocessing. new_cost = cost(on) essentials_cost = cost(essentials) info { "After preprocessing, cost=#{new_cost+essentials_cost}" } if new_cost >0 then begin # print "#7.1 #{Time.now}\n" cost = new_cost # Step 1: perform the reduction of on [F = REDUCE(F,D)] on = LogicTools.reduce(on,dc) # print "reduce:\non=#{on.to_s}\n" # Step 2: perform the expansion of on [F = EXPAND(F,R)] on = expand(on,off,deadline) # Also remove the duplicates on.uniq! # Step 3: perform the irredundant cover [F = IRREDUNDANT(F,D)] on = irredundant(on,dc,deadline) # on.each_cube do |cube| # if ((on+dc)-cube).cofactor_cube(cube).is_tautology? then # print "on=[#{on}]\ndc=[#{dc}]\ncube=#{cube}\n" # raise "REDUNDANT AFTER IRREDUNDANT" # end # end # Step 4: compute the cost new_cost = cost(on) info { "cost=#{new_cost+essentials_cost}" } end while(new_cost < cost) end # Readd the essential primes to the on result on += essentials # This is the resulting cover. info { "Final cost: #{cost(on)} (with #{on.size} cubes)" } return on end
Gets the size (the number of cubes).
# File lib/logic_tools/logiccover.rb, line 348 def size return @cubes.size end
Creates the smallest cube containing self
.
# File lib/logic_tools/logiccover.rb, line 779 def smallest_containing_cube return nil if @cubes.empty? # Empty cover case. # Create a new cube including "-" unless the columns of # all the cubes are identical. cbits = "-" * self.width self.width.times do |i| # print "cbits=#{cbits}\n" # cbits[i] = @cubes.reduce(nil) do |bit,cube| cbits.setbyte(i, @cubes.reduce(nil) do |bit,cube| # print "bit=#{bit} i=#{i} cube=#{cube}\n" if bit == nil then # bit = cube[i] bit = cube.getbyte(i) # elsif bit != cube[i] elsif bit != cube.getbyte(i) # bit = "-" bit = 45 break bit end bit end) end return Cube.new(cbits,false) # No need to clone cbits end
Sorts the cubes of the cover.
# File lib/logic_tools/logiccover.rb, line 474 def sort!(&blk) @cubes.sort!(&blk) end
Generates an equivalent but simplified cover from a set splitting it for faster solution.
Param:
deadline
-
the deadline for each step in second.
volume
-
the “volume” above which the cover is split before being solved.
NOTE: the deadline is acutally applied to the longest step only.
# File lib/logic_tools/logicsimplify_es.rb, line 560 def split_simplify(deadline,volume) info { "Spliting..." } # The on set is a copy of self [F]. on = self.simpler_clone on0 = Cover.new(*@variables) (0..(on.size/2-1)).each do |i| on0 << on[i].clone end on1 = Cover.new(*@variables) (((on.size)/2)..(on.size-1)).each do |i| on1 << on[i].clone end debug { "on0=#{on0}\n" } debug { "on1=#{on1}\n" } # Simplify each part independently inc_indent on0 = on0.simplify(deadline,volume) on1 = on1.simplify(deadline,volume) dec_indent # And merge the results for simplifying it globally. on = on0 + on1 on.uniq! new_cost = cost(on) # if (new_cost >= @first_cost) then # info { "Giving up with final cost=#{new_cost}" } # # Probably not much possible optimization, end here. # result = self.clone # result.uniq! # return result # end # Try to go on but with a timer (set to 7 times the deadline since # there are 7 different steps in total). begin Timeout::timeout(7*deadline) { on = on.simplify(deadline,Float::INFINITY) } rescue Timeout::Error info do "Time out for global optimization, ends here..." end end info do "Final cost: #{cost(on)} (with #{on.size} cubes)" end return on end
Creates the subtraction from self
minus one cover
.
cover
is either an instance of LogicTools::Cover
or a single instance of LogicTools::Cube
.
# File lib/logic_tools/logiccover.rb, line 602 def subtract(cover) # Check if the covers are compatible. if (cover.width != self.width) then raise "Incompatible cover for union: #{cover}" end # Creates the substraction cover. subtraction = Cover.new(*@variables) if cover.is_a?(Cube) then cover = [cover] elsif !(cover.is_a?(Cover)) then raise "Invalid class for cover union: #{cover.class}" end @cubes.each do |cube| subtraction << cube unless cover.each.include?(cube) end # Return the result. return subtraction end
Coverts to an AND-OR-NOT tree.
# File lib/logic_tools/logicconvert.rb, line 129 def to_tree() # Generate the variable index. vars = self.each_variable.to_a # Treat the trivial cases. if vars.empty? then return self.empty? ? NodeFalse.new : NodeTrue.new end return NodeFalse.new if self.empty? # Treat the other cases. # Generate the products. prods = self.each_cube.map do |cube| # Generate the litterals of the and litterals = [] cube.each.with_index do |val,i| if val == "0" then # "0" bits are converted to not litteral. litterals << NodeNot.new(NodeVar.new(vars[i])) elsif val == "1" then # "1" bits are converted to variable litteral litterals << NodeVar.new(vars[i]) end end # Create and and with the generated litterals. NodeAnd.new(*litterals) end # Is there an empty and? if prods.find { |node| node.empty? } then # Yes, this is a tautology. return NodeTrue.new else # No, generate the sum and return it. return NodeOr.new(*prods) end end
Removes duplicate cubes.
# File lib/logic_tools/logiccover.rb, line 468 def uniq! @cubes.uniq! return self end
Creates the union of self and cover
.
cover
is either an instance of LogicTools::Cover
or a single instance of LogicTools::Cube
.
# File lib/logic_tools/logiccover.rb, line 577 def unite(cover) # Check if the covers are compatible. if (cover.width != self.width) then raise "Incompatible cover for union: #{cover}" end # Creates the union cover. union = Cover.new(*@variables) # Fill it with the cubes of self and +cover+. @cubes.each { |cube| union.add(cube.clone) } if cover.is_a?(Cover) then cover.each_cube { |cube| union.add(cube.clone) } elsif cover.is_a?(Cube) then union.add(cover.clone) else raise "Invalid class for cover union: #{cover.class}" end # Return the result. return union end
Adds a cube
in front of the cover.
Creates a new cube if cube
is not an instance of LogicTools::Cube
.
# File lib/logic_tools/logiccover.rb, line 386 def unshift(cube) # Check the cube. cube = Cube.new(cube) unless cube.is_a?(Cube) if cube.width != self.width then raise "Invalid cube width for #{cube}, expecting: #{self.width}" end # The cube is valid, add it. @cubes.unshift(cube) # # The cubes of the cover are therefore unsorted. # @sorted = false end
Gets a variable by index
.
# File lib/logic_tools/logiccover.rb, line 358 def variable(index) return @variables[index].clone end
Gets the index of a variable
.
# File lib/logic_tools/logiccover.rb, line 363 def variable_index(variable) return @variables.index(variable) end
Gets the width (the number of variables of the boolean space).
# File lib/logic_tools/logiccover.rb, line 343 def width return @variables.length end