Выразить все 16 логических функций с оператором less than

15

Существует 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 переходит к самому раннему ответу (при условии, что они не редактировали свой ответ позже с более короткими выражениями, взятыми у кого-то другого).

Технически вам не нужно писать какой-либо реальный код для этого конкурса, но если вы написали какие-либо программы, которые помогут вам сгенерировать выражения, мы настоятельно рекомендуем опубликовать их.

Вы можете использовать этот фрагмент стека, чтобы проверить, соответствуют ли ваши выражения тому, что ожидается:

Кальвин Хобби
источник
8
-1, проблема слишком простая.
Исаак
2
Ну, я думаю, нет смысла публиковать другой ответ, так что вот моя попытка .
Sp3000
7
@isaacg Ты прав. Я бы сказал, что это далеко не самое простое соревнование PPCG, но тот факт, что оптимальные ответы будут практически идентичны, делает соревнование скучным. Тем не менее, я делать думаю , что он служит прекрасно в качестве личного упражнения, особенно для людей , которые не являются экспертами в области логики. Я уверен, что, по крайней мере, половина людей из PPCG здесь ради удовольствия, а не просто чтобы выиграть, иначе никто бы никогда не ответил на вопрос с победой.
Увлечения Кельвина,
Я бы , наверное , сравнить это с противоречивой практике гольф . Это был веселый и интересный вопрос, если немного проще.
Sp3000
2
Если кому-то интересно, вот 3 переменные. Самые длинные выражения соответствуют (0, 0, 0, 1, 0, 1, 1, 0)и (0, 1, 1, 0, 1, 0, 0, 0).
Sp3000

Ответы:

5

100 знаков

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
источник
9

Есть несколько вариантов для некоторых из них, поэтому этот набор из 100 символов не идентичен ранее опубликованным.

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

Более легким доказательством <функционально полной является то, чтоA<(B<1) дает NOR.

Код, который я использовал для нахождения этого, представляет собой серьезное упрощение некоторого логического кода оптимизации, который я использовал в предыдущих задачах, с двумя небольшими изменениями:

  1. Сделайте счет выражения длиной его строки, а не количеством операций.
  2. Сделайте так, чтобы строка избегала лишних скобок, чтобы минимизировать длину.
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;
        }
    }
}
Питер Тейлор
источник
Какое общее количество символов?
user253751
@immibis, 100 символов, так же, как и другие.
Питер Тейлор
«избегайте лишних скобок, чтобы минимизировать длину», нет, вы не избегаете их, чтобы сократить, но соблюдать правила.
Эрик Outgolfer
@EriktheOutgolfer, я не уверен на 100%, что вы имеете в виду, но я думаю, что вы имеете в виду « Это означает, что бесполезные паретезы и выражения формы A<B<1недопустимы». Если это так, проверьте отметки времени: это было редактирование, сделанное после этого ответа.
Питер Тейлор
2

100 знаков

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
источник
1

100 знаков

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

Эй, это не совсем то же самое, что и другие. Я потратил около 10 минут на это, так что стоит публиковать в любом случае, даже если это 2 года.

nog642
источник
0

100 знаков

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
Эрик Outgolfer
источник