Спирина, М.С. Дискретная математика

f ( x i, x2, ..., х*_ь x*, x*+I, x„) зависит от переменной xk сущ е ­ с т в ен н о . если 3z = (z,, z2, zk_ i, zk, z*+1, ..., z„) e В" такой, что f(.Z 1» ^2, •••> Zk- i , Zk, Zk+ 1 , Z„) ^ f ( Z \ , Z2, . . . , Z*_ ] , Z^, Z/.+ | , z „ ) . В таком случае сама переменная хк называется с ущ е с т в ен н о й . Если х* не является существенной, т.е. Vz = (z,, z2, . . . , zA_ ,, zk, zk+l, ..., z„) e Bn выполняется равенство/ ( z , , z2, ..., z*_ ,, z*. z*+1, ..., z„) = = / ( z , , z2, ..., z*_|, zk, zk+u ..., z„), то переменная x* называется ф ик тивн ой . Например, тождественные нуль и единица любого чис­ ла переменных ни от одной из них не зависят существенно. Для лучшего осознания несущественности можно привести анало­ гичный пример из геометрии. Функция z(x, у) = 5х + 4 не зависит от переменной у явно, и ее график состоит из прямых, парал­ лельных оси у. Вдоль каждой такой прямой значение х не меняется, у — меняется, а значение функции z не меняется. В двоичной логике та же ситуация, но рассматриваются только значения ар­ гументов 0 и 1. Например, в функции (11000011) фиктивной яв­ ляется третья переменная, в функции ( 11001100 ) — первая и тре­ тья, в функции ( 00110010 ) все переменные существенны. Очевидно, что к любой функции п переменных можно ис­ кусственно добавить к фиктивных переменных, например, при­ веденным выше способом, домножив на х л+1 vx^T,. Соответствен­ но из таблицы истинности можно вычеркнуть столбец фиктив­ ной переменной х* и повторяющиеся строки, например, вида ( Z | , Z2, • •• , Zk _ \ , 1 , Z ^ + i , . . . , Zrt) И Л И ( Z | , Z2 , . . . , Zk __ | , 0 , Zk+ 1, . . . , Z„ ) по выбору. Полученные таким способом функции будем считать равными. С п о с о бы за д ан и я б ул евы х ф ункций . Мы убедились, что логи­ ческую функцию можно задать ан ал и т и ч е ск и , т.е. в виде форму­ лы, или с помощью таблицы истинности, в левой части которой выписаны все возможные значения аргумента, а в правой — соот­ ветствующие им значения функции. Таблица истинности для бу­ левой функции п переменных будет иметь вид (табл. 4.4). Мы выписали сводные таблицы для функций при п = 1 и п - 2 и показали, что этим функциям соответствуют унарные и би­ нарные отношения. Можно было бы выписать такую масштабную Т а б л и ц а 4.4 Таблица истинности для булевой функции п переменных *1 *2 х п / (* ь * 2 , 0 0 0 0 > О о . , 0 ) 0 0 0 1 о о , 0 1 ) 1 1 1 0 / ( 1 1 , . . , 1 0 ) 1 1 1 1 / ( 1 1 , . . , 1 ) 139