3.5 Логические функции многих переменных
Все логические операции, которые были рассмотрены в 3.2, распространяются и на функции нескольких переменных. Теперь будем рассматривать функции F(x1, x2,…, xn), где xi - логические переменные, которые принимают значения нуля или единицы. Для описания логики функционирования аппаратных и программных средств компьютера используется алгебра логики, или булева алгебра. Два элемента алгебры логики - ее константы - 0 (ложь) и 1 (истина). Во всех компьютерах используются сигналы двух видов. Сигналы можно интерпретировать как двоичные числа, или логические переменные.
Логической функцией F от набора логических переменных х1,…, хn называется функция, которая может принимать только два значения: логический 0 и логическая 1.
Область определения логической функции конечна и зависит от количества возможных наборов аргументов. Если n - число аргументов, то количество возможных наборов аргументов равно 2n.
Множество значений функции F(x1,…, xn) - это множество {0,1}, т. е. F=0 либо 1.
Любая логическая функция может быть задана с помощью таблицы истинности, в левой части которой записываются наборы аргументов, а в правой - соответствующие значения функции.
x1 |
x2 |
… |
xn-1 |
xn |
F(x1, x2,…, xn-1, xn) |
|
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) |
|
… |
… |
… |
… |
… |
… |
|
1 |
1 |
… |
1 |
1 |
F (1,1,…, 1,1) |
Вектором значений булевой функции F(x1,…, xn) называется упорядоченный набор всех значений функции F, при которых значения упорядочены по лексикографическому порядку множества аргументов {0,1}n.
Поскольку всего имеется 2n наборов нулей и единиц (|{0,1}n|=2n), существует ровно булевых функций F(x1,…, xn) от n переменных:
.
При n=2 количество функций равно 16, при n=3 - 256 и т. д. На рис. 3 представлены в упорядоченном виде наборы аргументов для ряда функций - отрицания 0, функций одного, двух и трёх аргументов.
Рис. 3. Упорядоченные наборы аргументов
- Часть 3. Элементы алгебры логики
- 3.1 Введение в алгебру логики
- 3.2 Основные функции алгебры логики
- 3.3 Формулы алгебры логики
- Контрольные вопросы
- 3.4 Законы алгебры логики и следствия из них
- 3.5 Логические функции многих переменных
- 3.6 Построение формул алгебры логики по заданной таблице истинности
- Контрольные вопросы и упражнения
- Контрольные вопросы и упражнения
- Контрольные вопросы
- 3.9 Неполностью определенные логические функции
- 3.10 Формы представления булевых функций
- 3.10.1 Семантические деревья
- 3.10.2 Бинарные диаграммы решений (БДР)