Hay 16 funciones booleanas distintas para dos variables binarias, A y 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
El operador menor que <
, que normalmente no se considera un operador lógico como NOT, AND u OR, es de hecho una de estas funciones (F4) cuando se aplica a valores booleanos:
A B | A < B
-----------
0 0 | 0
0 1 | 1
1 0 | 0
1 1 | 0
Curiosamente, podemos simular cualquiera de las otras 15 funciones usando expresiones que solo contienen los símbolos ()<AB10
. Estas expresiones se leen y evalúan tal como lo harían en muchos lenguajes de programación estándar, por ejemplo, los paréntesis deben coincidir y <
deben tener argumentos a cada lado.
Específicamente, estas expresiones deben cumplir con la siguiente gramática (dada en forma Backus-Naur ):
element ::= A | B | 1 | 0
expression ::= element<element | (expression)<element | element<(expression) | (expression)<(expression)
Esto significa que no se permiten paréntesis inútiles y expresiones de la forma A<B<1
.
Por lo tanto, la expresión A<B
coincide con la función F4 y A<B<1
debe cambiarse a (A<B)<1
o A<(B<1)
.
Para demostrar que todas las otras 15 funciones se pueden convertir en expresiones, es suficiente formar un conjunto de expresiones que esté funcionalmente completo , porque entonces, por definición, se pueden componer en expresiones para cualquier función.
Uno de estos conjuntos de expresiones es x<1
(where x
is A
or B
), which is ¬x
, and (((B<A)<1)<A)<1
, which is A → B
. Se sabe que la negación ( ¬
) y la implicación ( →
) son funcionalmente completas.
Desafío
Usando los caracteres ()<AB10
, escriba 16 expresiones en la forma descrita anteriormente que sean equivalentes a cada una de las 16 funciones booleanas distintas.
El objetivo es hacer que cada una de las expresiones sea lo más breve posible. Su puntaje es la suma del número de caracteres en cada una de sus 16 expresiones. El puntaje más bajo gana. Tiebreaker va a la respuesta más temprana (siempre que no hayan editado su respuesta más tarde con expresiones más cortas tomadas de otra persona).
Técnicamente no necesitas escribir ningún código real para este concurso, pero si escribiste algún programa para ayudarte a generar las expresiones, te recomendamos que las publiques.
Puede usar este fragmento de pila para verificar si sus expresiones hacen lo que se espera:
fuente
(0, 0, 0, 1, 0, 1, 1, 0)
y(0, 1, 1, 0, 1, 0, 0, 0)
.Respuestas:
100 caracteres
fuente
Hay algunas opciones para algunos de estos, por lo que este conjunto de 100 caracteres no es idéntico a los publicados anteriormente.
Una prueba más fácil que
<
esté funcionalmente completa sería la queA<(B<1)
proporciona NOR.El código que usé para encontrar esto es una gran simplificación de algunos códigos de optimización booleanos que he usado en desafíos anteriores, con dos pequeños cambios:
fuente
A<B<1
" . Si es así, revisa las marcas de tiempo: eso fue Una edición realizada después de esta respuesta.100 caracteres
fuente
100 caracteres
Oye, no es exactamente lo mismo que los otros. Pasé como 10 minutos en esto, así que vale la pena publicar de todos modos, incluso si esto tiene 2 años.
fuente
100 caracteres
fuente