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<1
są niedozwolone.
Tak więc wyrażenie A<B
pasuje do funkcji F4 i A<B<1
musi zostać zmienione na (A<B)<1
lub 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 x
jest A
lub B
), który jest ¬x
i (((B<A)<1)<A)<1
któ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:
źródło
(0, 0, 0, 1, 0, 1, 1, 0)
i(0, 1, 1, 0, 1, 0, 0, 0)
.Odpowiedzi:
100 znaków
źródło
Istnieje kilka opcji dla niektórych z nich, więc ten zestaw 100 znaków nie jest identyczny z poprzednio opublikowanymi.
Łatwiejszym
<
funkcjonalnie kompletnym dowodem byłbyA<(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:
źródło
A<B<1
są niedozwolone. ” Jeśli tak, sprawdź znaczniki czasu: to było edycja dokonana po tej odpowiedzi.100 znaków
źródło
100 znaków
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.
źródło
100 znaków
źródło