Формулы сднф и скнф

Формулы сднф и скнф

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

Введем следующие определения:

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

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

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

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

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

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

Приведем примеры формул, соответствующих и не соответствующих этим определениям:

Формула называется СДНФ, если:

1) она является ДНФ;

2) каждая элементарная конъюнкция ДНФ содержит все наименования переменных, от которых зависит формула, и каждое наименование входит в него один раз;

3) среди элементарных конъюнкций ДНФ нет одинаковых.

Примеры:

1. — СДНФ

2. — не является СДНФ, т.к. в первой скобке нет переменной Z.

Формула называется СКНФ, если

1) она является КНФ;

2) каждая элементарная дизъюнкция КНФ содержит все наименования переменных, от которых зависит формула и это наименование входит только один раз;

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

Пример:

— СКНФ

Теорема 1: Если формула не тождественно истинная, то для нее существует и при том единственная СКНФ.

Теорема 2: Если формула не тождественно ложная, то для нее существует и при том единственная СДНФ.

Совершенные формы можно строить с помощью:

1) равносильных преобразований;

2) таблиц истинности.

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

Рассмотрим этот алгоритм на конкретном примере, используя таблицу истинности

X Y Z F(x,y,z)

1) выбираем те строки таблицы , на которых формула принимает значение истина: 2, 4, 7, 8;

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

3) из элементарных конъюнкций составляем ДНФ.

— СДНФ

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

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

Данный алгоритм аналогичен алгоритму построения СДНФ.

1) выбираем строки таблицы, на которых формула принимает значение ложь: 1, 3, 5, 6;

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

Читайте также:  Как удалиться с ютуба

3) из элементарных дизъюнкции составляем КНФ.

— СКНФ

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

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

Описанный способ нахождения СНДФ и СНКФ исходной формулы по таблице истинности бывает более трудоёмким, чем следующий:

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

1) приводим исходную формулу к ДНФ;

2) если в элементарную конъюнкцию некоторая переменная входит со своим отрицанием, то удаляем эту конъюнкцию из ДНФ;

3) если в элементарную конъюнкцию некоторая переменная входит несколько раз, то удаляем эти переменные кроме одной;

4) если в некоторую элементарную конъюнкцию некоторая переменная или переменные не входят, то заменяем её на эквивалентную форму, добавляя к ней одну или несколько переменных в виде и, применяя закон дистрибутивности, приводим формулу к ДНФ;

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

В результате получаем СДНФ.

Пример:

Пусть дана ДНФ функции. Найдте СДНФ функции.

СДНФ

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

1) приводим исходную формулу к КНФ;

2) если в элементарную дизъюнкцию некоторая переменная входит со своим отрицанием, то удаляем эту конъюнкцию из КНФ;

3) если в элементарную дизъюнкцию некоторая переменная входит несколько раз, то удаляем эти переменные кроме одной;

4) если в некоторую элементарную дизъюнкцию некоторая переменная или переменные не входят, то заменяем её на эквивалентную форму, добавляя к ней одну или несколько переменных в виде и, применяя закон дистрибутивности, приводим формулу к КНФ;

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

В результате получаем СКНФ.

Пример:

Пусть дана КНФ функции . Найти СКНФ функции.

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

Рассмотрим следующие алгоритмы:

1) Для определения типа формулы надо построить ДНФ (КНФ) и

проверить критерий ложности (критерий истинности). Если критерий выполнен, то формула тождественно ложна (тождественно истинна), если нет, то строим КНФ (ДНФ) и проверяем критерий истинности

(критерий ложности), если критерий выполнен, то формула тождественно истинна (тождественно ложна) в противном случае, формула только выполнима.

2) Для определения типа формулы надо построить СДНФ или СКНФ. Если СДНФ построена, то формула не является тождественно ложной. Далее считаем число слагаемых в СДНФ: если их ,где n — число переменных, от которых зависит формула, то формула тождественно истинна, в противном случае выполнима.

Если СКНФ построена, то формула не тождественно истинна. Если число слагаемых в СКНФ равно , где n — число переменных, то формула тождественно ложна, в противном случае формула выполнима.

Читайте также:  Программа будильник на телефон

Лекция 6. Канонические формы логических формул, используемых в ЭВМ

6.1 Основные термины. Понятие СДНФ и СКНФ.

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

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

a xor b ≡ ( a and ( not b )) or (( not a ) and b ).

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

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

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

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

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

Пример 1. Формулы являются элементарными конъюнкциями; первые две из них — одночленными.

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

Пример 2. Приведем две дизъюнктивные нормальные формы:

Определение 4. Формула А от k переменных называется совершенной дизъюнктивной нормальной формой (СДНФ), если:

1) А является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция k переменных , причем на i-м месте этой конъюнкции стоит либо переменная , либо ее отрицание;

2) все элементарные конъюнкции в такой ДНФ попарно различны.

Задание 1. Даны формулы:

;

;

Определить, являются ли они СДНФ двух переменных.

Решение. Формула А является СДНФ двух переменных. Формулы В и С не являются СДНФ. Формула В зависит от трех переменных, но количество переменных в элементарных конъюнкциях меньше трех. В формуле С переменная х2 дважды входит в одну и ту же элементарную конъюнкцию.

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

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

Пример 1 Приведем три элементарные дизъюнкции:
.

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

Пример 2. Формулы

являются конъюнктивными нормальными формами.

Определение 7. Формула А от k переменных называется совершенной конъюнктивной нормальной формой (СКНФ),если:

Читайте также:  Факториальная система счисления это

1) А является КНФ, в которой каждая элементарная дизъюнкция есть дизъюнкция k переменных , причем на i-м месте этой дизъюнкции стоит либо переменная х, либо ее отрицание;

2) все элементарные дизъюнкции в такой КНФ попарно различны.

Задание 2. Даны формулы и . Определить, являются ли они СКНФ.

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

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

Ответ. Да, любую булеву функцию, не равную тождественно 0 или 1, можно представить в виде СДНФ или СКНФ.
Для обоснования этого утверждения имеется теорема.

Теорема 1. Пусть — булева функция от n переменных, не равная тождественно нулю. Тогда существует совершенная дизъюнктивная нормальная форма, выражающая функцию f.

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

1. В таблице истинности отмечаем наборы переменных, на которых значение функции f равно единице.

2. Записываем для каждого отмеченного набора конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае — ее отрицание.

3. Все полученные конъюнкции связываем операциями дизъюнкции.

Следствие теоремы 1. Для любой формулы можно найти равносильную ей ДНФ.

Пример 3. Требуется построить формулу для функции f(x1, х2, х3), заданной таблицей истинности:

x1 x2 x3 f(x1, х2, х3)

Используя описанный выше алгоритм, построим для нее СДНФ:

Теорема 2. Пусть — булева функция n переменных, не равная тождественно единице. Тогда существует совершенная конъюнктивная нормальная форма, выражающая функцию f.

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

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

1. В таблице истинности отмечаем наборы переменных, на которых значение функции f равно нулю.

2. Записываем для каждого отмеченного набора дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 0, то в конъюнкцию включаем саму переменную, в противном случае — ее отрицание.

3. Все полученные дизъюнкции связываем операциями конъюнкции.

Следствие теоремы 2. Для любой формулы можно найти равносильную ей КНФ.

Пример 4. Выразим функцию импликация с помощью операций отрицания, дизъюнкции и конъюнкции. Для этого запишем таблицу истинности функции импликация:

x1 x2 f(x1, х2, х3)

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

Ответ:

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

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

Лучшие изречения: Да какие ж вы математики, если запаролиться нормально не можете. 8774 — | 7582 — или читать все.

Ссылка на основную публикацию
Установить gvlk ключ что это
В связи с недавним выходом окончательной RTM версии пакета Microsoft Office 2016, корпоративные заказчики уже могут начинать переход на новую...
Топ вай фай адаптеров для пк
На заре развития интернета люди пользовались только проводным трафиком. После этого в «моду» начали входить модемы, которые подключались к беспроводному...
Топ дешевых наушников с хорошим звуком
Проводные наушники должны умереть! Так решил мобильный рынок и производители смартфонов, стремительно избавляющиеся от устаревшего 3,5 мм джека. Стоит ли...
Установить openal32 dll для windows 7
Данная библиотека задействуется во многих процессах во время работы компьютера. Например, она используется в играх, мультимедиа и различных программах. Иногда...
Adblock detector