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

определяет импликацию Лукасевича только для первых пяти

нечетных чисел: 3, 5, 7, 11 и 13. Однако если

то в общем случае Например, пусть п = 17,

х= 2 и у= 12. Тогда

Таким образом,. в то время как Можно показать, что итерация формулы (D*) будет задавать классы простых чисел, для которых формулаопределяет Пусть

Тогда

и так далее.

Таким образом, смысл итерации состоит в том, что берется исходная формула в ней осуществляется операция замены

дизъюнкции на импликацию(эту операцию обозначим по­средством: затем над полученной формулой произ­водится операция обращения (REV), т. е. импликация записывается в обратную сторону, и, наконец, обе формулы соединяются дизъ­юнктивно.

Заметим, что дизъюнкцию в силу формулы

можно заменить на обычную дизъюнкцию что упрощает вычис­ления. Тогда в общем случае запись итерации выглядит так:

Обозначим посредством Рі класс простых чисел, при которых В силу идемпотентности операции замена дизъ­юнкции насохраняет значения обоих членов дизъюнкции

когда они равны, при переходе кОтсюда следует, что класс Рі-1 содержится в Рі. Тогда имеем

С помощью компьютерной программы, написанной в 1995 г., можно вычислить другие Рі. Например,

Класс Р4, содержит новые простые числа в количестве 51; класс P5 содержит 21 новое простое число.

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

По существу формула является законом порождения клас­сов простых чисел [Karpenko 1996]. Подчеркнем, что в силу нали­чия штриха Шеффера этот закон может описываться итера­цией только одной-единственной функции, а именно штриха Шеффера

Для наглядности приведем график для определенного числа простых чисел. По вертикали показано число итераций, по гори­зонтали - простые числа.

Заметим, что вычислять простые числа по формулевесьма громоздко и не эффективно, тем более что для этого существует огромное число различных алгоритмов (см. обзор [Василенко 1988]). В данном случае нас интересует разбиение простых чисел на классы Рі. И программа выполняет именно эту задачу, т. е. вычисляется только для случаев, когда п =р. Поэтому введем функцию i, которая по каждому простому числу дает число итераций i(p). Можно упростить исходную формулу (D*), заменив в ней вхождения функции на х→у и при этом рассматривая только случай Однако на компьютерный процесс вычисления это влияет незначительно.

Мы показали, что итерация порождает классы простых чи­сел, но встает принципиальный вопрос: порождаются ли все простые числа? На этот вопрос дает ответ

Теорема 4. Каждое простое число (кроме 2) содержится в неко­тором классе Pi [Карпенко 1997].

8. Бесконечнозначные логики

Мир бесконечнозначных логик исключительно широк. На самом деле этот универсум, как мы увидим, континуален. Рассмотрим наиболее известные и важные примеры бесконечнозначных логик,

Однако существует проблема, что считать бесконечнозначной логикой. Например, матрица, полученная в результате счетного числа умножений матрицы классической двузначной логики высказываний С2 саму на себя имеет истинностных значений, т. е. континуальна, и эта матрица является характеристической для С2. Это же число истинностных значений имеет и модальная логи­ка S5 в интерпретации А. Прайора (см. ниже). Но отличие между логиками С2 и S5 весьма существенно: S5 вообще не имеет конеч­ной характеристической матрицы [Scroggs 1951]. Поэтому S5 явля­ется бесконечнозначной логикой. Другим примером бесконечно­значной матрицы, а вернее, бесконечной последовательности конечных матриц, является последовательность матриц С. Яськовского (см. раздел 4.3.2), которая является характеристи­ческой для интуиционистской логики Int. Заметим, что первона­чально не было ясно, является ли Int конечнозначной логикой или бесконечнозначной. В одних книгах по многозначным логикам рассматриваются модальные льюисовские системы и Int, в других нет. Но мы уже знаем, как из Int получается трех­значная логика Рейтинга G3 (см. раздел 3.2), из S5-четырехзначная логика V2 (см. раздел 5.4.3.1), а из релевантной логики R — трехзначная паранепротиворечивая логика RM3 (см. раздел 3.5.2.1). Поэтому кратко рассмотрим эти логики наряду с другими.

Начнем с наиболее известной и самоочевидной бесконечно­значной логики, которая носит имя Лукасевича.

8.1. Бесконечнозначная логика Лукасевича

Простым способом построения бесконечнозначной логики является следующее естественное обобщение классических операций:

Тогда бесконечнозначную логику можно задать следующей матрицей:

Обратим внимание, что хотя операции определяются точно так же, как и в классической логике С2, тем не менее обобщение С2 оказалось совсем «не классическим», поскольку даже формула не является законом. И вообще, здесь нет тавтологий. Если ограничимся тремя истинностными значениями, то получим трех­значную логику Клини К3. В связи с этим понятно замечание, сде­ланное в [Dorning, Trilles and Valverde 1981], что импликация Лукасевича → была введена из-за того факта, что естественное обобщение классической булевой операции в многозначной логике не удовлетворяет принципу тождества для всех

Бесконечнозначная логика Лукасевичаявляется истори­чески первым примером логики, в которой явно определено беско­нечное (счетное или континуальное) множество истинностных зна­чений. Само понятие бесконечнозначной логики введено Я. Лукасевичем в [Lukasiewicz 1929] (см. в особенности [Lukasiewicz and Tarsia 1930]). Обобщение конечнозначной логики Лукасевича(см. выше раздел 5.1.1) на бесконечнозначный слу­чай не составляет труда, поскольку символ п не входит в опре­деление логических операций в Поэтому равенства для отри­цания ~ и импликации → сохраняются; в качестве истинностных значений для счетнозначной логики берется множество рацио­нальных чисел из отрезка [0, 1], а для континуальной логики - множество действительных чисел в отрезке