Основний теоретичний матеріал

Елементарною кон’юнкцією називається вираз , де всі змінні , які ввійшли у склад кон’юнкції, різні, (m – ранг ЕК).

Диз’юнктивною нормальною формою (ДНФ) даної бф називається її представлення у вигляді диз’юнкції деяких елементарних кон’юнкцій.

Для будь-якої булевої функції справедлива формула диз’юнктивного розкладу по сукупності змінних:

.

Досконалою диз’юнктивною нормальною формою (ДДНФ) даної бф називається її представлення у вигляді:

.

Елементарною диз’юнкцією називається вираз:

,

де всі змінні, які ввійшли у склад диз’юнкції, різні, .

Кон’юнктивною нормальною формою (КНФ) даної бф називається її представлення у вигляді кон’юнкції деяких елементарних диз’юнкцій.

Досконалою кон’юктивною нормальною формою (ДДНФ) даної бф називається її представлення у вигляді:

Правила побудови ДДНФ:

1. ДДНФ бф f містить стільки ЕК, скільки одиниць у стовбчику значень таблиці істинності f.

2. кожному наборові значення змінних функції f, на якому вона дорівнює 1, у ДДНФ цієї функції відповідає єдина ЕК всіх змінних така, що змінна входить до неї із запереченням, якщо і без заперечення, якщо .

Правила побудови ДКНФ:

1. ДКНФ бф f – це кон’юнкція всіх елементарних диз’юнкцій вигляду

, де – всі війкові кортежі, на яких функція набуває значення 0.

2. В i-ту з цих диз’юнкцій змінна входить із запереченням якщо у відповідному війковому кортежі і без заперечення, якщо , , .

Поліномом Жегалкіна булевої функції називається її представлення у вигляді суми за модулем два деяких елементарних кон’юнкцій. Поліном Жегалкіна може бути знайдено за допомогою формул

,

в якій необхідно розкрити дужки і спростити вираз за допомогою відношень:

,

, , ,

, .

Поиск по сайту: