Моделирование логических схем посредством теории множеств

Размещено на http://www.allbest.ru/

Моделирование логических схем посредством теории множеств

В.Л. Чечулин

Аннотация

На основании известных теорем о непротиворечивости лямбда-исчисления, доказанных в семантике самопринадлежности, описан способ моделирования логических схем посредством теории множеств, использующий модель двузначной логики; из этих теорем о непротиворечивости следует непротиворечивость моделей логических схем.

Ключевые слова: теория множеств с самопринадлежностью; модели и непротиворечивость лямбда-исчисления; модели логических схем; логические функции; непротиворечивость моделей логических схем.

Введение

В теории множеств с самопринадлежностью [1] была построена адекватная модельная область для лямбда-исчисления [2, 3], а также модель логики высказываний [2]. Кроме того, в семантике самопринадлежности были доказаны теоремы о непротиворечивости лямбда-исчисления [4]. Эти результаты позволяют моделировать посредством теории множеств логические схемы, с обоснованием того, что эти модели непротиворечивы. Ниже описан способ и примеры моделирования логических схем Первоначальные рукописные наброски этой работы относятся к зиме 1996-1997 гг.

Чечулин В.Л., 2012.

1. Обоснование моделирования

Теорема о непротиворечивости лямбда-исчисления доказана в слабой (для модельной области лямбда-исчисления) и сильной (на всем М) форме [4]. Для моделирования логических схем значима вторая (сильная) форма теоремы.

Теорема 1 (сильная непротиворечивость). Лямбда-исчисление, реализуемое на теории множеств с самопринадлежностью, - непротиворечиво. моделирование множество логика

Схема доказательства такова, что "сильное" доказательство непротиворечивости лямбда-исчисления не использует понятия модельной области (т. е. не зависит от результатов теоремы о слабой непротиворечивости). Рассматривается множество всех множеств М. Множества в нём выделяются схемой свёртывания А = {xM | (x) или L(х)}. Если высказывание L дополнить лямбда-абстрактором и внешней по отношению к свертыванию переменной, то имеется реализация лямбда-исчисления в теории множеств

А(y) = {xM | (x) или Lл(х, лу.у)}(y),

где yM.

При этом по теореме о непротиворечивости теории множеств [1] высказывание Lл(х, y) не может задавать одновременно множество A(y) и его дополнение, - таким образом, совокупность высказываний Lл(х, y) (для произвольных y из М) - непротиворечива, это и доказывает теорему.

Размещено на http://www.allbest.ru/

Теорема 1 позволяет рассматривать в качестве выражений L(.) с внешней переменной не только произвольные лямбда-выражения, но и выражения, относящиеся к логике высказываний, для которой имеются модели в теории множеств с самопринадлежностью, см. табл. 1, 2.

Таким образом, наличие констант и М, а также отношений импликации и отрицания (… ) позволяет строить модели логических схем посредством теории множеств, причем по теореме 1 модели эти непротиворечивы.

2. Построения моделей схем

Входы логических схем (см. рис. 1) обозначаются ai, выход - b. Запись модели инвертора такова:

b={xM|(x) или х=(a)}(a), (1)

где аi, b принимают значения , М.

Модель элемента 2ИЛИ:

b={xM|(x) или х=((а 1)a2)}(a1,a2).

Модель элемента 2И:

b={xM|(x) или х=((а 1(a2)))}(a1, a2).

Модель элемента 2И-НЕ:

b={xM|(x) или х=(а 1(a2))}(a1, a2).

Эти логические элементы образуют базис, посредством которого строятся остальные более сложные логические схемы [5, с. 12].

В общем виде модель логического элемента - это схема свертывания с высказыванием, дополненная внешними переменными

b={xM|(x) или L(x, у 1,… уn)}(у 1,… уn). (2)

По теореме 1 высказывание L(.) в схеме (2) задает некоторый объект, но не его дополнение. Это означает, что построенные модели логических схем - непротиворечивы.

Аналогично строятся модели более сложных схем, например модель RS-триггера (рис. 2), построенного из двух элементов 2ИЛИ-НЕ.

Размещено на http://www.allbest.ru/

Модель RS-триггера состоит из двух взаимосвязанных выражений:

b={xM|(x) или х=(((а 1)d))}(a1, d)

d={xM|(x) или х=(((c2)b))}(c2, b).

Более сложные схемы строятся аналогично, набор основных логических функций, реализуемых в базисе, указанном в табл. 1, приведен в табл. 3.

3. Замечание о модельной области

В модельной области лямбда-исчисления также строятся непротиворечивые модели, но иного вида, реализующие арифметику на подмножестве множества натуральных чисел, например модель сумматора двух чисел (b=a1+a2) такова:

b={xM|(x) или хPa2(a1)}(a1, a2), (3)

где a1, a2 N, а Pa2(a1) - простой последователь степени a2, взятый от a1.

Известна следующая теорема [4, 6]:

Теорема 2 (слабая непротиворечивость). Лямбда-исчисление над его модельной областью (конечные натуральные числа) в теории множеств с самопринадлежностью непротиворечиво. ?

Общий вид схемы свертывания с высказыванием, дополненной внешними переменными, принимающими значения в конечной области натурального ряда К, КN,

b, у 1,… уn КN, таков:

b={xM|(x) или L(x, у 1,… уn)}(у 1,… уn). (4)

По теореме 2 высказывание L(.) в схеме (4) задает некоторый объект, но не его дополнение. Это означает, что построенные модели над областью K натуральных чисел непротиворечивы.

Заключение

Показано, что модели логических схем, строящиеся посредством теории множеств с самопринадлежностью, являются непротиворечивыми; приведены примеры построения базисных логических элементов и RS-триггера. Способ построения моделей логических схем использует модель двузначной логики, для которой ранее доказана теорема исключения третьего [2].

Таким образом, непротиворечивость получаемых моделей обоснована посредством результатов теории множеств с самопринадлежностью.

Список литературы

1. Чечулин В.Л. Теория множеств с самопринадлежностью (основания и некоторые приложения): монография. Пермь, 2010. 100 с. URL: http://elibrary.ru/item.asp?id=15267103

2. Чечулин В.Л. О приложениях семантики самопринадлежности // Вестн. Перм. ун-та. Сер. Математика. Механика. Информатика. 2009. Вып. 3 (29). С.10-17.

3. Чечулин В.Л. Об одном варианте модельной области лямбда-исчисления // Синтаксис и семантика логических систем. Иркутск, 2010. С.112-114.

4. Чечулин В.Л. О непротиворечивости лямбда-исчисления // В мире научных открытий. Сер. Математика. Механика. Информатика. 2011. №1. С. 203-206.

5. Потемкин И.С. Функциональные узлы цифровой автоматики. М., 1988. 320 с. URL: http://www.nkras.ru/articles/2011/1/vypusk12011pdf

6. Chechulin V.L. About the selfconsidering semantic in the mathematical logic // Bull. Symbolic Logic. Vol.16, Is. 1(2010). P.111-112.

Размещено на Allbest.ru