Булевой функцией y=f(x₁, x₂ . x_n) от п переменных x₁, x₂, x_n называется любая функция, в которой аргументы и функция могут принимать значение либо 0 либо 1, т.е. булева функция это правило по которому произвольному набору нулей и единиц (x₁, x₂ . x_n) ставится в соответствие значение 0 или 1.

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

Булеву функцию от n переменных можно задать таблицей истинности, в которой наборы значений аргументов расположены в порядке возрастания их номеров: сначала идет набор, представляющий собой двоичное разложение 0 (этот набор имеет номер 0); затем идет набор, являющийся двоичным разложением 1, потом 2, 3 и т.д. Последний набор состоит из n единиц и является двоичным разложением числа 2 n -1 (такой порядок расположения наборов назовем лексикографическим порядком). Учитывая, что отсчет начинается с 0, а значение булевой функции может быть либо 0 либо 1, заключаем, что существует всего 2 2 n различных булевых функций от n переменных. Таким образом, имеется, например, 16 булевых функций от двух переменных, 256 — от трех и т. д.

Пример (голосование): Рассмотрим устройство, фиксирующее принятие некоторой резолюции «комитетом трех». Каждый член комитета при одобрении резолюции нажимает свою кнопку. Если большинство членов голосуют «за», то резолюция принимается. Это фиксируется регистрирующим прибором. Таким образом, устройство реализует функцию f(x,y,z), таблица истинности которой имеет вид:

Булева функция также однозначно задается перечислением всех наборов, на которых она принимает значение 0, либо перечислением всех наборов, на которых она принимает значение 1.Полученную в примере функцию f можно также задать следующей системой равенств: f(0,0,0) = f(0,0,1) = f(0,1,0) = f(1,0,0) = 0.

Вектором значений булевой функции y=f(x₁, x₂ . x_n) называется упорядоченный набор всех значений функции f, при котором значения упорядочены по лексикографическому порядку. Например, пусть функция трех переменных f задана вектором значений (0000 0010) и необходимо найти набор, на котором f принимает значение 1. Т.к. 1 стоит на 7 месте, а нумерация в лексикографическом порядке начинается с 0, то необходимо найти двоичное разложение 6. Таким образом, функция f принимает значение 1 на наборе (110).

Булевы функции

Видео:Собственные значения и собственные векторы матрицы (4)Скачать

Содержание

Видео:Для булевой функции, заданной вектором значений, определитьСкачать

1 Понятие булевой функции

В курсе математического анализа изучаются функции, определённые на числовой прямой или на отрезке числовой прямой или на (гипер-) плоскости и т.п. Так или иначе область определения – непрерывное множество. В курсе дискретной математики изучаться должны функции, область определения которых – дискретное множество * . Простейшим (но нетривиальным) таким множеством является множество, состоящее из двух элементов. * Так мы и приходим к понятию булевой функции.

Определение 1 (Булева функция). Булевой функцией от n аргументов называется функция f из n -ой степени множества в множество .

Иначе говоря, булева функция – это функция, и аргументы и значение которой принадлежит множеству . Множество мы будем в дальнейшем обозначать через B .

Булеву функцию от n аргументов можно рассматривать как n -местную алгебраическую операцию на множестве B . При этом алгебра W >, где W – множество всевозможных булевых функций, называется алгеброй логики .

Конечность области определения функции имеет важное преимущество – такие функции можно задавать перечислением значений при различных значениях аргументов. Для того, чтобы задать значение функции от n переменных, надо определить значения для каждого из 2 n наборов. Эти значения записывают в таблицу в порядке соответствующих двоичных чисел. В результате получается таблица следующего вида:

Раз у нас есть стандартный порядок записывания наборов, то для того, чтобы задать функцию, нам достаточно выписать значения 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, тождественная функция , т.е. функция, значение которой совпадает с аргументом и так называемая функция « отрицание ». Отрицание будем обозначать символом ¬ как унарную операцию. Приведём таблицы этих четырёх функций:

Как видим, функции от некоторого числа переменных можно рассматривать как функции от большего числа переменных. При этом значения функции не меняется при изменении этих «добавочных» переменных. Такие переменные называются фиктивными , в отличие от остальных – существенных .

Определение 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 – суммой по модулю 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 .

Видео:Вектор. Сложение и вычитание. 9 класс | МатематикаСкачать

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 ».

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

1. x & y = y & x
2. x Ъ y = y Ъ x
3. x Е y = y Е x
4. x & ( y & z ) = ( x & y ) & z
5. x Ъ ( y Ъ z ) = ( x Ъ y ) Ъ z
6. x Е ( y Е z ) = ( x Е y ) Е z
7. x Ъ ( y & z ) = ( x Ъ y ) & ( x Ъ z )
8. x & ( y Ъ z ) = ( x & y ) Ъ ( x & z )
9. ¬¬x = x
10. ¬ ( x & y ) = ¬x Ъ ¬y
11. ¬ ( x Ъ y ) = ¬x & ¬y
12. x & x = x
13. x & ¬x = 0
14. x & 0 = 0
15. x & 1 = x
16. x Ъ x = x
17. x Ъ ¬x = 1
18. x Ъ 0 = x
19. x Ъ 1 = 1
20. x Е y = ( x & ¬y ) Ъ ( ¬x & y )
21. x Й y = ¬x Ъ y
22. 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 )) * =

Видео:Собственные значения и собственные векторыСкачать

4 Разложение функции по переменным

Теорема 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 может быть представлена в следующей форме: *

Следствие 2 (Совершенная конъюнктивная нормальная форма).

Любая функция f может быть представлена в следующей форме: * f ( x 1 . x m ) = x 1 ¬ s 1 Ъ . Ъ x m ¬ s m

Таким образом, любая булева функция может быть представлена суперпозицией конъюнкции, дизъюнкции и отрицания. Разложение по всем переменным в дизъюнкцию называется совершенной дизъюнктивной нормальной формой функции, а в конъюнкцию – совершенной конъюнктивной нормальной формой . *

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

Чтобы получить совершенную дизъюнктивную нормальную форму, надо взять все наборы, на которых значение функции равно 1 и записать для каждого из них конъюнкцию переменных и их отрицаний. Если в наборе значение переменной 0 – то переменную надо взять с отрицанием, если 1 – без отрицания. Из получившихся конъюнкций надо построить дизъюнкцию.

Чтобы получить совершенную конъюнктивную нормальную форму, надо взять все наборы, на которых значение функции равно 0 и записать для каждого из них дизъюнкцию переменных и их отрицаний. Если в наборе значение переменной 0 – то переменную надо взять без отрицания, если 1 – с отрицанием. Из получившихся дизъюнкций надо построить конъюнкцию.

Пример 4 (совершенная дизъюнктивная нормальная форма).

Построим совершенную дизъюнктивную нормальную форму функции, заданной следующей таблицей.

Наборы, на которых функция равна 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 ).

💡 Видео

Собственные векторы и собственные числа линейного оператораСкачать

18+ Математика без Ху!ни. Скалярное произведение векторов. Угол между векторами.Скачать

Функция распределения непрерывной случайной величины. Вероятность попадания в интервалСкачать

Математика без Ху!ни. Непрерывность функции, точки разрыва.Скачать

9 класс, 15 урок, Определение числовой функции. Область определения, область значения функцииСкачать

Теория вероятностей #12: случайная величина, плотность и функция распределенияСкачать

Функция. Область определения функции. Практическая часть. 10 класс.Скачать

Понятие функции. 7 класс.Скачать

Функция распределения и плотность распределенияСкачать

Способы задания функции. 10 класс.Скачать

7 4 Собственные векторы и собственные значенияСкачать

Математика без Ху!ни. Смешанное произведение векторовСкачать

Координаты вектора. 9 класс.Скачать

Что такое вектора? | Сущность Линейной Алгебры, глава 1Скачать

7 класс, 36 урок, Что означает в математике запись y = f(х)Скачать