Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
ф1 (#111 • ? ч ^11| • • ?nlj ? * Xni) , .. >
* ? *t (^il? 1 • 'J » 1 •! ?«1| • 1 », Xtl./) ,
где l = ]log2 к [ *), причем если значение at имеет двоичный код сщ ... а(, (1 = 1, ..п), то значение /(cti,.. .,а„)
имеет двоичный код
ф1(®ц, • • ч CSi?, • ? *i Ot-ni)". • »
* * ? Ф* (®ilj * • *i Oti?, . . CCni, .. -, OCth!) •
При этом операции суперпозиции в Рн будет соответствовать весьма специальная операция над системой функций (ер*, ..фЭ из Pi. Возможность кодирования функций из Ри системами функций из Р2 может быть полезной при решении логических задач на ЭВМ, но мало что дает для исследований в ковечнозначных логиках. Факты, свидетельствующие о своеобразии Ph при к > 3, были известны, начиная с работ Слупецкого [50], а также работ Кузнецова [15] и Яблонского [35, 36]. Однако более поздние результаты показали, что различие между Ph и Р2 значительно существеннее, чем это казалось раньше.
В настоящем параграфе мы собираемся коснуться лишь некоторых сторон этой проблемы. Пас будут интересовать следующие три вопроса.
1. Вопрос о существовании базисов для замкнутых классов в Рк.
2. Вопрос о мощности системы всех замкнутых классов в Pk.
3. Вопрос о возможности представления функций пз Рк посредством полиномов.
*) ]а[ обозначает наименьшее целое число, не меньшее а,
ГЛ. 2. fc-ЗНАЧНАЯ ЛОГИКА
Є?
Как это вытекает из теорем Поста и Жегалкина, в алгебре логики мы имеем следующие ответы на поставленные вопросы.
1. Каждый замкнутый класс в Рг имеет конечный базис.
2. Мощность множества всех замкнутых классов в Рг равна Н0.
3. Всякая функция в Р2 может быть записана в виде полинома по mod 2.
Для Рь (к 5s 3) соответствующие ответы составляют содержание последующих теорем. Первая из них есть теорема Янова.
Теорема 11 (Янов [39]). Для всякого к (к > 3) существует в Рк замкнутый класс, не имеющий базиса.
Доказательство. Рассмотрим последовательность функций
/о “ О*
II при х, = ... = Хі = 2, n . (і - 1, 2, ...).
IU в остальных случаях
Обозначим через множество всех функций, получающихся из {/0, /ь . ..} путем переименования (без отождествления) переменных. Легко видеть, что 2Jtb — замкнутый класс. Допустим, что 9Д* имеет базис. Тогда в базисе іпііі,Четен функция f, получающаяся из функции }а0 путем переименования переменных, для которой число пв минимально. Далее возможны два случая.
1. Базис содержит еще хотя бы одну функцию Этой функции соответствует функция fnL и Пі > п0. Так как /,,и может быть получена из fHl путем отождествления переменных, то f выражается через что противоречит определению базиса.
2. Базис состоит из единственной функции f. В этом случае никакая функция /„ нри п > пй не может быть получена из f, так как (..., /,v ...)s0. Мы опять приходим к противоречию.
Итак, остается допустить, что 2Я* не имеет базиса. Теорема доказана.
Теорема 12 (Мучник [39]). Для всякого к (к > 3) существует в Рк замкнутый класс со счетным базисом.
5*
ей Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
Доказательство. Рассмотрим последовательность функций (1 = 2, 3, ...)
..а+) =
1 при х1= ... = Хз-1 = Х}+1 = ,.. = х1= 2, Х)=1 ?
= ' (/ ~ • ? • ). Ос
О в остальных случаях.
Обозначим через замкнутый класс, порожденный системой (/г, /з, ..Покажем, что эта система является базисом в ЭЛ,,. Для доказательства достаточно установить, что никакая из функций /„, не может быть выражена в виде формулы через остальные функции системы, т. е. что невозможно представление
/т = 5? [/г, * ? «, /т-1, /т+1, • •
Если записать формулу 51 несколько подробнее, то получим
51 [/г, - . /т-1, /т+1, • • *1 =
' /г (^[/г, * * /т—1, /т+1, • • *], • . •
• • », ^г[/г, ? • •, /т—1, /т+1, • • ?])
ИЛИ
/т(й+, • • Л-т)
/г (^Д/г, ? • *, /т—1, /т+1, • > •], • • *
* ? •, ^[/г, * ? >, /т-1, /т+1, ,..])*
Априори возможны три случая.
1. Среди формул 53,, ..., 33г (здесь г >2) по крайней мере две формулы ОТЛИЧНЫ от символов переменных. Тогда при любых значениях переменных хи ..хт на соответствующих местах функции /г возможны лишь значения 0 и 1 и поэтому правая часть будет тождественно равна нулю. Последнее противоречит возможности такого представления, так как /т Ф 0.
2. Среди фюрмул §91? ..39г найдется только одна фор-' мула 5)3, которая отлична от символа переменной. По условию остальные формулы сводятся к переменным, и поскольку г >2, то найдется по крайней мере одна формула 53Р = Хд. Рассмотрим набор хх — ... — а;й_1 = #3+, =...
... = хт = 2 и хд = 1. На этом наборе формула 53а принимает значение либо 0, либо 1. Следовательно, при данном выборе значений переменных у функции }Т на двух ме-
ГЛ. 2. ft-ЗНАЧНАЯ ЛОГИКА
69
стах будут стоять значения, отличные от 2. Поэтому правая часть примет значение 0. Б то же время левая часть на данном наборе равна 1. Мы пришли к противоречию.
3. Все формулы ©!, ..— символы переменных. В этом случае г>т и, следовательно, в формуле встретятся по крайней мере два вхождения некоторой переменной хр. Взяв набор #, = ...= хр-± = xp+i = ...== хт = = 2 и хр = 1, мы обратим левую часть в 1, а правую в 0. Следовательно, этот случай также невозможен. Теорема доказана.
