Совершенная нормальная форма кантора

Совершенная нормальная форма кантора

Соверше́нная дизъюнкти́вная норма́льная фо́рма (СДНФ) — это такая ДНФ, которая удовлетворяет трём условиям:

  • в ней нет одинаковых элементарных конъюнкций
  • в каждой конъюнкции нет одинаковых ( пропозициональных ) букв
  • каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причём в одинаковом порядке.

Любая булева формула, не являющаяся тождественно ложной, может быть приведена к СДНФ, причём единственным образом [1] , то есть для любой выполнимой функции алгебры логики существует своя СДНФ, причём единственная.

Пример нахождения СДНФ [ править | править код ]

Для того, чтобы получить СДНФ функции, требуется составить её таблицу истинности. К примеру, возьмём одну из таблиц истинности:

В ячейках результата f ( x 1 , x 2 , x 3 ) <displaystyle f(x_<1>,x_<2>,x_<3>)> отмечаются лишь те комбинации, которые приводят логическое выражение в состояние единицы. Далее рассматриваются значения переменных, при которых функция равна 1. Если значение переменной равно 0, то она записывается с инверсией. Если значение переменной равно 1, то без инверсии.

Первая строка содержит 1 в указанном поле. Отмечаются значения всех трёх переменных, это:

  • x 1 = 0 <displaystyle x_<1>=0>
  • x 2 = 0 <displaystyle x_<2>=0>
  • x 3 = 0 <displaystyle x_<3>=0>

Нулевые значения — тут все переменные представлены нулями — записываются в конечном выражении инверсией этой переменной. Первый член СДНФ рассматриваемой функции выглядит так: x 1 ¯ ⋅ x 2 ¯ ⋅ x 3 ¯ <displaystyle <overline <1>>>cdot <overline <2>>>cdot <overline <3>>>>

Переменные второго члена:

  • x 1 = 0 <displaystyle x_<1>=0>
  • x 2 = 0 <displaystyle x_<2>=0>
  • x 3 = 1 <displaystyle x_<3>=1>

Таким образом анализируются все ячейки f ( x 1 , x 2 , x 3 ) <displaystyle f(x_<1>,x_<2>,x_<3>)> . Совершенная ДНФ этой функции будет дизъюнкцией всех полученных членов (элементарных конъюнкций).

Совершенная ДНФ этой функции:

f ( x 1 , x 2 , x 3 ) = ( x 1 ¯ ∧ x 2 ¯ ∧ x 3 ¯ ) ∨ ( x 1 ¯ ∧ x 2 ¯ ∧ x 3 ) ∨ ( x 1 ¯ ∧ x 2 ∧ x 3 ¯ ) ∨ ( x 1 ∧ x 2 ∧ x 3 ¯ ) <displaystyle f(x_<1>,x_<2>,x_<3>)=(<overline <1>>>land <overline <2>>>land <overline <3>>>)vee (<overline <1>>>land <overline <2>>>land x_<3>)vee (<overline <1>>>land x_<2>land <overline <3>>>)vee (x_<1>land x_<2>land <overline <3>>>)>

Булевы тождества(названы по имени Дж.Буля – основателя математической логики) — система теоретико-множественных тождеств (законов), которым подчиняются введенные выше операции над множествами.

Система полна в том смысле, что любое соотношение между множествами является следствием булевых тождеств. В систему булевых тождеств входят следующие группы соотношений (равенств, правил выполнения преобразований множеств):

Читайте также:  Голосовой помощник алиса установить на телефон

1) коммутативность (переместительность) объединения и пересечения

2) ассоциативность (сочетательность) объединения и пересечения

3) дистрибутивность (распределительность) пересечения относительно объединения и объединения относительно пересечения

4) идемпотентность объединения и пересечения

5) действия с универсальным U и пустым Æ множествами

А + Æ = А, A + U = U, A∙Æ = Æ, A∙U = A, A + Ā = U, A∙Ā = Æ, Ū = Æ;

6) двойственность (законы де-Моргана)

, ;

7) правило двойного дополнения (отрицания) – закон инволюции

.

Нормальная форма Кантора (НФК)множества. Пусть имеются n произвольных множеств . Рассмотрим различные произведения (пересечения), составленные из исходных множеств и их дополнений . На основании булевых тождеств (входящих в четвертую и пятую группы) можно считать, что каждая буква (с черточкой и без черточки) входит в произведение не более одного раза, так как в противном случае произведение либо упрощается, либо равно Æ.

Потребуем, чтобы каждая буква входила в произведение только один раз. Такие произведения называются конституентами (составляющими). Пользуясь законом коммутативности, будем располагать буквы в порядке возрастания их номеров. Тогдаконституента есть не что иное, как произведение, в котором, во-первых, ровно n сомножителей и, во-вторых, каждый i-й сомножитель – это (i = 1,2,…,n).

Выражение, задающее некоторое множество М в виде объединения различных элементарных пересечений (конституент), называется нормальной формой Кантора множества М.

Замечание. Ясно, что НФК конкретного множества не обязательно содержит все возможные конституенты. Так, например, если множество М получено в результате операций над тремя множествами (т.е. при n = 3 ), то его НФК будет содержать не более 8 возможных конституент:

.

Так как равные множества имеют одинаковую НФК (один и тот же состав конституент), то представление множеств в виде НФК может быть, в частности, использовано для их сравнения (проверки на совпадение).

Алгоритм (правила) приведения множества к НФК (см. пример 1.5). Процесс приведения множества к сумме элементарных пересечений (конституент) в общем случае распадается на следующие этапы:

Читайте также:  Toshiba satellite a200 1m8 драйвера

1) с помощью законов де-Моргана и двойного дополнения добиваемся того, чтобы черточки (причем не более одной) стояли только над буквами;

2) пользуясь законом дистрибутивности пересечения, раскрываем скобки и приводим к выражению вида сумма произведений;

3) одинаковые множители в произведениях заменяем одним (свойство идемпотентности пересечения);

4) произведения, содержащие некоторую букву и ту же букву с черточкой (множество и его дополнение), удаляем (в силу тождеств пятой группы);

5) если некоторое произведение содержит менее n букв, то для

добавления недостающих букв используется одно из следствий булевых тождеств — закон склеивания, в соответствии с которым

6) если в результате преобразований полученная сумма

произведений содержит одинаковые слагаемые, то из них оставляем только одно (свойство идемпотентности объединения).

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Только сон приблежает студента к концу лекции. А чужой храп его отдаляет. 8952 — | 7621 — или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Элементарной конъюнкцией называется конъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.

Примеры элементарных конъюнкций:

Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ) и выглядит следующим образом:

где и — различные элементарные конъюнкций.

Алгоритм приведения к ДНФ может быть описан с привлечением приведенных выше равносильностей:

  • 1. Используя закон двойного отрицания и законы Де Моргана все отрицания «спускаются» до переменных;
  • 2. Раскрываются скобки по распределительному закону;
  • 3. С помощью законов поглощения, противоречия и исключенного третьего удаляются лишние конъюнкции и повторение переменных;
  • 4. С помощью соотношений с участием логическими константами, удаляются оставшиеся константы.

Элементарной дизъюнкцией называется дизъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.

Примеры элементарных дизъюнкций:

Всякая конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ) и выглядит следующим образом:

Читайте также:  Vk messenger mac os

где и — различные элементарные дизъюнкции.

Алгоритм приведения к КНФ может быть описан с помощью тех же соотношений и законов, которые использовались и в алгоритме для ДНФ.

  • 1. Используя закон двойного отрицания и законы Де Моргана все отрицания «спускаются» до переменных;
  • 2. Раскрываются скобки по распределительному закону;
  • 3. С помощью законов поглощения, противоречия и исключенного третьего удаляются лишние дизъюнкции и повторения переменных;
  • 4. С помощью соотношений с участием логическими константами, удаляются оставшиеся константы.

Совершенной дизъюнктивной нормальной формой формулы алгебры высказываний (СДНФ) называется ДНФ, в которой: 1) все слагаемые содержат сомножителем все переменные — без отрицания либо с отрицанием, но не вместе. 2) отсутствуют повторения слагаемых и сомножителей.

Совершенной конъюнктивной нормальной формой формулы алгебры высказываний (СКНФ) называется КНФ, в которой: 1) каждый сомножитель содержит слагаемым каждую переменную, без отрицания либо с отрицанием, но не вместе; 2) отсутствуют повторения сомножителей и слагаемых.

Замечание: Обратим внимание, что одно определение получается из другого заменой друг другом слов «слагаемое» и «сомножитель».

СДНФ некоторой формулы двух переменных:

СКНФ функции трех переменных:

Допустимыми для СДНФ (СКНФ) являются только некоторые полные конъюнкции (дизъюнкции): содержащие — без повторений — все переменные этой функции — с отрицаниями или без них.

Опишем два способа приведения к совершенным нормальным формам.

1-Й СПОСОБ — АНАЛИТИЧЕСКИЙ

Алгоритм приведение к СДНФ:

  • 1. Приводят к ДНФ с помощью равносильных преобразований;
  • 2. Умножают на единицы, представленные в виде дизъюнкций каждой недостающей переменной, с ее отрицанием;
  • 3. Раскрывают скобки — по первому распределительному закону;
  • 4. Исключают повторения слагаемых.

Алгоритм приведение к СКНФ:

  • 1. Формулу приводят к КНФ;
  • 2. Прибавляют нули, представленные в виде конъюнкций каждой недостающей переменной с ее отрицанием;
  • 3. С помощью второго распределительного закона приводят эти сомножители к суммам первой степени, т. е. не содержащим произведений;
  • 4. Исключают повторения сомножителей.
Ссылка на основную публикацию
Смарт часы фикситайм 3 отзывы
Данный товар недоступен для доставки в Ваш регион Мы всегда стремимся к лучшему, чтобы радовать своих покупателей самыми выгодными ценами....
Сколько метров полоса разгона
Добрый день, уважаемый читатель. В этой статье речь пойдет про дополнительные полосы, предназначенные для разгона и торможения транспортных средств. Такие...
Сколько микрофонов в телефоне
Автор : Семён Романов Время чтения: 2 минуты Содержание Типы микрофонов Расположение в устройстве Возможности гарнитуры Как происходит подавление шумов...
Смарт часы эпл для детей
1 min Apple Watch — самые популярные умные часы в мире. Является ли это идеальным выбором для вашего ребенка, зависит...
Adblock detector