| X | Y | Z | F |
Если функция задана таблицей истинности, а нужно получить эту функцию в виде выражения (формулы), можно использовать следующий алгоритм:
1) записать произведение, включающее каждую переменную в прямом или инверсном виде 1 раз, такое что оно равно 1 на одном из наборов значений переменных, на котором функция F принимает значение 1, например для набора (0, 1, 1) таким произведением будет . Если значение переменной в текущем наборе равно 0, то эту переменную записывают с отрицанием. Такое произведение называется минтермом.
2) Записать сумму всех минтермов, соответствующих единицам исходной функции.
В результате мы получим функцию, принимающую значение 1 на тех же наборах аргументов, что и функция, заданная таблицей истинности:
(данная функция равна 1 в 4 строчках, поэтому произведений – 4).
Такая запись функции называется совершенной дизъюнктивной нормальной формой (СДНФ). СДНФ – это запись функции в виде дизъюнкции конъюнкций (суммы произведений), причем в каждое произведение входят все переменные.
Запись функции по нулям
Для каждой строки таблицы истинности, в которой функция равна 0, записать сумму всех переменыых, причем если значение переменной равно 1 в данной строке таблицы, то переменную записывают с отрицанием. Полученные суммы нужно перемножить.
Для той же таблицы истинности:
Такая запись функции называется совершенной конъюнктивной нормальной формой (СКНФ).
Логические функции от двух аргументов
Существуют 16 логических функций от двух аргументов, каждая из которых задается собственной таблицей истинности.
| Константа нуль | Конъюнк-ция | Запрет по B | Перемен-ная A | Запрет по A | Перемен-ная B | Исключающее ИЛИ | Дизъюнк-ция | ||
| A | B | A B | А | B | |||||
| Стрелка Пирса | Эквивалентность | Инверсия B | Импликация от B к A | Инверсия A | Импликация от A к B | Штрих Шеффера | Константа единица | ||
| A | B | ||||||||
Рассмотрим некоторые функции более подробно.
Стрелка Пирса
| A | B | |
Запись этой функции в виде СДНФ дает
Графическое обозначение логической схемы, осуществляющей эту операцию:
(Единица в прямоугольнике означает логическое сложение, а кружочек на правой границе прямоугольника – инвертирование сигнала)
Функция следования (импликация от A к B)
| A | B | |
Импликация соответствует высказыванию “если … , то…” Эта функция принимает значение ложь, только когда из истины следует ложь.
Через основные операции эта функция может быть записана как (см. правило записи функции по нулям).
Графическое обозначение логической схемы, осуществляющей эту операцию:
(Кружочек на левой границе означает инверсию сигнала)
Функция эквивалентность
| A | B | |
Эквивалентность соответствует высказыванию “… тогда и только тогда, когда”. Эта функция принимает значение истина, когда оба высказывания одновременно либо ложны, либо истинны.
Через основные операции эта функция может быть записана как
Графическое обозначение логической схемы, осуществляющей эту операцию:
Штрих Шеффера
| A | B | |
Запись этой функции по нулям дает .
Графическое обозначение логической схемы, осуществляющей эту операцию:
