Как превратить таблицу истинности в наименьший блок if / else

20

Как я могу взять таблицу истинности и превратить ее в сжатый блок if?

Например, допустим, у меня есть таблица истинности, где A и B - условия, а x, y и z - возможные действия:

A B | x y z
-------------
0 0 | 0 0 1
0 1 | 0 0 1
1 0 | 0 1 0
1 1 | 1 0 0

Это может превратиться в нижний блок if:

if(A)
{
    if(B)
    {
        do(x)
    }
    else
    {
        do(y)
    }
}
else
{
    do(z)
}

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

Juan
источник
10
Вы имеете в виду преобразование карты Карно в каскад Ифельса?
чокнутый урод
@ratchet: Похоже, я делаю, не так ли? Я не знал о них раньше. Придется немного почитать, но все же и приложение, которое сделает это для меня, было бы неплохо, если не сказать больше, чтобы проверить мои результаты, полученные вручную.
Хуан
1
@jalayn большинство инструментов Karnaugh предназначены для цифровых схем; у них другая эвристика, чем то, о чем идет речь
чокнутый урод
1
@jsoldi: Ответы, которые вы получите, будут зависеть от того, какой сайт вы спрашиваете. Если вы ищете комментарии к определенному фрагменту кода, содержащему некоторые блоки if-then-else, это, безусловно, относится к проверке кода (бета) . Stackoverflow научит вас инструментам и методам. На сайте programmers.SE люди скажут вам, следует ли вам / не следует беспокоиться о переписывании логических операторов для человеческого понимания или для более быстрого выполнения.
Руонг
2
Рекомендации инструмента не по теме, но если вы поменяете вопрос на «Как я могу это сделать?» это будет по теме. Если вам нужна рекомендация по программному обеспечению, перейдите на softwarerecs.stackexchange.com.
Килиан Фот

Ответы:

14

Если вы разрабатываете карту Карно, то и код может выглядеть так же:

//                   a      b
def actionMap = [ false: [false: { z() },
                          true:  { z() }],
                  true:  [false: { x() },
                          true:  { y() }]]

actionMap[a][b]()
Кевин Клайн
источник
Что это за язык? Javascript? Python?
TheLQ
TheLQ, не Python, может быть JavaScript. Но это было бы очень похоже, если бы было написано на python
grizwako
@TheLQ: это Groovy, потому что это то, чем я занимаюсь в наши дни, и, вероятно, также Ruby. Код для Javascript, Python, LUA или Perl будет очень похожим.
Кевин Клайн
2
Это, конечно, имеет эффект оценки b, даже если оценка не нужна. Может быть, это проблема, а может и нет.
Псевдоним
@kevincline, пожалуйста, довольно, пожалуйста, "Lua", а не "LUA". :)
Мачадо
4

В C # .NET вы можете использовать класс Dictionary, чтобы получить результат без IF ELSE, как показано ниже. Приятная вещь в этом:

  1. Это читабельно
  2. Новые ключи будут уникальными (в противном случае вы получите ошибку)
  3. Последовательность не имеет значения
  4. Легко добавлять или удалять записи

Если у вас нет эквивалента класса словаря, вы можете сделать то же самое в двоичной функции поиска / поиска.

//A B | x y z
//-------------
//0 0 | 0 0 1
//0 1 | 0 0 1
//1 0 | 0 1 0
//1 1 | 1 0 0
// Create a Dictionary object and populate it
Dictionary<string, string> _decisionTable = new Dictionary<string, string>() { 
    { "0,0", "0,0,1" }, 
    { "0,1", "0,0,1" }, 
    { "1,0", "0,1,0" }, 
    { "1,1", "1,0,0"} 
};

//usage example: Find the values of X,Y,Z for A=1,B=0
Console.WriteLine(_decisionTable["1,0"]);
Console.Read();
Без шансов
источник
1
Мне нравится это решение, единственное изменение, которое я хотел бы сделать, это использовать словарь <Tuple <bool, bool>, Tuple <bool, bool, bool> вместо словаря <string, string>. Тогда вам не нужно создавать строку для поиска и деконструировать результат впоследствии, так как Tuples сделает это за вас.
Lyise
@ Lyise, спасибо за ваше замечание. Вы абсолютно правы. Я должен учесть вашу хорошую мысль, когда у меня будет шанс.
NoChance
2

То, что вы хотите, это алгоритм Rete . Это автоматически объединяет набор правил и расставляет их приоритеты в виде дерева, как вы описываете.

Существует ряд коммерческих систем «движка правил», которые делают это в очень больших масштабах (миллионы правил), где скорость исполнения важна.

Алекс Фейнман
источник
2

Вот ваша библиотека :) И вам не нужно передавать полную K-таблицу, только те поля, которые вас интересуют :) Предполагается, что это оператор AND в таблице истинности. Если вы хотите использовать больше операторов, вы сможете переписать его. Вы можете иметь любое количество аргументов. Написано pythonи проверено.

def x():
    print "xxxx"

def y():
    print "yyyyy"

def z(): #this is default function
    print "zzzzz"

def A():
    return 3 == 1

def B():
    return 2 == 2


def insert(statements,function):
    rows.append({ "statements":statements, "function":function })

def execute():
    for row in rows:
        print "==============="
        flag = 1

        for index, val in enumerate(row["statements"]):
            #for first pass of lopp, index is 0, for second its 1....
            #if any function returns result different than one in our row, 
            # we wont execute funtion of that row (mark row as not executable)
            if funcs[index]() != val:
                flag = 0

        if flag == 1:
            #we execute function 
            row["function"]()
        else: z() #we call default function


funcs = [A,B]  #so we can access functions by index key
rows = []

insert( (0,0), y)
insert( (0,1), y)
insert( (1,0), x)
insert( (1,1), x)
insert( (0,1), x)

execute()
grizwako
источник
1

Отобразите входные данные в одно значение, а затем включите его:

#define X(a, b) (!!(a) * 2 + !!(b))
switch(X(A, B)) {
case X(0, 0):
    ...
    break;
case X(0, 1):
    ...
    break;
case X(1, 0):
    ...
    break;
case X(1, 1):
    ...
    break;
}
#undef X
Deduplicator
источник
1

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

typedef void(*VoidFunc)(void);

void do(int a, int b)
{
    static VoidFunc myFunctions[4] = {z, z, y, x}; // the lookup table

    VoidFunc theFunction = myFunctions[ a * 2 + b ];
    theFunction();
}

Это хорошее решение, когда количество входов относительно мало, так как количество записей в таблице должно быть 2 ^^ n, где n - количество входов. 7 или 8 входов могут быть управляемыми, 10 или 12 начинает уродливым. Если у вас столько входных данных, попробуйте сначала упростить их другими способами (например, картами Карно).

Калеб
источник
0

Посмотрите на программное обеспечение «Gorgeous Karnaugh» - оно может принимать таблицы истинности в качестве примера, принимать аналитические логические определения, принимать сценарии Lua для построения таблиц истинности. Затем программное обеспечение «Gorgeous Karnaugh» рисует K-карты для взятого ввода, который вы можете минимизировать вручную или с помощью логического минимизатора «Espresso», и производит вывод для C / C ++ и некоторых аппаратных языков. Посетите страницу с краткими сведениями о «Великолепном Карно» - http://purefractalsolutions.com/show.php?a=xgk/gkm

Петруччо
источник
Это очень похоже на то, что мне нужно, но ifпосле ввода таблицы истинности код C / C ++ не может показывать ничего, кроме пустых s.
Хуан
Да, этот инструмент предназначен для минимизации логических функций - после ввода таблицы истинности вам необходимо минимизировать логическую функцию (PoS / SoP - на 0 / на 1). Код C ++ можно найти в окне «Результаты минимизации» после минимизации.
Петручио