# Most elegant implementation of a truth table?

28 views

### Nimmi Srivastav

May 31, 2004, 5:41:37 PM5/31/04
to
Kindly suggest the most elegant and efficient implementation of a
multi-column truth table.

Thanks,
Nimmi

### Willem

May 31, 2004, 6:11:07 PM5/31/04
to
Nimmi wrote:
) Kindly suggest the most elegant and efficient implementation of a
) multi-column truth table.

give you some more context ?

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

### Ben Pfaff

May 31, 2004, 6:17:25 PM5/31/04
to
nimmi_s...@yahoo.com (Nimmi Srivastav) writes:

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

Perhaps a two-dimensional array?
--
"If a person keeps faithfully busy each hour of the working day, he
can count on waking up some morning to find himself one of the
competent ones of his generation."
--William James

### Bill Godfrey

May 31, 2004, 6:42:51 PM5/31/04
to
nimmi_s...@yahoo.com (Nimmi Srivastav) wrote:
> 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

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.

### Vardhan Varma

Jun 1, 2004, 6:33:39 AM6/1/04
to
Willem wrote:

> 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

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

### Zahid Faizal

Jun 1, 2004, 10:30:11 PM6/1/04
to
nimmi_s...@yahoo.com (Nimmi Srivastav) wrote in message news:<8b0c42d.04053...@posting.google.com>...

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

### sande...@yahoo.com

Dec 28, 2015, 9:33:22 PM12/28/15
to
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