7. Булевы функции. Мощность множества булевых функций от переменных.

Функции, определенные на множестве E²={0,1} и принимающее значение на множестве называются булевыми функциями или функция алгебры логики.

Функцию F алгебры логики удобно задавать при помощи таблицы, в которой аргументы расположены в порядке возрастания, т.е. будем считать что аргументы упорядочены в алфавитном порядке, т.е. будем обозначать, что аргумент(0,0,0,1) предшествует({) аргументу (0,0,1,0), а аргумент (0,0,1,0){(1,0,0,1).

Наборы , будем называть соседними поi-й координате, а наборы называются противоположными.

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

Свойства булевой функции:

1. x◦y=y◦x (коммутативность операций, где ◦ обозначает операции

2. x◦(x◦y)=(x◦y)◦z ассоциативность

3. 

4. правило де моргана

5. правило поглощения

6. правило поглощения

7. Дистрибутивность конъюнкции отн. Дизъюнкции.

8. Дистрибутивность конъюнкции отн. Суммы по модулю.

9. Дистрибутивность дизъюнкции отн. Конъюнкции.

10. 

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

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

Мощность множества всех булевых функций от n переменных для фиксированного n- это количество булевых функций от n переменных. Мощность высчитывается по формуле

8. Элементарные булевы функции.

Будем рассматривать следующие элементарные функции:

1. наз. Тождественный нуль и тождественная единица.

2. наз. Тождественная функция истинности и отрицание .

3. конъюнкция и дизъюнкция.

4. импликация

5. функция Шеффера (отр. конъюнкция )).

6. эквивалентности .

7. сумма по модулю 2 (отр. Эквивалентности )

8. стрелка Пирса, (отр. дизъюнкция ).

Таблица истинности для функции

с одной переменной.

x
0	0	1	0	1
1	0	1	1	0

Таблица истинности для функций с 2 переменными

0	0	0	0	1	1	1	0	1
0	1	0	1	1	1	0	1	0
1	0	0	1	0	1	0	1	0
1	1	1	1	1	0	1	0	0

9. Формулы. Основные эквивалентности формул.

В каждой формуле над полем Р сопоставляется функция из Р₂ множество всех возможных булевых функций.

Формулы V и G считаются эквивалентными, если соответствующие им функции f_u = h_g равны.

Правила: 1. Внешние скобки в формулах как правило опускаются.

2. Формула UG записывается в виде U●G или UG.

При этом считают, что знак отрицания связывает сильнее, чем логическое знак умножить связывает сильнее, чем знак любой из операций или

А знак = связывает слабее, чем вышеперечисление операции в формуле.

Функции f₁ – f₁₁ – Элементарные функции подчиняются следующим эквивалентности:

1. x◦y=y◦x (коммутативность операций, где ◦ обозначает операции

2. x◦(x◦y)=(x◦y)◦z ассоциативность

3. 

4. правило де моргана

5. правило поглощения

6. правило поглощения

7. Дистрибутивность конъюнкции отн. Дизъюнкции.

8. Дистрибутивность конъюнкции отн. Суммы по модулю.

9. Дистрибутивность дизъюнкции отн. Конъюнкции.

10. 

    1. 

    2. 

    3. 

11. (дополнительные не из наших лекций)Выражение эквивалентности через другие операции:

x~y = =x⊕y⊕1

x~y = (∨y)&(x∨) = x&y ∨ &

12. Выражение ⊕ через другие операции:

x ⊕ y = (x&)∨ (&y) = (∨) & (x ∨ y)

13. Выражение импликации через другие операции:

x→y = →x→y= xy⊕x⊕1

x→= y→ x→y = ∨y x→y=