С.В. Яблонский - Введение в дискретную математику (1060464), страница 11
Текст из файла (страница 11)
Все могут быть порождены 1 при у; (х) 0 при Яункции одной переменной иг Р, Й ууункцияуки х О, (1=1, ...,Й вЂ” 1) х 1, х в остальных случаях $ 5. Особенности Й-значнык логик Предыдущий материал показывает, что во многом конечнозначные логики положи на двузначную логику. В них сохраняются многие результаты, имеющие место в двуаначной логике.
Правда, рост значности все-таки 3 Ввававиа в виакра ую иаю ауику и функцией Ь(х). Доказательства этик теорем несложны, поэтому они опускаются. В ааключение рассмотрим еще одно приложение доказанного критерия полноты. Мы дадим характеристическое свойство функции из Р„образующей полную систему (функппя Шеффера). Это свойство является незначительным усилением теоремы Мартина 144$ Теорема 10.
Фупкция 1(хо ..., х„) иг Р„где Й >3, является ууункцигй Шгугуууугра тогда и только тогда, когда 1(х„..., хв) порождает все функции одной переменной, принимающие нс более Й вЂ” 1 значений. Доказательство. Необходимость очевидна. Достаточность. Очевидно, Дх„..., х„) должна принимать все Й значепнй, так как из нее получаются, например, все константы.
Если ( — несущественная функция, то ( есть подстановка и из нее можно получить только подстановки. В этом случае мы не получим даже констант. Значит, это невозможно, т. е. 1 является существенной функцией. Применяя критерий полноты, приходим к тому, что система $ = ()(хо ..., х„)) является полной. Теорема доказана. бб ч. г. фтнкцнонлльнык снсткмы с опкглцнязгн приводит к известным уело!кненпям формулировок и доказательств. Однако теперь уже накоплено достаточно много фактов, указывающих на своеобразие конечнозначных логик, в том числе и фактов, выявляющих существенное отличие Р, при й ~ 3 от Р,.
Этк обстоятельства тем более заслуживают внимания, если иметь в виду работу Поста [46], в которой была выдвинута идея сведения конечнозначных логик к двузначной логике. Он предложил вместо функции 1(л„..., л„) из Р, рассматривать спетому функций ф!(х!о ° ° ! л!!! ° . ! зи!! ° ° .! ля!)! ° ° ° ° ° ! ф!(л!!! ° ° ! х«, ° ., хл!..., зм), где 1=]1оя!Й[е), причем если значение а, имеет двоичный коД ао... а<, (! = 1, ..., л), то значение 1(а„..., а„) имеет двоичный код !р!(а!о ° ° в а!!ю ° ° ! аа!! ° ° .! аю!) ...
ф!(аго ..., сс,!, ..., а„„..., а.,). При этом операции суперпозиции в Р, будет соответствовать весьма специальная операция над системой функций (ф„..., <р,) из Р,. Возможность кодирования функций из Р, системами функций из Р, может быть полезной при решении логических вадач на ЭВМ, но мало что дает для исследований в конечнозначпых логиках. Факты, свидетельствующие о своеобразии Р, прп й ~ 3, были известны, начиная с работ Слупецкого [50], а также работ Кузнецова [15] и Яблонового [35, 36]. Однако более поздние результаты показали, что различие между Р, и Р, значительно существеннее, чем это казалось раньше.
В настоящем параграфе мы собираемся коснуться лишь некоторых сторон этой проблемы. Нас будут интересовать следующие три вопроса. 1. Вопрос о существовании базисов для замкнутых классов в Р.. 2. Вопрос о мощности системы всех замкнутых классов в Р„. 3. Вопрос о возможности представления функций из Р, посредстзоы полиномов. а) )э( обозначает азвмевьшеэ целое число, ве иевывеэ а. ГЛ. З.
З-ЗНАЧНАЯ ЛОГИКА Как зто вытекает иа теорем Поста и Я(егалкияа, в алгебре логики мы имеем следующие ответы на поставленные вопросы. 1. Каждый замкнутый класс в Р, имеет конечный базис. 2. Мощность множества всех замкнутых классов з Р, равна И,. 3. Всякая функция в Р, может быть записана в виде полинома по гной 2. Для Р, (й ~ 3) соответствующие ответы составляют содержание последующих теорем.
Первая из нпх есть теорема Янова. Теорема 11 (Янов [39]). Для всякого й (Й~ 3) существует в Р„замкнутый класс, не имеющий базиса. Доказательство. Рассмотрим последозательпость функций ~з = О, (1 при х, ... х; = 2, (О в остальных случаях Обозначим через йй„множество всех функций, получающихся из Ц„)и ...) путем переименования (без отояздествления) переменных. Легко видеть, что йй„— замкнутый класс. Допустим, что зк, имеет базис. Тогда в оазисе найдется функция ~, получающаяся из функции т'.,з пу тем переименования переменных, для которой число п, минимально. Далее возможны два случая.
1. Базис содержит еще хотя бы одну функцию ~'. Этой функции соответствует функция тз, и н,) л,. Так как ),, может быть получена из т'„, путем отождествления переменных, то ~ выражается через у', что противоречит определению базвса. 2. Базис состоит из единственной функции ~. В етом случае никакая функция )„ при и ) и, не может быть получена из Г, так как ),,(..., )„ы ...) = =О. Мы опять приходим к противоречию. Итак, остается допустить, что И, не имеет базиса. Теорема доказана.
Т е о р е и а 12 (Мучник [39]). Для всякого й (й > 3) существует в Р„замкнутый класс со счетным базисом. 63 ч. ь Фуппц!гоналънык снстямы с Опквациями Докааательство. Рассмотрим последовательность функций (г 2, 3, ...) 1,(х„..., х,)— 1 при я,= ... -х~,-х~+,- ... = х,= 2, х,-1 0 1 ° г1)т О в остальных случаях. Обозначим через йй„замкнутый класс, порожденный системой ()н 5, ...). Покажем, что зта система является базисом в йь Для докааательства достаточно установить, что никакая из функций 1 не может быть выражена в виде формулы через остальные функции системы, т.
е. что невозможно представление 1.=6[~*..", 1.-о 1.+ь" 1 Если записать формулу 6 несколько подробнее, то получим И (Ун ° ° ~ 1 -ь 1 +о ° ° т -1.(6И, ".,1 —,1+," 1, "° ...! 6 Рм ° ° ~ 1 -н 1т+н ° )) или 1-( " *-)- - И03~, ..., ~--, 1.+, 1, "° ..., 6,1Ь, .", 1 -, 1 +, " ]) Априори возможны три случая. 1. Среди формул 6„..., 6, (здесь г> 2) по крайней мере две формулы отличны от символов переменных. Тогда при любых значениях переменных хо ..., х на соответствующих местах функции 1, воаможны лишь значения О и 1 и поэтому правая часть будет тождественно равна нулю. Последнее противоречит возможности такого представления, так как 1„ че О.
2. Среди формул 6„ ..., 6, найдется только одна формула 6„ которая отлична от символа переменной. По условию остальные формулы сводятся к переменным, и поскольку г> 2, то найдется по крайней мере одна формула 6т я,. Рассмотрим набор х, ... я,, я,+, х ° 2 и ят 1. На этом наборе формула 6, принимает значение либо О, либо 1.
Следовательно, при данном выборе значений переменных у функции ~, на двух ме- 69 2'Л. 2. »-ЗНАЧНАЯ ЛОГНКЛ стах будут стоять значения, отличные от 2. Поэтому правая часть примет аначение О. В то же время левая часть на данном наборе равна 2. Мы пришли к противоречию. 3.
Все формулы 2)» ..., Е, — символы переменных. В этом случае г> и» и, следовательно, в формуле встретятся по крайней мере два вхоягдения некоторой переменной хр. Взяв набор х, ... х,, х,+, ... х,. ° 2 и х, 2, мы обратим левую часть в 1, а правую в О. Следовательно, этот случай также невозможен. Теорема доказана. Непосредственно к докааанному примыкает следующая теорема. Теорема 23. Для всякого й (й > 3) Р, содержит континуум различных замкнутых классов. Доказательство. Число замкнутых классов в Р.
можно оценить сверху числом всех подмножеств функций из Р,. Так как Р, содержит счетное число функций, то число подмножеств Р, равно континууму. Для завершения доказательства нужно оценить снизу число замкнутых классов в Р,. С этой целью рассмотрим замкнутый класс йки построенный прп доказательстве предыдущей теоремы. Этот класс имеет базис (1и 1., " ). Образуем для каждой последовательности (р» рь ), где 2 < р, < р, <..., класс ЮЦР» ри ...) как класс, порожденный системой функций[1р», 1р,, ...].Легко видеть, что е))»(Р» Р» ° ° )Фу))»(Р» Р»2 ° ° )» (Р» Рг, " ) чь (Р', Рг', " ! Следовательно, семейство ИИ~(р» ри ...)) является континуальным семейством.
Теорема доказана. Теорема $4. Система полиномов по шойй полна в Р„ тогда и только тогда, когда й р, где р — простое число. Доказательство. Легко видеть, что для любой функции 1(хи ..., х„) иа Р, имеет место представление 1(х„..., х„) Х 1о (х») ° ° ° 1ев (х,.) 1(о„..., о„) (шод й). (в»,...,вв) оо ч.
1. Фтнкционвльные системы с ОпеРАЦийми Поэтому вопрос о представимости функции ( полиномами по шой)с сводится к вопросу о представимости в виде полиномов функций !о(х)о ° ° о 1о-о(Х) ° В силу того, что а, + а,(р — 1)' + а,(р — 1)' + ... + ав о(р — 1)' ' - а(р — 1) Определитель атой системы 1 О О 1 1 1 Ь 1 2 2 О 1Р 1 2Р— (Л-1!' " (Л-1)в ' есть определитель Вандермонда. Как известно, П () — ). Оло()СР-1 о) Малая теорема Ферма обосвовывается тав. Пусть 1 ( а ~ М; Л вЂ” 1, тогда числа П а 1, ..., оа о а(Л вЂ” 1) ве сравввмы по овойр. Поэтому П ... гв р ооо (Л вЂ” 1)! (шобЛ) и (р — 1)! ва ааво-'(р — 1)! (ооой Л) вли 1 аа ав ' (шой Л). 1~ (х) = )о (х — о), мы можем утверждать, что система полиномов по шой й ' полна тогда и только тогда, когда представима в виде полинома функция Ь(х).
1. Пусть й р. В этом случае, опираясь на малую теорему Ферма ав ' 1(шой р) (1 < а < р — 1), получаем 1,(х) 1 — х' ' (шойр), т. е. Систеыа полиномов полна в Роа). Можно указать другой способ решения этой же зада- чи. Будем искать представление функции я(х), вавися- п(ей от одной переменной, в виде полинома, пользуясь методом неопределенных коэффициентов я(х) по+ а,х+... + ав,х' '. Мы получаем систему уравнений ао+а, 0'+а, 0'+...+а,, 0'-' я(О), а,+а, 1о+ао 1'+... +ав о 1о '- я(1), а,+а, 2'+а, 2'+...+ав о 2" '=у(2), 21 ГЛ.
2. А-ЗНАЧНАЯ ЛОГИКА Так как р — простое число, то А чь 0(шеар). Пользуясь правилом Крамера и учитывая, что»2 Ф 0(шо») р), мы сможем решить в целых числах сравнения а»»2»2»(шо») р) (» = О, ..., р — 1), где Л» — соответствующий минор. Итак, мы приходим к единственному решению исходной системы и, следовательно, к полиному, изображающему л(х). 2. Пусть й чар. Тогда й =й»й„где й > й» > 1. Допустим, что 1»(х) = Ь, + Ь»х+... + Ь х' (п2о») й).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
