Drücken Sie alle 16 booleschen Funktionen mit dem Operator less than aus

15

Es gibt 16 verschiedene Boolesche Funktionen für zwei Binärvariablen, A und 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   

Der less than-Operator <, der normalerweise nicht als logischer Operator wie NOT, AND oder OR aufgefasst wird, ist tatsächlich eine der folgenden Funktionen (F4), wenn er auf boolesche Werte angewendet wird:

A B | A < B
-----------
0 0 | 0
0 1 | 1
1 0 | 0
1 1 | 0

Interessanterweise können wir jede der 15 anderen Funktionen mit Ausdrücken simulieren , die nur die Symbole enthalten ()<AB10. Diese Ausdrücke werden wie in vielen Standard-Programmiersprachen gelesen und ausgewertet, z. B. müssen Klammern übereinstimmen und <Argumente auf beiden Seiten enthalten.

Insbesondere müssen diese Ausdrücke der folgenden Grammatik entsprechen (in Backus-Naur-Form angegeben ):

element ::= A | B | 1 | 0
expression ::= element<element | (expression)<element | element<(expression) | (expression)<(expression)

Dies bedeutet, dass nutzlose Parethesen und Ausdrücke des Formulars A<B<1nicht erlaubt sind.

Der Ausdruck A<Bentspricht also der Funktion F4 und A<B<1muss in (A<B)<1oder geändert werden A<(B<1).

Um zu beweisen, dass alle 15 anderen Funktionen in Ausdrücke umgewandelt werden können, genügt es, eine Menge von Ausdrücken zu bilden, die funktional vollständig sind , da sie dann per Definition zu Ausdrücken für jede Funktion zusammengesetzt werden können.

Eine solche Menge von Ausdrücken ist x<1(wo xist Aoder B), was ist ¬xund (((B<A)<1)<A)<1was ist A → B. Negation ( ¬) und Implication ( ) sind bekanntermaßen funktional vollständig.

Herausforderung

()<AB10Schreiben Sie unter Verwendung der Zeichen 16 Ausdrücke in der oben beschriebenen Form, die jeder der 16 verschiedenen Booleschen Funktionen entsprechen.

Ziel ist es, jeden Ausdruck so kurz wie möglich zu halten. Ihre Punktzahl ist die Summe der Anzahl der Zeichen in jedem Ihrer 16 Ausdrücke. Die niedrigste Punktzahl gewinnt. Tiebreaker geht zur frühesten Antwort über (vorausgesetzt, sie haben ihre Antwort später nicht mit kürzeren Ausdrücken bearbeitet, die von jemand anderem stammen).

Sie müssen technisch gesehen keinen echten Code für diesen Wettbewerb schreiben. Wenn Sie jedoch Programme geschrieben haben, die Sie beim Generieren der Ausdrücke unterstützen, wird dringend empfohlen, diese zu veröffentlichen.

Mit diesem Stack-Snippet können Sie überprüfen, ob Ihre Ausdrücke den Erwartungen entsprechen:

Calvins Hobbys
quelle
8
-1, das Problem ist zu einfach.
Isaacg
2
Nun, ich denke, es macht keinen Sinn, eine weitere Antwort zu posten, also hier ist mein Versuch .
Sp3000,
7
@isaacg Du hast recht. Ich würde sagen, es ist alles andere als der einfachste PPCG-Wettbewerb aller Zeiten, aber die Tatsache, dass die optimalen Antworten nahezu identisch sind, macht ihn als Wettbewerb langweilig. Aber ich tue denke , es ist völlig in Ordnung , als eine persönliche Übung dient, vor allem für Menschen , die keine Experten in der Logik sind. Ich bin mir sicher, dass mindestens die Hälfte der Leute bei PPCG zum Spaß hier sind, nicht nur um zu gewinnen, oder niemand würde jemals eine Frage mit einem nicht gewinnenden Beitrag beantworten.
Calvins Hobbys
Ich würde wahrscheinlich das zu den umstrittenen vergleichen Golf - Übungs . Dies war eine lustige und interessante Frage, wenn auch etwas einfach.
Sp3000,
2
Wenn jemand interessiert ist, hier sind 3 Variablen. Die längsten Ausdrücke entsprechen (0, 0, 0, 1, 0, 1, 1, 0)und (0, 1, 1, 0, 1, 0, 0, 0).
Sp3000,

Antworten:

5

100 Zeichen

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
quelle
9

Für einige von ihnen gibt es einige Optionen, sodass dieses 100-Zeichen-Set nicht mit den zuvor veröffentlichten identisch ist.

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

Ein einfacherer Beweis, der <funktional vollständig ist, wäre, dass A<(B<1)NOR ergibt.

Der Code, den ich verwendet habe, um dies zu finden, ist eine starke Vereinfachung eines Booleschen Optimierungscodes, den ich bei früheren Herausforderungen verwendet habe, mit zwei kleinen Änderungen:

  1. Stellen Sie die Punktzahl eines Ausdrucks auf die Länge der Zeichenfolge und nicht auf die Anzahl der Operationen ein.
  2. Vermeiden Sie unnötige Klammern, um die Länge zu minimieren.
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
quelle
Wie hoch ist die Gesamtzahl der Zeichen?
user253751
@immibis, 100 Zeichen, genau wie die anderen.
Peter Taylor
"Vermeiden Sie unnötige Klammern, um die Länge zu minimieren" nein, Sie vermeiden sie nicht, um sie zu verkürzen, sondern um die Regeln einzuhalten.
Erik der Outgolfer
@EriktheOutgolfer, ich bin mir nicht 100% sicher, was Sie meinen, aber ich vermute, dass Sie sich auf " Dies bedeutet, dass nutzlose Paresen und Ausdrücke des Formulars A<B<1nicht zulässig sind. " Beziehen . Wenn ja, überprüfen Sie die Zeitstempel: das war eine nach dieser Antwort vorgenommene Bearbeitung .
Peter Taylor
2

100 Zeichen

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
quelle
1

100 Zeichen

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

Hey, es ist nicht genau dasselbe wie die anderen. Ich habe ungefähr 10 Minuten damit verbracht, es lohnt sich also trotzdem etwas zu posten, auch wenn dies 2 Jahre alt ist.

nog642
quelle
0

100 Zeichen

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 der Outgolfer
quelle