Булевы функции
Видео:Дискретная математика. Лекция 2: Функции и отображенияСкачать
Содержание
Видео:Математика это не ИсламСкачать
1 Понятие булевой функции
В курсе математического анализа изучаются функции, определённые на числовой прямой или на отрезке числовой прямой или на (гипер-) плоскости и т.п. Так или иначе область определения – непрерывное множество. В курсе дискретной математики изучаться должны функции, область определения которых – дискретное множество * . Простейшим (но нетривиальным) таким множеством является множество, состоящее из двух элементов. * Так мы и приходим к понятию булевой функции.
Определение 1 (Булева функция). Булевой функцией от n аргументов называется функция f из n -ой степени множества в множество .
Иначе говоря, булева функция – это функция, и аргументы и значение которой принадлежит множеству . Множество мы будем в дальнейшем обозначать через B .
Булеву функцию от n аргументов можно рассматривать как n -местную алгебраическую операцию на множестве B . При этом алгебра W >, где W – множество всевозможных булевых функций, называется алгеброй логики .
Конечность области определения функции имеет важное преимущество – такие функции можно задавать перечислением значений при различных значениях аргументов. Для того, чтобы задать значение функции от n переменных, надо определить значения для каждого из 2 n наборов. Эти значения записывают в таблицу в порядке соответствующих двоичных чисел. В результате получается таблица следующего вида:
x 1 | x 2 | . | x n- 1 | x n | f |
---|---|---|---|---|---|
0 | 0 | . | 0 | 0 | f(0,0. 0,0) |
0 | 0 | . | 0 | 1 | f(0,0. 0,1) |
0 | 0 | . | 1 | 0 | f(0,0. 1,0) |
0 | 0 | . | 1 | 1 | f(0,0. 1,1) |
. | . | . | . | . | . |
1 | 1 | . | 0 | 0 | f(1,1. 0,0) |
1 | 1 | . | 0 | 1 | f(1,1. 0,1) |
1 | 1 | . | 1 | 0 | f(1,1. 1,0) |
1 | 1 | . | 1 | 1 | f(1,1. 1,1) |
Раз у нас есть стандартный порядок записывания наборов, то для того, чтобы задать функцию, нам достаточно выписать значения f (0,0. 0,0) , f (0,0. 0,1) , f (0,0. 1,0) , f (0,0. 1,1). f (1,1. 0,0) , f (1,1. 0,1) , f (1,1. 1,0) , f (1,1. 1,1). Этот набор называют вектором значений функции .
Таким образом, различных функций n переменных столько, сколько различных двоичных наборов длины 2 n * . А их 2 в степени 2 n .
Множество B содержит два элемента – их можно рассматривать как булевы функции от нуля (пустого множества) переменных – константу 0 и константу 1 .
Функций от одной переменной четыре: это константа 0, константа 1, тождественная функция , т.е. функция, значение которой совпадает с аргументом и так называемая функция « отрицание ». Отрицание будем обозначать символом ¬ как унарную операцию. Приведём таблицы этих четырёх функций:
x | 0 | x | ¬ x | 1 |
---|---|---|---|---|
0 | 0 | 0 | 1 | 1 |
1 | 0 | 1 | 0 | 1 |
Как видим, функции от некоторого числа переменных можно рассматривать как функции от большего числа переменных. При этом значения функции не меняется при изменении этих «добавочных» переменных. Такие переменные называются фиктивными , в отличие от остальных – существенных .
Определение 2 (Фиктивные и существенные переменные). Переменная x i называется фиктивной (несущественной) переменной функции f ( x 1 ,···,x n ), если f ( x 1 ,···,x i- 1 ,0 ,x i+ 1 ,···,x n ) = f ( x 1 ,···,x i- 1 ,1 ,x i+ 1 ,···,x n ) для любых значений x 1 ,···,x i- 1 ,x i+ 1 ,···,x n . Иначе переменная x i называется существенной .
Функций от двух аргументов шестнадцать. Наиболее употребимые из этих функций (только те, которые существенно зависят от обеих переменных) мы приводим в следующей таблице:
x 1 | x 2 | x 1 & x 2 | x 1 Ъ x 2 | x 1 Й x 2 | x 1 Е x 2 | x 1 є x 2 | x 1 | x 2 |
---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
Эти функции записываются как бинарные операции в инфиксной нотации. x 1 & x 2 называется конъюнкцией , x 1 Ъ x 2 – дизъюнкцией , x 1 Й x 2 – импликацией , x 1 є x 2 – эквивалентностью , x 1 Е x 2 – суммой по модулю 2 , x 1 | x 2 – штрихом Шеффера .
Значения 0 и 1 часто интерпретируют как «ложь» и «истину». Тогда понятным становится название функции «отрицание» – она меняет «ложь» на «истину», а «истину» на «ложь». Отрицание читается как «не». Конъюнкция читается обычно как «и» – действительно, конъюнкция равна 1 тогда и только тогда, когда равны 1 и первая и вторая переменная. * Кроме x 1 & x 2 часто используют обозначение x 1 Щ x 2 или x 1 · x 2 или x 1 x 2 или min( x 1 ,x 2 ). Дизъюнкция читается «или» – дизъюнкция равна 1 тогда и только тогда, когда равны 1 первая или вторая переменная. * Импликация выражает факт, что из x 1 следует x 2 . * Импликацию часто также обозначают x 1 ® x 2 .
Видео:Дискретная математика. Видео 3. Полнота системы функций.Скачать
2 Суперпозиция функций
Определение 3 (Суперпозиция функций). Суперпозицией булевых функций f 0 и f 1 . f n называется функция f ( x 1 . x m ) = f 0 ( g 1 ( x 1 . x m ) . g k ( x 1 . x m )), где каждая из функций g i ( x 1 , . x m ) либо совпадает с одной из переменных (тождественная функция), либо – с одной из функций f 1 . f n .
Пример 1 (суперпозиция функций).
Функция f ( x,y ) = ¬ ( x & y ) является суперпозицией функций ¬ и &. Функция g ( x,y ) = x Е ( x Ъ y ) является суперпозицией функций Е и Ъ . Функция h ( x,y,z ) = ( x & y ) Е z является суперпозицией функций Е и &. Построим таблицы этих функций.
Суперпозицию ( x & y ) Е ( ¬x Ъ ¬y ) можно прочитать как « x и y плюс не x или не y ».
Следующие соотношения могут быть проверены прямым сравнением значений функций в левой и правой части соотношения на всевозможных наборах аргументов.
- x & y = y & x
- x Ъ y = y Ъ x
- x Е y = y Е x
- x & ( y & z ) = ( x & y ) & z
- x Ъ ( y Ъ z ) = ( x Ъ y ) Ъ z
- x Е ( y Е z ) = ( x Е y ) Е z
- x Ъ ( y & z ) = ( x Ъ y ) & ( x Ъ z )
- x & ( y Ъ z ) = ( x & y ) Ъ ( x & z )
- ¬¬x = x
- ¬ ( x & y ) = ¬x Ъ ¬y
- ¬ ( x Ъ y ) = ¬x & ¬y
- x & x = x
- x & ¬x = 0
- x & 0 = 0
- x & 1 = x
- x Ъ x = x
- x Ъ ¬x = 1
- x Ъ 0 = x
- x Ъ 1 = 1
- x Е y = ( x & ¬y ) Ъ ( ¬x & y )
- x Й y = ¬x Ъ y
- x є y = ( x & y ) Ъ ( ¬x & ¬y )
Видео:Булевы функцииСкачать
3 Двойственные функции
Определение 4 (Двойственная функция). Функция g ( x 1 . x n ) = ¬f ( ¬x 1 . ¬x n ) называется двойственной функцией к функции f и обозначается f * .
Пример 2 (двойственные функции).
( x & y ) * = ¬ ( ¬x & ¬y ) = x Ъ y .
Предложение 1 (Двойственная к двойственной функции). Функция, двойственная к двойственной функции f равна самой функции f.
Доказательство. f * ( x 1 . x n ) * = ( ¬f ( ¬x 1 . ¬x n )) * = *
= ¬¬f ( ¬¬x 1 . ¬¬x n ) = *
= f ( x 1 . x n ) *
Рассмотрим, что происходит с таблицей двойственной функции. Замена набора ( x 1 . x n ) на ( ¬x 1 . ¬x n ) соответствует «переворачиванию» таблицы. Действительно, наборы ( x 1 . x n ) и ( ¬x 1 . ¬x n ) расположены симметрично относительно середины таблицы. Теперь остаётся применить операцию ¬ к результату функции, т.е. поменять 0 на 1 и 1 на 0. Т.о. вектор значений функции, двойственной к исходной, получается из вектора исходной функции переворачиванием и заменой 0 на 1, а 1 на 0.
Пример 3 (вектор двойственной функции).
Функции x & y и x Ъ y , задаваемые векторами значений (0,0,0,1) и (0,1,1,1) двойственны друг к другу. Также двойственными являются x Е y и x є y , задаваемые векторами (0,1,1,0) и (1,0,0,1). Каждая из функций x и ¬x (векторы (0,1) и (1,0) соответственно) двойственна сама себе.
Теорема 1 (Принцип двойственности). Функция, двойственная к суперпозиции функций, равна суперпозиции двойственных функций. Точнее: f 0 ( f 1 . f m ) * = f 0 * ( f 1 * . f m * )
Доказательство. f 0 ( f 1 ( x 1 . x n ) . f m ( x 1 . x n )) * =
= ¬f 0 ( f 1 ( ¬x 1 . ¬x n ) . f m ( ¬x 1 . ¬x n )) = | * |
= ¬f 0 ( ¬¬f 1 ( ¬x 1 . ¬x n ) . ¬¬f m ( ¬x 1 . ¬x n )) = | * |
= ¬f 0 ( ¬f 1 * ( x 1 . x n ) . ¬f m * ( x 1 . x n )) = | * |
= f 0 * ( f 1 * ( x 1 . x n ) . f m * ( x 1 . x n )) | * |
Видео:Что такое вектора? | Сущность Линейной Алгебры, глава 1Скачать
4 Разложение функции по переменным
x s = |
|
Теорема 2 (Разложение в дизъюнкцию). Любую функцию f ( x 1 . x m ) для любого n (1 Ј n Ј m ) можно представить в виде f ( x 1 . x m ) = x 1 s 1 & . & x n s n & f ( s 1 . s n ,x n+ 1 . x m )
Доказательство. Покажем, что для любого набора значений переменных ( x 1 . x n ,x n+ 1 . x m ) значения левой и правой частей совпадают. Возьмём фиксированный набор ( x 1 . x n ,x n+ 1 . x m ). Рассмотрим выражение x 1 s 1 & . & x n s n . Если одно из значений x i s i равно 0, то и всё выражение равно 0. Тогда и выражение x 1 s 1 & . & x n s n & f ( s 1 . s n ,x n+ 1 . x m ) равно 0. Единице же выражение x 1 s 1 & . & x n s n равно только в том случае, если s 1 = x 1 , . s n = x n . При этом f ( s 1 . s n ,x n+ 1 . x m ) = f ( x 1 . x n ,x n+ 1 . x m ) Таким образом, значение правой части всегда равно равно f ( x 1 . x m ), то есть значению левой части.
Теорема 3 (Разложение в конъюнкцию). Любую функцию f ( x 1 . x m ) для любого n (1 Ј n Ј m ) можно представить в виде f ( x 1 . x m ) = x 1 ¬ s 1 Ъ . Ъ x n ¬ s n Ъ f ( s 1 . s n ,x n+ 1 . x m )
Разложения по всем переменным дают суперпозицию конъюнкции, дизъюнкции и отрицания.
Следствие 1 (Совершенная дизъюнктивная нормальная форма).
Любая функция f может быть представлена в следующей форме: *
f ( x 1 . x m ) = x 1 s 1 & . & x m s m & f ( s 1 . s m ) = * |
= x 1 s 1 & . & x m s m |
Следствие 2 (Совершенная конъюнктивная нормальная форма).
Любая функция f может быть представлена в следующей форме: * f ( x 1 . x m ) = x 1 ¬ s 1 Ъ . Ъ x m ¬ s m
Таким образом, любая булева функция может быть представлена суперпозицией конъюнкции, дизъюнкции и отрицания. Разложение по всем переменным в дизъюнкцию называется совершенной дизъюнктивной нормальной формой функции, а в конъюнкцию – совершенной конъюнктивной нормальной формой . *
Совершенная дизъюнктивная и конъюнктивная нормальная формы дают способ представления булевой функции через суперпозицию конъюнкции, дизъюнкции и отрицания если у нас есть таблица значений функции.
Чтобы получить совершенную дизъюнктивную нормальную форму, надо взять все наборы, на которых значение функции равно 1 и записать для каждого из них конъюнкцию переменных и их отрицаний. Если в наборе значение переменной 0 – то переменную надо взять с отрицанием, если 1 – без отрицания. Из получившихся конъюнкций надо построить дизъюнкцию.
Чтобы получить совершенную конъюнктивную нормальную форму, надо взять все наборы, на которых значение функции равно 0 и записать для каждого из них дизъюнкцию переменных и их отрицаний. Если в наборе значение переменной 0 – то переменную надо взять без отрицания, если 1 – с отрицанием. Из получившихся дизъюнкций надо построить конъюнкцию.
Пример 4 (совершенная дизъюнктивная нормальная форма).
Построим совершенную дизъюнктивную нормальную форму функции, заданной следующей таблицей.
x | y | z | f |
---|---|---|---|
0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
Наборы, на которых функция равна 1 – это (0,1,1), (1,0,1), (1,1,0), (1,1,1). Первый набор даёт конъюнкцию ¬x & y & z , второй – x & ¬y & z , третий – x & y & ¬z , четвёртый – x & y & z . В результате получаем ( ¬x & y & z ) Ъ ( x & ¬y & z ) Ъ ( x & y & ¬z ) Ъ ( x & y & z ).
Видео:Вектор. Сложение и вычитание. 9 класс | МатематикаСкачать
Булевы функции и их представления
Булевы функции от n переменных
Булевы функции 1 В отечественной литературе их также часто называют функциями алгебры логики . названы в честь английского математика ХIХ века Дж. Буля, который впервые применил алгебраические методы для решения логических задач. Они образуют самый простой нетривиальный класс дискретных функций — их аргументы и значения могут принимать всего два значения (если мощность множества значений функции равна 1, то это тривиальная функция — константа !). С другой стороны, этот класс достаточно богат и его функции имеют много интересных свойств. Булевы функции находят применение в логике, электротехнике, многих разделах информатики.
Обозначим через B двухэлементное множество . Тогда
Теорема 3.1. .
Доказательство.Действительно, по теореме 1.1 число функций из k -элементного множества A в m -элементное множество B равно m k . В нашем случае B= , а A = B n . Тогда m=2 и k= |B n | = 2 n . Отсюда следует утверждение теоремы.
Имеется несколько различных способов представления и интерпретации булевых функций . В этом разделе мы рассмотрим геометрическое и табличное представления , а также представление с помощью логических формул . В «Эквивалентность формул и нормальные формы» будет показано, как булевы функции можно представлять с помощью формул специального вида — дизъюнктивных и конъюнктивных нормальных форм и многочленов Жегалкина . Кроме того, в лекциях «Предварительные сведения» и «Индукция и комбинаторика» (курс «Введение в схемы, автоматы и алгоритмы») будет рассмотрено еще два способа представления булевых функций : логические схемы и упорядоченные бинарные диаграммы решений .
Геометрическое представление
Bn можно рассматривать как единичный n-мерный куб . Каждый набор из нулей и единиц длины n задает вершину этого куба. На рис. 3.1 представлены единичные кубы Bn при n=3,4 .
При этом существует естественное взаимно однозначное соответствие между подмножествами вершин n-мерных единичных кубов и булевыми функциями от n переменных: подмножеству соответствует его характеристическая функция
Например, верхней грани куба B 3 (ее вершины выделены на рисунке) соответствует функция f : f(0,0,1)=f(0,1,1)=f(1,0,1)=f(1,1,1) =1 и f(0,0,0)=f(0,1,0)=f(1,0,0)=f(1,1,0) =0 . Очевидно, что указанное соответствие действительно взаимнооднозначное: каждая булевая функция f от n переменных задает подмножество Af=<(x1, . xn)|f(x1, . xn)=1> вершин B n . Например, функция, тождественно равная 0, задает пустое множество , а функция, тождественно равная 1, задает множество всех вершин B n .
Табличное представление
Булевы функции от небольшого числа аргументов удобно представлять с помощью таблиц . Таблица для функции f(x1, . xn) имеет n+1 столбец. В первых n столбцах указываются значения аргументов x1, . xn , а в (n+1) -ом столбце значение функции на этих аргументах — f(x1, . xn) .
x1 | . | . | . | xn-1 | xn | f(x1, . xn) |
---|---|---|---|---|---|---|
0 | . | . | . | 0 | 0 | f(0, . 0,0) |
0 | . | . | . | 0 | 1 | f(0, . 0,1) |
0 | . | . | . | 1 | 0 | f(0, . 1,0) |
. | . | . | . | . | . | |
1 | . | . | . | 1 | 1 | f(1, . 1,1) |
Наборы аргументов в строках обычно располагаются в лексикографическом порядке:
существует такое , что при , а .
Если эти наборы рассматривать как записи чисел в двоичной системе счисления , то 1-ая строка представляет число 0, 2-ая — 1, 3-я — 2, а последняя — 2 n -1 .
При больших n табличное представление становится громоздким, например, для функции от 10 переменных потребуется таблица с 1024 строками. Но для малых n оно достаточно наглядно.
📺 Видео
Дискретная математика. Видео 1. Минимизация булевых функций.Скачать
Монотонность булевых функцийСкачать
Высшая математика. Линейные пространства. Векторы. БазисСкачать
Важнейшие замкнутые классы. Теорема ПостаСкачать
18+ Математика без Ху!ни. Скалярное произведение векторов. Угол между векторами.Скачать
Булевы функции. Функции алгебры логики. Что это?Скачать
Нахождение функции случайного вектораСкачать
Булевы функции и способы их заданияСкачать
Булевы функцииСкачать
Характеристические векторы множествСкачать
Двойственные функции ПрактикаСкачать
Олегу Тинькову запрещён вход на Мехмат МГУСкачать
6. Функция. Дискретная математикаСкачать