Введение в схемы, автоматы и алгоритмы


Табличное представление


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

f(x_1, \ldots, x_n)
имеет
n+1
столбец. В первых
n
столбцах указываются значения аргументов
x_1, \ldots, x_n
, а в
(n+1)
-ом столбце значение функции на этих аргументах -
f(x_1,\ldots , x_n)
.

Таблица 1.1. Табличное представление функции

f(x_1, \ldots, x_n)
x_1
  .  .  .  
x_{n-1}
  
x_n
f(x_1,\ldots x_{n-1}, x_n)

0
  .  .  .  
0
  
0

0
  .  .  .  
0
  
1

0
  .  .  .  
1
  
0

.  .  .  .  .  .

1
  .  .  .  
1
  
1

f(0, \ldots, 0,0)

f(0, \ldots, 0,1)

f(0, \ldots, 1,0)

\ldots

f(1, \ldots, 1,1)

Наборы аргументов в строках обычно располагаются в лексикографическом порядке:

(\alpha_1, \ldots, \alpha_n) \prec (\beta_1, \ldots, \beta_n)\ \Leftrightarrow
существует такое
i \in [1,n]
, что при
j < i\ \alpha_j = \beta_j,
а
\alpha_i < \beta_i
. Если эти наборы рассматривать как записи чисел в двоичной системе счисления, то 1-ая строка представляет число 0, 2-ая - 1, 3-я - 2, ... , а последняя -
2^n-1
.

При больших

n
табличное представление становится громоздким, например, для функции от 10 переменных потребуется таблица с 1024 строками. Но для малых
n

оно достаточно наглядно.




Начало  Назад  Вперед



Книжный магазин