Class: TestEspresso

Inherits:
Object
  • Object
show all
Defined in:
lib/logic_tools/test_logic_tools.rb

Overview

Class for testing the implementation of the ESPRESSO algorithm.

Instance Method Summary collapse

Constructor Details

#initialize(seed = 0, deadline = Float::INFINITY, volume = Float::INFINITY) ⇒ TestEspresso

Creates the tester with a seed for random generation, a

+deadline+ for the simplify steps and a +volume+ before splitting
the cover.



19
20
21
22
23
24
25
26
27
 
# File 'lib/logic_tools/test_logic_tools.rb', line 19

def initialize(seed = 0, deadline = Float::INFINITY,
                           volume = Float::INFINITY)
    # Ensures ESPRESSO is used.
    load "logic_tools/logicsimplify_es.rb"

    @seed = seed
    @deadline = deadline
    @volume = volume
end

Instance Method Details

#same_truth_table?(cover0, cover1) ⇒ Boolean

Checks if covers have the same truth table.

Returns:

  • (Boolean) 


81
82
83
84
85
86
87
88
 
# File 'lib/logic_tools/test_logic_tools.rb', line 81

def same_truth_table?(cover0,cover1)
    return false unless cover0.width == cover1.width
    # Check for each entry.
    (2**cover0.width).times do |i|
        return false unless cover0.eval(i) == cover1.eval(i)
    end
    return true
end

#test_espresso(cover) ⇒ Object

Tests espresso on a given cover.



133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
 
# File 'lib/logic_tools/test_logic_tools.rb', line 133

def test_espresso(cover)
    print "ESPRESSO on cover=[#{cover.to_s}]...\n"
    simple = cover.simplify(@deadline,@volume)
    print "result: [#{simple}]\n"
    check0 = (cover + simple.complement).is_tautology?
    # check0 = same_truth_table?(cover,simple)
    # assert_equal(true,check0)
    print "check 0 = #{check0}\n"
    raise "Test failure" unless check0
    check1 = (cover.complement + simple).is_tautology?
    # assert_equal(true,check1)
    print "check 1 = #{check1}\n"
    raise "Test failure" unless check1
    return true
end

#test_espresso_all(test = nil) ⇒ Object

Tests the implementation of the espresso algorithm on each

possible 1-cube cover of 4 variables.

Test only on cover if a +test+ number is given.



153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
 
# File 'lib/logic_tools/test_logic_tools.rb', line 153

def test_espresso_all(test = nil)
    generator = Generator.new("a","b","c","d")
    generator.seed = @seed
    if test then
        test = test.to_i
        print "Test #{test}: "
        return test_espresso(generator.make_1cover(test))
    else
        generator.each_1cover.with_index do |cover,i|
            print "Test #{i}: "
            return false unless test_espresso(cover)
        end
        return true
    end
end

#test_espresso_random(generator) ⇒ Object

Tests ESPRESSO on a cover generated by a random generator.



170
171
172
173
174
175
176
 
# File 'lib/logic_tools/test_logic_tools.rb', line 170

def test_espresso_random(generator)
    # Genrate a random cover.
    cover = generator.random_cover
    # Test it.
    return false unless test_espresso(cover)
    return true
end

#test_espressos_random(number = 1024, dimensions = 4, max = nil) ⇒ Object

Tests ESPRESSO on randomly number cover cases on a dimensions boolean

space, including at most +max+ cubes.



180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
 
# File 'lib/logic_tools/test_logic_tools.rb', line 180

def test_espressos_random(number = 1024, dimensions = 4, max = nil)
    # Create the variables.
    base = "`"
    variables = dimensions.times.map { |i| base.next!.clone }
    # Create the generator.
    generator = Generator.new(*variables)
    generator.seed = @seed
    generator.max = max if max
    # Ensures a rate of "-" large enough to have a high probability of
    # an interesting cover (i.e., which is actually simplifiable).
    # This rate +r+ is obainted as the solution of the followings:
    # max/2 * 2**(r*dimensions) >= 2**dimensions
    # NOTE: max/2 is the average size of the cover.
    generator.rate = Math::log2(2**(dimensions+1)/max.to_f)/dimensions
    # Ensures the rate is not too small though.
    generator.rate = 0.3 unless generator.rate >= 0.3
    print "rate=#{generator.rate}\n"
    # Performs the tests.
    number.times do |i|
        print "Test #{i}: "
        return false unless test_espresso_random(generator)
    end
    return true
end

#test_qm(tree) ⇒ Object

Tests Quine Mac Cluskey on a given tree.



92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
 
# File 'lib/logic_tools/test_logic_tools.rb', line 92

def test_qm(tree)
    print "Quine Mc Cluskey algorithm on expression=[#{tree}]...\n"
    simple = tree.simplify()
    print "result: [#{tree}]\n"
    cover = tree.to_cover
    check0 = (cover + simple.complement).is_tautology?
    # check0 = same_truth_table?(cover,simple)
    # assert_equal(true,check0)
    print "check 0 = #{check0}\n"
    raise "Test failure" unless check0
    check1 = (cover.complement + simple).is_tautology?
    # assert_equal(true,check1)
    print "check 1 = #{check1}\n"
    raise "Test failure" unless check1
    return true
end

#test_qm_all(test = nil) ⇒ Object

Tests the implementation of the espresso algorithm on each

possible 1-cube cover of 4 variables.

Test only on cover if a +test+ number is given.



113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
# File 'lib/logic_tools/test_logic_tools.rb', line 113

def test_qm_all(test = nil)
    generator = Generator.new("a","b","c","d")
    generator.seed = @seed
    if test then
        test = test.to_i
        print "Test #{test}: "
        return test_qm(generator.make_std_conj(test))
    else
        generator.each_std_conj.with_index do |tree,i|
            print "Test #{i}: "
            return false unless test_qm(tree)
        end
        return true
    end
end

#test_tautologies_random(number = 1024, dimensions = 4) ⇒ Object

Tests randomly number tautology cases on a dimensions boolean

space.



64
65
66
67
68
69
70
71
72
73
74
75
76
77
 
# File 'lib/logic_tools/test_logic_tools.rb', line 64

def test_tautologies_random(number = 1024, dimensions = 4)
    # Create the variables.
    base = "`"
    variables = dimensions.times.map { |i| base.next!.clone }
    # Create the generator.
    generator = Generator.new(*variables)
    generator.seed = @seed
    # Performs the tests.
    number.times do |i|
        print "Test #{i}: "
        return false unless test_tautology_random(generator)
    end
    return true
end

#test_tautology_random(generator) ⇒ Object

Tests the tautology check on covers generated by a random generator.

NOTE: ends when a tautology is actually found.



41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
# File 'lib/logic_tools/test_logic_tools.rb', line 41

def test_tautology_random(generator)
    # Create the cover.
    cover = Cover.new(*generator.each_variable)
    # Tautology results.
    taut0, taut1 = false, false
    # Add random cubes to the cover until a tautology is met while.
    begin
        # Add a random cube.
        cover << generator.random_cube
        print "Tautology check on cover=[#{cover.to_s}]...\n"
        # Check if the cover is a tautology using the standard approach.
        taut0 = cover.is_tautology?
        print "Through is_tautology?: #{taut0}; "
        # Check it again with a truth table.
        taut1 = truth_tautology(cover)
        print "through truth table: #{taut1}\n"
        raise "Test failure" unless taut0 == taut1
    end while (!taut0)
    return true
end

#truth_tautology(cover) ⇒ Object

Checks if a cover is a tautology by generating its truth table.



30
31
32
33
34
35
36
 
# File 'lib/logic_tools/test_logic_tools.rb', line 30

def truth_tautology(cover)
    ## Generate each possible input and test it on the cover.
    (2**(cover.width)).times do |i|
        return false unless cover.eval(i)
    end
    return true
end