Главная   Онлайн инструменты по математической логике   Мат. логика теория   Как считает компьютер?   Схемы для ЭВМ    

Нормальные формы

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



     Нормальные формы являются синтаксически однозначным способом записи формулы, реализующей заданную функцию.
     Если х - логическая переменная, а σ∈{0,1} то выражение

Xσ = {x если σ=1
¬x если σ=0

     или

Xσ = {1 если x=σ
0 если x≠σ

называется литерой. Литеры x и ¬x называются контрарными. Конъюнктом называется конъюнкция литер. Дизъюнктом называется дизъюнкция литер. Например, формулы XY¬Z и XYX¬X являются конъюнктами, формулы XvYv¬Z и XvYv¬X - дизъюнктами, а формула ¬Z является одновременно и конъюнктом и дизъюнктом.
     Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция конечного числа конъюнктов.
     Конъюнктивной нормальной формой (КНФ) называется конъюнкция конечного числа дизъюнктов.
     Более просто: ДНФ - это сумма произведений, а КНФ - это произведение логических сумм.
     Примеры.
     1. XYvYZvX - это ДНФ (сумма произведений).
     2. (Xv¬Yv¬Z)(XvY)Z - это КНФ (произведение сумм).
     3. ¬XvYvZv¬W - это ДНФ и КНФ (одновременно).
     4. ¬XY¬ZW - это ДНФ и КНФ (одновременно).
     5. (XvXvY)(YvZvX)Z - это КНФ.
     6. XY¬Z и XYX¬X - это ДНФ.
     7. X(XvYZ)¬(X¬YZ) - это не нормальная форма (не ДНФ и не КНФ).
     Пусть функция f записана в базисе S1. Данная функция приводится к нормальной форме следующим путем:
     1) используем законы де Моргана, чтобы преобразовать формулу к виду, в котором знаки отрицания относятся только к отдельным переменным;
     2) применяем правило снятия двойного отрицания: ¬(¬X)=X
     3) далее использовать законы дистрибутивности, причем необходимо использовать первый закон дистрибутивности для приведения к ДНФ
     H1&(H2vH3)=(H1&H2)v(H1&H3),
и второй закон дистрибутивности для приведения к КНФ.
     H1v(H2&H3)=(H1vH2)&(H1vH3).
     Любая булева функция может иметь бесконечно много представлений в виде ДНФ и КНФ. Например, используя дополнительно законы инверсий и правила операций с константами можно добиться, чтобы в каждом отдельном конъюнкте или дизъюнкте любая переменная входила бы не более одного раза (либо сама, либо ее отрицание).
     Пример: Для приведения к ДНФ используем 1-ый акон дистрибутивности.
     X¬Y¬(XY¬vZ)=X¬Y(¬Xv¬Yv¬(¬Z))(YvZ)=
         - это КНФ
     =(0vX¬YvX¬YZ)(YvZ)=(X¬YvX¬YZ)(YvZ)=
         - это другая КНФ
     =X¬YYvX¬YZYvX¬YZvX¬YZZ=0v0vX¬YZvX¬YZ=X¬YZvX¬YZ
         - это ДНФ
     Пример: Для приведения к КНФ необходимо использовать второй закон дистрибутивности.
     XvY¬(XYv¬Z)=XvY(¬(XY)¬(¬Z))=XvY(¬Xv¬Y)Z=XvYZ(¬Xv¬Y)=(XvYZ)(Xv¬Xv¬Y)=
     =(XvY)(XvZ)(1v¬Y)=(XvY)(XvZ) - это КНФ

@ 2010 - 2016 tablica-istinnosti.ru Рейтинг@Mail.ru