Дискретно-непрерывная математика (стр. 55 )

Из леммы 1 и леммы 2 получаем теорему, которая дает кри­терий функциональной предполноты множества функций

Теорема . т. т.т., когда для любогоп

есть простое число.

В итоге мы имеем новое определение понятия простого числа: произвольное натуральное число является простым т. т.т., ко-

гда множество всех функций. соответствующее n+1-значным матричным логикам Лукасевича, есть функционально предполное

множество в Рп+1, а именно Отсюда следует, что суще-

ствует бесконечная последовательность-значных логик Лука-севича (ps — s-e в порядке возрастания простое число в натуральном ряду чисел), которым соответствует последовательность предполных множеств функций, такая, чтодля всех s =1,2,...

Обратим внимание, что после доказательства поя­вилось еще два доказательства этой теоремы: [Hendry 1983] и [Urquhart 1986]. Последнее доказательство целиком основа­но на критерии Мак-Нотона об определимости функций в За­метим, что на это уже указывал (см. [Финн 1976]), поскольку из теоремы Мак-Нотона следует утверждение леммы 2. Действительно,т. т.т., когда наибольший об­щий делитель чисел п и ξ делит нацело η.

Следствия из осмысления теоремы оказались со­всем неожиданными. Получен результат о структурализации про­стых чисел в виде корневых деревьев и представлен алгоритм, ко­торый по каждому простому числу строит его корневое дерево. Построена конечнозначная логика Kn+1 такая, что Kn+1 имеет класс тавтологий т. т.т., когда п есть простое число, при этом доказано, что для этого случая Kn+1 есть логика Лукасевича . Таким обра­зом, дана характеризация простых чисел посредством специального вида логических матриц. Построена функция (штрих) Шеффера для простых чисел, т. е. для классов функций, соответствующих Kn+1. Комбинирование различных алгебро-логических определений простого числа привело к формулировке алгоритма порождения классов простых чисел. Также дана характеризация посредством логических матриц степени простого числа, нечетных чисел и, са­мое сложное, чётных чисел. Всё это изложено в монографии [Кар­пенко 2000] (см. также [Karpenko 2006]), название которой было подсказано автору .

Здесь мы рассмотрим логику Kn+1 и ее функциональные свой­ства, а также сам алгоритм.

7.6.2. Матричная логика для простых чисел

Если простые числа можно охарактеризовать предполными клас­сами функций, то почему бы не найти характеризацию простых чисел посредством соответствующих классов тавтологий.

Впервые это было сделано в {Карпенко 1982; 1989] (см, также [Karpenko 1989]), где следующим образом определяется функция если и х, у имеют общий делитель;

в остальных случаях. Тогда логика Kn+1 отличается от заменой

Однако для более простого доказательства последующих тео­рем имеет смысл переопределить функцию

Определим матрицуследующим образом:

где

гдеобозначает, что х и у не являются взаимнопростыми

числами, аесть импликация Лукасевича.

Соответствующую матричную логику обозначим посредством а множество всех суперпозиций функций обозначим посредством

Теорема 1. Для любого есть простое число т. т.т., когда

(подробное доказательство см. в [Карпенко 2000]).

Таким образом, теорема 1 дает новое определение простого числа. Введя обычным образом пропозициональный язык и функцию оценки v на нем, получаем, что матричная логика имеет класс тавтологий т. т.т., когда п есть простое число, т. е. каждое простое число определяется соответствующим классом тавтологий. В связи с этим возникает нетривиальный вопрос о функциональных свойствах

Теорема 2. Для любоготакого, что п есть простое число,

Доказательство.

Из определения следует, что множество функций

не является функционально полным ни для какого По край-

ней мере функциисохраняют множество значений

{0, п}, как и множество функций Поскольку множество

функционально предполно для случая, когда п есть простое число (теорема ), то для этого случая

Надо показать, что функция.определима посредством

суперпозицииЭто можно сделать с помощью следую-

щих определений:

Полное доказательство см. в [Карпенко 2000], что намного ко­роче, чем доказывать эту теорему с функцией

Теорема 3. Для любого п есть простое число т. т.т,, когда

Доказательство;

I. Если есть простое число, то (теорема 2).

ІІ. Если то есть простое число. Докажем

контрапозицию этого утверждения. Пусть не есть простое

число. Тогда из теоремы 1 (необходимость) следует, что Но свойства множества функций такие, что для любого

Следовательно, еслине есть простое число, то

В заключение определим функцию Шеффера для класса

функций Кп+1 (см. [Karpenko 1994; 2006] :

Теперьпосредством функциинадо определить функции

7.6.3. Алгоритм порождения классов простых чисел

Заменим в теореме 2 (ІІ) функциюна функцию Обо-

значим новую последовательность формул посредством (А*) -( D*). Нетрудно показать, что тогда формула (D*):