ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с

• Название: В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
• Дата: 12.09.2022
• Размер: 4.33 Mb.
• Имя файла: ДИСКРЕТНАЯ МАТЕМАТИКА (1).pdf
• Тип: Реферат; #673155
• страница: 21 из 25

5.3. Функциональная полнота систем булевых функций Функционально полным набором называется множество таких элементарных булевых функций {f
1
, f
2
, … , f
k
}, что произвольная булева функция f может быть записана в виде формулы через функции этого множества. Решение задачи формирования функциональной полных наборов элементарных функций с использованием принципов необходимости и достаточности основано на понятии замкнутого относительно операции суперпозиции класса функций. Операция суперпозиции заключается в подстановке вместо аргументов других булевых функций. Функция
h(x
1
,…, x
n
) = g(f
1
(x
1
,…, x
n
),…, f
k
(x
1
,…, называется суперпозицией функций g и f
1
,…, f
k
. Суперпозиция функций одного аргумента порождает функции одного аргумента. Суперпозиция функций двух аргументов дает возможность строить функции любого числа аргументов. Классом функций называется множество функций, обладающих общими свойствами. Класс булевых функций, функционально замкнутый по операции суперпозиции, есть множество функций, любая суперпозиция которых дает функцию, также принадлежащую этому множеству. Все элементарные функции подразделяются по своим свойствам на пять замкнутых классов
1) функции, сохраняющие 0;
2) функции, сохраняющие 1;
3) самодвойственные;
4) монотонные
5) линейные.
1. Булева функция называется функцией, сохраняющей 0, если на нулевом наборе аргументов она равна нулю, те. f(0,0,…,0) = 0. Элементарными функциями, сохраняющими 0, являются восемь первых функций. Булева функция называется функцией, сохраняющей 1, если на единичном наборе аргументов она равна единице, те. f(1,1,…,1) = 1. Элементарными функциями, сохраняющими 1, являются функции сне- четными индексами f
1
, f
3
, f
5
, f
7
, f
9
, f
11
, f
13
, f
15 3. Булева функция называется самодвойственной, если на каждой паре противоположных наборов аргументов она принимает противоположные значения, те.
)
,...,
,
(
)
,...,
,
(
2 1
2 1
n
n
x
x
x
f
x
x
x
f

. Элементарными само- двойственными функциями являются функции f
3
, f
5
, f
10
, f
12

250 4. Булева функция называется монотонной, если при возрастании набора аргументов значения этой функции не убывают. Набор аргументов считается больше другого набора, если в нем есть хотя бы один аргумент, больший по значению, и нет ни одного, меньшего по значению. Если у двух наборов есть аргументы и больше, и меньше, то наборы считаются несравнимыми. У функций двух переменных несравнимыми являются наборы 0, 1 и 1, 0. Таким образом, проверку на монотонность для каждой элементарной функции надо провести по двум путями. Монотонными функциями являются f
0
, f
1
, f
3
, f
5
, f
7
, f
15 5. Булева функция называется линейной, если ее можно представлять в виде f(x
1
,x
2
,…,x
n
) = a
n

x
n

…

a
2

x
2

a
1

x
1

a
0
, где a
i

{0, 1};
i = 0, Существуют восемь линейных элементарных функций (табл. 5.5). Таблица 5.5 Линейные элементарные булевы функции
а
2
а
1
а
0
Линейные функции
0 0
0 0 = f
0 0
0 1
1 = f
15 0
1 0
x
1
= f
3 0
1 1
x
1

1 = f
12 1
0 0
x
2
= f
5
1 0
1
x
2

1 = f
10 1
1 0
x
2

x
1
= f
6 1
1 1
x
2

x
1

1 = Для того, чтобы набор элементарных булевых функций был функционально полным, необходимо и достаточно, чтобы в него входили
1) хотя бы одна функция, не сохраняющая 0;
2) хотя бы одна функция, не сохраняющая 1;
3) хотя бы одна не самодвойственная;
4) хотя бы одна немонотонная) хотя бы одна нелинейная При формировании функционально полных наборов элементарных функций целесообразно рассматривать только двенадцать функций из шестнадцати, так как пары f
2
и f
4
, f
3
и f
5
, f
10
и f
12
, f
11
и f
13
представляют собой с точностью до нумерации аргументов одну функцию запрет, повторение, отрицание и импликацию соответственно.

251 Для удобства подбора функционально полных наборов используют таблицу (табл. 5.6), в которой каждой строке соответствует элементарная функция, а столбцам — свойства функций несохраняемость 0, не- сохраняемость 1, несамодвойственность, немонтоность и нелинейность. На пересечении строки и столбца ставится крестик, если функция, соответствующая строке, обладает свойством, соответствующим столбцу. Признаком функциональной полноты являются наличие крестика в каждом столбце таблицы хотя бы для одной из составляющих систему булевых функций. Из таблицы видно, что операции Пирса и Шеффера каждая в отдельности являются функционально полными наборами, а операция повторения не играет никакой роли при формировании функционально полных наборов. Таблица 5.6 Свойства элементарных булевых функций Функция Свойства
Несох- раняе- мость 0
Несох- раняе- мость 1
Несамо- двойственность Немо- нотон- ность Нелинейность Константа 0 (0) x x
Конъюнкция (f
1
) x x
Запрет (f
2
, f
4
) x x x x
Повторение (f
3
, f
5
)
Неравнозначность (f
6
) x x x
Дизъюнкция (f
7
) x x
Операция Пирса (f
8
) x x x x x
Равнозначность (f
9
) x x x
Отрицание (f
10
, f
12
) x x x
Импликация (f
11
, f
13
) x x x x
Операция Шеффера (f
14
) x x x x x
Константа 1 (f
15
) x x
5.4. Аналитические способы задания булевых функций Среди аналитических способов задания функций (задание функций формулами) широкое распространение получили совершенная дизъюнктивная нормальная форма, совершенная полиномиальная нормальная форма, совершенная конъюнктивная нормальная форма, дизъюнктивная нормальная форма, конъюнктивная нормальная форма, произвольная скобочная форма и полином Жегалкина.

252 Совершенная дизъюнктивная нормальная форма (СДНФ) представляет собой дизъюнкцию конституент единицы.
Конституентой единицы называется функция, принимающая значение только на единственном наборе.
Конституента единицы записывается как логическое произведение всех аргументов функции, некоторые из них могут быть с отрицаниями. Например, функция
4 3
2 1
x
x
x
x
f

является конституантой единицы и принимает значение 1 на единственном наборе 1001. Для того, чтобы получить аналитическое выражение в СДНФ функции, заданной таблично, нужно составить дизъюнкцию конституент единицы для тех наборов значений аргументов, для которых значение функции равно 1, причем символ любой переменной в некоторой кон- ституенте берется со знаком отрицания, если конкретное значение переменной в рассматриваемом наборе имеет значение 0. Пример 5.1. Для функций, заданных таблицей истинности (табл. 5.7),
СДНФ имеет вид
3 2
1 3
2 1
3 2
1 3
2 1
1
x
x
x
x
x
x
x
x
x
x
x
x
f




3 2
1 3
2 1
3 2
1 Таблица 5.7 Таблица истинности
x
1
x
2
x
3
f
1
f
2
0 0
0 0
0 0
0 1
1 0
0 1
0 1
0 0
1 1
0 1
1 0
0 1
0 1
0 1
0 1
1 1
0 0
1 1
1 1
1 0 Если в СДНФ заменить операции дизъюнкции операциями сложения по модулю 2, то равенство сохранится. Такая форма называется совершенной полиномиальной нормальной формой (СПНФ). Пример 5.2. Для функций, заданных таблицей истинности (см. табл.
5.7), СПНФ имеет вид
3 2
1 3
2 1
3 2
1 3
2 1
1
x
x
x
x
x
x
x
x
x
x
x
x
f




3 2
1 3
2 1
3 2
1 2
x
x
x
x
x
x
x
x
x
f




253 Совершенная конъюнктивная нормальная форма (СКНФ) представляет собой конъюнкцию конституент нуля.
Конституентой нуля называется функция, принимающая значение 0 на единственном наборе.
Конституента нуля записывается в виде дизъюнкции всех аргументов, некоторые из них могут быть с отрицаниями. Каждому набору соответствует своя конституента 0. Например, набору 0110 переменных
x
1
, x
2
, x
3
, x
4
соответствует конституента нуля
4 3
2 Для того, чтобы получить аналитическое выражение функции, заданной таблично, в СКНФ, нужно составить конъюнкцию конституент нуля для тех наборов значений аргументов, на которых значение функции равно 0, причем символ любой переменной в некоторой конститу- енте берется со знаком отрицания, если ее конкретное значение в рассматриваемом наборе равно 1. Пример 5.3. Для функций, заданных таблицей истинности (см. табл. 5.7), совершенная конъюнктивная нормальная форма имеет вид
)
)(
)(
)(
(
3 2
1 3
2 1
3 2
1 3
2 1
1
x
x
x
x
x
x
x
x
x
x
x
x
f









)
)(
)(
)(
)(
(
3 2
1 3
2 1
3 2
1 3
2 1
3 2
1 Кроме совершенных нормальных форм булевых функций существуют другие нормальные формы. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций. Элементарной конъюнкцией называется конъюнкция конечного числа различных между собой переменных, каждая из которых может быть с отрицанием. Рангом элементарной конъюнкции называется число переменных в данной конъюнкции.
Конституента единицы представляет собой элементарную конъюнкцию, ранг которой равен количеству аргументов функции. ДНФ может содержать элементарные конъюнкции различного ранга, например
2 3
1 3
2 3
2 Конъюнктивной нормальной формой (КНФ) называется конъюнкция элементарных дизъюнкций. Элементарной дизъюнкцией называется дизъюнкция конечного числа различных между собой переменных, каждая из которых может быть с отрицанием.

254 Рангом элементарной дизъюнкции называется число переменных в данной дизъюнкции.
Конституента нуля представляет собой элементарную дизъюнкцию, ранг которой равен количеству аргументов функции. КНФ может содержать элементарные дизъюнкции различного ранга, например
3 2
1 3
2 1
)
)(
(
x
x
x
x
x
x
f




. Кроме совершенных форм булевых функций существует произвольная скобочная форма (инфиксная запись, например
)
(
))
(
(
4 1
3 2
4 2
3 3
2 1
x
x
x
x
x
x
x
x
x
x
f





. Еще одно представление булевых функций получается с использованием операций конъюнкции

, сложения по модулю 2

и константы 1. Алгебра надмножеством булевых функций с бинарными операциями и

и константой 1 называется алгеброй Жегалкина. В алгебре Жегал- кина выполняются следующие соотношения
x
1

x
2
= x
2

x
1
;
(5.1)
x
1
(x
2

x
3
) = x
1
x
2

x
1
x
3
;
(5.2)
x
1

x
1
= 0;
(5.3)
x
1

0 = x
1
;
(5.4)
x
1
(x
2
x
3
) = (x
1
x
2
) x
3
;
(5.5)
x
1
x
2
= x
2
x
1
;
(5.6)
x
1
x
1
= x
1
;
(5.7)
x
1

1 = x
1
;
(5.8)
x
1

0 = 0.
(5.9) Отрицание и дизъюнкция выражаются так
1 1
1


x
x
;
(5.10)
2 1
2 1
2 1
2 1
2 1
1
)
1
)(
1
(
x
x
x
x
x
x
x
x
x
x









;
(5.11) Если в произвольной формуле алгебры Жегалкина раскрыть скобки и произвести всевозможные упрощения по соотношениям (5.1) — (5.9), то получится формула, имеющая вид суммы произведений, те. полинома по модулю 2. Такая формула называется полиномом Жегалкина для данной функции. От произвольной скобочной записи булевой функции или от нормальной формы всегда можно перейти к форме алгебры Жегал- кина и, следовательно, полиному Жегалкина, используя равенства
(5.10) и (5.11), а также равенство, вытекающее из (5.11): если f
1
f
2
= 0, то
f
1

f
2
= f
1

f
2
. Оно, в частности, позволяет заменять знак дизъюнкции знаком ―

‖ в случае, когда исходная формула — СДНФ.

255 Пример 5.4. Преобразование произвольной скобочной формы булевой функции в полином Жегалкина:
1 2
1 3
2 1
2 1
2 1
2 2
1 2
1 3
2 1
3 2
1 3
2 1
2 3
2 1
2 1
2 1
3 1
2 3
1 3
2 1
2 1
2 1
3 1
2 3
2 1
2 1
2 1
3 1
2 3
2 1
2 1
2 1
3 1
2 Пример 5.5. Преобразование СДНФ булевой функции в полином Же- галкина:
3 2
3 1
3 1
3 2
1 3
2 3
2 1
3 2
1 3
2 1
3 2
1 3
2 1
3 2
1 3
2 1
)
1
(
)
1
(
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x














5.5. Основные законы булевой алгебры и их следствия Основные законы булевой алгебры.
1. Коммутативность а)
1 2
2 1
x
x
x
x

; б)
1 2
2 1
x
x
x
x



2. Ассоциативность а)
3 2
1 3
2 1
)
(
)
(
x
x
x
x
x
x

; б)
)
(
)
(
3 2
1 3
2 1
x
x
x
x
x
x





3. Дистрибутивность конъюнкции относительно дизъюнкции
3 1
2 1
3 2
1
)
(
x
x
x
x
x
x
x



4. Дистрибутивность дизъюнкции относительно конъюнкции
)
)(
(
)
(
3 1
2 1
3 2
1
x
x
x
x
x
x
x




5. Идемпотентность: а)
x
xx

; б)
x
x
x


6. Двойное отрицание
x
x

7. Свойства константа б ) x

0 = 0 ; в ) x

1 = 1 ; где. Законы де Моргана а)
2 1
2 1
x
x
x
x


; б)
2 1
2 1
x
x
x
x


9. Закон противоречия
0

x
x
10. Закон "исключенного третьего Следствиями основных законов булевой алгебры являются правило склеивания, правило поглощения, правило вычеркивания и ряд других соотношений, позволяющих преобразовывать, в частности упрощать, формулы булевых функций.
1. Правила склеивания а)
1 2
1 2
1
x
x
x
x
x


; б)
1 2
1 2
1
)
)(
(
x
x
x
x
x



2. Правила поглощения а)
1 1
2 1
x
x
x
x


; б)
1 1
2 1
)
(
x
x
x
x


3. Правила вычеркивания а)
1 2
1 2
1
x
x
x
x
x



; б)
1 2
1 В булевой алгебре существует дизъюнктивное разложение Шеннона:
1 0
2 1
)
,...,
,...,
,
(
y
x
y
x
x
x
x
x
f
i
i
n
i


, где x
i
– переменная разложения
y
0
и y
1
– коэффициенты разложения
)
,...,
0
,...,
,
(
2 1
0
n
x
x
x
f
y

;
)
,...,
1
,...,
,
(
2 Дизъюнктивное разложение Шеннона позволяет выразить булеву функцию через переменную разложения (с отрицанием и без отрицания) и функции (коэффициенты разложения, зависящие от меньшего количества аргументов. Если выполнить разложение Шеннона булевой функции, заданной в любой аналитической форме, по всем переменным, то получим СДНФ этой функции.

257