Most elegant implementation of a truth table?

[Nimmi Srivastav]

Kindly suggest the most elegant and efficient implementation of a
multi-column truth table.

Thanks,
Nimmi

[Willem]

Nimmi wrote:
) Kindly suggest the most elegant and efficient implementation of a
) multi-column truth table.

That's quite an odd question, unanswerable as is. Didn't your professor
give you some more context ?


SaSW, Willem

[Vardhan Varma]

Post by Willem
) Kindly suggest the most elegant and efficient implementation of a
) multi-column truth table.
That's quite an odd question, unanswerable as is. Didn't your professor
give you some more context ?
SaSW, Willem

BDD are one way to efficiently store simple truth tables.
Are you going to have edges too ?

[Ben Pfaff]

Post by Nimmi Srivastav
Kindly suggest the most elegant and efficient implementation of a
multi-column truth table.

Perhaps a two-dimensional array?

[Bill Godfrey]

Post by Nimmi Srivastav
Kindly suggest the most elegant and efficient implementation of a
multi-column truth table.

Given a number of boolean inputs, the table lists all possible combinations
of inputs and for each row gives a boolean output.

For example...
A B OUTPUT
F F F
F T T
T F T
T T T

(Are we thinking of the same thing so far?)

The inputs of all truth tables are predictable. If the false becomes 0 and
true becomes 1, the input rows all progress from all zeros to all ones,
counting up in binary. Once we know how many inputs, we can discard them as
they can be trivially recreated.

The only thing left is the outputs. There will always be 2**n outputs.
Store them as a binary value or an array of booleans, whichever is more
convienient in your preferred language.

So now you've stored your output booleans, you need to index that array
given a set of input values. Turn the inputs into a set of bits and then
into a binary value as before, and there's your index.

Bill, twiddling.

[Zahid Faizal]

Post by Nimmi Srivastav
Kindly suggest the most elegant and efficient implementation of a
multi-column truth table.
Thanks,
Nimmi

One way to code truth tables is to use a tabular approach. I will
describe the implementation of "non-boolean" truth tables (if there is
such a thing), since the traditional truth tables are degenerate cases
of the "non-boolean" truth tables

The simplest implementation is to use a multi-dimensional array.
Suppose the truth table has 4 input columns. In this case you could
use a four-dimensional array. Of course this assumes that in each
column the indices are zero-based and contiguous. If that is not the
case, you can still use a multi-dimensional array, but instead of
using the input column entries directly as indices, you can create a
mapping function that maps the input column values to a zero-based
contiguous range and use the mapped values instead. Kindly note that
there is no restriction on the output column of the truth table.

As an alternative, you could use a single dimension array and compute
the correct index to use "manually". Let us assume that the truth
table has four columns: A, B, C and D (arranged most significant to
least significant). Further, let us assume that the range of values
in these columns is as follows:
A 0..a-1 (i.e. number of values equals 'a')
B 0..b-1 (i.e. number of values equals 'b')
C 0..c-1 (i.e. number of values equals 'c')
D 0..d-1 (i.e. number of values equals 'd')

A multi-dimensional array index of the type Table[i][j][k][l] can be
translated into an index into a one-dimensional array using the
following formula:
b*c*d*i + c*d*j + d*k + l

This looks somewhat complicated, but once you get a hang of it, it is
really quite trivial.

Hope that helps
--ZF

[s***@yahoo.com]

Post by Zahid Faizal
One way to code truth tables is to use a tabular approach. I will
describe the implementation of "non-boolean" truth tables (if there is
such a thing), since the traditional truth tables are degenerate cases
of the "non-boolean" truth tables
The simplest implementation is to use a multi-dimensional array.
Suppose the truth table has 4 input columns. In this case you could
use a four-dimensional array. Of course this assumes that in each
column the indices are zero-based and contiguous. If that is not the
case, you can still use a multi-dimensional array, but instead of
using the input column entries directly as indices, you can create a
mapping function that maps the input column values to a zero-based
contiguous range and use the mapped values instead. Kindly note that
there is no restriction on the output column of the truth table.
As an alternative, you could use a single dimension array and compute
the correct index to use "manually". Let us assume that the truth
table has four columns: A, B, C and D (arranged most significant to
least significant). Further, let us assume that the range of values
A 0..a-1 (i.e. number of values equals 'a')
B 0..b-1 (i.e. number of values equals 'b')
C 0..c-1 (i.e. number of values equals 'c')
D 0..d-1 (i.e. number of values equals 'd')
A multi-dimensional array index of the type Table[i][j][k][l] can be
translated into an index into a one-dimensional array using the
b*c*d*i + c*d*j + d*k + l
This looks somewhat complicated, but once you get a hang of it, it is
really quite trivial.
Hope that helps
--ZF

Thank goodness for this posting. I actually had a need for the reverse operation: decomposing a composite index into its constituents. Using the OP example, we can use the following formulas:

i = QUOTIENT(Composite, b*c*d)
j = QUOTIENT(MOD(Composite,b*c*d), c*d)
k = QUOTIENT(MOD(MOD(Composite,b*c*d),c*d), d)
l= MOD(MOD(MOD(Composite,b*c*d), c*d),d)

or alternately

i = Composite / (b*c*d)
j = (Composite %(b*c*d)) /(c*d)
k = ((Composite % (b*c*d)) % (c*d )) / d
l= ((Composite%(b*c*d) % (c*d)) % d

{(Prev_numerator % Prev_denominator) / (Prev_denominator-sans-the-leftmost-index)}

For further illustration, I am showing a mapping between the zero-based composite index and the zero-based individual indices for a hypothetical 4-D array of dimension [2][3][4][5]
0 -->> [0][0][0][0]
1 -->> [0][0][0][1]
2 -->> [0][0][0][2]
3 -->> [0][0][0][3]
4 -->> [0][0][0][4]
5 -->> [0][0][1][0]
6 -->> [0][0][1][1]
7 -->> [0][0][1][2]
8 -->> [0][0][1][3]
9 -->> [0][0][1][4]
10 -->> [0][0][2][0]
11 -->> [0][0][2][1]
12 -->> [0][0][2][2]
13 -->> [0][0][2][3]
14 -->> [0][0][2][4]
15 -->> [0][0][3][0]
16 -->> [0][0][3][1]
17 -->> [0][0][3][2]
18 -->> [0][0][3][3]
19 -->> [0][0][3][4]
20 -->> [0][1][0][0]
21 -->> [0][1][0][1]
22 -->> [0][1][0][2]
23 -->> [0][1][0][3]
24 -->> [0][1][0][4]
25 -->> [0][1][1][0]
26 -->> [0][1][1][1]
27 -->> [0][1][1][2]
28 -->> [0][1][1][3]
29 -->> [0][1][1][4]
30 -->> [0][1][2][0]
31 -->> [0][1][2][1]
32 -->> [0][1][2][2]
33 -->> [0][1][2][3]
34 -->> [0][1][2][4]
35 -->> [0][1][3][0]
36 -->> [0][1][3][1]
37 -->> [0][1][3][2]
38 -->> [0][1][3][3]
39 -->> [0][1][3][4]
40 -->> [0][2][0][0]
41 -->> [0][2][0][1]
42 -->> [0][2][0][2]
43 -->> [0][2][0][3]
44 -->> [0][2][0][4]
45 -->> [0][2][1][0]
46 -->> [0][2][1][1]
47 -->> [0][2][1][2]
48 -->> [0][2][1][3]
49 -->> [0][2][1][4]
50 -->> [0][2][2][0]
51 -->> [0][2][2][1]
52 -->> [0][2][2][2]
53 -->> [0][2][2][3]
54 -->> [0][2][2][4]
55 -->> [0][2][3][0]
56 -->> [0][2][3][1]
57 -->> [0][2][3][2]
58 -->> [0][2][3][3]
59 -->> [0][2][3][4]
60 -->> [1][0][0][0]
61 -->> [1][0][0][1]
62 -->> [1][0][0][2]
63 -->> [1][0][0][3]
64 -->> [1][0][0][4]
65 -->> [1][0][1][0]
66 -->> [1][0][1][1]
67 -->> [1][0][1][2]
68 -->> [1][0][1][3]
69 -->> [1][0][1][4]
70 -->> [1][0][2][0]
71 -->> [1][0][2][1]
72 -->> [1][0][2][2]
73 -->> [1][0][2][3]
74 -->> [1][0][2][4]
75 -->> [1][0][3][0]
76 -->> [1][0][3][1]
77 -->> [1][0][3][2]
78 -->> [1][0][3][3]
79 -->> [1][0][3][4]
80 -->> [1][1][0][0]
81 -->> [1][1][0][1]
82 -->> [1][1][0][2]
83 -->> [1][1][0][3]
84 -->> [1][1][0][4]
85 -->> [1][1][1][0]
86 -->> [1][1][1][1]
87 -->> [1][1][1][2]
88 -->> [1][1][1][3]
89 -->> [1][1][1][4]
90 -->> [1][1][2][0]
91 -->> [1][1][2][1]
92 -->> [1][1][2][2]
93 -->> [1][1][2][3]
94 -->> [1][1][2][4]
95 -->> [1][1][3][0]
96 -->> [1][1][3][1]
97 -->> [1][1][3][2]
98 -->> [1][1][3][3]
99 -->> [1][1][3][4]
100 -->> [1][2][0][0]
101 -->> [1][2][0][1]
102 -->> [1][2][0][2]
103 -->> [1][2][0][3]
104 -->> [1][2][0][4]
105 -->> [1][2][1][0]
106 -->> [1][2][1][1]
107 -->> [1][2][1][2]
108 -->> [1][2][1][3]
109 -->> [1][2][1][4]
110 -->> [1][2][2][0]
111 -->> [1][2][2][1]
112 -->> [1][2][2][2]
113 -->> [1][2][2][3]
114 -->> [1][2][2][4]
115 -->> [1][2][3][0]
116 -->> [1][2][3][1]
117 -->> [1][2][3][2]
118 -->> [1][2][3][3]
119 -->> [1][2][3][4]


--SS