2.Булевы функции Аксёнов Сергей Владимирович к.т.н., доцент каф.ОСУ ТПУ Национальный исследовательский Томский политехнический университет Логика и теория алгоритмов

Темы лекции 1.Множества, отношения и функции 2. Булевы функции от одного и двух аргументов 3. Булевы функции от n аргументов 4. Системы булевых функций 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В.

Понятие множества Опр. Множество – совокупность объектов, которая рассматривается как одно целое. Опр. Элементы – объекты, составляющие множество. Множества обозначают заглавными буквами латинского алфавита: A, B, C, …, а элементы множества – малыми латинскими буквами a, b, c, …, a 1, a 2, a 3, … Элемент а принадлежит множеству А: a A Элемент b не принадлежит множеству B: b B Множество, состоящее из элементов a 1, a 2, …, a n, обозначается {a 1, a 2, …, a n } Запись {x : S(x)} обозначает множество таких объектов x, которые удовлетворяют некоторому свойству S(x). 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В.

Включение и равенство множеств Опр. Множество А называется подмножеством множества В (или говорят А включается в В), если каждый элемент множества А принадлежит множеству В. Запись А В. Опр. Множества А и В называются равными, если А состоит из тех и только из тех элементов, которые принадлежат В. Запись А=В. Опр. Множество А называется собственным подмножеством множества, если А В и А В. Запись А В Опр. Множество называется пустым множеством, если оно не содержит ни одного элемента. Существует единственное пустое множество, обозначаемое символом. Опр. Множество, содержащее все возможные элементы, называется универсальным. Это множество обозначается символом U. 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В.

Операции над множествами: Объединение множеств 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Опр. Объединением множеств А и В называется множество, обозначаемое А В, состоящее из тех и только из тех элементов, которые принадлежат хотя бы одному из множеств А и В. А В={x: x A или x B }

Операции над множествами: Пересечение множеств 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Опр. Пересечением множеств А и В называется множество, обозначаемое А В, состоящее из тех и только из тех элементов, которые принадлежат одновременно к множеству А и множеству В. А В={x: x A и x B }

Операции над множествами: Разность множеств 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Опр. Разностью множеств А и В называется множество, обозначаемое А \В, состоящее всех элементов множества А, которые не принадлежат множеству В. А \В={x: x A и x B }

Операции над множествами: Дополнение множества 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Опр. Дополнением множества А в множестве U, называется множество обозначаемое Ā, состоящее из тех элементов множества U, которые не принадлежат к множеству А. Ā=U\A={x: x U и x A }

Пример 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Опр. Дополнением множества А в множестве U, называется множество обозначаемое Ā, состоящее из тех элементов множества U, которые не принадлежат к множеству А. Ā=U\A={x: x U и x A }

Свойства операций над множествами Ч.1 1.Идемпотентность объединения A A=A 2.Идемпотентность пересечения A A=A 3.Коммутативность объединения A B=B A 4.Коммутативность пересечения A B=B A 5.Ассоциативность объединения A (B C)=(A B) C 6.Ассоциативность пересечения A (B C)=(A B) C 7.Дистрибутивность объединения относительно пересечения A (B C)=(A B) (A C) 8.Дистрибутивность пересечения относительно объединения A (B C)=(A B) (A C) 9.1-ый закон поглощения A (B A)=A 10.2-ой закон поглощения A (B A)=A 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В.

Свойства операций над множествами Ч ый закон де Моргана 12.2-ой закон де Моргана 13. A U=U, A U=A 14. A =A, A = 15. A Ā=U, A Ā= Закон инволюции Булевы функции Логика и теория алгоритмов, Аксёнов С.В.

Свойства операций над множествами и отношения включения множеств 1. A AB, B AB 2. A B A, A B B 3. AB A B=A 4. AB A B=B 5. AB Ā B=U 6. 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В.

Бинарные отношения 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Опр. Упорядоченной парой, составленной из элементов a и b называется пара (a, b), в которой указано, какой элемент является первым, а какой – вторым. Упорядоченные пары (a, b) и (c, d) называются равными, если a=c и b=d. Опр. Прямым (или декартовым) произведением двух множеств A и B называется множество A × B всевозможных упорядоченных пар (a, b), таких, что a A и b B. A × B={(a, b): a A и b B} Опр. Бинарным отношением между элементами множеств A и B называется любое множество упорядоченных пар (a, b), таких, что a A и b B.

Функции Ч.1 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Опр. Бинарное отношение f A × B называется функцией, заданной на множестве A и принимающей значения в множестве В (или отображением А в В), если: 1) для любого x A найдется y B, такой, что (x, y) f; 2) для любых xA, y 1, y 2 B из того, что (x, y 1 ) f и (x, y 2 ) f, следует y 1 = y 2. Элемент у называется значением функции f для аргумента x b и обозначается f(x). Множество А называется областью определения функции f. Множество В называется областью изменения функции f. Запись f: A B

Функции Ч.2 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Опр. Функция f : A B называется инъективной (или взаимооднозначной), если для любых x 1, x 2 A из равенства f(x 1 )=f(x 2 ) непременно вытекает равенство аргументов x 1 =x 2. Опр. Функция f : A B называется суръективной (или отображением А на В), если для любого y B найдется хотя бы один x A, такой, что y=f(x). Опр. Функция f : A B называется биективной (или биекцией), если она одновременно инъективна и суръективна.

Понятие n-арного отношения 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Опр. Кортеж– упорядоченный набор n объектов a 1, a 2, …, a n. Обозначение: ( a 1, a 2, …, a n ) Два кортежа ( a 1, …, a n ) и ( b 1, …, b n ) называют равными если a i = b i, i=1,…, n. Опр. Прямым произведением множеств A 1, …, A n называют множество A 1 × … × A n ={(x 1, …, x n ): x 1 A 1,…, x n A n } Опр. n-арным отношением между элементами множеств A 1, …, A n называется любое подмножество прямого произведения A 1 × … × A n.

Булевы функции от одного аргумента 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Опр. Булевой функцией от одного аргумента называется функция f, заданная на множестве из двух элементов и принимающая значения в том же двухэлементном множестве. f: {0,1} {0,1} xf 0 (x)f 1 (x)f 2 (x)f 3 (x) f 0 (x) = 0 (тождественный нуль), f 1 (x) = x (тождественная функция), f 1 (x) = x (отрицание), f 3 (x) = 1 (тождественная единица)

Булевы функции от двух аргументов Ч.1 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Опр. Булева функция от двух аргументов есть функция g, заданная на множестве {0,1} × {0,1} и принимающая значения в двухэлементном множестве {0,1} 0 · x y+v xyg0g0 g1g1 g2g2 g3g3 g4g4 g5g5 g6g6 g7g

Булевы функции от двух аргументов Ч.2 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. y x |1 xyg8g8 g9g9 g 10 g 11 g 12 g 13 g 14 g g 0 – тождественный нуль g 15 – тождественная единица g 1 – конъюнкция g 7 – дизъюнкция

Булевы функции от двух аргументов Ч.3 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. g 13 – импликация g 9 – эквивалентность g 11 – антиимпликация (обратная импликация) g 6 – сумма Жегалкина (сложение по модулю 2) g 14 – штрих Шеффера (отрицание конъюнкции) g 8 – стрелка Пирса (отрицание дизъюнкции)

Свойства дизъюнкции, конъюнкции и отрицания 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Для булевых функций выполняются следующие равенства: 1.Идемпотентность x v x = x, x · x = x 2.Коммутативность x v y = y v x, x · y = y · x 3.Ассоциативность (x v y) v z = x v (y v z), (x · y ) · z = x · (y · z) 4. x v 1 = 1, x · 1 = x 5. x v 0 = x, x · 0 = 0 6. Дистрибутивность x v (y · z) = ( x v y ) · (x v z), x · (y v z)= (x · y) v (x · z) 7. Законы поглощения x v (x · y) = x, x · (x v y) = x 8. Законы де Моргана (x · y ) = x v y, ( x v y) = x · y 9. x v x =1, x · x =0 10. x =x

Свойства эквивалентности, импликации и отрицания 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Для булевых функций выполняются следующие равенства: 1. x x=1, xx=0 2.Коммутативность эквивалентности xy = y x 3.Ассоциативность эквивалентности (xy)z =x (yz) 4. 1 x=x, 0x=1 5. x y = xy 6. x y = yx 7. x x=1 8. x x=x, x x =x 9. 1 x=x, 0x=1 10. x1=1, x0=x

Выражение одних булевых функций через другие 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Справедливы следующие равенства: 1. x · y = (x v y ), x v y = (x · y) 2. x v y = (x y) y, x v y=x y 3. x y=x v y 4. x y=(x y) · (y x) 5. x = x|x 6. x |y=(x · y) 7. x v y= x|y=(x|x)|(y|y) 8. x=x x 9. x y=(x v y) 10. x · y=x y=(x x) (y y)

Понятие булевой функции от n аргументов 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Опр. Булевой функцией от n аргументов называется функция f, заданная на множестве {0, 1} n и принимающая значения на двухэлементном множестве {0, 1}. Т. (о числе булевых функций от n аргументов) Число различных булевых функций от n аргументов равно 2 2 n. Опр. Суперпозицией булевых функций g 1 (y 1 1, y 2 1, …, y m1 1 ), …, g n (y 1 n, y 2 n, …, y m1 n ) в булеву функцию f(x 1, x 2, …, x n ) называется новая функция, получается новая булева функция, получающаяся из функции f(x 1, x 2, …, x n ) подстановкой вместо аргументов x 1, x 2, …, x n функций g 1, g 2, …, g n соответственно f(g 1 (y 1 1, y 2 1, …, y m1 1 ), …, g n (y 1 n, y 2 n, …, y mn n )).

Выражение булевых функций через конъюнкцию, дизъюнкцию и отрицание 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Лемма. (о разложении функции по переменной) Для произвольной булевой функции f(x 1, x 2, …, x n ) справедливы следующие формулы, называемые формулами разложения этой функции по переменной x 1 : f(x 1, x 2, …, x n )=(x 1 · f (1, x 2, …, x n ) ) v (x 1 · f(0, x 2, …, x n )) f(x 1, x 2, …, x n )=(x 1 v f(0, x 2, …, x n )) · (x 1 v f(1, x 2, …, x n )). Т. (о представлении булевых функций через конъюнкцию, дизъюнкцию и отрицание) Всякая булева функция f(x 1, x 2, …, x n ) может быть представлена в виде суперпозиции конъюнкции, дизъюнкции и отрицания, причём знак отрицания стоит только непосредственно около переменной и не стоит ни перед одной из внутренних скобок.

Полные системы булевых функций 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Опр. Система булевых функций называется полной, если всякая булева функция является суперпозицией функций этой системы. Т. Следующие системы булевых функций являются полными 1){v,, ' }; 2){+,, ' }; 3){ v, ' }; 4){, ' }; 5){, ' }; 6){ | };7){ }.

Специальные классы булевых функций Ч.1 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Опр. Говорят, что булева функция f(x 1, x 2, …, x n ) сохраняет 0, если f(0, 0, …, 0)=0. Обозначим P 0 – класс всех булевых функций, сохраняющих 0. Опр. Говорят, что булева функция f(x 1, x 2, …, x n ) сохраняет 1, если f(1, 1, …, 1)=1. Обозначим P 1 – класс всех булевых функций, сохраняющих 1. Опр. Булева функция f*(x 1, x 2, …, x n ) называется двойственной функцией для булевой функции f(x 1, x 2, …, x n ), если f*(x 1, x 2, …, x n ) = f ' (x 1 ', x 2 ', …, x n ' ) для любых x 1, x 2, …, x n. Опр. Булева функция называется самодвойственной, если f*=f. Класс всех самодвойственных булевых функций обозначим S.

Проверка функции на самодвойственность 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Задача. Выяснить является ли булева функция f(x,y,z) =xy v xz v yz самодвойственной. f ' (x ',y ',z ' ) = (x ' y ' v x ' z ' v y ' z ' ) ' = (x'' v y'')(x'' v z'')(y'' v z'') = (x v y)(x v z)(y v z) = (xx v xy v xz v yz)(y v z) = (x v xy v xz v yz)(y v z) = (xy v xyy v xyz v yyz v xz v xyz v xzz v yzz) = (xy v xy v xyz v yz v xz v xyz v xz v yz) = (xy v xyz v yz v xz) = (xy v yz v xz) = (xy v xz v yz) = f(x, y, z) функция f(x,y,z) является самодвойственной

Специальные классы булевых функций Ч.2 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Введение отношения порядка. 0 0, 01, 11. Опр. Булева функция f(x 1, x 2, …, x n ) называется монотонной, если для любых 1, 2, …, n, 1, 2, …, n {0,1} из 1 1, 2 2, …, n n немедленно следует f( 1, 2, …, n ) f( 1, 2, …, n ). Класс всех монотонных функций обозначим M. Опр. Булева функция f*(x 1, x 2, …, x n ) называется линейной, если её можно представить в виде полинома Жегалкина первой степени: f(x 1, x 2, …, x n ) = a 0 + a 1 x 1 + a 2 x 2 + … +a n x n, где a 0, a 1, a 2, …, a n – постоянные, равные либо 0, либо 1. Класс всех линейных булевых функций обозначим L.

Проверка функции на монотонность 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Задача. Выяснить является ли булева функция f(x,y,z) =xyz + xy + xz монотонной. #xyzxyzxyxzxyz+xy+xz Монотонность (2)-(8) (4), (6), (8) (4), (7), (8) (8) (6)-(8) (8) По всем сравнимым наборам выполняется условие монотонности функция f(x,y,z) монотонна

Нахождение полинома Жегалкина 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Справедливы следующие равенства: 1. x = x+1 2. x v y = x + y + xy 3. (x + y)(w + z) = xw+yw+xz+yz 4. x+x=0 Задача. Для формулы z (x y ) xy найти полином Жегалкина z (x y ) zy = =z x z y xy = z x + z y + xy+ z x z y +z x xy+ z y xy+z x z y xy= x z + y z + xy+ xy z +x y z = x( z+1) + y( z+1) + x(y+1)+ xy( z+1) +x( y+1)( z+1 ) = xz+x+yz+y+xy+x+xyz+xy + xyz+xy+xz+x = x+yz+y+xy

Нахождение полинома Жегалкина методом неопределённых коэффициентов 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Задача. Для формулы f(x, y, z) = z (x y ) xy найти полином Жегалкина Для формулы f(x, y, z) полином Жегалкина имеет вид: a 0 +a 1 x+a 2 y+a 3 z+a 12 xy+a 13 xz+a 23 yz+a 123 xyz xyz z(x y) xy Коэффициенты 0000 a 0 = a 0 + a 3 =0 0 + a 3 =0 a 3 = a 0 + a 2 =1 0 + a 2 =1 a 2 = a 0 + a 2 + a 3 + a 23 = a 23 =0 a 23 = a 0 + a 1 =1 0 + a 1 =1 a 1 = a 0 + a 1 + a 3 + a 13 = a 13 =1 a 13 = a 0 + a 1 + a 2 + a 12 = a 12 =1 a 12 = a 0 + a 1 + a 2 + a 3 + a 12 + a 13 + a 23 + a 123 = a 123 =1 a 123 =0

Собственные и замкнутые классы булевых функций 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Опр. Класс булевых функций называется собственным, если он не пуст и не совпадает с классом всех булевых функций. Опр. Класс булевых функций называется замкнутым или классом Поста, если он вместе со всякими своими функциями содержит любую их суперпозицию. Т. Классы P 0, P 1, S, M, L являются собственными замкнутыми классами булевых функций.

Теорема Поста о полноте системы булевых функций 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Т. (о полноте системы булевых функций) Система булевых функций {f 1, f 2, …, f n,…} является полной тогда и только тогда, когда в этой системе имеется функция, не принадлежащая классу P 0, имеется функция, не принадлежащая классу P 1, имеется функция, не принадлежащая классу S, не принадлежащая классу M, имеется функция, не принадлежащая классу L. Опр. Базисом называется минимальная полная система булевых функций, т.е. такая система, удаление из которой хотя бы одной булевой функции делает систему неполной.

Пример: полнота и нахождение базиса 2.Булевы функции Логика и теория алгоритмов, Аксёнов С.В. Задача. Определить является ли система полной и если она является полной, то найти базис (x+y)z, 1, xy y z, x+y+z. P0P0 P1P1 SLM (x+y)z(x+y)z xy y z x+y+z В системе присутствуют все необходимые функции – она является полной. Только функции (x+y)z, 1 составляют базис для системы булевых функций. Проверка булевых функций на принадлежность классам P 0, P 1, S, L, M: