Затруднения в алгоритме формирования таблиц истинности

#c_sharp #тестирование

Доброго времени суток, уважаемые коллеги. Дабы упростить себе немного жизнь, решил
написать приложение, которое поможет мне строить матрицу состояний на основании некоторой
логики. Для описания проблемы, с которой я столкнулся, предлагаю ввести некоторые базовые
понятия, которые я буду в дальнейшем использовать.


Сигнал – это базовая единица. Может существовать как самостоятельно, так и в логике
формирования параметра (будет рассмотрен ниже). Тип сигнала может быть следующим –
int, real, bool(на данном этапе написания приложения реализую только этот тип сигнала),
enum и range (Например сигнал может быть типа int, однако валидными для него значения
будут [0..4])
Параметр – это составная единица логики. Имеет внутреннюю логику формирования. Может
формироваться только из сигналов, либо из сигналов и других параметров. Тип параметра
может быть как bool, так и любой числовой. Также параметр может формироваться с помощью
блоков if/then/else. Например 

A = if(B)then(true)
      Else (if (C) then (true) Else (false))
ВАЖНО: в логике формирования одного параметра могут принимать участие несколько одинаковых
сигналов. Например : A = (B|C)&(B|D), где A – это параметр, а B, C, D – это сигналы
типа bool. Также, в логике формирования нескольких параметров могут принимать участие
несколько одинаковых сигналов. Например A = (B|C), E = (B|D), F = (A&B), где A,E,F
– параметры, а B,C,D – сигналы типа bool.


Итак, перейдём к элементарным примерам ожидаемой работы приложения.
1)  Допустим, есть следующая логика формирования параметра A «A = (B&C)», где B и
С – это сигналы типа bool. Данный выход является базовым, для операции “&”. На выходе
приложение должно выдать следующую таблицу(матрицу состояний) : 
 
2)  Допустим, есть следующая логика формирования параметра A «A = (B|C)», где B и
С – это сигналы типа bool. Данный выход является базовым, для операции “|”. На выходе
приложение должно выдать следующую таблицу(матрицу состояний) :

3)  Допустим, есть следующая логика формирования параметра A «A = (B&C)|D», где B,
C и D – это сигналы типа bool. В данном примере синей границей выделена ситуация для
«&», а красной для «|». Стоит отметить, что для ситуации с «|» показано 2 случая, поскольку
случай, когда D = false, а (B&D) = true показан в первой строке примера для оператора
«&». На выходе приложение должно выдать следующую таблицу(матрицу состояний) :


Исходя из вышеописанного, у меня возникло к Вам несколько просьб о помощи с реализацией:  

1)  Подскажите, как можно реализовать приоритет выполнения операций?  

2)  Каким образом мне лучше строить таблицу для логики формирования основного (родительского)
параметра? Есть ли соображения как элегантно реализовать данный алгоритм?  

3)  Как реализовать логику для блоков if/then/else

Собственно, мои начальные наброски приложения Вы можете найти в https://github.com/RusProgrammer/Logica

Буду рад любой помощи с Вашей стороны и заранее Вам благодарен.
    

Ответы

Ответ 1

Предположим, наша задача сводится к построению минимальной не противоречивой таблицы
истинности для некоторого логического выражения. Тогда есть два варианта варианта получить
такую минимальную таблицу:


Строить таблицу в которой указаны наборы входных значений для получения истинного
результата, остальные приводят к ложному (у нас же бинарная логика?)
Строить таблицу в которой указаны наборы входных значений для получения ложного результата,
остальные приводят к истинному.


В обоих случаях мы получаем такую таблицу истинности, по которой можно восстановить
исходную функцию для которой она была получена.

Вспомним немного теории. В бинарной логике существует 16 различных функций от 2х
аргументов. Из них три две and и or дополненные унарным отрицанием not образуют базис,
т.е. такой набор функций, с помощью которого можно составить выражение определяющее
любую из 16 возможных функций.

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

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

Приоритет операций: not, and, or в порядке убывания, по аналогии с математическими
-(унарный), *, +

Для удобства, сложные функции приводят сначала к виду КНФ/ДНФ а затем к виду СКНФ/СДНФ
(гуглим прямо по аббревиатуре, первой же ссылкой будет статья на вики)

Теперь рассмотрим несколько простых функций и минимальные таблицы истинности для
них, для определенности считаем что мы ищем истинные результаты.

And  

x1 x2 | y
1  1  | 1


y = x1 & x2 (КНФ и СКНФ совпадают)

остальные наборы приводят к 0 и приводить их не требуется

Or

x1 x2 | y
1  1  | 1
1  0  | 1
0  1  | 1


y = x1 | x2 (КНФ)= x1&x2 | x1&~x2 | ~x1&x2 (СКНФ)  

XOR

x1 x2 | y
1  0  | 1
0  1  | 1


y = x1&~x2 | ~x1&x2 (КНФ и СКНФ совпадают)

Думаю принцип понятен. Не сложно заметить, что в виде СКНФ, знаки аргументов  в выражении
фактически копируют нужные строки из таблицы истинности.

Теперь рассмотрим выражение из вопроса A = (B&C)|D. вобщем то оно уже представлено
в форме КНФ, осталось расширить его до СКНФ и получить таблицу истинности.

A = B&C | D = B&C&D | B&C&~D | ~B&~C&D

B C D | A
1 1 1 | 1
1 1 0 | 1
0 0 1 | 1 


Ок. Допустим теперь нам нужно добавить зависимость от аргумента E так, что в результате
получается выражение  A = ((B&C)|D)&E. Не сложно заметить, что оно использует в качестве
аргумента предыдущее выражение. Тогда можно воспользоваться предыдущим результатом:

A = (B&C | D)&E = (B&C&D | B&C&~D | ~B&~C&D) & E = B&C&D&E | B&C&~D&E | ~B&~C&D&E 

B C D E | A
1 1 1 1 | 1
1 1 0 1 | 1
0 0 1 1 | 1 


Те же 3 строки, ну уже с учетом дополнительного параметра. В общем то добавление
новых параметров к имеющимся не составляет труда. В случае объединения двух выражений
ровно то же самое. Правила бинарной алгебры логики можно посмотреть тут, в принципе
они не сильно отличаются от правил арифметических преобразований, но некоторые существенные
отличия все таки есть, так что повторить не повредит, даже если уже их знаете.

Теперь как это применить для программирования этой самой логики. С одной стороны,
мы задаем формулу, анализируем ее, преобразуем к нужному виду и формируем таблицу.
Не слишком сложно, но если проект инженерный, я бы пошел от обратного.

Строим таблицу истинности нашего абстрактного вычислителя и кладем ее в массив. Эта
таблица и будет программой для нашего вычислителя. Теперь когда нам потребуется выполнить
операцию, мы проходим по строкам таблицы истинности и объединяем все элементы строки
операцией and, если элемент в строке равен 0, предварительно инвертируем (применяем
отрицание) соответствующий входной сигнал. Затем объединяем результаты строк операцией
or и отдаем результат пользователю. Если входной набор удовлетворяет одной из строк
таблицы, на выходе будет истина, в противном случае ложь. Таким образом мы можем получить
некий абстрактный вычислитель, программируемый с помощью таблицы истинности. Разумеется,
такое решение уступает по производительности варианту с намертво вкомпилированной в
код логикой, однако при этом позволяет менять логику на ходу, за это и платим производительностью.

Для варианта с большим количеством входов и выходов и выходов, можно применить более
хитрый прием. Задать целыми числами массив пар: состояние входов => состояние выходов,
также определить какое состояние выходов должно быть, если ни состояние входов не совпадает
ни с одним из заданных. Дальше просто - из входных сигналов формируем последовательность
бит числа, и, уже в виде числа, сравниваем с заданными состояниями, нашли - возвращаем
заданные ответ, не нашли, возвращаем предусмотренное на этот случай значение. Ответ
можно возвращать как числом, так и массивом bool-значений, разобрать число на биты
не сложно.




  1) Подскажите, как можно реализовать приоритет выполнения операций?


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


  2) Каким образом мне лучше строить таблицу для логики формирования основного (родительского)
параметра? Есть ли соображения как элегантно реализовать данный алгоритм?


выше я написал что есть 2 пути, анализ знаков аргументов в выражении приведенном
к СКНФ/СДНФ виду, либо идти в обратную сторону, и вместо вычисления таблицы истинности,
выводить формулу по заданной таблице. Второе проще и в реализации и для конечного пользователя,
т.к. ему не нужно будет вспоминать нюансы алгебры логики для получения корректного
выражения.


  3) Как реализовать логику для блоков if/then/else


Не понял причем ту это, но по идее можно реализовать как тернарный оператор ? : с
соответствующей обработкой.



Пример построения таблицы по выражению приведу на примере последнего выражения:

var ResultTable = new List>();
var expr = "B&C&D&E|B&C&~D&E|~B&~C&D&E";//выражение в СКНФ-форме
var lines = expr.Split('|');
for(int i = 0; i < lines.Length; i++)
{
    ResultTable.Add(new List);
    var args = line[i].Split('&');
    for(int j = 0; j < args.Length; j++)
    {
        table[i].Add(args[j][0] != '~'); 
    }
}


Получим список строк, содержащих значения аргументов, в зависимости от наличия инверсии
перед аргументом. Значения функции можно не вводить, т.к. известно, что СКНФ строится
для истинных значений функции (СДНФ - для ложных).

Это один из возможных путей реализации и далеко не единственный.



Небольшое замечание, иногда имеет смысл предварительно оценить количество возможных
истинных и ложных состояний и выбрать СКНФ или СДНФ представление в зависимости от
того, каких значений меньше. Это может быть критично для функций с большим числом аргументов,
т.к. суммарное число возможных входных наборов 2^n, где n-число аргументов в выражении,
и если из них всего несколько приводит к истинному результату - выбираем СКНФ, если
несколько ложных, остальные истинные - выбираем СДНФ. Так мы всегда будем получать
таблицы с числом строк меньше либо равным (2^n)/2.



Если что забыл, пишите в комментариях, дополню.