Разложение булевой функции в заданной точке пространства. Лабораторная работа Функции алгебры логики (булевы функции). Разложение по всем переменным

Поделитесь работой в социальных сетях

Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск

аранов Виктор Павлович. Дискретная математика.

Раздел 4. Функциональные системы с операциями. Алгебра логики.

Лекция 21. Принцип двойственности. Разложение функций по переменным. Совершенные ДНФ и КНФ

Лекция 21. ПРИНЦИП ДВОЙСТВЕННОСТИ. РАЗЛОЖЕНИЕ БУЛЕВЫХ

ФУНКЦИЙ ПО ПЕРЕМЕННЫМ. СОВЕРШЕННЫЕ ДИЗЪЮНКТИВНАЯ И

КОНЪЮНКТИВНАЯ НОРМАЛЬНЫЕ ФОРМЫ

План лекции:

Принцип двойственности.
Разложение булевых функций по переменным. Совершенные дизъюнктивная и конъюнктивная нормальные формы.

Принцип двойственности

Функция, равная, называется двойственной функцией к функции .

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

Легко установить для функций 0, 1, что

функция 0 двойственна 1;
функция 1 двойственна 0;
функция двойственна;
функция двойственна;
функция двойственна;
функция двойственна.

Из определения двойственности следует, что

т. е. функция является двойственной к (свойство взаимности).

Принцип двойственности. Если формула реализует функцию, то формула, т. е. формула, полученная из заменой функций соответственно на, реализует функцию.

Формулу будем называть формулой, двойственной к.

Для доказательства этого утверждения необходимо проверить его справедливость для элементарных шагов суперпозиции и.

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

Тогда

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

Доказательство справедливости принципа двойственности для шага проведем на примере. Пусть

Тогда

т. е. функция получается из и так же, как функция из и.

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

Пример 1. Из тождества следует тождество.

Действительно,

;; .

Пример 2. Построение формулы для отрицания функции.

Из определения двойственной функции следует

Получаем следующее правило: пусть формула реализует функцию. Чтобы получить формулу для функции нужно в формуле заменить все переменные на их отрицания.

Найдем отрицание для функции.

Так как, то.

Разложение булевых функций по переменным. Совершенные

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

Введем обозначение

где параметр, равный либо 0, либо 1. Очевидно, что

Легко видеть, что 1 тогда и только тогда, когда.

Теорема о разложении функций по переменным. Каждую функцию алгебры логики при любом () можно представить в следующей форме:

, (1)

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

Это представление называется разложением функции по переменным .

Доказательство. Рассмотрим произвольный набор значений переменных и покажем, что левая и правая части соотношения (1) принимают на нем одно и то же значение. Левая часть дает. Правая

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

Разложение по переменной:

Функции и называются компонентами разложения. Данное разложение полезно, когда какие-либо свойства устанавливаются по индукции.

Разложение по всем переменным:

При тождественно не равной 0 оно может быть преобразовано:

В результате окончательно получим

. (2)

Такое разложение называется совершенной дизъюнктивной нормальной формой (совершенной д. н. ф.).

Непосредственно к понятию совершенной д. н. ф. примыкает следующая теорема.

Теорема. Каждая функция алгебры логики может быть представлена формулой в базисе.

Доказательство.1) Пусть. Тогда, очевидно,

Пусть тождественно не равна 0. Тогда ее можно представить формулой (2).

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

Пример 3. Найти совершенную д. н. ф. для функции.

Совершенная д. н. ф. есть выражение типа П. Покажем, что при тождественно не равной 1 ее можно представить в виде. Запишем для двойственной функции (очевидно не равной тождественно 0) разложение в виде совершенной д. н. ф.:

Из принципа двойственности следует

Таким образом, получаем разложение, которое называется совершенной конъюнктивной нормальной формой (совершенной к. н. ф.):

. (3)

Пример 4. Построить совершенную к. н. ф. для функции.

Имеем.

Другие похожие работы, которые могут вас заинтересовать.вшм>
200.		Нормальные формы логических функций	63.53 KB
	Нормальные формы логических функций Представление булевой функции в форме дизъюнкции конъюнктивных термов конституент единицы Ki 2.7 называется дизъюнктивной нормальной формой ДНФ этой функции. содержат в точности по одной все логические переменные взятые с отрицаниями или без них то такая форма представления функции называется совершенной дизъюнктивной нормальной формой СДНФ этой функции. Как видно при составлении СДНФ функции нужно составить дизъюнкцию всех минтермов при которых функция принимает значение 1.
9015.		МЕТОДЫ МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ	81.74 KB
	ДНФ и схемы из ФЭ. Минимизация булевых функций на основе построения тупиковых ДНФ. Минимизация булевых функций на основе построения тупиковых ДНФ Сокращенная тупиковая и минимальная ДНФ находятся в следующем соотношении. Тупиковая ДНФ получается из сокращенной путем удаления некоторых членов.
9017.		ПРОБЛЕМА МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ	109.86 KB
	ДНФ и схемы из ФЭ. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ План лекции: Понятие дизъюнктивной нормальной формы ДНФ. Понятие ДНФ. Выражение при где элементарная конъюнкция ранга называется дизъюнктивной нормальной формой ДНФ.
14731.		Разложение сигналов в обобщенный ряд Фурье по системам ортогональных функций. Функции Уолша	38.95 KB
	Разложение сигналов в обобщенный ряд Фурье по системам ортогональных функций. Ознакомить с основными характеристиками сигналов и помех. Изучить представление сигналов в виде обобщенного ряда Фурье по системам ортогональных функций. Разложение сигналов в обобщенный ряд Фурье по системам ортогональных функций.
6707.		Проектирование реляционных баз данных. Проблемы проектирования в классическом подходе. Принципы нормализации, нормальные формы	70.48 KB
	Что такое проект реляционной базы данных Это набор взаимосвязанных отношений в которых определены все атрибуты заданы первичные ключи отношений и заданы еще некоторые дополнительные свойства отношений которые относятся к принципам поддержки целостности. Поэтому проект базы данных должен быть очень точен и выверен. Фактически проект базы данных это фундамент будущего программного комплекса который будет использоваться достаточно долго и многими пользователями.
4849.		Формы и методы осуществления функций государства	197.3 KB
	Термин «функция» имеет в отечественной и зарубежной научной литературе далеко не одинаковое значение. В философском и общесоциологическом плане, он рассматривается, как «внешнее проявление свойств какого-либо объекта в данной системе отношений»; как совокупность обычных или же специфических действий отдельных лиц или органов
1790.		Разложение на слагаемые	180.15 KB
	Саме слово алгоритм походить від algorithmi – латинської форми написання імені великого математика ІХ ст. аль-Хорезмі, який сформулював правила виконання арифметичних дій. Спочатку під алгоритмами і розуміли тільки правила виконання чотирьох арифметичних дій над багатоцифровими числами.
2690.		Изучение работоспособности сверл с переменным шагом винтовой линии	18.85 KB
	Модели процесса резания могут быть представлены системой математических уравнений, определяющих в каждом конкретном случае оценочную функцию или критерии работоспособности режущих инструментов, а также технические ограничения по кинематике станка, жесткости режущих инструментов и в целом технологической системы
17088.		УГОЛОВНАЯ ОТВЕТСТВЕННОСТЬ ЗА ПРЕСТУПЛЕНИЯ, СОВЕРШЕННЫЕ В СОСТАВЕ ОРГАНИЗОВАННОЙ ПРЕСТУПНОЙ ГРУППЫ	50.97 KB
	Ломтев ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы исследования обуславливается потребностью в дальнейшем развитии и совершенствовании теории и практики реализации уголовной ответственности за преступления совершаемые в составе организованной преступной группы. Исследования в сфере противодействия организованной преступности показывают что именно в составе организованных преступных групп совершаются наиболее опасные и трудно раскрываемые преступления. В рамках решения задачи повышения эффективности уголовного закона в части борьбы с...
11576.		Понятие, виды и формы сделок. Последствия несоблюдения требуемой формы сделок	49.82 KB
	Признание сделки недействительной виды недействительной сделки. Прикладная ценность курсовой работы заключается в упрощении понятия сделки то есть публичного его представления в более доступной форме.

Пусть G - параметр, равный 0 или 1.

Введем обозначение:

Проверкой легко установить, что x G = 1, тогда и только тогда, когда
x = G. Отсюда следует, конъюнкция равна 1 (здесь G равен 0 или 1) тогда и только тогда, когда . Например, конъюнкция (в которой G 2 = G 1 = 0, G 3 = G 4 = 1) равна 1 только в случае, когда x 1 = x 2 = 0, x 3 = x 4 = 1.

Теорема 1. Всякая булева функция f(x 1 , x 2 , x n) может быть представлена в следующей форме:

где 1 ≤ k ≤ n, в дизъюнкции берется по всем наборам значений переменных.

Это представление носит название разложения функции по переменным . Например, при n = 4, k = 2 разложение (3.1) имеет вид:

Докажем справедливость разложения (3.1). Для этого возьмем произвольный набор значений переменных . Покажем, что левая и правая части соотношения (3.1) принимают при нем одно и то же значение. Действительно, так как x G = 1 тогда и только тогда, когда x = G, то среди 2 К конъюнкции правой части (3.1) в единицу обращается только одна, в которой . Все остальные конъюнкции равны нулю.

Поэтому . В качестве следствия из разложения (3.1) получаем следующие два специальных разложения.

Разложение по переменной x n:

Если булева функция не есть константа 0, то справедливо разложение

Разложение по всем переменным:

, (3.3)

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

Разложение (3.3) называется совершенной дизъюнктивной нормальной формой (сокращенная запись СДНФ) функции.

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

Таким образом, существует взаимно однозначное соответствие между таблицей истинности функции и ее СДНФ. А это значит, что СДНФ для булевой функции единственна.

Единая булева функция, не имеющая СДНФ, есть константа 0.

Пример 1. Найти совершенную дизъюнктивную форму для функции .

Составим таблицу истинности для данной функции:

Отсюда получаем: = = .

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

Теорема 2. Всякая булева функция может быть представлена в следующей форме:

где 1≤k≤n, а конъюнкция берется по всем 2 k наборам значений переменных.

Действительно, пусть - произвольный набор значений переменных. Покажем, что левая и правая части соотношения (3.4) принимают при нем одно и то же значение. Так как только тогда, когда , то среди 2 k дизъюнкций правой части (3.4) в 0 обращается только одна, в которой . Все остальные дизъюнкции равны 1.

Поэтому = = .

Непосредственно из разложения (3.4) следуют разложения булевых функций:

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

Единственная булева функция, не имеющая СКНФ, есть константа 1.

Пример 2. Найти совершенную конъюнктивную нормальную форму для функции .

Составим таблицу истинности для данной функции.

Отсюда получаем СКНФ

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

В силу приведенного определения ДНФ будут, например, выражения: , .

Как отмечено в пункте 2.2, все логические операции можно свести к трем: конъюнкции, дизъюнкции и отрицания. Причем, ввиду закона
де Моргана, знак отрицания можно предполагать отнесенным только к переменным.

Теперь, используя дистрибутивный закон, раскрываем скобки и получаем дизъюнктивную нормальную форму. Итак, справедлива следующая теорема.

Теорема 3. Для любой формулы алгебры логики существует равносильная ей дизъюнктивная нормальная форма.

Доказательство данной теоремы дает способ построения дизъюнктивной нормальной формы для любой формулы алгебры логики.

Пример 3. Найти дизъюнктивную нормальную форму для следующей формулы: .

Исключая знак по закону и применяя законы де Моргана и двойного отрицания, получаем:

Затем, применяя закон дистрибутивности, раскроем скобки

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

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

Такими являются, например, выражения:

, .

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

Итак, справедлива следующая теорема.

Теорема 4. Для любой формулы алгебры логики существует равносильная ей конъюнктивная нормальная форма.

Доказательство данной теоремы дает способ построения конъюнктивной нормальной формы для любой формулы алгебры логики.

Пример 4. Найти дизъюнктивную и конъюнктивную нормальные формы для следующей формулы: .

Используя закон , исключаем знак . Получаем формулу .

Используя закон де Моргана, получаем формулу . Раскрывая скобки, получаем дизъюнктивную нормальную форму

Чтобы получить конъюнктивную нормальную форму, применим к формуле дистрибутивный закон, получаем:

Последнее выражение является конъюнктивной нормальной формой. Так как и , то полученная КНФ равносильна следующей КНФ:

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

1) все конъюнкции попарно различны;

2) каждая конъюнкция содержит ровно n переменных;

3) в каждой конъюнкции встречаются все n переменных.

На примере 1 мы рассмотрели один из способов построения СДНФ, основанный на составлении таблицы истинности. Следующий способ построения СДНФ основан на применении законов алгебры логики.

Пример 5. Найти совершенную дизъюнктивную форму формулы .

Используя, что , получаем . Ввиду законов
де Моргана и двойного отрицания имеем получили дизъюнктивную нормальную форму . Данная ДНФ равносильна формуле .

Раскрывая скобки, получаем: .

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

Учитывая разложение (3.6), нетрудно заметить, что совершенная конъюнктивная нормальная форма формулы алгебры логики, содержащей ровно n различных переменных, есть ее конъюнктивная нормальная форма, в которой:

1) все дизъюнкции попарно различны;

2) каждая дизъюнкция содержит ровно n членов;

3) в каждой дизъюнкции встречаются все n переменных., если она при всех значениях входящих в нее переменных принимает значение истинно .

Примерами тождественно истинных формул являются формулы:

тождественно ложной , если она при всех значениях, входящих в нее переменных, принимает значение ложь.

Примерами тождественно ложных формул являются формулы:

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

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

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

Рассмотрим следующие два способа решения этой задачи.

Способ 1. (табличный) Для того, чтобы определить, является ли данная формула тождественно истинной или нет, достаточно составить ее таблицу истинности.

Однако данный способ, хотя и дает принципиальное решение проблемы разрешимости, он довольно громоздкий.

Способ 2. основан на приведении формул к нормальной форме.

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

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

Пусть теперь данная формула является тождественно истинной, и пусть есть некоторая дизъюнкция в КНФ данной формулы. Допустим, что данная дизъюнкция не содержит переменной вместе с ее отрицанием. В таком случае мы можем каждой переменной, не стоящей под знаком отрицания, дать значение 0, а каждой переменной, стоящей под знаком отрицания - значение 1. После указанной подстановки все дизъюнкции станут равны 0, следовательно, формула не является тождественно истинной. Получили противоречие.

Пример 7. Выяснить, будет ли тождественно истинной формула

Используя, что , получаем .

Применяя закон дистрибутивности, получаем КНФ:

Так как каждая дизъюнкция содержит некоторую переменную вместе с ее отрицанием, то формула тождественно истинна.

Аналогично предыдущей теореме доказывается теорема:

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

Разложение булевых функций по переменным.

Пусть G – параметр, равный 0 или 1. Введем обозначение:

Проверкой легко установить, что x G = 1, тогда и только тогда, когда x = G. Отсюда следует, конъюнкция равна 1 (здесь G равен 0 или 1) тогда и только тогда, когда . К примеру, конъюнкция (в которой G 2 = G 1 = 0, G 3 = G 4 = 1) равна 1 только в случае, когда x 1 = x 2 = 0, x 3 = x 4 = 1.

Теорема 1 Всякая булева функция f(x 1 ,x 2 ,…,x n) должна быть представлена в следующей форме:

где 1 ≤ k ≤ n, в дизъюнкции берется по всем наборам значений переменных.

Это представление носит название разложения функции по переменным . К примеру, при n = 4, k = 2 разложение (3.1) имеет вид:

По этой причине . В качестве следствия из разложения (3.1) получаем следующие два специальных разложения.

Разложение по переменной x n:

В случае если булева функция не есть константа 0, то справедливо разложение

Разложение по всем переменным:

, (3.3)

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

Разложение (3.3) принято называть совершенной дизъюнктивной нормальной формой (сокращенная запись СДНФ) функции.

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, существует взаимно однозначное соответствие между таблицей истинности функции и ее СДНФ. А это значит, что СДНФ для булевой функции единственна.

Единая булева функция, не имеющая СДНФ, есть константа 0.

Пример 1 Найти совершенную дизъюнктивную форму для функции .

Составим таблицу истинности для данной функции:

Отсюда получаем: = = .

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

Теорема 2 Всякая булева функция должна быть представлена в следующей форме:

где 1≤k≤n, а конъюнкция берется по всем 2 k наборам значений переменных.

Действительно, пусть – произвольный набор значений переменных. Покажем, что левая и правая части соотношения (3.4) принимают при нем одно и то же значение. Так как только тогда, когда , то среди 2 k дизъюнкций правой части (3.4) в 0 обращается только одна, в которой . Все остальные дизъюнкции равны 1.

По этой причине = = .

Непосредственно из разложения (3.4) следуют разложения булевых функций:

Последнее разложение носит название совершенной конъюнктивной нормальной формы (СКНФ). Разложение (3.6) дает способ построения СКНФ. Для этого в таблице истинности отмечаем все строки , в которых . Для каждой такой строки образуем дизъюнкцию и затем все полученные конъюнкции соединяем знаком конъюнкции. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, существует взаимно однозначное соответствие между таблицей истинности функции и ее СКНФ. А это значит, что СКНФ для булевой функции единственна.

Единственная булева функция, не имеющая СКНФ, есть константа 1.

Пример 2 Найти совершенную конъюнктивную нормальную форму для функции .

Составим таблицу истинности для данной функции.

Отсюда получаем СКНФ

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

В силу приведенного определения ДНФ будут, к примеру, выражения: , .

Как отмечено в пункте 2.2, все логические операции можно свести к трем: конъюнкции, дизъюнкции и отрицания. Причем, ввиду закона де Моргана, знак отрицания можно предполагать отнесенным только к переменным.

Теорема 3 Для любой формулы алгебры логики существует равносильная ей дизъюнктивная нормальная форма.

Пример 3 Найти дизъюнктивную нормальную форму для следующей формулы: .

Исключая знак по закону и применяя законы де Моргана и двойного отрицания, получаем:

Затем, применяя закон дистрибутивности, раскроем скобки

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

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

Такими являются, к примеру, выражения:

, .

Итак, справедлива следующая теорема.

Теорема 4 Для любой формулы алгебры логики существует равносильная ей конъюнктивная нормальная форма.

Пример 4 Найти дизъюнктивную и конъюнктивную нормальные формы для следующей формулы: .

Используя закон , исключаем знак . Получаем формулу .

Используя закон де Моргана, получаем формулу . Раскрывая скобки, получаем дизъюнктивную нормальную форму

Чтобы получить конъюнктивную нормальную форму, применим к формуле дистрибутивный закон, получаем:

1) все конъюнкции попарно различны;

2) каждая конъюнкция содержит ровно n переменных;

3) в каждой конъюнкции встречаются все n переменных.

Пример 5 Найти совершенную дизъюнктивную форму формулы .

Используя, что , получаем . Ввиду законов де Моргана и двойного отрицания имеем получили дизъюнктивную нормальную форму . Данная ДНФ равносильна формуле .

Раскрывая скобки, получаем: .

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

1) все дизъюнкции попарно различны;

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

Примерами тождественно истинных формул являются формулы:

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

Примерами тождественно ложных формул являются формулы:

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

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

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

Рассмотрим следующие два способа решения этой задачи.

Способ 1 (табличный) Для того, чтобы определить, является ли данная формула тождественно истинной или нет, достаточно составить ее таблицу истинности.

При этом данный способ, хотя и дает принципиальное решение проблемы разрешимости, он довольно громоздкий.

Способ 2 основан на приведении формул к нормальной форме.

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

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

Пусть теперь данная формула является тождественно истинной, и пусть есть некоторая дизъюнкция в КНФ данной формулы. Допустим, что данная дизъюнкция не содержит переменной вместе с ее отрицанием. В таком случае мы можем каждой переменной, не стоящей под знаком отрицания, дать значение 0, а каждой переменной, стоящей под знаком отрицания – значение 1. После указанной подстановки все дизъюнкции станут равны 0, следовательно, формула не является тождественно истинной. Получили противоречие.

Пример 7 Выяснить, будет ли тождественно истинной формула

Используя, что , получаем .

Применяя закон дистрибутивности, получаем КНФ:

Аналогично предыдущей теореме доказывается теорема:

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

Разложение булевых функций по переменным. - понятие и виды. Классификация и особенности категории "Разложение булевых функций по переменным." 2017, 2018.

Пусть s принимает значения 0 или 1, т.е. s {0, 1}.

Введем обозначение:

x s = Øx , если s = 0, x s = x , если s = 1.

Т.е. x 0 = Øx , x 1 = x .

Очевидно, что x s = 1, если x = s и x s = 0, если x s .

Теорема 4.5 (о разложении булевой функции по переменным).

Каждая булева функция f (x 1 , x 2 , ... , x n ) может быть представлена в виде:

f (x 1 , x 2 , ... , x n ) = f (x 1 , x 2 , ... , x m , x m +1 , ... , x n ) =

V x 1 s 1 &x 2 s 2 &...&x m sm & f (s 1 , s 2 , ... s m , x m +1 , ... , x n ), (4.1)

m n , где дизъюнкция берется по всем наборам (s 1 , s 2 , ... , s m ) (их 2 m ).

Например, для m = 2, n = 4 разложение (4.1) включает в себя четыре (2 m = 2 2 =4) конъюнкции и имеет вид:

f (x 1 , x 2 , x 3 , x 4) = x &x &f (0, 0, x 3 , x 4) V x &x &f (0, 1, x 3 , x 4) V x & x &f (1, 0, x 3 , x 4) V x & x &f (1, 1, x 3 , x 4) = Øx 1 &Øx 2 &f (0, 0, x 3 , x 4) V Øx 1 &x 2 &f (0, 1, x 3 , x 4) V x 1 &Øx 2 &f (1, 0, x 3 , x 4) V x 1 &x 2 &f (1, 1, x 3 , x 4).

Доказательство теоремы 4.5.

Теорема будет доказана, если показать, что равенство (4.1) выполняется для произвольного набора переменных (y 1, y 2 , ... , y m , y m +1 , ... , y n ) .

Подставим этот произвольный набор переменных в левую и правую части равенства (4.1).

В левой части получим f (y 1, y 2 , ... , y n ) .

Т. к. y s = 1 только, когда y = s , то среди 2 m конъюнкций y 1 s 1 &y 2 s 2 &...&y m sm в правой части (4.1) только одна обратится в 1 – та, в которой y 1 = s 1 ,…, y m = s m . Все остальные конъюнкции равны 0. Поэтому в правой части (4.1) получим:

y 1 y 1 &y 2 y 2 &...&y m ym &f (y 1, y 2 , ... , y m , y m +1 , ... , y n ) = f (y 1, y 2 , ... , y n ) .

Теорема 4.5 доказана.

Теорема 4.6 (о представлении булевой функции формулой в СДНФ),

Всякая булева функция f (x 1 , x 2 , ... , x n ),не равная тождественно 0, может быть представлена формулой в СДНФ, которая определяется однозначно с точностью до перестановки дизъюнктивных членов.

Доказательство.

При m = n получим важное следствие теоремы 4.5:

f (x 1 , x 2 , ... , x n ) = V x 1 s 1 &x 2 s 2 &...&x n sn , (4.2)

f (s 1 , s 2 , ... , s n ) = 1

где дизъюнкция берется по всем наборам (s 1 , s 2 , ... , s n ), на которых f = 1.

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

Очевидно также, что для булевой функции f (x 1 , x 2 , ... , x n ), тождественно равной 0, разложение (2) не существует.

В силу изложенного для получения формулы булевой функции f (x 1 , x 2 , ... , x n ) в СДНФ можно воспользоваться следующим алгоритмом.

Алгоритм 4.3. (Алгоритм представления булевой функции, заданной таблицей, формулой в СДНФ).

Шаг 1. s 1 , s 2 , ... , s n , для которых значение f равно 1, т. е. f (s 1 , s 2 , ... , s n ) = 1.

Шаг 2. Для каждого такого набора (строки таблицы) составляем конъюнкцию x 1 s 1 &x 2 s 2 &...&x n sn , где x i si = x i , если s i = 1 и x i si =Øx i , если s i = 0, i = 1, 2, ... ,n .

Шаг 3. Составляем дизъюнкцию всех полученных конъюнкций. В результате получится формула данной функции в СДНФ.

Пример 4.15.

Найдем формулу в СДНФ для функции f (x 1 , x 2 , x 3), заданной таблицей 4.4.

f (x 1 , x 2 , x 3) =1. Это 4-ая, 5-ая. 6-ая и 8-ая строки.

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

x 1 0 &x 2 1 &x 3 1 = Øx 1 &x 2 &x 3 .

x 1 1 &x 2 0 &x 3 0 = x 1 &Øx 2 &Øx 3 .

x 1 1 &x 2 0 &x 3 1 = x 1 &Øx 2 &x 3 .

x 1 1 &x 2 1 &x 3 1 = x 1 &x 2 &x 3 .

3. Составляем дизъюнкцию всех полученных конъюнкций и находим СДНФ:

f (x 1 , x 2 , x 3) = Øx 1 &x 2 &x 3 V x 1 &Øx 2 &Øx 3 V x 1 &Øx 2 &x 3 V x 1 &x 2 &x 3 .

Убеждаемся, что это выражение совпадает с полученным ранее в примере 4.13 представлением нашей формулы в СДНФ.

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

Теорема 4.7 (о представлении булевой функции формулой в СКНФ),

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

Доказательство.

Рассмотрим функцию Øf (x 1 , x 2 , ... , x n ). В соответствии с теоремой 4.6, если она не равна тождественно 0, существует ее формула в СДНФ. Обозначим эту формулу F 1 . Очевидно, условие, что функция Øf (x 1 , x 2 , ... , x n ) не равна тождественно 0, равносильно условию, что функция f (x 1 , x 2 , ... , x n ) не равна тождественно 1. Кроме того, по закону де Моргана формула F 2 º ØF 1 находится в СКНФ (отрицание конъюнкции есть дизъюнкция отрицаний). По закону двойного отрицания

F 2 º ØF 1 º ØØf (x 1 , x 2 , ... , x n ) º f (x 1 , x 2 , ... , x n ),

что и доказывает теорему.

Для получения формулы булевой функции f (x 1 , x 2 , ... , x n ) в СКНФ следует воспользоваться следующим алгоритмом.

Алгоритм 4.4. (Алгоритм представления булевой функции, заданной таблицей, формулой в СКНФ)

Шаг 1. Выбираем в таблице все наборы переменных s 1 , s 2 , ... , s n , для которых значение f (s 1 , s 2 , ... , s n ) = 0.

Шаг 2. Для каждого такого набора (строки таблицы) составляем дизъюнкцию

x 1 Ø s 1 Vx 2 Ø s 2 V...Vx n Ø sn , где x i Ø si = x i , если s i = 0 и x i Ø si = Øx i , если s i = 1, i = 1, 2, ... , n .

Шаг 3. Составляем конъюнкцию всех полученных дизъюнкций. В результате получится СКНФ.

Пример 4.16.

Найдем формулу в СКНФ для функции f (x 1 , x 2 , x 3), заданной таблицей 4.4.

1. Выберем в таблице строки, где f (x 1 , x 2 , x 3) = 0. Это 1-ая, 2-ая и 3-я и 7-ая строки.

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

x 1 1 Vx 2 1 Vx 3 1 = x 1 Vx 2 Vx 3 .

x 1 1 Vx 2 1 Vx 3 0 = x 1 Vx 2 VØx 3 .

x 1 1 Vx 2 0 Vx 3 1 = x 1 VØx 2 Vx 3 .

x 1 0 Vx 2 0 Vx 3 1 = Øx 1 VØx 2 V x 3 .

3. Составляем конъюнкцию всех полученных дизъюнкций и находим СКНФ:

f (x 1 , x 2 , x 3) = (x 1 Vx 2 Vx 3)&(x 1 Vx 2 VØx 3)&(x 1 VØx 2 Vx 3)&(Øx 1 VØx 2 Vx 3).

Это выражение совпадает с полученным ранее в примере 4.14 представлением нашей формулы в СКНФ.

Замечание. Т. к. всего строк в таблице функции 2 n , то, если число дизъюнктивных членов в СДНФ равно p , а число конъюнктивных членов в СКНФ равно q , то p +q =2 n .

Так, для функции, рассмотренной в примерах 4.15 и 4.16, n = 3, p = 4, q = 4, p + q = 8 = 2 3 .

Разложение Шеннона Рассмотрим разложение булевой функции f (x 1, x 2, . . . , xn) по переменной xi. Разложение Шеннона: f (x 1, x 2, . . . , xn)= xi f(x 1, . . . , xi 1, 1, xi+1, . . . , xn) xi f(x 1, . . . , xi 1, 0, xi+1, . . . , xn). Доказательство (не умоляя общности, для i =1). Если x 1 = 0, то f(0, x 2, . . . , xn) = 0 f (1, x 2, . . . , xn) 1 f(0, x 2, . . . , xn) = f (0, x 2, . . . , xn). Если x 1 = 1, то f(1, x 2, . . . , xn) = 1 f(1, x 2, . . . , xn) 0 f(1, x 2, . . . , xn) = f(0, x 2, . . . , xn). ЧТД Пример. Булеву функцию f (x, y, z) = x y / y z , разложим по переменной z: f (x, y, z) = z(x y / y 1) z (x y / y 0)= [по свойствам 0 и 1] = z z (x y / y). Сомножитель f (x 1, . . . , xi -1, 1, xi+1, . . . , xn) в формуле Шеннона называется коэффициентом разложения функции f (x 1, x 2, . . . , xn) по переменной xi при xi, а сомножитель f (x 1, . . . , xi -1, 0, xi+1, . . . , xn) - коэффициентом разложения функции f (x 1, x 2, . . . , xn) по xi при xi. Пример. f (x, y, z) = x y / y = y (x 1 / 0) y (x 0 / 1). x 1 / 0 - коэффициент разложения функции f (x, y, z) по y при y ; x 0 / 1 - коэффициент разложения функции f (x, y, z) по y при y.

Разложение функции по k переменным Доказательство. Подставим в левую и правую части равенства произвольный набор a 1 a 2. . . an: Упростим правую часть, рассуждая следующим образом. Нетрудно проверить, что 1, если и только если ai = 0 = 1, 11 = 1, но 0 1 = 0 и 10 = 0), ci (в самом деле: 0 поэтому конъюнкция равна единице лишь в единственном случае, когда наборы a 1 a 2. . . ak и с1 с2. . . сk совпадают. А это значит, что она не обращает в ноль лишь одно слагаемое правой части - то, для которого a 1 a 2. . . ak = с1 с2. . . сk и в котором сама обращается в единицу. Подставив в ставшееся слагаемое a 1 a 2. . . ak вместо с1 с2. . . сk , получим

Совершенная дизъюнктивная нормальная форма (Сов. ДНФ) Применив формулу разложения булевой функции f (x 1, x 2, . . . , xn) по k переменным при k = n, получим: Поскольку коэффициентами разложения f (c 1, c 2, . . . , cn) в этой формуле являются значения функции f (x 1, x 2, . . . , xn) на всевозможных наборах c 1 c 2. . . cn, то возможны два случая: если набор c 1 c 2. . . cn M 0 (f), то f (c 1, c 2, . . . , cn) = 0 и поэтому обращается в 0 соответствующее слагаемое правой части; если набор c 1 c 2. . . cn M 1 (f), то f(c 1, c 2, . . . , cn)=1 и слагаемое упрощается. В результате имеем: Совершенная дизъюнктивная нормальная форма булевой функции, или Сов. ДНФ, - это формула вида:

Утверждение о единственности Сов. ДНФ Любая булева функция, кроме константы 0, представима cовершенной дизъюнктивной нормальной формой, и она единственна для данной функции. Алгоритм построения Сов. ДНФ (по таблице истинности) вытекает из определения Сов. ДНФ и состоит в циклическом выполнении следующего шага: в векторе столбце значений функции выбирается очередная 1 и по набору значений аргументов этой строки формируется конъюнкция всех аргументов с соблюдением следующего правила: если i‑я компонента набора равна 0, то переменная xi входит в конъюнкцию в степени 0 (с инверсией), иначе в степени 1 (без инверсии); полученная конъюнкция добавляется в формулу как очередное слагаемое. Пример. Обратим внимание на тот факт, что нам впервые удалось от табличного способа задания функции перейти к формульному!

Утверждение о единственности Сов. КНФ Любая булева функция, кроме константы 1, представима cовершенной конъюнктивной нормальной формой, и она единственна для данной функции. Алгоритм построения Сов. КНФ по таблице истинности вытекает из определения Сов. КНФ и состоит в циклическом выполнении следующего шага: в векторе столбце значений функции выбирается очередной 0 и по набору значений аргументов этой строки формируется дизъюнкция всех аргументов с соблюдением следующего правила: если i‑я компонента набора равна 0, то переменная xi входит в дизъюнкцию в степени 1 (без инверсии), иначе в степени 0 (с инверсией); полученная дизъюнкция добавляется в Сов. КНФ как очередной сомножитель. Пример.

Элементарная конъюнкция и ДНФ Рассмотрим множество переменных x 1, x 2, . . . , xn. Элементарной конъюнкцией назовем конъюнкцию, в которую каждая переменная входит не более одного раза (с инверсией или без инверсии). Примеры. x 1 x 2 x 3 x 4, x 1 x 2 x 4 , x 3 - элементарные конъюнкции, x 1 x 2 x 4, x 1 x 3 - неэлементарные. В частности, 1 - это элементарная конъюнкция, не содержащая ни одной переменной. Число переменных, образующих элементарную конъюнкцию, назовем ее рангом. Пример. Ранг элементарной конъюнкции x 1 x 2 x 4 равен трем. Полной конъюнкцией назовем элементарную конъюнкцию, состоящую из всех переменных, т. е. конъюнкцию ранга n. Пример. При n = 4 конъюнкция x 1 x 2 x 3 x 4 - полная. Дизъюнктивной нормальной формой (ДНФ) назовем дизъюнкцию различных элементарных конъюнкций. Пример. x 1 x 2 x 4 x 1 x 2 x 3 x 4 x 3 - ДНФ. Очевидно, что совершенная ДНФ является частным случаем ДНФ. Длиной ДНФ назовем число конъюнкций в данной ДНФ. Рангом ДНФ назовем сумму рангов ее конъюнкций. Пример. Длина ДНФ из предыдущего примера равна трем, а ранг - восьми.