15
3
There are 16 distinct boolean functions for two binary variables, A and B:
A B | F0 | F1 | F2 | F3 | F4 | F5 | F6 | F7 | F8 | F9 | F10 | F11 | F12 | F13 | F14 | F15
-----------------------------------------------------------------------------------------
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
The less than operator <
, which normally isn't thought of as a logic operator like NOT, AND, or OR, is in fact one of these functions (F4) when applied to boolean values:
A B | A < B
-----------
0 0 | 0
0 1 | 1
1 0 | 0
1 1 | 0
Interestingly, we can simulate any of the 15 other functions using expressions that only contain the symbols ()<AB10
. These expressions are read and evaluated just as they would be in many standard programming languages, e.g. parentheses must match and <
must have arguments on either side of it.
Specifically, these expressions must comply with the following grammar (given in Backus-Naur form):
element ::= A | B | 1 | 0
expression ::= element<element | (expression)<element | element<(expression) | (expression)<(expression)
This means that useless paretheses and expressions of the form A<B<1
are not allowed.
So the expression A<B
matches the function F4, and A<B<1
must be changed to (A<B)<1
or A<(B<1)
.
To prove that all of the 15 other functions can be turned into expressions, it suffices to form a set of expressions that is functionally complete, because then, by definition, they can be composed into expressions for any function.
One such set of expressions is x<1
(where x
is A
or B
), which is ¬x
, and (((B<A)<1)<A)<1
, which is A → B
. Negation (¬
) and implication (→
) are known to be functionally complete.
Challenge
Using the characters ()<AB10
, write 16 expressions in the form described above that are equivalent to each of the 16 distinct boolean functions.
The goal is to make each of the expressions as short as possible. Your score is the sum of the number of characters in each of your 16 expressions. The lowest score wins. Tiebreaker goes to the earliest answer (provided they didn't edit their answer later with shorter expressions taken from someone else).
You do not technically need to write any real code for this contest but if you did write any programs to help you generate the expressions, you are highly encouraged to post them.
You can use this Stack Snippet to check if your expressions do what's expected:
function check() {
var input = document.getElementById('input').value.split('\n'), output = ''
if (input.length == 1 && input[0].length == 0)
input = []
for (var i = 0; i < 16; i++) {
var expected = [(i & 8) >> 3, (i & 4) >> 2, (i & 2) >> 1, i & 1]
output += 'F' + i.toString() + '\nA B | expected | actual\n-----------------------\n'
for (var j = 0; j < 4; j++) {
var A = (j & 2) >> 1, B = j & 1, actual = '?'
if (i < input.length) {
try {
actual = eval(input[i]) ? 1 : 0
} catch (e) {}
}
output += A.toString() + ' ' + B.toString() +
' | ' + expected[j] + ' | ' + actual.toString() + ' '
if (expected[j] != actual)
output += ' <- MISMATCH'
if (j != 3)
output += '\n'
}
if (i != 15)
output += '\n\n'
}
document.getElementById('output').value = output
}
<textarea id='input' rows='16' cols='64' placeholder='put all 16 expressions here in order, one per line...'></textarea><br><br>
<button type='button' onclick='check()'>Check</button><br><br>
<textarea id='output' rows='16' cols='64' placeholder='results...'></textarea><br>
"?" means there was some sort of error
8-1, problem is too simple. – isaacg – 2015-03-26T08:28:48.413
2
Well I guess there's no point posting another answer, so here's my attempt.
– Sp3000 – 2015-03-26T08:31:53.3037@isaacg You're right. I'd say it's far from the simplest PPCG contest ever but the fact that optimal answers will be almost exactly identical makes it kind of boring as a competition. However, I do think it serves perfectly fine as a personal exercise, especially for people who aren't experts in logic. I'm sure at least half the people on PPCG are here for fun, not just to win, or else no one would ever answer a question with a non-winning submission. – Calvin's Hobbies – 2015-03-26T08:48:38.540
I'd probably compare this to the controversial golf practice. This was a fun and interesting question, if a bit easy.
– Sp3000 – 2015-03-26T09:08:06.8932
If anyone's interested, here's 3 variables. The longest expressions correspond to
– Sp3000 – 2015-03-26T09:22:49.913(0, 0, 0, 1, 0, 1, 1, 0)
and(0, 1, 1, 0, 1, 0, 0, 0)
.I'm not even sure this is metagolf, since this doesn't really ask for a program that golfs the results. It's more like a normal code golf which is so specific that someone could use a program to do the work for them (which in theory is possible for any code golf, although very hard in practice). – Martin Ender – 2015-03-26T10:18:49.667
@MartinBüttner Yeah, I wasn't quite sure what to tag it. – Calvin's Hobbies – 2015-03-26T10:22:25.953
Forgive my pedantry, but I fixed the BNF into actual BNF, including the restriction that
A<B<0
is not allowed. This should make it easier for people to make language generators as well. – orlp – 2015-03-26T13:16:52.450Just an observation: As is evident from the posted entries, the material implication "If A then B" may be achieved by a shorter phrase than the one you gave. Actually by a sub-phrase of the one you gave--therefore I'm guessing that you knew this form but deliberately obfuscated/lengthened it for the purpose of the challenge. – mathmandan – 2015-03-26T19:41:09.253