Problem 209

[LarryBlake]

I'm pretty sure I don't understand this problem. A truth table T(a, b, c, d, e, f) has 2^6 = 64 rows. To do T1 AND T2 (where T1 and T2 are 6 bit tables), do I compare T1.row1 to T2.row1, T1.row2 to T2.row2, etc? And get an answer < 64?

If this isn't right, can you give a smaller example? Or point me at a good link?

[harryh]

A six-input binary truth table has indeed 2⁶=64 rows.
However, there are 2⁶⁴ different six-input truth tables.

As an example, consider 2-input binary truth tables:
each one of them has 4 rows, but there are 2⁴=16 such truth-tables, as shown below:

.
x y : A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P
---   -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
0 0 : 0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1
0 1 : 0  0  0  0  1  1  1  1  0  0  0  0  1  1  1  1
1 0 : 0  0  1  1  0  0  1  1  0  0  1  1  0  0  1  1
1 1 : 0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1

Each of the columns A-P above, represents a distinct 2-input binary truth table. A few of them are well known and have specific names e.g. column B is usually called "AND", column H is usually called "OR" etc. But most of them are not particularly useful, so they do not have distinct names.

Now, if you were asked to find how many of the 16 truth tables presented above have a special property e.g.
T(a, b) AND T(b, a XOR b) = 0 for all 2-bit inputs (a,b), what would you do?

One possible approach might be to write down all the possible 2-bit inputs (a, b).
For each input (a,b), write down (b, a XOR b), then list which of the truth-tables presented above satisfy the given condition:

.
(a, b)  (b,a XOR b)  Tables for which T(a, b) AND T(b, a XOR b) = 0
------  -----------  ----------------------------------------------
(0, 0)  (0, 0)       A B C D E F G H
(0, 1)  (1, 1)       A B C D E G I J K L M O
(1, 0)  (0, 1)       A B C D E F I J K L M N
(1, 1)  (1, 0)       A B C E F G I J K M N O

Observe that the required property is true for all 2-bit inputs, only for the truth-tables A, B, C and E: so the answer is 4.

Problem 209 (View Problem) is asking you to find how many of the 2⁶⁴ six-input truth-tables have a certain property for all 6-bit inputs. Caution: The special property I used as an example, is NOT the same as the one used in problem 209.

[LarryBlake]

harryh, thank you for the very detailed reply. Unfortunately, I've read it a few times and still don't get it.

When I look at column B, I see that it mirrors the "AND" interpretation of the inputs. Column A appears to be "0 no matter what", and P appears to be "1 no matter what".

1. Is it necessary that I understand each column, or can I just take the logic "as is"?
2. To make a 3 input table T(x, y, z), do I take the result of T(x, y) and operate on it with z?

Sorry I'm being dense...

[harryh]

1. Is it necessary that I understand each column, or can I just take the logic "as is"?

You just take it "as is"; as I've already mentioned before, most of the possible truth-tables do not a have a clear interpretation: that's why they don't have a name.

2. To make a 3 input table T(x, y, z), do I take the result of T(x, y) and operate on it with z?

No, you just take all three inputs "together". It might or might not be possible to write a 3-input binary function (truth-table) f(x,y,z) in the form g( h(x,y), z), and you have no need to worry about that. A possible 3-input table might be:

x y z : Q
-----   -
0 0 0 : 1 
0 0 1 : 0
0 1 0 : 1
0 1 1 : 1
1 0 0 : 1
1 0 1 : 0
1 1 0 : 0
1 1 1 : 1

There are 2⁸=256 possible 3-input tables: every possible combination of 0's and 1's in column Q is such a truth-table.
You do not need to attach a particular meaning or "understanding" to each one of them.

Think of an n-input binary truth-table as an arbitrary set of rules specifying the position (on / off) for n switches, such that a light bulb is lit. (But you don't need to actually produce a wiring diagram! If implemented with wires and logic circuits, some truth-tables may require that one or more switches are not connected at all!).

Sorry I'm being dense...

No, you are not! It's just something new for you

[LarryBlake]

This is starting to make some sense, but I need to ponder it a bit longer.

I see now that I need to generate 64 bit strings, not 6, but here's an example from 6. Do I have this right?

One of the columns (A through something more than P) has a value of 001001. Let's call that column Q. If Q in the second table evaluates to 010010 and I AND the two strings, I get 000000.

Repeat 2⁶⁴ times and give the count?

[zwuupeape]

You are not going to repeat anything 2⁶⁴ any time soon, but if you were to brute force that... You will need to enumerate boolean arrays of length 64. Every integer x 0 to 63 can be mapped one-to-one with a 6-tuple a,b,c,d,e,f. In the array, x is set to false if the function returns false with this input, and true otherwise. So, for example, 000100 = 2 in binary. If tau(0,0,0,1,0,0) = 1, then array[2] should be false.

[harryh]

I see now that I need to generate 64 bit strings, not 6, but here's an example from 6. Do I have this right?

One of the columns (A through something more than P) has a value of 001001. Let's call that column Q. If Q in the second table evaluates to 010010 and I AND the two strings, I get 000000.

Repeat 2⁶⁴ times and give the count?

Yes, you are right. But as zwuupeape said, that's an attempt to brute-force the solution and it is going to take a very long time.
Nevertheless, it may be a good idea to use that approach for 3-input or 4-input truth-tables (I don't think it would be feasible for 5-input truth tables) in order to get a better grasp of what it is all about, as well as to obtain an estimate of how long it would take to cover 6-input truth-tables by this method. It will also give you a chance to study the simpler cases, thus hopefully leading you to more efficient methods.

If you decide to do so, here are a couple of intermediate results:

Of the 256 binary truth-tables with 3 inputs, I find 28 s.t. &tau;(a, b, c) AND &tau;(b, c, a XOR (b AND c)) = 0 for all 3-bit inputs.

Similarly, there are 65536 binary truth-tables with 4 inputs and I find that 1596 of them satisfy the condition
&tau;(a, b, c, d) AND &tau;(b, c, d, a XOR (b AND c)) = 0 for all 4-bit inputs.

--------------

So, for example, 000100 = 2 in binary. If tau(0,0,0,1,0,0) = 1, then array[2] should be false.

I think there is a typo there. I'd say: "... 000100 = 2² = 4, ... then array[4] should ... "

[LarryBlake]

Okay, I think I have it (the objective, not the answer). Thanks, guys!

[PurpleBlu3s]

A six-input binary truth table has indeed 2⁶=64 rows.
(a, b) (b,a XOR b) Tables for which T(a, b) AND T(b, a XOR b) = 0
------ ----------- ----------------------------------------------
(0, 0) (0, 0) A B C D E F G H
(0, 1) (1, 1) A B C D E G I J K L M O
(1, 0) (0, 1) A B C D E F I J K L M N
(1, 1) (1, 0) A B C E F G I J K M N O[/tt]

I don't understand how you 'combine' (a, b) and (b, a XOR b). How do you AND a pair of inputs - i.e. what is (0,1) AND (1,1)?

[thundre]

I don't understand how you 'combine' (a, b) and (b, a XOR b). How do you AND a pair of inputs - i.e. what is (0,1) AND (1,1)?

If (a,b) = (0,1), then (b, a XOR b) = (1,1).

You AND the outputs of the T function, not the inputs.

T(a, b) AND T(b, a XOR b)

[PurpleBlu3s]

I don't understand how you 'combine' (a, b) and (b, a XOR b). How do you AND a pair of inputs - i.e. what is (0,1) AND (1,1)?

If (a,b) = (0,1), then (b, a XOR b) = (1,1).

You AND the outputs of the T function, not the inputs.

T(a, b) AND T(b, a XOR b)

How do you determine the result of T(a,b)?

[thundre]

How do you determine the result of T(a,b)?

You define T yourself. For 2 variables, there are 2^(2^2) possible truth tables. Harry named them A through P above. Any 2-variable T you invent is going to match one of his.

[PurpleBlu3s]

How do you determine the result of T(a,b)?

You define T yourself. For 2 variables, there are 2^(2^2) possible truth tables. Harry named them A through P above. Any 2-variable T you invent is going to match one of his.

Sorry, I'm just not seeing it.

Say T(a, b) = 0000 (A), and T(b, a XOR b) = 0001 (B), I would conclude that with those conditions, T(a, b) AND T(b, a XOR b) = 0.
Then do this for all 256 combinations of letters A to P. Is that correct?

Thanks for your help.

EDIT: Actually I think I understand it now. You have to pick a possible binary string to map the inputs to, e.g. T(a,b) = 0101, then (0,0) = 0, (0,1) = 1, (1,0) = 0, (1,1) = 1. Then for T(b,a XOR b), (0,0), (1,1), (0,1), (1,0) are AND'ed with the above to give 0101 AND 0110 = 0. So 0101 is an example of a possible binary string we are looking for. Is that right?

[tm507211]

Hi, I'm not sure if I'm totally understanding the problem and would really appreciate any help understanding what exactly the problem is asking. I've looked at several of the other posts about this question and I get that the truth tables t(a,b,c,d,e,f) (I'll refer to this as t1 later) and t(b,c,d,e,f,a XOR (b And c)) (and this as t2) are 64 bit long with 2^(2^6) = 2^64 different combinations.

But what I'm not exactly understanding is what t1 AND t2 = 0 is asking for (I'm fairly certain it's asking me to compare two sets of truth tables, but how exactly?) Does a particular t1 combination correspond to a particular t2 combination? or do I compare it some other way?

Thanks for any help.

[tm507211]

Ok, I think I figured out what I need to do. I tried understanding another one of the posts about this problem. And looked at how exactly a 2 bit input example worked. And I think I figured out that t2 is a particular rotation of the rows from t1. So that a row in t2 with input 101010 has the same rows as the row following the input 101010 in t1. Then we compare the first column of t1 and t2 and so on until we reach the last row. Of course this will be slow if trying to use brute force method since it'd have to happen 2^64 times. (but i've not noticed a particular pattern yet, but I may when I try this method with 3 or 4 bit inputs)

If this isn't correct or if there's a better way of understanding this feel free to correct me.

[hk]

Please don't start a new topic for a problem, when there already exists one.

[tm507211]

Ok, Sorry about that, some forums prefer that you post your question on a different thread, I'll keep that in mind if i have questions on other problems.

[kenbrooker]

Please Note: I have another Post immediately below this one...

As an example, consider 2-input binary truth tables:
each one of them has 4 rows, but there are 2⁴=16 such truth-tables, as shown below:

.
x y : A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P
---   -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
0 0 : 0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1
0 1 : 0  0  0  0  1  1  1  1  0  0  0  0  1  1  1  1
1 0 : 0  0  1  1  0  0  1  1  0  0  1  1  0  0  1  1
1 1 : 0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1

Each of the columns A-P above, represents a distinct 2-input binary truth table. A few of them are well known and have specific names e.g. column B is usually called "AND", column H is usually called "OR" etc. But most of them are not particularly useful, so they do not have distinct names.

"Clarification" from the Philosophy Department and,
I imagine, Electrical Engineering:

A = Contradiction or Always False or "Unsatisfiable"
B = AND or Conjunction or "Minimally not Contradictory" (or Multiplication?)
C = Not Implication (not (not x OR y))=(x AND not y) or "Minimally not Contradictory"
D = x (regardless of y)
E = (not x AND y) or "Minimally not Contradictory"
F = y (regardless of x)
G = XOR or EOR or EXOR or Exclusive Disjunction or Mutual Exclusion or "addition modulo 2" or "either, or"
H = OR or Inclusive Disjunction (x "unless" y?)=(x "if not" y?)=("unless" y, x?) or "Minimally not Tautological"
I = NOR or not OR or "Minimally not Contradictory"
J = XNOR or not XOR or Equivalence or Biconditional or Mutual Implication (x<->y)=(x"if and only if"y)=(y"if and only if"x)
K = Not y (regardless of x)
L = (x OR not y) or "Minimally not Tautological"
M = Not x (regardless of y)
N = Implication or Conditional (x -> y)=("if" x "then" y)=(not x OR y)=(x "only if" y) or "Minimally not Tautolgical"
O = NAND or not AND or Sheffer's Stroke or "alternative denial" or "Minimally not Tautological"
P = Tautology or Always True or "Satisfiable and Valid"

"But most of them are not particularly useful, so they do not have distinct names" is... true because
false implies false is... true, though all of harryh's posts were most helpful to me...

All of the 16 above can be expressed using only not, AND and OR; e.g. N = not x OR y.
All of the 16 above can be expressed via Sheffer's Stroke alone; i.e. via O = NAND.
All of the 16 above can be expressed via I = NOR alone.

[kenbrooker]

As an example, consider 2-input binary truth tables:
each one of them has 4 rows, but there are 2⁴=16 such truth-tables, as shown below:

.
x y : A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P
---   -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
0 0 : 0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1
0 1 : 0  0  0  0  1  1  1  1  0  0  0  0  1  1  1  1
1 0 : 0  0  1  1  0  0  1  1  0  0  1  1  0  0  1  1
1 1 : 0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1

Each of the columns A-P above, represents a distinct 2-input binary truth table. A few of them are well known and have specific names e.g. column B is usually called "AND", column H is usually called "OR" etc. But most of them are not particularly useful, so they do not have distinct names.

Now, if you were asked to find how many of the 16 truth tables presented above have a special property e.g.
T(a, b) AND T(b, a XOR b) = 0 for all 2-bit inputs (a,b), what would you do?

One possible approach might be to write down all the possible 2-bit inputs (a, b).
For each input (a,b), write down (b, a XOR b), then list which of the truth-tables presented above satisfy the given condition:

.
(a, b)  (b,a XOR b)  Tables for which T(a, b) AND T(b, a XOR b) = 0
------  -----------  ----------------------------------------------
(0, 0)  (0, 0)       A B C D E F G H
(0, 1)  (1, 1)       A B C D E G I J K L M O
(1, 0)  (0, 1)       A B C D E F I J K L M N
(1, 1)  (1, 0)       A B C E F G I J K M N O

Observe that the required property is true for all 2-bit inputs, only for the truth-tables A, B, C and E: so the answer is 4.

I'm not sure if harryh is still with us but can anyone please confirm that,
in harryh's 2-bit input example above,
the Truth Table T(b, aXORb)
looks like so?

b aXORb : A B C D E F G H I J K L M N O P
- -----   - - - - - - - - - - - - - - - -  
0   0   : 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
1   1   : 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0   1   : 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1   0   : 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

[traxex]

I'm not sure if harryh is still with us but can anyone please confirm that, in harryh's 2-bit input example,
where I think that last sentence was intended to read ..... the required property is not true.....,

I think the sentence is correct the way it's written. The property in question is "T(a, b) AND T(b, a XOR b) = 0". This is true iff "T(a, b) AND T(b, a XOR b)" is not true, which might be the source of the confusion; in other words, the property already includes a negation.

Can anyone please confirm that the
Truth Table T(b, aXORb)
looks like so?

I get the same truth table. You can use [tt]...[/tt] to display tables like this in monospace font.

gp> T(t,x,y) = (t >> (3-2*x-y)) % 2;
gp> XOR(x,y) = !x != !y;
gp> for(x=0,1,for(y=0,1,print(y" "XOR(x,y)" : "vector(16,i,T(i-1,y,XOR(x,y))))))
0 0 : [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
1 1 : [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
0 1 : [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]
1 0 : [0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1]