АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Диз’юнктивна нормальна форма

Читайте также:
  1. C.) При кодировании текстовой информации в кодах ASCII двоичный код каждого символа в памяти ПК занимает
  2. g) процесс управления информацией.
  3. I Курс I I семестр (полная форма обучения)
  4. II. Формальная логика как первая система методов философии.
  5. IV. Информационный блок.
  6. IV. УЧЕБНО-МЕТОДИЧЕСКОЕ, ИНФОРМАЦИОННОЕ И МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
  7. V. Завершите предложения, используя информацию из текста.
  8. V. Завершите предложения, используя информацию из текста.
  9. V. Завершите предложения, используя информацию из текста.
  10. V. Завершите предложения, используя информацию из текста.
  11. V. Операции в пользу мира в информационный век
  12. А не интенсивность, которая выясняется только спустя некоторое время, после получения информации о последствиях.

Означення 2.6. Елементарною кон’юнкцією називається кон’юнкція, що містить будь-яку кількість літералів, де кожна атомарна формула зустрічається лише один раз.

Приклад 2.9 – елементарні кон’юнкції однієї змінної;

– елементарні кон’юнкції двох змінних;

– елементарні кон’юнкції трьох змінних;

– не є елементарними кон’юнкціями.p

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

Приклад 2.10. – приклад диз’юнктивної нормальної форми, де – атомарні формули. , , – кон’юнкції відповідних літералів.p

Означення 2.8. k-диз’юнктивна нормальна форма – це диз’юнктивна нормальна форма, в якій кожна кон’юнкція містить рівно k літералів.

Приклад 2.11. Наступна формула записана в 2-ДНФ:

.▲

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

1. Використати правила усунення імплікації та еквівалентності.

2. Застосувати закон подвійного заперечення та закони де Моргана, щоб перенести знак заперечення безпосередньо до атомарних формул.

3. Використати закони дистрибутивності для кон’юнкції відносно диз’юнкції (p Ù(q Ú r) =(p Ù q) Ú (p Ù r)) для побудови диз’юнктивної нормальної форми.

Приклад 2.12. Звести до диз’юнктивної нормальної форми формулу .

1. Вилучення імплікації:

2. Застосування закону де Моргана:

3. Використання закону подвійного заперечення:

4. Використання закону дистрибутивності:

5. Застосування закону асоціативності:

6. Використання закону ідемпотентності:

Отже, отримана є ДНФ формули . ▲

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

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

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)