Class: LogicTools::Node

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/logic_tools/logictree.rb,
lib/logic_tools/logicsimplify.rb

Overview

Enhances the Node class with expression simplifying.

Direct Known Subclasses

NodeNary, NodeUnary, NodeValue, NodeVar

Instance Method Summary collapse

Instance Method Details

#distribute(dop, node) ⇒ Object

Creates a new tree where the current node is distributed over node

according to the +dop+ operator.



210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
 
# File 'lib/logic_tools/logictree.rb', line 210

def distribute(dop,node)
    fop = dop == :and ? :or : :and
    # print "dop=#{dop}, fop=#{fop}, node.op=#{node.op}\n"
    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
        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 ⇒ Object

Iterate over the children.

--
TODO generate an Enumerator.



151
152
 
# File 'lib/logic_tools/logictree.rb', line 151

def each
end

#each_line ⇒ Object

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
--
TODO generate an Enumerator.



105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
 
# File 'lib/logic_tools/logictree.rb', line 105

def each_line
    # Get the variables
    vars = self.getVariables
    # 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 ⇒ Object

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

Iteration parameters:
* +vars+: the variables of the expression
--
TODO generate an Enumerator.



138
139
140
141
142
143
144
145
 
# File 'lib/logic_tools/logictree.rb', line 138

def each_maxterm
    each_line do |vars,val|
        unless val then
            vars.each { |var| var.value = !var.value }
            yield(vars)
        end
    end
end

#each_minterm ⇒ Object

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

Iteration parameters:
* +vars+: the variables of the expression
--
TODO generate an Enumerator.



128
129
130
 
# File 'lib/logic_tools/logictree.rb', line 128

def each_minterm
    each_line { |vars,val| yield(vars) if val }
end

#eql?(val) ⇒ Boolean

:nodoc:



249
250
251
 
# File 'lib/logic_tools/logictree.rb', line 249

def eql?(val) # :nodoc:
    self == val
end

#flatten ⇒ Object

Creates a new tree where the and, or or not operator of

the current node is flattened.

Default: simply duplicates the node.



196
197
198
 
# File 'lib/logic_tools/logictree.rb', line 196

def flatten
    return self.dup
end

#flatten_deep ⇒ Object

Creates a new tree where all the and, or and not operators

from the current node are flattened.

Default: simply duplicate.



204
205
206
 
# File 'lib/logic_tools/logictree.rb', line 204

def flatten_deep
    return self.dup
end

#getVariables ⇒ Object

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



78
79
80
81
 
# File 'lib/logic_tools/logictree.rb', line 78

def getVariables()
    result = self.getVariablesRecurse
    return result.flatten.uniq.sort
end

#hash ⇒ Object

:nodoc:



246
247
248
 
# File 'lib/logic_tools/logictree.rb', line 246

def hash # :nodoc:
    to_sym.hash
end

#inspect ⇒ Object

:nodoc:



235
236
237
 
# File 'lib/logic_tools/logictree.rb', line 235

def inspect # :nodoc:
    to_s
end

#op ⇒ Object

Gets the operator.

Default: +nil+ (none).



86
87
88
 
# File 'lib/logic_tools/logictree.rb', line 86

def op
    nil
end

#simplify ⇒ Object

Generates an equivalent but simplified representation of the

expression represented by the tree rooted by the current node.

Uses the Quine-Mc Cluskey method.



247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
 
# File 'lib/logic_tools/logicsimplify.rb', line 247

def simplify
    # Step 1: get the generators
    
    # Gather the minterms which set the function to 1 encoded as
    # bitstrings
    minterms = []
    each_minterm do |vars|
        minterms << vars2int(vars)
    end

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

    # Create the implicant table
    implicants = Hash.new {|h,k| h[k] = SameXImplicants.new }

    # Convert the minterms to implicants without x
    minterms.each do |term|
        implicant = Implicant.new(term)
        implicants[implicant.mask] << implicant
    end

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

    # Group the adjacent implicants to obtain the generators
    size = 0
    generators = []
    # The main iterator
    has_merged = nil
    begin
        has_merged = false
        mergeds = Hash.new { |h,k| h[k] = SameXImplicants.new }
        implicants.each_value do |group|
            group.sort! # Sort by number of one
            size = group.size
            # print "size = #{size}\n"
            group.each_with_index do |implicant0,i0|
                # print "implicant0 = #{implicant0}, i0=#{i0}\n"
                ((i0+1)..(size-1)).each do |i1|
                    # Get the next implicant
                    implicant1 = group[i1]
                    # print "implicant1 = #{implicant1}, i1=#{i1}\n"
                    # No need to look further if the number of 1 of 
                    # implicant1 is more than one larger than 
                    # implicant0's
                    break if implicant1.count > implicant0.count+1
                    # Try to merge
                    mrg = implicant0.merge(implicant1)
                    # print "mrg = #{mrg}\n"
                    # Can merge
                    if mrg then
                        mergeds[mrg.mask] << mrg
                        # Indicate than a merged happend
                        has_merged = true
                        # Mark the initial generators as not prime
                        implicant0.prime = implicant1.prime = false
                    end
                end 
                # Is the term prime?
                if implicant0.prime then
                    # print "implicant0 is prime\n"
                    # Yes add it to the generators
                    generators << implicant0
                end
            end
        end
        # print "mergeds=#{mergeds}\n"
        # Prepare the next iteration
        implicants = mergeds
    end while has_merged

    # print "generators with covers:\n"
    # generators.each {|gen| print gen,": ", gen.covers,"\n" }

    # Step 2: remove the redundancies
    
    # Select the generators using Petrick's method
    # For that purpose treat the generators as variables
    variables = generators.map {|gen| VarImp.new(gen) }
    
    # Group the variables by cover
    cover2gen = Hash.new { |h,k| h[k] = [] }
    variables.each do |var|
        # print "var=#{var}, implicant=#{var.implicant}, covers=#{var.implicant.covers}\n"
        var.implicant.covers.each { |cov| cover2gen[cov] << var }
    end
    # Convert this hierachical table to a product of sum
    # First the sum terms
    sums = cover2gen.each_value.map do |vars|
        # print "vars=#{vars}\n"
        if vars.size > 1 then
            NodeOr.new(*vars.map {|var| NodeVar.new(var) })
        else
            NodeVar.new(vars[0])
        end
    end
    # print "sums = #{sums.to_s}\n"
    # Then the product
    # expr = NodeAnd.new(*sums).uniq
    if sums.size > 1 then
        expr = NodeAnd.new(*sums).reduce
    else
        expr = sums[0]
    end
    # Convert it to a sum of product
    # print "expr = #{expr.to_s}\n"
    expr = expr.to_sum_product(true)
    # print "Now expr = #{expr.to_s} (#{expr.class})\n"
    # Select the smallest term (if several)
    if (expr.op == :or) then
        smallest = expr.min_by do |term|
            term.op == :and ? term.size : 1
        end
    else
        smallest = expr
    end
    # The corresponding implicants are the selected generators
    if smallest.op == :and then
        selected = smallest.map {|term| term.variable.implicant }
    else
        selected = [ smallest.variable.implicant ]
    end

    # Sort by variable order
    selected.sort_by! { |implicant| implicant.bits }

    # print "Selected prime implicants are: #{selected}\n"
    # Generate the resulting tree
    variables = self.getVariables()
    # First generate the prime implicants trees
    selected.map! do |prime|
        # Generate the litterals 
        litterals = []
        prime.each.with_index do |c,i|
            case c
            when "0" then
                litterals << NodeNot.new(NodeVar.new(variables[i]))
            when "1" then litterals << NodeVar.new(variables[i])
            end
        end
        # Generate the tree
        NodeAnd.new(*litterals)
    end
    # Then generate the final sum tree
    return NodeOr.new(*selected)
end

#size ⇒ Object

Gets number of children.

Default: +0+ (none).



93
94
95
 
# File 'lib/logic_tools/logictree.rb', line 93

def size
    0
end

#to_std_conjunctive ⇒ Object

Generates the equivalent standard conjunctive form.



155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
 
# File 'lib/logic_tools/logictree.rb', line 155

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 ⇒ Object

Generates the equivalent standard disjunctive form.



174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
 
# File 'lib/logic_tools/logictree.rb', line 174

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) ⇒ Object

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

Argument +flattened+ tells if the tree is already flattend



231
232
233
 
# File 'lib/logic_tools/logictree.rb', line 231

def to_sum_product(flattened = false)
    return self.dup
end

#to_sym ⇒ Object

Converts to a symbol.

There is exactly one symbol per possible tree.



242
243
244
 
# File 'lib/logic_tools/logictree.rb', line 242

def to_sym
    to_s.to_sym
end