Канонічні форми перемикальних функцій

Означення 1. Формула називається тотожньо істинною, якщо вона при всіх значеннях змінних, що входять до її складу, набуває значення 1. Наприклад, x  = 1.

Означення 2. Формула називається тотожньо хибною, якщо вона при всіх значеннях змінних, що входять до її складу, набуває значення 0. Наприклад, x = 0.

Означення 3. Формула називається здійсненою (нейтральною), якщо вона не є тотожною 0 або 1.

Можна поставити таке завдання: задати єдиний спосіб (алгоритм), який дає змогу для кожної формули з’ясувати, чи є вона здійсненою, тобто чи не є вона тотожною 0 або 1.

Таке завдання має назву проблеми розв’язності.

Досконалі диз’юнктивні нормальні форми перемикальних функцій

Означення 1. Логічний добуток будь-якої кількості різних незалежних змінних, що входять із запереченням або без нього, називається елементарною кон’юнкцією (x₁x₂ ).

Означення 2. Якщо функцію задано формулою у вигляді диз’юнкції елементарних кон’юнкцій, то кажуть, що її задано диз’юнктивною нормальною формою (ДНФ).

Наприклад, f(x) = x₁x₂x₃ + x₂x₃ + x₂.

Означення 3. Конституентою одиниці (мінтермом) називають перемикальну функцію n аргументів, яка набуває значення 1 тільки на одному їх кортежі.

Означення 4. Досконалою диз’юнктивною нормальною формою (ДДНФ) формули A(x₁, x₂, …, x_n), що містить n різних змінних називається ДНФ, яка має такі властивості:

• в ній немає однакових доданків;

• жоден із доданків не містить двох однакових співмножників;

• жоден із доданків не містить змінну разом з її запереченням;

• в кожному окремому доданку є як співмножник або змінна x_i, або її заперечення для будь-якого i = 1, 2, …, n.

Досконалі кон’юнктивні нормальні форми перемикальних функцій

Означення 1. Логічна сума будь-якої кількості різних незалежних змінних, що входять із запереченням або без нього, називається елементарною диз’юнкцією.

Означення 2. Якщо будь-яку функцію задано формулою у вигляді кон’юнкції елементарних диз’юнкцій, то кажуть, що функцію задано її кон’юктивною нормальною формою (КНФ).

Означення 3. Конституентою нуля (макстермом) називають перемикальну функцію n аргументів, яка набуває значення 0 тільки в одному наборі. Існує 2ⁿ конституент нуля.

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

Означення 5. Досконалою кон’юктивною нормальною формою (ДКНФ) перемикальної функції називається її КНФ, що задовольняє такі умови:

• в ній немає двох однакових співмножників;

• жоден із співмножників не містить двох однакових доданків;

• жоден із співмножників не містить будь-яку змінну разом з її запереченням;

• кожен співмножник містить як складову x_i або для будь-якого i = 1, 2, …, n.

Властивості досконалих форм

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

• у ДДНФ (ДКНФ) не має двох однакових мінтермів (макстермів);

• у ДДНФ (ДКНФ) жоден із мінтермів (макстермів) не містить двох однакових співмножників (змінних);

• у ДДНФ (ДКНФ) жоден із мінтермів (макстермів) не містить разом із змінною її заперечення.

Твердження. Будь-яка функція алгебри логіки, крім абсолютно хибної і абсолютно істинної функції, може бути подана у ДКНФ і ДДНФ.