Читать онлайн «Кибернетический сборник. Старая серия. Выпуск 8»

Кибернетический сборник 8 СБОРНИК ПЕРЕВОДОВ под редакцией А. А. Ляпунова и О. Б. Лупанова 19 6 4 Издательство • МИР • Москва Научный совет по кибернетике Академии наук СССР Сборник работ зарубежных авторов по различным вопросам теории управляющих систем — восьмой в выпускаемой с 1960 г. Издательством иностранной литературы серии сборников по кибернетике. В первом разделе помещены статьи по различным вопросам математической логики, синтеза вероятностных преобразователей и теории кодирования. Второй раздел посвящен применению в цифровых вычислительных машинах систем счисления остаточных классов (вместо обычных позиционных систем счисления). В двух статьях последнего раздела рассматриваются модели образования привычек и обучения. Указаны способы реализации этих моделей. Сборник будет полезен математикам, специалистам по вычислительной технике, а также лицам других специальностей, занимающимся вопросами кибернетики и ее приложений. Редакция литературы по математическим наукам Математические вопросы НЕКОТОРЫЕ КРИТЕРИИ ПОЛНОТЫ ДЛЯ МНОЖЕСТВ ФУНКЦИЙ МНОГОЗНАЧНОЙ ЛОГИКИ ) Л. Саломаа 1. Пусть Еп обозначает множество функций f(xv ... , xk), у которых значения и аргументы х1 принадлежат фиксированному конечному множеству N={1, 2, ... . п], /г>2. Будем говорить, что подмножество F с Еп порождает функцию /, если / представляется в виде суперпозиции элементов из F. В частности, F называется полным множеством (или множеством Шеффера), если оно порождает каждый элемент из Еп2). В настоящей статье мы установим некоторые критерии полноты. Всюду в дальнейшем п обозначает число элементов в множестве N. Введем еще некоторые термины и понятия. Пусть Gv ... , Gk— непустые подмножества N. Тогда f(Gv ... . Gk) обозначает множество значений, принимаемых функцией f(xv ... . xk), если для каждого / аргумент х{ принимает любые значения из множества G . Функция f(xv ♦. . , Xj, ... , xk) существенно зависит от аргумента Xj, если существуют множества G/t такие, что f(Ov ... . Gy. ... . Gk) содержит по крайней мере два элемента, а каждое G/f / Ф у, содержит только один элемент. Функция f(xx, ... , xk) удовлетворяет условию Слупецкого, если она существенно зависит по крайней мере от двух аргументов и принимает все п значений, т. е. f(N, ... , N) = N. Говорят, что функция одного аргумента g(x) имеет род t (1 ^ <;*<>), если она принимает в точности t значений. Функция g(x) рода / имеет тип [av a2, ... . at], если av— натуральные числа, такие, что ах-{- #2 + ... -f- а, •-= п и для каждого v, 1<><Л существует значение bv, которое функция g(x) принимает в точности #v раз. В этом разделе мы докажем следующее утверждение. 1) Salomaa A. , Some completeness criteria for sets of function >ver a finite domain, I, II, Turun Yloplston Julkaisuja Annates UniversitatL fur- kuensis, sarja A, 53 (1962), 1—9; 63 (1963), 1—19. 2) Подробные определения см. в [1] или [2]. 8 А. С Л Л О Л1 А А Теорема 1. Предположим, что п "> Ь и F — подмножество Еп, содержащее группу четных подстановок Ап и произвольную функцию f{xv ... . xk), удовлетворяющую условию Слупецкого. В этом случае F полно. Предварительно докажем несколько лемм.