Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

8 обозначаются P 2 , множество всех логических функций n переменных – P 2 (n) . Для задания функции f(x 1 ,…,x n ) достаточно указать, какие значения функции соответствуют каждому из наборов значений аргументов, т.е. выписать таблицу 2.1. Таблица 2.1 x 1 ,…, x n-1 , x n f( x 1 ,…, x n-1 x n ) 0 ,…, 0, 0 f( 0, ,…, 0, 0) 0 ,…, 0, 1 f( 0 ,…, 0, 1) 0 ,…, 1, 0 f( 0 ,…, 1, 0) 0 ,…, 1, 1 f( 0 ,…, 1, 1) … 1 ,…, 1, 1 f( 1 ,…, 1, 1) Можно видеть, что наборы n переменных принимают 2 n различных наборов значений (Это может быть доказано по индукции). Для удобства мы будем использовать стандартное расположение наборов значений аргументов: если набор рассматривать как запись числа в двоичном исчислении, то расположение наборов соответствует естественному расположению чисел 0,1,...,2 n -1. Рассмотрим представление некоторого числа b в двоичной системе исчисления (т.е. в системе, имеющей только две цифры 0 и 1 ). Если b можно представить в виде b=b n 2 n + b n-1 2 n-1 +…+ b 1 2 1 + b o 2 o , где b i  B, i=0,…,n , т.е. либо 0 либо 1 , то двоичная запись числа b будет выглядеть следующим образом b n b n-1 …b 1 b o . Пример 1.2.1: 0 10 =0  2 o =0 2 1 10 =1  2 o =1 2 2 10 =1  2 1 +0  2 o =10 2 6 10 =1  2 2 +1  2 1 +0  2 o =110 2 Вернемся к приведенной выше таблице. При любом наборе значений аргументов логическая функция может принимать значение либо 0 , либо 1 . Поскольку число различных наборов