Существует 16 различных логических функций для двух двоичных переменных, A и 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
Оператор less than <
, который обычно не рассматривается как логический оператор NOT, AND или OR, на самом деле является одной из этих функций (F4) при применении к логическим значениям:
A B | A < B
-----------
0 0 | 0
0 1 | 1
1 0 | 0
1 1 | 0
Интересно, что мы можем смоделировать любую из 15 других функций, используя выражения, которые содержат только символы ()<AB10
. Эти выражения читаются и оцениваются так же, как и во многих стандартных языках программирования, например, круглые скобки должны совпадать и <
иметь аргументы по обе стороны от них.
В частности, эти выражения должны соответствовать следующей грамматике (приведенной в форме Бэкуса-Наура ):
element ::= A | B | 1 | 0
expression ::= element<element | (expression)<element | element<(expression) | (expression)<(expression)
Это означает, что бесполезные паретезы и выражения формы A<B<1
не допускаются.
Таким образом, выражение A<B
соответствует функции F4 и A<B<1
должно быть изменено на (A<B)<1
или A<(B<1)
.
Чтобы доказать, что все 15 других функций могут быть превращены в выражения, достаточно сформировать набор выражений, который является функционально завершенным , потому что тогда, по определению, они могут быть составлены в выражения для любой функции.
Одним из таких наборов выражений является x<1
(где x
есть A
или B
), который есть ¬x
, и (((B<A)<1)<A)<1
, который есть A → B
. Отрицание (¬
Известно, что ) и импликация ( →
) функционально завершены.
Вызов
Используя символы ()<AB10
, напишите 16 выражений в форме, описанной выше, которые эквивалентны каждой из 16 различных логических функций.
Цель состоит в том, чтобы сделать каждое выражение максимально коротким. Ваша оценка - это сумма количества символов в каждом из 16 выражений. Самый низкий балл побеждает. Tiebreaker переходит к самому раннему ответу (при условии, что они не редактировали свой ответ позже с более короткими выражениями, взятыми у кого-то другого).
Технически вам не нужно писать какой-либо реальный код для этого конкурса, но если вы написали какие-либо программы, которые помогут вам сгенерировать выражения, мы настоятельно рекомендуем опубликовать их.
Вы можете использовать этот фрагмент стека, чтобы проверить, соответствуют ли ваши выражения тому, что ожидается:
источник
(0, 0, 0, 1, 0, 1, 1, 0)
и(0, 1, 1, 0, 1, 0, 0, 0)
.Ответы:
100 знаков
источник
Есть несколько вариантов для некоторых из них, поэтому этот набор из 100 символов не идентичен ранее опубликованным.
Более легким доказательством
<
функционально полной является то, чтоA<(B<1)
дает NOR.Код, который я использовал для нахождения этого, представляет собой серьезное упрощение некоторого логического кода оптимизации, который я использовал в предыдущих задачах, с двумя небольшими изменениями:
источник
A<B<1
недопустимы». Если это так, проверьте отметки времени: это было редактирование, сделанное после этого ответа.100 знаков
источник
100 знаков
Эй, это не совсем то же самое, что и другие. Я потратил около 10 минут на это, так что стоит публиковать в любом случае, даже если это 2 года.
источник
100 знаков
источник