class LogicTools::Cover

Represents a cover of a boolean function.

Public Class Methods

new(*variables) click to toggle source

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

+(cover)
Alias for: unite
-(cover)
Alias for: subtract
<<(cube)
Alias for: add
[](index) click to toggle source

Gets a cube by index.

# File lib/logic_tools/logiccover.rb, line 410
def [](index)
    return @cubes[index]
end
add(cube) click to toggle source

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
Also aliased as: <<
cofactor(var,val) click to toggle source

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
cofactor_cube(cube) click to toggle source

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
complement() click to toggle source

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
each(&blk)
Alias for: each_cube
each_cube(&blk) click to toggle source

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
Also aliased as: each
each_variable(&blk) click to toggle source

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
empty?() click to toggle source

Tells if the cover is empty.

# File lib/logic_tools/logiccover.rb, line 353
def empty?
    return @cubes.empty?
end
eval_input(input) click to toggle source

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
find_binate() click to toggle source

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
intersects?(cube_or_cover) click to toggle source

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
is_tautology?() click to toggle source

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
simpler_clone() click to toggle source

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
simplify(deadline = Float::INFINITY, volume = Float::INFINITY) click to toggle source

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
size() click to toggle source

Gets the size (the number of cubes).

# File lib/logic_tools/logiccover.rb, line 348
def size
    return @cubes.size
end
smallest_containing_cube() click to toggle source

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
sort!(&blk) click to toggle source

Sorts the cubes of the cover.

# File lib/logic_tools/logiccover.rb, line 474
def sort!(&blk)
    @cubes.sort!(&blk)
end
split_simplify(deadline,volume) click to toggle source

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
subtract(cover) click to toggle source

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
Also aliased as: -
to_tree() click to toggle source

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
uniq!() click to toggle source

Removes duplicate cubes.

# File lib/logic_tools/logiccover.rb, line 468
def uniq!
    @cubes.uniq!
    return self
end
unite(cover) click to toggle source

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
Also aliased as: +
unshift(cube) click to toggle source

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
variable(index) click to toggle source

Gets a variable by index.

# File lib/logic_tools/logiccover.rb, line 358
def variable(index)
    return @variables[index].clone
end
variable_index(variable) click to toggle source

Gets the index of a variable.

# File lib/logic_tools/logiccover.rb, line 363
def variable_index(variable)
    return @variables.index(variable)
end
width() click to toggle source

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