Exprese las 16 funciones booleanas con el operador menor que

15

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<Bcoincide con la función F4 y A<B<1debe cambiarse a (A<B)<1o 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 xis Aor 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:

Pasatiempos de Calvin
fuente
8
-1, el problema es demasiado simple.
isaacg
2
Bueno, supongo que no tiene sentido publicar otra respuesta, así que aquí está mi intento .
Sp3000
77
@isaacg Tienes razón. Yo diría que está lejos de ser el concurso de PPCG más simple, pero el hecho de que las respuestas óptimas sean casi exactamente idénticas lo hace aburrido como una competencia. Sin embargo, yo lo creo que sirve perfectamente bien como un ejercicio personal, especialmente para las personas que no son expertos en la lógica. Estoy seguro de que al menos la mitad de las personas en PPCG están aquí por diversión, no solo para ganar, o de lo contrario nadie respondería una pregunta con una presentación no ganadora.
Calvin's Hobbies
Probablemente lo compararía con la práctica de golf controvertida . Esta fue una pregunta divertida e interesante, aunque un poco fácil.
Sp3000
2
Si alguien está interesado, aquí hay 3 variables. Las expresiones más largas corresponden a (0, 0, 0, 1, 0, 1, 1, 0)y (0, 1, 1, 0, 1, 0, 0, 0).
Sp3000

Respuestas:

5

100 caracteres

0
(A<1)<B
B<A
A
A<B
B
((B<A)<((A<B)<1))<1
(A<(B<1))<1
A<(B<1)
(B<A)<((A<B)<1)
B<1
(A<B)<1
A<1
(B<A)<1
((A<1)<B)<1
1
jimmy23013
fuente
9

Hay algunas opciones para algunos de estos, por lo que este conjunto de 100 caracteres no es idéntico a los publicados anteriormente.

0
(B<A)<A
B<A
A
A<B
B
((A<B)<((B<A)<1))<1
(A<(B<1))<1
A<(B<1)
(A<B)<((B<A)<1)
B<1
(A<B)<1
A<1
(B<A)<1
((B<A)<A)<1
1

Una prueba más fácil que <esté funcionalmente completa sería la que A<(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:

  1. Haga que el puntaje de una expresión sea la longitud de su cadena en lugar del número de operaciones.
  2. Haga que la cadena evite paréntesis innecesarios, para minimizar la longitud.
import java.util.*;

public class PPCG48193 {

    public static void main(String[] args) {
        Expr[] optimal = new Expr[16];
        int unfound = 16;

        PriorityQueue<Expr> q = new PriorityQueue<Expr>();
        q.offer(new Expr(0, "0"));
        q.offer(new Expr(15, "1"));
        q.offer(new Expr(3, "A"));
        q.offer(new Expr(5, "B"));
        while (unfound > 0) {
            Expr e = q.poll();
            if (optimal[e.val] != null) continue;

            optimal[e.val] = e;
            unfound--;
            for (Expr e2 : optimal) {
                if (e2 != null) {
                    Expr e3 = e.op(e2), e4 = e2.op(e);
                    if (optimal[e3.val] == null) q.offer(e3);
                    if (optimal[e4.val] == null) q.offer(e4);
                }
            }
        }

        for (Expr e : optimal) System.out.println(e.expr);
    }

    private static class Expr implements Comparable<Expr> {
        public final int val;
        public String expr;

        public Expr(int val, String expr) {
            this.val = val;
            this.expr = expr;
        }

        public Expr op(Expr e) {
            String l = expr.contains("<") ? String.format("(%s)", expr) : expr;
            String r = e.expr.contains("<") ? String.format("(%s)", e.expr) : e.expr;
            return new Expr((15 - val) & e.val, String.format("%s<%s", l, r));
        }

        public int compareTo(Expr e) {
            int cmp = expr.length() - e.expr.length();
            if (cmp == 0) cmp = val - e.val;
            return cmp;
        }
    }
}
Peter Taylor
fuente
¿Cuál es el recuento total de personajes?
user253751
@immibis, 100 caracteres, igual que los demás.
Peter Taylor
"evitar paréntesis innecesarios, para minimizar la longitud" no, no los evita para acortar pero para cumplir con las reglas.
Erik the Outgolfer
@EriktheOutgolfer, no estoy 100% seguro de lo que quieres decir, pero mi mejor conjetura es que te estás refiriendo a " Esto significa que no se permiten paréntesis inútiles y expresiones del formularioA<B<1 " . Si es así, revisa las marcas de tiempo: eso fue Una edición realizada después de esta respuesta.
Peter Taylor
2

100 caracteres

0
(A<B)<B
B<A
A
A<B
B
((A<B)<((B<A)<1))<1
(B<(A<1))<1
B<(A<1)
(A<B)<((B<A)<1)
B<1
(A<B)<1
A<1
(B<A)<1
((A<B)<B)<1
1
isaacg
fuente
1

100 caracteres

0
(A<1)<B
B<A
A
A<B
B
((A<B)<((B<A)<1))<1
((B<1)<A)<1
(B<1)<A
(A<B)<((B<A)<1)
B<1
(A<B)<1
A<1
(B<A)<1
((A<1)<B)<1
1

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.

nog642
fuente
0

100 caracteres

0
(A<1)<B
B<A
A
A<B
B
((A<B)<((B<A)<1))<1
(A<(B<1))<1
A<(B<1)
(A<B)<((B<A)<1)
B<1
(A<B)<1
A<1
(B<A)<1
((B<1)<A)<1
1
Erik el Outgolfer
fuente