Булевы функции одной и двух переменных

Булевы функции одной и двух переменных можно легко перечислить.

Функции одной переменной:

булевы функции одной и двух переменных - student2.ru (3.1)

Функции двух переменных:

булевы функции одной и двух переменных - student2.ru (3.2)

Сравнивая определения функций (3.1, 3.2) и логических операций (1.0 ― 1.11), можно сделать вывод, что булевы функции одной и двух переменных можно представить первичными логическими формулами. Поэтому булевы функции одной и двух переменных называют соответствующей операцией:

булевы функции одной и двух переменных - student2.ru ― константа 0;

булевы функции одной и двух переменных - student2.ru ― повторения аргумента;

булевы функции одной и двух переменных - student2.ru ― отрицание аргумента,

булевы функции одной и двух переменных - student2.ru ― константа 1;

булевы функции одной и двух переменных - student2.ru ― константа 0;

булевы функции одной и двух переменных - student2.ru ― конъюнкция;

булевы функции одной и двух переменных - student2.ru ― отрицание импликации;

булевы функции одной и двух переменных - student2.ru ― повторение аргумента булевы функции одной и двух переменных - student2.ru ;

булевы функции одной и двух переменных - student2.ru ― отрицание обратной импликации;

булевы функции одной и двух переменных - student2.ru ― повторение аргумента булевы функции одной и двух переменных - student2.ru ;

булевы функции одной и двух переменных - student2.ru ― сложение по модулю 2;

булевы функции одной и двух переменных - student2.ru ― дизъюнкция;

булевы функции одной и двух переменных - student2.ru ― стрелка Пирса;

булевы функции одной и двух переменных - student2.ru ― эквивалентность;

булевы функции одной и двух переменных - student2.ru ― отрицание аргумента булевы функции одной и двух переменных - student2.ru ;

булевы функции одной и двух переменных - student2.ru ― обратная импликация;

булевы функции одной и двух переменных - student2.ru ― отрицание аргумента булевы функции одной и двух переменных - student2.ru ;

булевы функции одной и двух переменных - student2.ru ― импликация;

булевы функции одной и двух переменных - student2.ru ― штрих Шиффера;

булевы функции одной и двух переменных - student2.ru ― константа 1.

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

/*Пример 3.1

булевы функции одной и двух переменных - student2.ru ,

булевы функции одной и двух переменных - student2.ru . */

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

/*Пример 3.2

булевы функции одной и двух переменных - student2.ru . */

Логическое выражение представляет одну булеву функцию. Обратное утверждение не верно. Любая логическая функция может быть представлена многими формулами (теоретически неограниченным количеством). Формулы, представляющие одну и ту же функцию, называются равносильными. Равносильные формулы соединяются знаком равенства (=).

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 1

Упражнение 1. Записать таблицу истинности булевой функции булевы функции одной и двух переменных - student2.ru по ее номеру.

Выполнение. Заданная функция зависит от четырех аргументов. Количество слов булевы функции одной и двух переменных - student2.ru . Номер функции булевы функции одной и двух переменных - student2.ru . Дополняем его (номер) слева нулями до 16 (в соответствии количеству слов): булевы функции одной и двух переменных - student2.ru .

Таблица истинности:

булевы функции одной и двух переменных - student2.ru ,

Упражнение 2.Булева функция булевы функции одной и двух переменных - student2.ru з неизвестным номером k задана таблицей истинности

булевы функции одной и двух переменных - student2.ru .

Определить номер k этой функции.

Выполнение.

булевы функции одной и двух переменных - student2.ru .

Упражнение 3. Определитьномер булевой функции

булевы функции одной и двух переменных - student2.ru

заданной логической формулой.

Выполнение.

булевы функции одной и двух переменных - student2.ru .

булевы функции одной и двух переменных - student2.ru .

В результате:

булевы функции одной и двух переменных - student2.ru .

ВАРИАНТЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

Вариант k = Таблица истинности функции булевы функции одной и двух переменных - student2.ru булевы функции одной и двух переменных - student2.ru
1. = 234. булевы функции одной и двух переменных - student2.ru булевы функции одной и двух переменных - student2.ru
2. = 214. булевы функции одной и двух переменных - student2.ru булевы функции одной и двух переменных - student2.ru .
3. = 227. булевы функции одной и двух переменных - student2.ru булевы функции одной и двух переменных - student2.ru
4. = 134. булевы функции одной и двух переменных - student2.ru булевы функции одной и двух переменных - student2.ru
5. = 124. булевы функции одной и двух переменных - student2.ru булевы функции одной и двух переменных - student2.ru
6. = 119. булевы функции одной и двух переменных - student2.ru = булевы функции одной и двух переменных - student2.ru
7. = 89. булевы функции одной и двух переменных - student2.ru булевы функции одной и двух переменных - student2.ru
8. = 95. булевы функции одной и двух переменных - student2.ru булевы функции одной и двух переменных - student2.ru
9. = 108. булевы функции одной и двух переменных - student2.ru булевы функции одной и двух переменных - student2.ru
10. = 117. булевы функции одной и двух переменных - student2.ru = булевы функции одной и двух переменных - student2.ru
11. = 146. булевы функции одной и двух переменных - student2.ru булевы функции одной и двух переменных - student2.ru
12. = 158. булевы функции одной и двух переменных - student2.ru булевы функции одной и двух переменных - student2.ru
13. = 128. булевы функции одной и двух переменных - student2.ru булевы функции одной и двух переменных - student2.ru .
14. = 185. булевы функции одной и двух переменных - student2.ru булевы функции одной и двух переменных - student2.ru .
15. = 194. булевы функции одной и двух переменных - student2.ru булевы функции одной и двух переменных - student2.ru
16. = 137. булевы функции одной и двух переменных - student2.ru = булевы функции одной и двух переменных - student2.ru .
17. = 194. булевы функции одной и двух переменных - student2.ru булевы функции одной и двух переменных - student2.ru .
18. = 239. булевы функции одной и двух переменных - student2.ru булевы функции одной и двух переменных - student2.ru .
19. = 253. булевы функции одной и двух переменных - student2.ru = булевы функции одной и двух переменных - student2.ru
20. = 246. булевы функции одной и двух переменных - student2.ru = булевы функции одной и двух переменных - student2.ru
21. = 125. булевы функции одной и двух переменных - student2.ru булевы функции одной и двух переменных - student2.ru
22. = 113. булевы функции одной и двух переменных - student2.ru булевы функции одной и двух переменных - student2.ru
23. = 114. булевы функции одной и двух переменных - student2.ru = булевы функции одной и двух переменных - student2.ru
24. = 249. булевы функции одной и двух переменных - student2.ru булевы функции одной и двух переменных - student2.ru
25. = 223. булевы функции одной и двух переменных - student2.ru = булевы функции одной и двух переменных - student2.ru .

4. СИСТЕМЫ БАЗОВЫХ (ЭЛЕМЕНТАРНЫХ) ОПЕРАЦИЙ

Определение булевых функций двух переменных (3.2) дает возможность убедиться в справедливости следующих равенств

булевы функции одной и двух переменных - student2.ru булевы функции одной и двух переменных - student2.ru (4.1)

На основании этого можно записать следующие тождества:

булевы функции одной и двух переменных - student2.ru (4.2)

булевы функции одной и двух переменных - student2.ru ; (4.3)

булевы функции одной и двух переменных - student2.ru , булевы функции одной и двух переменных - student2.ru ; (4.4)

булевы функции одной и двух переменных - student2.ru , булевы функции одной и двух переменных - student2.ru ; (4.5)

булевы функции одной и двух переменных - student2.ru , булевы функции одной и двух переменных - student2.ru ; (4.6)

булевы функции одной и двух переменных - student2.ru , булевы функции одной и двух переменных - student2.ru . (4.7)

С этих формул следует, что любая формула (булева функция) может быть представлена с помощью операции отрицание и любой операции из вышеперечисленных пар операций (1,0), булевы функции одной и двух переменных - student2.ru , булевы функции одной и двух переменных - student2.ru , булевы функции одной и двух переменных - student2.ru , булевы функции одной и двух переменных - student2.ru . Такие операции называются элементарными (базовыми), а их совокупность ― системой элементарных (базовых) операций.

Примером (одним из важнейших) систем элементарных операций есть

булевы функции одной и двух переменных - student2.ru (4.8)

Эта система элементарных операций ― избыточна. Это следует из истинности равенств

булевы функции одной и двух переменных - student2.ru , (4.9)

булевы функции одной и двух переменных - student2.ru , (4.10)

Эти равенства доказываются с использованием таблицы истинности:

булевы функции одной и двух переменных - student2.ru

Из равенств (4.9) и (4.10) следует, что систему элементарных операций (4.8) можно сократить, например, к системе:

( булевы функции одной и двух переменных - student2.ru (4.11)

Система элементарных операций (4.11) очень удобна и широко используется на практике. Она избыточна, так как

булевы функции одной и двух переменных - student2.ru , (4.12)

булевы функции одной и двух переменных - student2.ru , (4.13)

и поэтому ее можно сократить до

булевы функции одной и двух переменных - student2.ru (4.14а)

или

булевы функции одной и двух переменных - student2.ru . (4.14б)

Однако, и эти системы избыточны, если учесть тождества

булевы функции одной и двух переменных - student2.ru , (4.15)

булевы функции одной и двух переменных - student2.ru , (4.16)

булевы функции одной и двух переменных - student2.ru . (4.17)

С этих формул следует, что системы (4.14а) и (4.14б) можно сократить до одной операции:

булевы функции одной и двух переменных - student2.ru (4.18)

или

булевы функции одной и двух переменных - student2.ru . (4.19)

Впрочем, особенного практического значения это не имеет.

При вычислениях значений формул с операциями (4.8) следует учитывать их приоритеты:

– отрицание булевы функции одной и двух переменных - student2.ru ;

– конъюнкция булевы функции одной и двух переменных - student2.ru ;

– дизъюнкция булевы функции одной и двух переменных - student2.ru

– импликация булевы функции одной и двух переменных - student2.ru

– эквивалентность булевы функции одной и двух переменных - student2.ru

(сначала выполняются операции с меньшим номером в этом списке ― операции с большим приоритетом).

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

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

/*Пример 4.1.

Вычислить значение выражения

булевы функции одной и двух переменных - student2.ru

при булевы функции одной и двух переменных - student2.ru , булевы функции одной и двух переменных - student2.ru , булевы функции одной и двух переменных - student2.ru , булевы функции одной и двух переменных - student2.ru .

Выполнение:

1. булевы функции одной и двух переменных - student2.ru ;

2. булевы функции одной и двух переменных - student2.ru ;

3. булевы функции одной и двух переменных - student2.ru ;

4. булевы функции одной и двух переменных - student2.ru ;

5. булевы функции одной и двух переменных - student2.ru ;

6. булевы функции одной и двух переменных - student2.ru ;

7. булевы функции одной и двух переменных - student2.ru ;

8. булевы функции одной и двух переменных - student2.ru . */

5. БУЛЕВЫ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ

Булевы функции многих переменных ( булевы функции одной и двух переменных - student2.ru ) обычно записываются в виде логических формул, содержащих n логических переменных. Эти формулы можно получить суперпозицией с формул с одной или двумя переменными. Таблица истинности для функций многих переменных вычисляется по определению логических операций (1.1.0 ― 1.1.11).

/*Пример 5.1

Пусть задана функция двух переменных

булевы функции одной и двух переменных - student2.ru .

Подставим

булевы функции одной и двух переменных - student2.ru , булевы функции одной и двух переменных - student2.ru , булевы функции одной и двух переменных - student2.ru

в выражение заданной функции и получим функцию трех переменных

булевы функции одной и двух переменных - student2.ru .

Построим таблицу истинности этой функции.

булевы функции одной и двух переменных - student2.ru . */

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 2

Упражнение 1. Вычислить значение выражения

булевы функции одной и двух переменных - student2.ru

если булевы функции одной и двух переменных - student2.ru .

Выполнение.

1. булевы функции одной и двух переменных - student2.ru ;

2. булевы функции одной и двух переменных - student2.ru ;

3. булевы функции одной и двух переменных - student2.ru ;

4. булевы функции одной и двух переменных - student2.ru ;

5. булевы функции одной и двух переменных - student2.ru ;

6. булевы функции одной и двух переменных - student2.ru ;

7. булевы функции одной и двух переменных - student2.ru

8. булевы функции одной и двух переменных - student2.ru (значение выражения).

Упражнение 2.Определить номер функции трех переменных

булевы функции одной и двух переменных - student2.ru .

Выполнение.

булевы функции одной и двух переменных - student2.ru .

В результате:

булевы функции одной и двух переменных - student2.ru .

ВАРИАНТЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

Наши рекомендации