дизъюнкты и нормальные формы

Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы

Элементарной конъюнкцией называется конъюнкция, состоящая только из переменных или их отрицаний. Например: .

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

Если учесть, что нулевые конъюнкции можно опустить, а А*А=А, то приведенная ДНФ сведется к более простому виду: .

Дальнейшее упрощение получается с помощью законов поглощения: . Но полученная формула еще не является минимальной. Можно применить правило, основанное на соображениях симметрии: в рассматриваемой формуле каждая из переменных А, В, встречается два раза, но переменная В встречается один раз с отрицанием, а один раз без отрицания. Значит, симметрия нарушена по переменной В. Тогда тот член дизъюнкции, который эту переменную В не содержит, пропадет, т. е. поглотится АС.

Покажем, что это действительно так:

=

(по закону поглощения ) .

Мы доказали следующее правило поглощения:

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

1. . Этот трехчлен содержит два раза , два раза , но один раз и один раз . Значит,, симметрия нарушена по .

Поэтому, согласно нашему правилу, пропадает член, не содержащий букву (т. е. не содержащий ни , ни ). Значит, надо вычеркнуть .

2. . Этот трехчлен содержит два раза , два раза , но один раз и один раз . Симметрия нарушена по . Значит, вычеркиваем член, не содержащий , т. е. вычеркиваем .

Минимальной мы назовемту ДНФ, которая имеет самую ко­роткую запись.

Существует еще одно правило поглощения, которое тоже основано на соображениях симметрии:

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

Например: . Покажем, что это действительно так:

.

1. . Этот трехчлен содержит два раза , но содержит по одному разу и , и по одному разу и . Значит, симметрия нарушена дважды: по и по . Симметрия не нарушена только по . Поэтому, применяя наше правило, получим дизъюнкцию, одним членов которой будет , адругим — тот член трехчлена, | который_ не содержит . Значит, получим .

2. .

В этом трехчлене симметрия нарушена по и по . Симметрия не нарушена только по . Значит, = .

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

Например:

Среди всех этих ДНФ есть одна, которая отличаете однородностью и «совершенством» своей формы. Mы имеем в виду формулу:

Она так и называется: «совершенная дизъюнктивно-нормальная форма»(СДНФ).

Дадим точное определение:

СДНФ — это такая ДНФ, которая удовлетворяет следующим условиям:

1. Все элементарные конъюнкции различны.

2. Нет нулевых конъюнкций.

3. Ни одна из элементарных конъюнкций не содержит одинаковых членов.

4. Каждая элементарная конъюнкция содержит все переменные.

Чтобы получить СДНФ, надо сначала найти минимальную ДНФ. Тогда будут выполнены условия 1, 2, 3. Посли этого надо преобразовать эту минимальную ДНФ таким образом, чтобы было выполнено условие 4. Это делается следующим образом:

Приведение формул алгебры высказываний к КНФ виду

Элементарной дизъюнкцией называется дизъюнкция, состоящая только из переменных или их отрицаний. Например: .

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

Если воспользоваться равносильностью , то можно заменить через . Кроме того, известно, что, . А если один член дизъюнкции равен 1, то и вся дизъюнкция равна 1. Значит: . Но . Значит, единичный член конъюнкции мож­но просто опустить. Таким образом, первоначальная КНФ| сводится к более простой форме: .

Но эта формула не является еще минимальной. Для КНФ тоже существуют правила поглощения, основанные на соображениях симметрии. Эти правила можно полу­чить по закону двойственности из аналогичных правил, установленных для ДНФ.

Мы знаем, например, что: (симметрия нарушена по переменной . Поглотилось вы­ражение, не содержащее эту переменную). Запишем теперь двойственную равносильность: . В левой части стоит ранее полученная КНФ. Значит, эту КНФ действительно можно свести к более простой форме.

В то же время мы установили новое правило погло­щения:

Если КНФ зависит от трех переменных и представляет собой конъюнкцию трех элементарных дизъюнкций и если симметрия нарушена только по одной из пере­менных, то поглощается та элементарная дизъюнкция, которая эту переменную не содержит.

Аналогичным образом можно получить и второе пра­вило поглощения, основанное на соображениях симмет­рии. Мы уже знаем, что: .

Запишем двойственную равносильность:

Сформулируем соответствующее правило поглощения:

Если КНФ зависит от трех переменных и представляет собой конъюнкцию трех элементарных дизъюнкций и если симметрия нарушена по двум из этих пере­менных, то данная КНФ равносильна конъюнкции, одним из членов которой является переменная, по которой симметрия не нарушена, а вторым членом является тот член первоначальной КНФ, который эту переменную не содержит.

Чтобы найти минимальную КНФ, равносильную данной формуле, надо эту формулу сначала привести к виду ДНФ, затем надо разложить ее на «множители» и применить законы погло­щения.

Рассмотрим конкретный пример:

Можно поступить и по-другому. Новый подход начнет­ся с того момента, когда была получена формула . В этой формуле симметрия нарушена только по одной переменной . Мы применяли соответ­ствующий закон поглощения. А сейчас мы этого делать не будем. Вместо этого мы добавим к нашей формуле нулевую конъюнкцию, составленную из той переменной, по которой была нарушена симметрия, т. е. добавим и произведем группировку:

Источник

Совершенная нормальная форма — дизъюнктивная и конъюнктивная, правило построения

Что такое СДНФ

Нормальная форма логической формулы характеризуется тем, что для нее не свойственны эквивалентность, отрицание формул неэлементарного типа и знаки импликации.

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

СДНФ — совершенная дизъюнктивная нормальная форма формулы. СДНФ — способ написания функции алгебры логики в качестве логического выражения.

Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.

СДНФ формулы — это равнозначная ей формула, которая представляет собой дизъюнкцию элементарных конъюнкций, при которых функция достигает показателя «1».

ДНФ выглядит следующим образом:

СДНФ обладает некоторыми определенными свойствами:

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

При построении таблицы истинности важно помнить, что логические переменные со значением «0» необходимо брать с отрицанием.

Что такое СКНФ

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

Формула должна соответствовать нескольким условиям, чтобы называться СКНФ:

Правила построения по таблице истинности

Дизъюнктивная форма

Если функция равна 1, то для всех наборов переменных, при которых это происходит, записывается произведение. Однако переменные, которые имеют значение 0, берутся с отрицанием.

Конъюнктивная форма

Когда функция равна 0, то для всех наборов переменных, при которых это происходит, записывается сумма. Однако переменные, которые имеют значение 1, берутся с отрицанием.

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

Рассмотрим логическую функцию в виде таблицы истинности.

Алгоритм построения СДНФ по таблице истинности выглядит следующим образом:

Построим совершенную ДНФ:

И как результат получим следующую СДНФ:

Алгоритм построения СКНФ по таблице истинности выглядит следующим образом:

Построим совершенную КНФ:

И как результат получим следующую СКНФ:

Рассмотрев алгоритмы построения СДНФ и СКНФ ясно, что в случае подавляющей части наборов значений переменных функция равна 0, то значительно легче построить и СДНФ для получения ее формулы, а в обратном случае — СКНФ.

Доказательство эквивалентности

Доказать эквивалентность формул можно двумя способами.

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

Поглощение

Склеивание

Обобщенное склеивание

\(xz\;\vee\;y\overline z\;\vee\;xy\;=\;xz\;\vee y\overline z\)

\(xz\;\vee\;y\overline z\;\vee\;xy\;=\;xz\;\vee y\overline z\;\vee\;xyz\;\vee\;xy\overline z\;=\;xz\;\vee\;y\overline z\)

Расщепление

\(x\;\vee\;\overline xy\;=\;xy\;\vee\;x\overline y\;\vee\;\overline xy\;=\;xy\;\vee\;x\overline y\;\vee\;xy\;\vee\;\overline xy\;=\;x\;\cdot\;l\;\;\vee\;y\;\cdot\;l\;=\;x\;\vee\;y\)

Примеры с решением

Задача №1

Через применение закона де Моргана и правила \( x\;\rightarrow\;y\;=\;\overline x\;\vee\;y\) упростим выражения:

\(F\;=\;((((A\;\rightarrow\;B)\;\rightarrow\;\overline A)\;\rightarrow\overline B)\;\rightarrow\;\overline C)\;=\;(((\overline A\;\vee\;B)\;\rightarrow\;\overline A)\;\rightarrow\;\overline B)\;\rightarrow\overline C\;)\;=\)

\(=\;((((\overline A\;\vee\;B)\;\rightarrow\overline A)\;\rightarrow\overline B)\;\rightarrow\;\overline C)\;=\;((\overline<((\overline A\;\vee\;B)>\;\vee\;\overline A)\;\rightarrow\overline B)\;\rightarrow\overline C)\;=\)

\(=(((\overline A\;\vee\;B)\;\vee\;\overline A)\;\rightarrow\;\overline B)\;\rightarrow\;\overline C)\;=((\overline<(\overline<(\overline A\vee B)>\;\vee\;\overline A\;)>\;\vee\;\overline B)\;\rightarrow\;\overline C)\;=\)

\(=\;((\overline<(\overline A\;\vee\;B)>\;\vee\;\overline A)\;\wedge\;B)\;\vee\;\overline C\;=\;(((A\;\wedge\;\overline B)\;\vee\;\overline A)\;\wedge B)\;\vee\;\overline C\;=\)

\(=((A\overline B\;\vee\;\overline A)\;\vee\;\overline A)\;\wedge\;B)\;\vee\;\overline C\;=(((A\;\wedge\;\overline B)\;\vee\;\overline A)\;\wedge\;B)\;\vee\;\overline C\;=\)

\(=\;((A\overline B\;\vee\;\overline A)\;\wedge\;B)\;\vee\;\overline C\;=\;(A\overline BB\;\vee\;\overline AB)\;\vee\;\overline C\;=\;(0\;\vee\;\overline AB)\;\vee\;\overline C\;=\;\overline AB\;\vee\;\overline C\)

Далее приведем выражение к КНФ:

\(F\;=\;\overline AB\;\vee\;\overline C\;\;=\;(\overline A\;\vee\;\overline C)\;\wedge\;(B\;\vee\;\overline C)\)

Далее приведем выражение к СКНФ:

\(F\;=\;(\overline A\;\vee\;\overline C)\;\wedge\;(B\;\vee\;\overline C)\;=\;(\overline A\;\vee\:\overline C\;\vee\;B\overline B)\;\wedge\;(A\overline A\;\vee\;B\;v\;\overline C)\;=\)

\(=\;(\overline A\;\vee\;\overline C\;\vee\;B)\;\wedge\;(A\;\vee\;B\;\vee\;\overline C)\;\wedge\;(\overline A\;\vee\;\overline C\;\vee\;\overline B)\;\wedge\;(\overline A\;\vee\;B\;\;\overline C)\)

Задача №2

Используя эквивалентные преобразования, постройте ДНФ функции \(f(\widetilde x^n)\)

\(f(\widetilde x^3) = (\overlinex_2\;\oplus\;x_3)\;\cdot\;(x_1x_3\;\rightarrow\;x_2)\)

\(f(\widetilde x^3) = (\overlinex_2\;\oplus\;x_3)\;\cdot\;(x_1x_3\;\rightarrow\;x_2) = ((\overlinex_2\;\cdot\;\overline\;)\;\vee\;(\overline<\overlinex_2>\;\cdot\;x_3))\;\cdot\;(\overline\;\vee\;x_2)\;=\)

\(=(\overlinex_2\overline\;\cdot(x_1\vee x_3\vee x_2)\;\vee\;x_1x_3\;\cdot\;(\overline\;\vee\;\overline\;\vee\;x_2)\;\vee\;\overlinex_3\;\cdot\;(\overline\;\vee\;\overline\;\vee\;x_2))\;=\)

Источник

Дизъюнктивные и конъюнктивные нормальные формы

Формула вида (соответственно вида ), где все фигурирующие в ней переменные попарно различны, называется элементарной конъюнкцией (соответственно элементарной дизъюнкцией).

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

Теорема 6.2. Любая булева функция, отличная от константы 0 (соответственно от константы 1) представима в виде СДНФ (соответственно в виде СКНФ).

Согласно принципу двойственности, СКНФ для той же функции будет иметь вид

Из доказанного следует, что любая булева функция может быть представлена в виде формулы над стандартным базисом (СДНФ или СКНФ), и, значит, стандартный базис есть полное множество булевых функций.

Рассмотрим в качестве примера построение СДНФ и СКНФ для мажоритарной функции. Конституентами единицы для нее служат наборы:

Им соответствуют элементарные конъюнкции:

Тогда СДНФ, представляющая мажоритарную функцию, имеет вид

Для получения СКНФ для той же функции выпишем все конституенты нуля данной функции:

Сопоставим им элементарные дизъюнкции:

В результате получим СКНФ для мажоритарной функции в виде

Заметим, что если в формуле СКНФ (6.10) мы раскроем скобки и преобразуем полученное выражение согласно законам булевой алгебры, проведя тем самым эквивалентные преобразования СКНФ, то придем к формуле СДНФ (6.9).

Источник

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

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

Среди нормальных форм выделяются совершенные нормальные формы (такие формы, в которых функции записываются единственным образом).

Совершенная дизъюнктивная нормальная форма (СДНФ)

Определение. Формулу называют элементарной конъюнкцией, если она образованна конъюнкцией некоторого числа переменных или их отрицаний.

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

Определение. Логическая формула от k переменных называется совершенной дизъюнктивной нормальной формой (СДНФ), если:
1) формула является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция k переменных х₁, х₂, …, х_k, причем на i-м месте этой конъюнкции стоит либо переменная х_i, либо ее отрицание;
2) все элементарные конъюнкции в такой ДНФ попарно различны.

Совершенная конъюнктивная нормальная форма (СКНФ)

Определение. Формулу называют элементарной дизъюнкцией, если она образована дизъюнкцией некоторого числа переменных или их отрицаний.

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

Определение. Логическая формула от k переменных называется совершенной конъюнктивной нормальной формой (КДНФ), если:
1) формула является КНФ, в которой каждая элементарная дизъюнкция есть дизъюнкция k переменных х₁, х₂, …, х_k, причем на i-м месте этой дизъюнкции стоит либо переменная х_i, либо ее отрицание;
2) все элементарные дизъюнкции в такой КНФ попарно различны.

Алгоритм построения СДНФ по таблице истинности

Алгоритм построения СКНФ по таблице истинности

Пример: Дана таблица истинности логической функции от трех переменных. Построить логическую формулу, реализующую эту функцию.

Т.к. на большинстве строк таблицы истинности значение функции равно 1, то построим СКНФ. В результате получим следующую логическую формулу:
F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)

Проверим полученную формулу. Для этого построим таблицу истинности функции.

Сравнив исходную таблицу истинности и построенную для логической формулы, заметим, что столбцы значений функции совпадают. Значит, логическая функция построена верно.

Copyright © 2014-2021, Урок информатики
Все права защищены

Источник