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:

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

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

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;
        }
    }
}

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

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.

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