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

⇐ ПредыдущаяСтр 2 из 8Следующая ⇒

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сформулируем следующие теоремы:

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

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

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

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

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

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

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

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

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

Многочлены Жегалкина

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

Многочленом Жегалкина называется многочлен, являющийся суммой константы и различных одночленов, в которые каждая из переменных входит не выше, чем в первой степени.

Многочлен Жегалкина константы равен самой же константе; многочлен Жегалкина булевой функции одной переменной ; многочлен Жегалкина булевой функции двух переменных

многочлен Жегалкина булевой функции трех переменных

и т. д. Коэффициенты и свободный член принимают значения 0 или 1, а число слагаемых в формуле равно 2^п, где п — число переменных. Знак ⊕ — сумма Жегалкина или сумма по модулю два.

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

Сформулируем алгоритм построения многочлена Жегалкина.

Выше было указано, что любую функцию, отличную от константы 0, можно представить в виде СДНФ. Если сравним таблицы истинности дизъюнкции и суммы по модулю два, видим, что они отличаются только последней строкой, т. е. на наборе 11. Так как в СДНФ на каждом наборе только одна конъюнкция равна 1, то все дизъюнкции можно заменить суммами по модулю два. Кроме того, известно, что . На этом и основан первый алгоритм построения многочлена Жегалкина:

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

2. Составляем СДНФ.

3. В СДНФ каждый знак дизъюнкции меняем на знак суммы Жегалкина.

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

5. В полученной формуле каждое отрицание заменяем на .

6. Раскрываем скобки в полученной формуле, содержащей только функции ∧ и ⊕ и константу 1.

7. Приводим подобные члены, используя тождество .

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

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

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

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

На этом основан алгоритм определения линейности (или нелинейности) булевой функции.

1. По таблицам истинности булевой функции и выше указанным формулам находим коэффициенты:

2. Выписываем многочлен и проверяем, задаёт ли он эту функцию. Для этого строим таблицу истинности многочлена и сравниваем её с таблицей истинности функции .

Если таблицы истинности совпадают, то функция линейная и – её многочлен Жегалкина. В противном случае функция нелинейна.

МНОЖЕСТВА И ОТОБРАЖЕНИЯ

Понятие множества

Любое понятие дискретной математики можно определить с помощью понятия множества. Под множеством понимают объединение в одно общее объектов, хорошо различаемых нашей интуицией или нашей мыслью. Таково интуитивное определение понятия множества, данное основателем теории множеств Георгом Кантором. Это понятие в математике является первичным и, следовательно, не имеет строгого определения. Объекты, составляющие множество, будем называть его элементами. Множества будем обозначать прописными буквами латинского алфавита: А, В, С,..., а элементы множеств — строчными буквами а, b, с,.... Основное отношение между элементом а и содержащим его множеством А, обозначается так: (а принадлежит А). Если а не является элементом множества А, то пишут (а не принадлежит А). Некоторые множества имеют общепринятые обозначения: N — множество натуральных чисел; R — множество действительных чисел; Z — множество целых чисел.

2.2. Способы задания множеств

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

Первый способ мы назовем описанием множества, а второй способ — перечислением множества. Например, обозначение читается: «элементы множества U, обладающие свойством α » — это описание множества. Элементы перечисляемого множества принято заключать в скобки: {1, 2, 3,... } — множество натуральных чисел; {2, 4, 6,... } — множество четных чисел. Под многоточием в первом случае подразумеваются все последующие натуральные числа, а во втором — четные.

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

Подмножества

Множество, состоящее из некоторых элементов другого множества, называется подмножеством этого последнего множества. С целью изучения всех подмножеств данного множества введем следующую терминологию. Исходное множество будем называть универсальным множеством; подмножества, содержащие один элемент, будем называть единичными множествами; множество, вовсе не содержащее никаких элементов, будем называть пустым множеством и обозначать 0.

В качестве примера возьмем универсальное множество U, состоящее из трех элементов {а, b, с}. Собственные подмножества U — это множества, которые содержат некоторые, но не все элементы U. Этими подмножествами являются три множества из двух элементов {а, b}, {а, с}, {b, с} и три единичных множества {а}, {b}, {с}.

Будем считать подмножеством множества U и пустое множество 0, не содержащее элементов U.

Другими словами, множество А называется подмножеством множества В (обозначаем А ⊂ В), если все элементы множества А принадлежат В. Это означает справедливость следующего утверждения: для любого элемента а, если а ∊ А, то а ∊ В при условии А ⊂ В. Будем говорить также, что множество А содержится в Bили имеется включение множества А в B. Множества А и В называются равными или совпадающими (обозначается А = В), если они состоят из одних и тех же элементов, т. е. если А ⊂ В и

В ⊂ А. Таким образом, чтобы доказать равенство множеств, требуется установить два включения.

Операции над множествами

В первой главе были рассмотрены способы, которыми из данных высказываний могут быть образованы новые высказывания. Теперь мы будем рассматривать аналогичный процесс — образование новых множеств из данных множеств. Мы будем предполагать, что каждое из множеств, которое мы используем в этом процессе, является подмножеством некоторого универсального множества, и будем требовать, чтобы вновь образованное множество было подмножеством того же самого универсального множества. Как и всегда, мы можем задавать вновь образованное множество или путем описания, или путем перечисления.

Следует провести аналогию между логическими операциями и операциями над множествами.

Отрицание	Дополнение
Конъюнкция	Пересечение
Дизъюнкция	Объединение
Импликация	Разность

Чтобы нагляднее представить эти операции, изобразим их на диаграмме, называемой диаграммой Эйлера-Венна. Пусть прямоугольник обозначает универсальное множество, а круги внутри прямоугольника — подмножества.

Дополнением к множеству А называется множество элементов, которые не содержатся в А. Обозначают его и читают «дополнение множества А к U».

Пересечением множеств A и В называется множество элементов, принадлежащих и А и В. Обозначают A∩ Bи читают «пересечение А и B».

Если А и В — непустые множества, пересечение которых пусто, т. е. A∩ B=Ø, то их называют непересекающимися множествами.

Объединением множестве и В называется множество элементов, принадлежащих либо А, либо В (либо обоим). Обозначают A ∪ В и читают «объединение А и В».

Разностью множестве и В называется множество элементов, принадлежащих А и не принадлежащих В. Обозначают A\B ичитают «разность Aи B».

⇐ Предыдущая 123 4 5 6 7 8 Следующая ⇒