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

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

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

(3.1)

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

(3.2)

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

― константа 0;

― повторения аргумента;

― отрицание аргумента,

― константа 1;

― константа 0;

― конъюнкция;

― отрицание импликации;

― повторение аргумента ;

― отрицание обратной импликации;

― повторение аргумента ;

― сложение по модулю 2;

― дизъюнкция;

― стрелка Пирса;

― эквивалентность;

― отрицание аргумента ;

― обратная импликация;

― отрицание аргумента ;

― импликация;

― штрих Шиффера;

― константа 1.

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

/*Пример 3.1

,

. */

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

/*Пример 3.2

. */

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

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

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

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

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

,

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

.

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

Выполнение.

.

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

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

Выполнение.

.

.

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

.

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

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

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

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

(4.1)

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

(4.2)

; (4.3)

, ; (4.4)

, ; (4.5)

, ; (4.6)

, . (4.7)

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

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

(4.8)

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

, (4.9)

, (4.10)

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

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

( (4.11)

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

, (4.12)

, (4.13)

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

(4.14а)

или

. (4.14б)

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

, (4.15)

, (4.16)

. (4.17)

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

(4.18)

или

. (4.19)

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

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

– отрицание ;

– конъюнкция ;

– дизъюнкция

– импликация

– эквивалентность

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

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

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

/*Пример 4.1.

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

при , , , .

Выполнение:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. . */

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

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

/*Пример 5.1

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

.

Подставим

, ,

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

.

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

. */

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

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

если .

Выполнение.

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7.

8. (значение выражения).

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

.

Выполнение.

.

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

.

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