Class: LogicTools::Node

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

Overview

– Enhances the Node class with expression simplifying. ++

Direct Known Subclasses

NodeNary, NodeUnary, NodeValue, NodeVar

Instance Method Summary collapse

Instance Method Details

#cover?(tree) ⇒ Boolean

Tells if self covers tree

Returns:

  • (Boolean) 


288
289
290
291
 
# File 'lib/logic_tools/logictree.rb', line 288

def cover?(tree)
    # By default: equality comparison.
    return self == tree
end

#distribute(dop, node) ⇒ Object

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

according to the +dop+ operator.



234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
 
# File 'lib/logic_tools/logictree.rb', line 234

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

Iterate over the children.



163
164
165
166
167
 
# File 'lib/logic_tools/logictree.rb', line 163

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



112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
 
# File 'lib/logic_tools/logictree.rb', line 112

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

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

Iteration parameters:
* +vars+: the variables of the expression



149
150
151
152
153
154
155
156
157
158
159
160
 
# File 'lib/logic_tools/logictree.rb', line 149

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

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

Iteration parameters:
* +vars+: the variables of the expression



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

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

#eql?(val) ⇒ Boolean

:nodoc:

Returns:

  • (Boolean) 


277
278
279
 
# File 'lib/logic_tools/logictree.rb', line 277

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.



211
212
213
 
# File 'lib/logic_tools/logictree.rb', line 211

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.



219
220
221
222
 
# File 'lib/logic_tools/logictree.rb', line 219

def flatten_deep
    # print "flatten_deep #1 with self=#{self}\n"
    return self.dup
end

#get_variables ⇒ Object

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



80
81
82
83
 
# File 'lib/logic_tools/logictree.rb', line 80

def get_variables()
    result = self.get_variablesRecurse
    return result.flatten.uniq.sort
end

#hash ⇒ Object

:nodoc:



274
275
276
 
# File 'lib/logic_tools/logictree.rb', line 274

def hash # :nodoc:
    to_sym.hash
end

#include?(tree) ⇒ Boolean

Tells if self includes tree.

Returns:

  • (Boolean) 


282
283
284
285
 
# File 'lib/logic_tools/logictree.rb', line 282

def include?(tree)
    # By default: equality comparison.
    return self == tree
end

#inspect ⇒ Object

:nodoc:



263
264
265
 
# File 'lib/logic_tools/logictree.rb', line 263

def inspect # :nodoc:
    to_s
end

#is_parent? ⇒ Boolean

Tells if the node is a parent.

Default: +false+.

Returns:

  • (Boolean) 


88
89
90
 
# File 'lib/logic_tools/logictree.rb', line 88

def is_parent?
    return false
end

#op ⇒ Object

Gets the operator.

Default: +nil+ (none).



95
96
97
 
# File 'lib/logic_tools/logictree.rb', line 95

def op
    nil
end

#reduce ⇒ Object

Reduce the node by removing redundancy from it.

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



227
228
229
230
 
# File 'lib/logic_tools/logictree.rb', line 227

def reduce
    # By default, no possible reduction.
    self.clone
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.



729
730
731
732
733
734
735
736
737
 
# 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 ⇒ Object

Gets number of children.

Default: +0+ (none).



102
103
104
 
# File 'lib/logic_tools/logictree.rb', line 102

def size
    0
end

#to_cover(*variables) ⇒ Object

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

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



19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
# 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

    # Fill it with the cubes corresponding to each product
    tree.each do |product|
        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
                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 ⇒ Object

Generates the equivalent standard conjunctive form.



170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
 
# File 'lib/logic_tools/logictree.rb', line 170

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.



189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
 
# File 'lib/logic_tools/logictree.rb', line 189

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



259
260
261
 
# File 'lib/logic_tools/logictree.rb', line 259

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.



270
271
272
 
# File 'lib/logic_tools/logictree.rb', line 270

def to_sym
    to_s.to_sym
end