Функционально замкнутые классы. Специальные классы булевых функций

Сентябрь 12, 2022

Главная
Математика
Функционально замкнутые классы. Специальные классы булевых функций

Содержание

2. Специальные классы булевых функций Американский математик Эмиль Пост ввел в рассмотрение следующие замкнутые классы булевых функций:
3. Класс функций, сохраняющих константу 0 Определение. Говорят, что функция сохраняет константу 0, если f(0,0,…,0)=0 Примеры: f(x,y)=x⊕y
4. Определение. Говорят, что функция сохраняет константу 1, если f(1,1,…,1)=1 Примеры: f(x,y)=x~y f(x,y)=x·y Класс функций, сохраняющих константу
5. Двойственность Пусть f(x1, x2, …, xn ) – булева функция. Двойственной к ней называется функция f*,
6. Класс самодвойственных булевых функций Определение. Булева функция f(x1,…,xn) самодвойственна (принадлежит классу S), если она равна двойственной
7. Пример самодвойственной функции f(x,y,z)=xy+yz+xz
8. Алгоритм распознавания самодвойственной функции, заданной таблицей истинности для проверки самодвойственности булевой функции можно не получать двойственную
9. Являются ли функции f(x,y,z), g(x,y,z), h(x,y,z) самодвойственными? Задача:
10. Сравнимые наборы Два набора и называются сравнимыми ( ), если Запись означает, что набор α предшествует
11. Класс монотонных функций Определение. Булева функция f(x1, …, xn) называется монотонной (принадлежит классу M), если для
12. Является ли функция монотонной? Из элементарных булевых функций монотонными являются, например, конъюнкция и дизъюнкция. Не являются
13. Класс линейных функций Определение. Булева функция называется линейной (принадлежит классу L), если ее полином Жегалкина линеен.
15. Функциональная полнота системы булевых функций
16. Определение ФПС Определение. Множество функций N называется функционально полной системой (ФПС), если любая булева функция представима
17. Примеры ФПС Пример 1. Множество N1={&,+,–} является функционально полной системой, так как любую булеву функцию, кроме
18. Теорема о двух функционально полных системах Теорема. Если даны два множества N1 и N2 булевых функций
19. Пример. N1={&,+,–}, N2={&, –}. Как показано ранее, N1 – ФПС. Конъюнкция и инверсия содержатся в N2,
20. Задание: Докажите, что система функций {¬, v} является полной. Пусть f1(x1) = x1 f2(x1, x2) =
21. Существует функционально полная система, состоящая из одной булевой функции. Штрих Шеффера (И-НЕ) – x1 | x2
22. Доказательство x1 | x2 = x1 v x2 или x1 | x2 = x1 & x2
23. Стрелка Пирса (ИЛИ-НЕ) – x1 ↓ x2 Функция стрелка Пирса является полной. x1 ↓ x2 =
24. Теорема Поста Теорема (о полноте). Для того, чтобы система булевых функций Д была полной, необходимо и
25. Таблицы Поста В тех задачах, где требуется выяснить, является ли данная система {f1 f2, …, fn}
26. Пример. Выяснить, являются ли следующие системы булевых функций полными. Являются ли следующие системы булевых функций базисами.
29. Скачать презентацию

Слайд 2

Специальные классы булевых функций
Американский математик Эмиль Пост ввел в рассмотрение следующие

замкнутые классы булевых функций:
Функции, сохраняющие константу ноль T0 ;
Функции, сохраняющие константу один T1;
Самодвойственные функции S ;
Монотонные функции M ;
Линейные функции L .

Слайд 3

Класс функций, сохраняющих константу 0
Определение. Говорят, что функция сохраняет константу 0,

если f(0,0,…,0)=0
Примеры:
f(x,y)=x⊕y
f(x,y)=x·y

Слайд 4

Определение. Говорят, что функция сохраняет константу 1, если f(1,1,…,1)=1
Примеры:
f(x,y)=x~y
f(x,y)=x·y
Класс функций,

сохраняющих константу 1

Слайд 5

Двойственность
Пусть f(x1, x2, …, xn ) – булева функция. Двойственной к ней называется функция f*,

которая на противоположных наборах имеет значения, противоположные значениям функции f.

ПРИМЕР

(x~y)*=x⊕y

(x·y)*=x+y

Слайд 6

Класс самодвойственных булевых функций
Определение. Булева функция f(x1,…,xn) самодвойственна
(принадлежит классу S), если

она равна двойственной себе, то есть f(x1, …, xn) = f*(x1, …, xn)
Пример: f(x,y,z)=xy+yz+xz

Число различных самодвойственных булевых функций, зависящих от n переменных, равно 22n –1.

Слайд 7

Пример самодвойственной функции
f(x,y,z)=xy+yz+xz

Слайд 8

Алгоритм распознавания самодвойственной функции, заданной таблицей истинности
для проверки самодвойственности булевой функции

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

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

Слайд 9

Являются ли функции f(x,y,z), g(x,y,z), h(x,y,z) самодвойственными?
Задача:

Слайд 10

Сравнимые наборы
Два набора и называются сравнимыми ( ), если
Запись означает, что

набор α предшествует набору β.
Например, (0,0,1) (0,1,1). А наборы (0,1,0) и (1,0,0) несравнимы

Слайд 11

Класс монотонных функций
Определение. Булева функция f(x1, …, xn) называется монотонной (принадлежит классу M), если

для любой пары наборов α и β таких, что α β, выполняется условие монотонности: f(α)≤ f(β)

Пример: f(x,y)=x·y
f(x,y)=x+y

Слайд 12

Является ли функция монотонной?
Из элементарных булевых функций монотонными являются, например, конъюнкция

и дизъюнкция.
Не являются монотонными, например, штрих Шеффера и стрелка Пирса.

Теорема Булева функция, имеющая дизъюнктивную нормальную форму, не содержащую отрицаний, является монотонной функцией, отличной от 0 и 1.

Слайд 13

Класс линейных функций
Определение. Булева функция называется линейной (принадлежит классу L), если ее полином Жегалкина

линеен.

Из всех 16 булевых функций двух аргументов f(x1, x2) только 8 функций (22+1) принадлежат классу L: 0, 1, ⊕ , ~ , тождественные функции x1 и x2 и их инверсии x 1 и x 2

x+y=x⊕y⊕xy x∼y=1⊕x⊕y x→y=1⊕x⊕xy x↓y=1⊕x⊕y⊕xy x|y=1⊕xy

Слайд 14

Слайд 15

Функциональная полнота системы булевых функций

Слайд 16

Определение ФПС
Определение. Множество функций N называется функционально полной системой (ФПС), если любая булева функция

представима суперпозицией функций из N

Определение . Система булевых функций {f1 f2, …, fn} называется функционально полной, если произвольная булева функция может быть выражена через функции f1 f2, …, fn.

Слайд 17

Примеры ФПС
Пример 1. Множество N1={&,+,–} является функционально полной системой, так как любую

булеву функцию, кроме константы 0, можно представить совершенной ДНФ, то есть суперпозицией функций из N1 а константу 0 – формулой xx .
Пример 2. Множество N2={&,⊕,1} является ФПС, так как любую булеву функцию можно представить полиномом Жегалкина, то есть суперпозицией функций из N2, а константу 0 – формулой 1⊕1

Слайд 18

Теорема о двух функционально полных системах
Теорема. Если даны два множества N1 и N2 булевых

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

Пусть система {f1 f2, …, fn} — полна и любая из функций
f1, f2, …, fn может быть выражена через функции g1 g2, …, gn.
Тогда система {g1 g2, …, gn} также полна.

Слайд 19

Пример. N1={&,+,–}, N2={&, –}.
Как показано ранее, N1 – ФПС. Конъюнкция и инверсия содержатся

в N2, а дизъюнкция представима суперпозицией функций из N2:
x+y = x+y = x·y , значит, N2 – ФПС.

Слайд 20

Задание: Докажите, что система функций {¬, v} является полной.
Пусть
f1(x1) = x1

f2(x1, x2) = x1 + x2 f3(x1, x2) = x1 & x2
g1(x1) =x1 g2(x1, x2) = x1 + x2
Выразим f1, f2, f3 через g1, g2
f1(x1) = g1(x1) f2(x1, x2) = g2(x1, x2)
Используем закон де Моргана
f3(x1, x2) = x1 & x2 = x1 + x2 = g1(g2(g1(x1), g1(x2)))

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

Любая (сколь угодно сложная) булева функция может быть выражена через две функции {¬, v} или {¬, &}.

Слайд 21

Существует функционально полная система, состоящая из одной булевой функции.
Штрих Шеффера (И-НЕ)

– x1 | x2

Функция штрих Шеффера является базисом.

Слайд 22

Доказательство
x1 | x2 = x1 v x2 или x1 | x2

= x1 & x2
Тогда x1 = x1 & x1 = x1 | x1
x1 + x2 = x1 + x2 = x1&x2 = x1 | x2 = (x1 | x1) | (x2 | x2)
x1 & x2 = x1 & x2 = x1 | x2 = (x1 | x2) | (x1 | x2)

Таким образом, мы выразили через функцию штрих Шеффера функции {¬, &, v}.
Следовательно, система, состоящая только из функции штрих Шеффера, полна.

Слайд 23

Стрелка Пирса (ИЛИ-НЕ) – x1 ↓ x2
Функция стрелка Пирса является полной.
x1

↓ x2 = x1 & x2 или x1 ↓ x2 = x1 + x2
Тогда x1 = x1 + x1 = x1 ↓ x1
x1 + x2 = x1 + x2 = x1 ↓ x2 = (x1 ↓ x2) ↓ (x1 ↓ x2)
x1 & x2 = x1 & x2 = x1 + x2 = (x1 ↓ x1) ↓ (x2 ↓ x2)

Слайд 24

Теорема Поста
Теорема (о полноте). Для того, чтобы система булевых функций Д была

полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти замкнутых классов T0, T1, S, M, L.

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

Слайд 25

Таблицы Поста
В тех задачах, где требуется выяснить, является ли данная система

{f1 f2, …, fn} булевых функций полной, будем составлять таблицы, которые называются таблицами Поста. Данные таблицы имеют следующий вид.

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

Слайд 26

Пример. Выяснить, являются ли следующие системы булевых функций полными. Являются ли

следующие системы булевых функций базисами.

D2={x ⊕y ⊕z, x&y, 0, 1}

Слайд 27

Функционально замкнутые классы. Специальные классы булевых функций

Содержание

Специальные классы булевых функцийАмериканский математик Эмиль Пост ввел в рассмотрение следующие

Класс функций, сохраняющих константу 0Определение. Говорят, что функция сохраняет константу 0,

Определение. Говорят, что функция сохраняет константу 1, если f(1,1,…,1)=1Примеры: f(x,y)=x~yf(x,y)=x·yКласс функций,

Двойственность Пусть f(x1, x2, …, xn ) – булева функция. Двойственной к ней называется функция f*,

Класс самодвойственных булевых функций Определение. Булева функция f(x1,…,xn) самодвойственна (принадлежит классу S), если

Пример самодвойственной функцииf(x,y,z)=xy+yz+xz

Алгоритм распознавания самодвойственной функции, заданной таблицей истинности для проверки самодвойственности булевой функции

Являются ли функции f(x,y,z), g(x,y,z), h(x,y,z) самодвойственными?Задача:

Сравнимые наборыДва набора и называются сравнимыми ( ), если Запись означает, что

Класс монотонных функцийОпределение. Булева функция f(x1, …, xn) называется монотонной (принадлежит классу M), если

Является ли функция монотонной?Из элементарных булевых функций монотонными являются, например, конъюнкция

Класс линейных функцийОпределение. Булева функция называется линейной (принадлежит классу L), если ее полином Жегалкина

Функциональная полнота системы булевых функций

Определение ФПСОпределение. Множество функций N называется функционально полной системой (ФПС), если любая булева функция

Примеры ФПСПример 1. Множество N1={&,+,–} является функционально полной системой, так как любую

Теорема о двух функционально полных системахТеорема. Если даны два множества N1 и N2 булевых

Пример. N1={&,+,–}, N2={&, –}. Как показано ранее, N1 – ФПС. Конъюнкция и инверсия содержатся

Задание: Докажите, что система функций {¬, v} является полной.Пустьf1(x1) = x1

Существует функционально полная система, состоящая из одной булевой функции.Штрих Шеффера (И-НЕ)

Доказательствоx1 | x2 = x1 v x2 или x1 | x2

Стрелка Пирса (ИЛИ-НЕ) – x1 ↓ x2Функция стрелка Пирса является полной.x1

Теорема ПостаТеорема (о полноте). Для того, чтобы система булевых функций Д была

Таблицы ПостаВ тех задачах, где требуется выяснить, является ли данная система