Алгоритм получения сднф по таблице истинности

1. Отметить те строки таблицы истинности, в последнем столбце которых стоят 1.

2. Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно 1, то ее отрицание.

3. Все полученные конъюнкции связать в дизъюнкцию.

Алгоритм получения скнф по таблице истинности

1. Отметить те строки таблицы истинности, в последнем столбце которых стоят 0.

2. Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно 0, то в дизъюнкцию включать саму эту переменную, если равно 0, то ее отрицание.

3. Все полученные дизъюнкции связать в конъюнкцию.

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

Пример 5.

Получение СДНФ и СКНФ по таблице истинности
X Y F(X,Y) 0 0 0 0 1 1 1 0 1 1 1 0
СДНФ	СКНФ
1) Отметить звездочкой строки таблицы, в последнем строке которых
имеется 1: X Y F(X,Y) 0 0 0 0 1 1* X & Y 1 0 1* X & Y 1 1 0	имеется 0: X Y F(X,Y) 0 0 0* X  Y 0 1 1 1 0 1 1 1 0* X  Y
2) Выписать для каждой отмеченной строки:
конъюнкцию(&) всех переменных, причем, если значение переменной в данной строкеравно 1, то в конъюнкцию включитьсаму эту переменную,если равно 0, то ееотрицание ().	дизъюнкцию() всех переменных, причем, если значение переменной в данной строкеравно 0, то в дизъюнкцию включать саму переменную, еслиравно 1, то ееотрицание().
3) Все полученные выражения связать операцией:
дизъюнкции (X & Y)  ( X & Y)	конъюнкции (X  Y ) & (X  Y)