Головна

 Www.msta.ru |  Визначення та позначення. |  Операції над множинами. |  Потужність безлічі. |  Пряме твір множин. |  Тест 1. |  Бінарні відносини. |  Функції. |  Алгебраїчні структури і морфізм. |  тест II |

Диз'юнктивна і Кон'юнктивна нормальні форми

  1.  B) Аналітичні форми герундія і причастя
  2.  Choose the correct answerНачалоформи
  3.  I. Залежно від форми власності
  4.  I. Відмінності форми
  5.  II. По суб'єктивний бік в залежності від форми вини виділяють: необережних і навмисних злочинців.
  6.  Ing-форми
  7.  Ing-форми і ed-форми

нехай  , Будемо вважати, що  , якщо и  , якщо .

Кон'юнкція і диз'юнкція є асоціативними операціями: и  ). Тому визначені вирази и  , Які називаються елементарної кон'юнкція і елементарної диз'юнкція довжини n відповідно. Зауважимо, що кон'юнкція приймає значення 1 на єдиному наборі значень змінних  , А на всіх інших наборах значень змінних звертається до 0. Диз'юнкція ж, навпаки, приймає значення 0 на єдиному наборі значень змінних, а на всіх інших наборах значень змінних дорівнює 1.

Це дозволяє кожну булеву функцію представити у вигляді

або у вигляді

&

які називаються відповідно досконалої диз'юнктивній нормальною формою (д.н.ф.) і досконалий кон'юнктівной нормальної форми (к.н.ф.) для функції ?.

У скоєних д.н.ф. і к.н.ф. всі елементарні кон'юнкції (Е.К.) і елементарні диз'юнкції (Е.Д.) мають однакову довжину, рівну числу змінних n. Може, однак, виявитися, що у деяких Е.К. в досконалої д.н.ф. може бути опущена частина букв, а інші Е.К. можуть бути одночасно взагалі видалені, причому отримана д.н.ф. (Вже не скорочена) представлятиме ту ж саму функцію. Тим самим іноді вдається істотно спростити уявлення булевої функції у вигляді д.н.ф .. Аналогічно може бути спрощена і к.н.ф .. В процесі спрощення можуть використовуватися властивості 1) - 9) булевої алгебри.

 



 Визначення та основні властивості. |  Спрощення д.н.ф.
© um.co.ua - учбові матеріали та реферати