Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Определение. Система функций {Д, Д, ..Д, ..,} из замкнутого класса 2Я называется полной в 30Ї, если ее замыкание совпадает с ШЇ.
Иначе говоря, система полна в ЗОЇ, если каждая функция из ЗОЇ может быть выражена в виде формулы через функции данной системы.
Определение. Система функций {Д, Д, ..Л, . •.) из аамкнутого класса ЗОЇ называется его базисом, если она полна в ЗОЇ, но всякая ее собственная подсистема не является полной в 20Ї.
Так, система
Д = ХіХг, Д = 0, Д = 1, Д = Х1 + Хг + X,
является базисом в Р2. Можно показать, что система функций (0, 1, Хі&Хг, Хі V х2) является базисом для класса М.
Теорема 9 (Пост [47]). Каждый замкнутый класс иг Р3 имеет конечный базис.
Теорема 10 (Пост [47]). Мощность множества замкнутых классов в Р? — счетная.
Хотя вторая из этих теорем логически следует из первой, тем не менее в доказательстве Поста сначала устанавливается второй факт, а затем — первый.
Глава 2
Аг-ЗНАЧНАЯ ЛОГИКА
Конечнозначные логики вводятся как обобщение двузначной логики. В силу этого наше изложение местами будет кратким, а некоторые аналогичные определения и доказательства будут опущены. Особое внимание обратим на два обстоятельства:
1) в /е-значпых логиках сохраняются многие свойства и результаты, которые имели место в двузначной логике;
2) в к-зпачных логиках наблюдаются явления, обнаруживающие принципиальное их отличие от алгебры логики.
В связи с этим некоторые задачи не имеют такого
исчерпывающего решения как в алгебре логики, а другие вовсе не решены.
§ 1. Функции к -зпачной логики.
Формулы и реализация функций формулами
Пусть и — {и,, и2, ..ит, ..— исходный алфавит неременных (аргументов). Будем рассматривать функции / ,• ...»(Щу Ф «гц при V Ф р), аргументы
которых определены па множестве Ек = {0, 1, ..., к — 1), н такие, что /(й1, ..., ап)^Еъ когда а(? =
Для упрощения записи мы будем использовать для переменных пз II метаобозначения х, у, г, ..а также У и %1, ... и употреблять для функций более простую запись }{хч ..а:п).
Очевидно, что функция }(хи ..., хп) полностью определена, если задана ее таблица (см. табл. 1). В этой таблице наборы суть разложения в А-ичной системе счисления чисел 0, 1, ..кп — 1. Символ / здесь будет интерпретироваться как символ, обозначающий отображение, характеризуемое таблицей, а символы хи хг, ... ..., хп — как названия столбцов. Для функций одной переменной мы наряду с таблицами будем использовать запись в виде (обобщенной) подстановки
= 1, 2, ..п).
где 5 (а) = 1«.
?11 4 1 41я тЩИиНА.1ЬПЬЩ или 1±^Л1Ы и иИ.Ыг’АЩЩМН
обозначим через Рк множество всех функций &-знач-жШ лотки над алфавитом V, а также констант 0, 1, ... ., ,, к — 1. Так как число наборов (а1? .. а„) значений
нерешенных хи ..., хп равно кп, то имеем следующий реаультат.
Таблица 1
*1,-1 *»! /(*1, ? ?? • хп—1 х}1)
0 .. 0 0 /(<>, .. , 0, 0)
0 .. 0 1 Но, .. ,0, 1)
0 . 0 к —1 /(0, .. ,0. к — 1)
0 .. 1 0 НО, .. ,1, 0)
к — 1. к — 1 к Пк - 1, . . , к — 1 , к-1)
Теорема 1. Число всех функций из Рк, зависящих от п переменных х11 ..хп, равно киП-
Из сказанного вытекает, что в РК при к ^ 3 в значительной степени возрастают трудности по сравнению с Рг как в возможности эффективного использования табличного задания функции, так и в возможности просмотра всех функций от п переменных. Уже в Ря число функций от двух переменных равно З9 = 19683, т. е. это множество практически необозримо. В Рк часто употребляют вместо табличного задания функций задание при помощи алгоритма вычислимости функций. Например,
тах{;Г1, ..д:п)
можно рассматривать, как алгоритм, которых! для любого набора (а!, ..а„) значений переменных выдает их максимум. Этот алгоритм определяет в Рк единственную функцию, которую мы будем обозначать тем же символом.
Далее вводится {как в Р2) понятие существенной и несущественной переменных, а также понятие равенства функций. Это позволяет рассматривать функции в Рк с точностью до фиктивных переменных.
После этого рассматриваются примеры некоторых конкретпых функций из которые можно считать «элементарными» функциями.
1.) х — х 4- 1 (mod к). Здесь ? представляет обобщение отрицания в смысле «циклического» сдвига значений.
2) Nx = к — \ — х. Здесь Nx или, как часто обозначают, ~х является другим обобщением отрицания в смысле «зеркального» отображения значений, В литературе оно носит название отрицания Лукашевича.
Ik — 1 ври х — i,
О при хфг ' 7
Функции U (л;) при г Ф к — 1 являются обобщениями некоторых свойств отрицания.
[1 при х — г,
4) ;i (Л) = }о при хфи
Функция ji(x) — характеристическая функция значения i и при i?*k — 1 представляет собой обобщение отрицания.
о) min(xlt х2) — обобщение конъюнкции.
6) XiX2 (mod к) — второе обобщение конъюнкции.
7) max(*lt хг) — обобщение дизъюнкции.
8) Xi + ?2(mod к).
Из рассмотрения этого списка элементарных функций видно, что функции алгебры логики имеют в А-значной логике (к S* 8) по нескольку аналогов, каждый из которых обобщает соответствующее свойство функции.
Затем, так же как и в алгебре логики, вводится понятие формулы над множеством функций Формулы мы обозначаем символами St, S3,... без индексов и с индексами. Если мы хотим указать зависимость формулы от переменных или выделить функции, из которых построена формула, то употребляем обозначения
