26 . Истинностные характеризации с.Д.Н.Ф. И с.К.Н.Ф. Примеры

Имеется два способа задания истинностных функций — формулой и истинностной таблицей. По формуле легко составляется истинностная таблица.

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

0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	0

Совершенная ДНФэтой функции:

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

0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0

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

Четвёртая строка содержит 0 в указанном поле. Отмечаются значения всех четырёх переменных, это:

В дизъюнкцию записывается переменная без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1. Первый член СКНФ рассматриваемой функции выглядит так:

Остальные члены СКНФ составляются по аналогии

28 Элементарные функции алгебры логики.

Способы задания функций алгебры логики

Укажем следующие 4 способа задания функций алгебры логики:

1) словесное описание;

2) табличное представление;

3) графическое изображение;

4) алгебраическое (в виде формулы).

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

–это словесное описание функции.

графическое изображение; В графическом изображении единичные значения функции отмечаются некоторым способом, например «*», как на рисунке 1, а нулевые значения представляются неотмеченными вершинами единичного «куба» (в данном случае – квадрата).

Та же функция задается формулой:

29

Методы представления функций алгебры логики формулами С.Д.Н.Ф. и С.К.Н.Ф. Логическая функция совершенной дизъюнктивной нормальной формы (СДНФ): - если каждый член дизъюнктивной нормальной функции от n аргументов содержит все эти n аргументы, часть из которых входит в него с инверсией, а часть без нее.

- где f функция 3х переменных. Логическая функция совершенной конъюнктивной нормальной формы (СКНФ): - если каждый член конъюнктивной нормальной функции от n аргументов содержит все эти n аргументы, часть из которых входит в него с инверсией, а часть без нее.

- где f функция 3х переменны

30 Полиномы Жегалкина. Метод неопределенных коэффициентов построения полиномов Жегалкина для функций алгебры логики.

Полином Жегалкина — многочлен над кольцом , то естьполином с коэффициентами вида 0 и 1, где в качестве произведения берётся конъюнкция, а в качестве сложения — исключающее или

Полином Жегалкина представляет собой сумму по модулю два произведений неинвертированных переменных, а также (если необходимо) константы 1. Формально полином Жегалкина можно представить в виде

или в более формализованном виде как:

Примеры полиномов Жегалкина: