Wyraź wszystkie 16 funkcji logicznych za pomocą operatora mniej niż

15

Istnieje 16 różnych funkcji boolowskich dla dwóch zmiennych binarnych, A i 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   

Operator mniej niż <, który zwykle nie jest uważany za operator logiczny, taki jak NOT, AND lub OR, jest w rzeczywistości jedną z tych funkcji (F4), gdy jest stosowany do wartości boolowskich:

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

Co ciekawe, możemy symulować dowolną z 15 innych funkcji, używając wyrażeń zawierających tylko symbole ()<AB10. Wyrażenia te są odczytywane i oceniane tak jak w wielu standardowych językach programowania, np. Nawiasy muszą się zgadzać i <muszą mieć argumenty po obu stronach.

W szczególności wyrażenia te muszą być zgodne z następującą gramatyką (podaną w formie Backus-Naur ):

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

Oznacza to, że bezużyteczne paretheses i wyrażenia formy A<B<1są niedozwolone.

Tak więc wyrażenie A<Bpasuje do funkcji F4 i A<B<1musi zostać zmienione na (A<B)<1lub A<(B<1).

Aby udowodnić, że wszystkie 15 innych funkcji można przekształcić w wyrażenia, wystarczy utworzyć zestaw wyrażeń, który jest funkcjonalnie kompletny , ponieważ z definicji można je składać w wyrażenia dowolnej funkcji.

Jednym z takich zestawów wyrażeń jest x<1(gdzie xjest Alub B), który jest ¬xi (((B<A)<1)<A)<1który jest A → B. Negacja ( ¬) i implikacja ( ) są znane jako funkcjonalnie kompletne.

Wyzwanie

Używając znaków ()<AB10, napisz 16 wyrażeń w opisanej powyżej formie, które są równoważne każdej z 16 odrębnych funkcji boolowskich.

Celem jest, aby każde z wyrażeń było jak najkrótsze. Twój wynik jest sumą liczby znaków w każdym z 16 wyrażeń. Najniższy wynik wygrywa. Tiebreaker przechodzi do najwcześniejszej odpowiedzi (pod warunkiem, że nie edytował później swojej odpowiedzi z krótszymi wyrażeniami pobranymi od kogoś innego).

Technicznie nie musisz pisać żadnego prawdziwego kodu dla tego konkursu, ale jeśli napisałeś jakieś programy, które pomogą Ci wygenerować wyrażenia, bardzo zachęcamy do opublikowania ich.

Możesz użyć tego fragmentu stosu, aby sprawdzić, czy wyrażenia działają zgodnie z oczekiwaniami:

Hobby Calvina
źródło
8
-1, problem jest zbyt prosty.
isaacg
2
Cóż, myślę, że nie ma sensu publikować innej odpowiedzi, więc oto moja próba .
Sp3000,
7
@isaacg Masz rację. Powiedziałbym, że daleko mu do najprostszych zawodów PPCG, ale fakt, że optymalne odpowiedzi będą prawie dokładnie identyczne, sprawia, że ​​jest to trochę nudne jak zawody. Ja jednak zrobić , że to służy perfekcyjnie jako osobistego wysiłku, zwłaszcza dla ludzi, którzy nie są ekspertami w logice. Jestem pewien, że co najmniej połowa ludzi w PPCG jest tutaj dla zabawy, nie tylko po to, aby wygrać, bo inaczej nikt nigdy nie odpowiedziałby na pytanie, nie wygrywając zgłoszenia.
Calvin's Hobbies
Prawdopodobnie porównałbym to do kontrowersyjnej praktyki golfa . To było zabawne i interesujące pytanie, choć trochę łatwe.
Sp3000,
2
Jeśli ktoś jest zainteresowany, oto 3 zmienne. Najdłuższe wyrażenia odpowiadają (0, 0, 0, 1, 0, 1, 1, 0)i (0, 1, 1, 0, 1, 0, 0, 0).
Sp3000,

Odpowiedzi:

5

100 znaków

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
źródło
9

Istnieje kilka opcji dla niektórych z nich, więc ten zestaw 100 znaków nie jest identyczny z poprzednio opublikowanymi.

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

Łatwiejszym <funkcjonalnie kompletnym dowodem byłby A<(B<1)NOR.

Kod, który znalazłem, jest dużym uproszczeniem logicznego kodu optymalizacyjnego, którego użyłem przy wcześniejszych wyzwaniach, z dwiema drobnymi zmianami:

  1. Spraw, aby wynikiem wyrażenia była długość jego łańcucha, a nie liczba operacji.
  2. Spraw, aby ciąg unikał niepotrzebnych nawiasów, aby zminimalizować długość.
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
źródło
Jaka jest całkowita liczba znaków?
user253751
@immibis, 100 znaków, tak samo jak inne.
Peter Taylor
„unikaj niepotrzebnych nawiasów, aby zminimalizować długość” nie, nie unikaj ich, aby skrócić, ale aby zachować zgodność z zasadami.
Erik the Outgolfer
@EriktheOutgolfer, nie jestem w 100% pewien, co masz na myśli, ale najlepiej zgaduję, że masz na myśli „ Oznacza to, że bezużyteczne paretheses i wyrażenia formularza A<B<1są niedozwolone. ” Jeśli tak, sprawdź znaczniki czasu: to było edycja dokonana po tej odpowiedzi.
Peter Taylor
2

100 znaków

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
źródło
1

100 znaków

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

Hej, to nie jest dokładnie to samo co inne. Spędziłem na tym około 10 minut, więc i tak warto pisać, nawet jeśli ma to 2 lata.

nog642
źródło
0

100 znaków

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 the Outgolfer
źródło