Материал: Дискретная математика. учебное пособие. Горбунов В.В., Лапшина М.Л

, .

13. Для функций конъюнкция и дизъюнкция справедливы тождества: .

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

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

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

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

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

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

Например: — ДНФ.

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

Например: — КНФ.

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

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

.

2 ) Заменить знак отрицания, относящийся к выражениям типа или , знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:

.

3) Избавиться от знаков двойного отрицания.

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

Пример 4.1. Приведем формулу к ДНФ.

Решение.

Применим отрицание к переменным и сократим двойные отрицания:

.

Используем закон дистрибутивности, приведем формулу ДФН:

.

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

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

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

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

1. ДНФ не содержит двух одинаковых конъюнкций,

2. ни одна конъюнкция не содержит одновременно двух одинаковых переменных,

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

4. каждая конъюнкция содержит либо переменную х_i либо ее отрицание для всех переменных, входящих в формулу.

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

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

1. КНФ не содержит двух одинаковых дизъюнкций,

2. ни одна из дизъюнкций не содержит одновременно двух одинаковых переменных,

3. ни одна из дизъюнкций не содержит одновременно некоторую переменную и ее отрицание,

4. каждая дизъюнкция СКНФ содержит либо переменную х_i, либо ее отрицание для всех переменных, входящих в формулу.

Для построения СКДФ функции выписываем наборы такие, что f(x) = 1, составляется конъюнкция , а затем все эти конъюнкции соединяем знаком дизъюнкции.

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

V V…V ,

а затем все такие дизъюнкции соединяют знаком конъюнкции.

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

1. Каждая булева функция от «переменных, отличная от константы 0, имеет единственную СДНФ.

2. Каждая булева функция от п переменных, отличная от константы 1, имеет единственную СКНФ.

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

Задачи по теме «Булевы функции.»

Задача 1. Составьте таблицу истинности булевой функции трех переменных и найдите ее двоичный набор.

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

, , , , .

Последовательно составляются таблицы истинности всех указанных функций.

Таблица 24.

Лексикографическое упорядочение наборов в таблице истинности булевой функции позволяет задать функцию двоичным набором длины 2ⁿ, который будем обозначать буквой F. Двоичный набор данной функции F = 11111111. Отметим, что двоичный набор определяет булеву функцию в том и только в том случае, когда его длина есть степень двойки, а соответствующий показатель степени определяет число переменных данной функции.

Задача 2. Докажите тождественную истинность формулы .

Решение. Необходимо показать, что двоичный набор данной формулы F = 1111.

Составим таблицу истинности:

Таблица 25.

Задача 3. Докажите эквивалентность функций: и .

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

Таблица 26.