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

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


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

имеет
столбец. В первых
столбцах указываются значения аргументов
, а в
-ом столбце значение функции на этих аргументах -
.

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

  .  .  .  
  

  .  .  .  
  

  .  .  .  
  

  .  .  .  
  

.  .  .  .  .  .

  .  .  .  
  

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

существует такое
, что при
а
. Если эти наборы рассматривать как записи чисел в двоичной системе счисления, то 1-ая строка представляет число 0, 2-ая - 1, 3-я - 2, ... , а последняя -
.

При больших

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

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



Содержание раздела