Файл: 1. Булевы функции и способы их задания.pdf

1. Булевы функции и способы их задания.
Определение. Набор ̃ (
), где
{ }
̅̅̅̅̅̅̅̅̅ называется булевым или двоичным набором (вектором). Элементы набора называются компонентами или координатами. Число - длиной набора ̃.
Определение. Множество всех двоичных наборов длины образует мерный булев куб (
)
Пример 1. Изобразить графически для
{( ) ( )} –состоит из двух наборов, каждый из которых
можно изобразить точкой на прямой ОХ.
рис.1
{( ) ( ) ( ) ( )} –состоит из четырех наборов,
каждый из которых можно изобразить точкой на плоскости ХОY,
являющейся вершиной единичного квадрата с соответствующими
координатами.
рис.2
{( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )} –
состоит из восьми наборов, каждый из которых можно изобразить
точкой пространстве ХYZ, являющейся вершиной единичного куба с
соответствующими координатами

рис.3
Замечание 1. Число различных двоичных наборов длины равно
(
)
Доказательство:
Рассмотрим двоичный набор ̃ (
)
длины n. Поскольку
каждая компонента может принимать одно из двух возможных
значений либо 0 либо 1, то для заполнения каждой из nпозиций
двоичного набора имеется 2 варианта. Таким образом, число всех
возможных вариантов (
)
⏟
Определение. Каждому двоичному набору ̃ (
) можно взаимно однозначно сопоставить целое неотрицательное число ( ̃) такое что:
( ̃) ∑ называемое номером набора. ( ̃)
.
Например, для наборов из трех переменных номера будут такими:
( )
( )
( )
( )
( )
( )
( )
( )

Расположение двоичных наборов одной длины по порядку возрастания их номеров называется стандартным или лексикографическим расположением наборов.
Определение. Функция (
) областью определения которой является -мерный булев куб (
), а областью значениймножество
{ } называется булевой функцией или функцией алгебры логики.
Множество всех булевых функций зависящих от n переменных принято обозначать
( )
Способы задания булевых функций.
1. Табличный способ задания (таблица истинности)
Любую булеву функцию (
) можно представить в виде таблицы состоящей из двух столбцов: в первом в лексикографическом порядке расположены все двоичные наборы длины (всего строк), во втором в каждой строке записано значение, которое функция принимает на этом наборе
(
)
( )
( )
( )
( )
( )
( )
Пример 2. Табличный способ задания функции двух переменных
(
)
Наборы в первом столбце расположены в порядке возрастания номеров:
( )
( )
( )

( )
Во втором столбце расположены значения, которые функция принимает на соответствующих наборах.
( )
( )
( )
( )
2. Векторный способ задания булевой функции. Вектор значений
функции.
Поскольку в таблице истинности различных функций - переменных первый столбец всегда одинаковый, то функцию можно однозначно определить вектором соответствующим второму столбцу таблицы истинности:
̃ (
)
Где координата равна значению функции на наборе с номером
Пример 3. Вектор значений функции из примера 2 будет равен
̃ ( )
Замечание 2. |
( )|
Доказательство: так как вектор значений
̃ (
)
функции n-переменных имеет
координат, каждая из которых
может принимать лишь два возможных значения: либо 0 либо 1,
тогда число различных наборов длины
будет равно
. Значит и
различных булевых функций от n-переменных будет
, поскольку
между булевой функций и ее вектором значений имеется взаимно
однозначное соответствие.
Пример 4. Функция задана вектором значений
̃ ( )
Найдите таблицу истинности функции .
Поскольку в векторе значений функции восемь координат и
, то значит это функция от 3-х переменных ( ). Запишем таблицу истинности функции: первый столбик – все двоичные наборы трех

переменных расположенные в лексикографическом порядке, во второй столбик сверху вниз запишем вектор значений функции.
Таблица истинности данной функции:
̃
3. Задание булевой функции с помощью носителя.
Определение. Множество всех наборов ̃ (
) на которых функция (
) принимает значение 1 называется носителем функции
{ ̃
| ( ̃) }
Определение. Множество всех наборов ̃ (
) на которых функция (
) принимает значение 0 называется дополнением носителя функции
̅
̅
{ ̃
| ( ̃) }
Поскольку
̅
, то если мы перечислим все наборы на которых функция принимает значение 1 (т.е. зададим носитель) – это будет достаточно для однозначного задания булевой функции.
Пример 5. Найти носитель функции из примера 2.
{( ) ( )},
̅
{( ) ( )}
Пример 6. Найти носитель функции из примера 4.
{( ) ( ) ( ) ( )},
̅
{( ) ( ) ( ) ( )}
4. Геометрический способ задания булевой функции.
Этот способ удобно применять для функций зависящих не более чем от
4-х переменных. Для функций 1, 2,3 -х переменных на булевом кубе

отмечают (например "жирными" точками) вершины соответствующие наборам принадлежащим носителю функции. Для функций 4-х переменных используют карту Карно (см.)
Пример 7. Изобразить геометрически функции из примера 2 и из
примера 4.
̃ ( )
̃ ( )
рис.4
5. Задание функции с помощью формулы.
Двоичные функции одной переменной
Существует всего 4 двоичные функции зависящие от одной переменной
|
( )|
Приведем таблицы истинности этих функций
( )
( )
( )
( )
( ) – тождественный нуль
( ) – тождественная единица
( ) –тождественная функция
( ) ̅ – функция отрицание, или инверсия
Двоичные функции двух переменных
Двоичных функций двух переменных всего 16
|
( )|

Приведем таблицы истинности некоторых из них
|
1. или – функция конъюнкция, логическое умножение, логическое «и» ( ).
2.
– функция дизъюнкция, логическое сложение, логическое
«или» ( )
3.
– функция сложение по модулю 2, «исключающее или».
Значение функции равно остатку от деления алгебраической суммы чисел и на 2.
4.
– функция эквивалентность, логическое тождество. Функция принимает значение 1, на наборах где . Заметим, что значение функции «эквивалентность» на каждом наборе противоположно значению функции «сложение по модулю 2». Значит функцию
«эквивалентность» можно выразить формулой:
̅̅̅̅̅̅
5.
– функция импликация, «логическое следование». Для запоминания значений, которые принимает функция можно использовать правило: «из лжи может следовать все что угодно из истины следует только истина» (0-ложь, 1-истина)
6.
| – штрих Шеффера, «не и»
|
̅̅̅̅̅̅
7.
– стрелка Пирса, «не или»
̅̅̅̅̅̅̅
Перечисленные функции одной и двух переменных называются элементарными булевыми функциями. Другие двоичные функции двух и более переменных можно выразить через элементарные булевы функции с помощью формул.
Если функция задана формулой, то говорят что, формула реализует или представляет данную функцию.
Формулы, реализующие одну и туже функцию называются эквивалентными или равносильными.

Порядок выполнения действий в формулах:
1. Сначала выполняются действия в скобках
2. Функция «отрицание переменной» выполняется прежде других булевых функций. При этом учитывается, что если отрицание относится к некоторой функции, то скобки вокруг нее могут быть опущены, например: ( )
̅̅̅̅̅̅̅̅̅
̅̅̅̅̅̅̅.
3. выполняется раньше чем и (логическое умножение выполняется раньше сложения)
Пример 8. Для функции заданной формулой ( ) ( )
̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ найти вектор значений ̃.
Искомая функция является функцией трех переменных ( ).
Определим порядок действий: 5
̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
( ) ( )
Сначала выполняем действия в скобках и , потом логическое умножение , затем логическое сложение , функция инверсия выполняется последней так как относится к формуле, а не к переменной.
Каждое получившихся из пяти действий соответствует элементарной булевой функций:
̅
Запишем результаты этих действий в общую таблицу:
̅
Последний столбец таблицы истинности является вектором значений искомой функции

̃( ) ( )
Основные законы алгебры логики.
1. Коммутативность (переместительный закон)
Функция означает любую из функций |
Отметим, из всех элементарных булевых функций, только функция импликация не является перестановочной: , все остальные функции не зависят от порядка переменных, например: и
2. Ассоциативность (сочетательный закон)
( ) ( ), где { }
3. Дистрибутивность (распределительный закон)
( )
( )
( )( )
4. Законы де Моргана
̅̅̅̅̅̅ ̅ ̅
̅̅̅̅̅̅̅ ̅ ̅
5. Закон двойного отрицания
̿
6. Закон идемпотентности и
7. Закон противоречия
̅
8. Закон исключения третьего
̅
9. Свойства констант
̅
10. Закон поглощения
( )
11. Закон склеивания
̅
12. Законы сложения по модулю два

̅
̅
В справедливости этих законов, можно убедиться путем сопоставления таблиц истинности для левой и правой частей равенств.
2. Специальные представления булевых функций.
Дизъюнктивная и конъюнктивная нормальные формы
Введем обозначение
{
̅ то есть
̅ и
Определение. Логическое произведение переменных или их отрицаний называется элементарной конъюнкций
Например,
,
̅
,
̅
̅
– элементарные конъюнкции.
Определение. Логическая сумма переменных и их отрицаний называется элементарной дизъюнкцией например:
,
̅
,
̅
̅
– элементарные дизъюнкции.
Замечание 1. В элементарную конъюнкцию или дизъюнкцию не может
одновременно входить переменная и ее отрицание. (
̅
̅
не
является элементарной конъюнкцией).
Определение. Количество переменных и отрицаний переменных входящих в элементарную конъюнкцию (дизъюнкцию) называется ее рангом (обозначение )
Например, для ранг равен 1
( ), для
̅
̅
ранг равен 3 ( )

Определение. Дизъюнктивная нормальная форма ( )– это формула, в которой функция представлена в виде дизъюнкции элементарных конъюнкций.
Определение. Конъюнктивная нормальная форма ( )– это формула, в которой функция представлена в виде конъюнкции элементарных дизъюнкций.
Определение. Сумма всех рангов элементарных конъюнкций
(дизъюнкций) входящих в форму называется рангом формы (или сложностью формы)
Совершенная дизъюнктивная нормальная форма (СДНФ)
Определение. Представление функции в виде дизъюнкции элементарных конъюнкций построенных по всем наборам принадлежащим носителю функции называется совершенной дизъюнктивной нормальной формой
(СДНФ)
(
)
̃
Алгоритм построения СДНФ.
1. Находим наборы
̃ (
) входящие в носитель функции
, такие что (
)
2. Для каждого набора составляем соответствующую ему элементарную конъюнкцию
̃
3. Соединяем все полученные конъюнкции знаком
, получившаяся форма является СДНФ
̃
̃
Пример 1. Найти СДНФ функции заданной вектором значений
̃ ( )
Выпишем таблицу истинности данной функции ( ).
Подчеркнем наборы принадлежащие носителю функции, по каждому из этих наборов составляем элементарную конъюнкцию
̃
̅ ̅ ̅
̅ ̅

̅ ̅
̅
Составляем СДНФ
̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅
Теорема 1. Любая булева функция, не являющаяся константой, может быть представленная СДНФ.
Замечание 1.
|
| , где |
|- число наборов в носителе.
Доказательство. Каждая из элементарных конъюнкций, входящих в
СДНФ имеет ранг n, число таких конъюнкций равно числу наборов в
носителе функции, следовательно
|
| .
Совершенная конъюнктивная нормальная форма (СКНФ)
Определение. Представление функции в виде конъюнкции элементарных дизъюнкций построенных по всем наборам принадлежащим дополнению носителя функции называется совершенной конъюнктивной нормальной формой (СКНФ)
(
)
̃
̅
(
̅
̅
̅
)
Алгоритм построения СКНФ:
1. Находим наборы
̃ (
) входящие в дополнение носителяфункции
̅
, т.е. такие что (
) .
2. Для каждого набора составляем соответствующую ему элементарную дизъюнкцию
̃
̅
̅
̅
3. Соединяем все полученные дизъюнкции знаком
, получившаяся форма является СКНФ
̃
̅
̃
Пример 2. Найти СКНФ функции заданной вектором значений
̃ ( ) из примера 1.

Подчеркнем наборы принадлежащие дополнению носителю функции, по каждому из этих наборов составляем элементарную дизъюнкцию
̃
̅
̅
̅
̅
̅
̅
̅
̅ ̅
̅
̅
̅
̅ ̅
Составляем СДНФ
( ̅ )( ̅ ̅)( ̅ ̅)
Теорема 2. Любая булева функция, не являющаяся константой, может быть представленная как СКНФ.
Замечание 2.
|
̅
| , где |
̅
|- число наборов принадлежащих дополнению носителя.
Замечание 3. Если функция является тождественной константой ( ̃) или ( ̃) , ее тоже можно представить в виде суперпозиции переменной, отрицания переменной, , .
Например, возможны следующие представления: ̅ и ̅
Многочлен Жегалкина
Определение. Формула вида
( ̃) называется многочленом Жегалкина.
Другими словами это сумма по модулю два всех возможных элементарных конъюнкций, не содержащих отрицаний.
- либо 0 либо 1
Теорема 3 (Жегалкин И.И.). Любая булева функция представима в виде многочлена Жегалкина причем единственным образом (с точностью до перестановки слагаемых).

Рассмотрим два алгоритма для нахождения многочлена Жегалкина.
Алгоритм 1 построения многочлена Жегалкина (посредством СДНФ)
1. В СДНФ функции заменить все символы на символы .
2. Выносим за скобки одинаковые сомножители и упрощаем формулу, применяя закон: ̅ ( ̅) (так как ̅ ).
3. Все отрицания переменных
̅
заменяем на выражения
4. Раскрываем скобки, применяя сочетательный и распределительный законы алгебры логики, приводим подобные члены, вычеркивая одинаковые пары слагаемых, поскольку .
5. Полученный в результате преобразований многочлен будет многочленом Жегалкина для данной функции.
Пример 3. Найти многочлен Жегалкина для функции из примера 1, используя СДНФ.
В примере 1 мы нашли СДНФ для ̃ ( )
̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅
1. Заменяем знак на знак
̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅
2. Вынесем за скобки общие множители и упростим формулу, учитывая что ̅
̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅( ̅ ) ̅ ̅ ( ̅ ) ̅ ̅ ̅ ̅
3. Заменим все отрицания переменных
̅
и раскроем скобки
̅ ̅ ̅ ̅ ( )( ) ( )( )
( ) ( )
Вычеркиваем одинаковые пары слагаемых, так как
Алгоритм 2 построения многочлена Жегалкина (метод треугольника)
1. Выписываем левый столбец таблицы истинности (он одинаков для всех функций переменных)
2. Вектор значений функции выписываем горизонтально в первую строку, т.е. около набора из всех нулей.