7. Многозначные логики. Особенности многозначных логик (1268168)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Лекция: Особенности многозначных логик.Замкнутый класс, базис замкнутого класса.Теоремы Янова и Мучника о существовании вмногозначных логиках замкнутых классов безбазиса и замкнутых классов со счетным базисом.Лектор — доцент Селезнева Светлана Николаевнаselezn@cs.msu.suФакультет ВМК МГУ имени М.В. ЛомоносоваЛекции на сайте http://mk.cs.msu.suОсобенности многозначных логикБазис замкнутого классаПусть A, A ⊆ Pk , — замкнутый класс, и B ⊆ A.Множество B называется базисом класса A, если1) [B] = A, т.е. система B полна в A;2) для каждой функции f ∈ B верно [B \ {f }] 6= A, т.е.

системаB неизбыточна в A.В P2 каждый базис всего класса P2 содержит не более 4-хфункций.Э. Пост доказал, что в P2 каждый замкнутый класс имеетконечный базис.Особенности многозначных логикТеорема ЯноваТеорема 1 (Ю.И. Янова). В Pk при k ≥ 3 существуетзамкнутый класс, не имеющий базиса.Доказательство. Пусть k ≥ 3. Рассмотрим множествофункций {f0 , f1 , f2 , . . .} ⊆ Pk :f0 = 0,fi (x1 , . .

. , xi ) =1, x1 = . . . = xi = 2,0, иначе.Пусть A = [{f0 , f1 , f2 , . . .}].Заметим, чтоfi (. . . , fj , . . .) = 0.Поэтому в классе A содержатся только функции, конгруэнтныефункциям f0 , f1 , f2 , . . ..Особенности многозначных логикТеорема ЯноваДокажем от противного, что замкнутый класс A не имеетбазиса.Пусть B ⊆ A – базис класса A, и fn0 — функция с наименьшиминдексом в базисе B.Возможны два случая.Особенности многозначных логикТеорема ЯноваДоказательство.1.

В базисе B есть еще хотя бы одна функция fn1 , где n1 > n0 .Но тогда противоречие с п. 2 определения базиса, т.к.fn0 (x1 , . . . , xn0 ) = fn1 (x1 , . . . , xn0 , xn0 , . . . , xn0 ).Особенности многозначных логикТеорема ЯноваДоказательство.2. В базисе B есть только функция fn0 .

Но тогда противоречиес п. 1 определения базиса, а именно, никакая функция fn приn > n0 не может быть получена, т.к.fn0 (. . . , fn0 , . . .) = 0.Значит, класс A не имеет базиса.Особенности многозначных логикТеорема МучникаТеорема 2 (А.А. Мучника). В Pk при k ≥ 3 существуетзамкнутый класс, имеющий счетный базис.Доказательство. Пусть k ≥ 3. Рассмотрим множествофункций {f2 , f3 , . . .} ⊆ Pk : 1, x1 = . . . = xj−1 = xj+1 = . . .

= 2, xj = 1,j = 1, . . . , i,fi (x1 , . . . , xi ) =0, иначе.Пусть A = [{f2 , f3 , . . .}].Докажем, что B = {f2 , f3 , . . .} — базис замкнутого класса A.Докажем от противного, что для каждого n0 = 2, 3, . . . функцияfn0 не задается формулой над множеством B \ {fn0 }.Особенности многозначных логикТеорема МучникаДоказательство.Пустьfn0 (x1 , . . .

, xn0 ) = fn1 (F1 , . . . , Fn1 ).Возможны три случая.Особенности многозначных логикТеорема МучникаДоказательство.Пустьfn0 (x1 , . . . , xn0 ) = fn1 (F1 , . . . , Fn1 ).1. Среди формул F1 , . . . , Fn1 не менее двух, которые неявляются переменными:fn0 (x1 , . . . , xn0 ) = fn1 (. . . , fi , . . . , fj , . . .).Но тогда противоречие на наборе (1, 2, .

. . , 2) ∈ Ekn0 , т.к.1 = fn0 (1, 2, . . . , 2) = fn1 (. . . , {0, 1}, . . . , {0, 1}, . . .) = 0.Особенности многозначных логикТеорема МучникаДоказательство.Пустьfn0 (x1 , . . . , xn0 ) = fn1 (F1 , . . . , Fn1 ).2. Среди формул F1 , . . . , Fn1 только одна, которая не являетсяпеременной. Т.к. n1 > 2, хотя бы одна формула равнапеременной, например, x1 :fn0 (x1 , . . . , xn0 ) = fn1 (x1 , . . .

, fi , . . .).Но тогда противоречие на наборе (1, 2, . . . , 2) ∈ Ekn0 , т.к.1 = fn0 (1, 2, . . . , 2) = fn1 (1, . . . , {0, 1}, . . .) = 0.Особенности многозначных логикТеорема МучникаДоказательство.Пустьfn0 (x1 , . . . , xn0 ) = fn1 (F1 , . . . , Fn1 ).3. Все формулы F1 , . .

. , Fn1 являются переменными. Тогдаn1 > n0 , и хотя бы одна переменная встречается по меньшеймере дважды, например, x1 :fn0 (x1 , . . . , xn0 ) = fn1 (x1 , . . . , x1 , . . .).Но тогда противоречие на наборе (1, 2, . . . , 2) ∈ Ekn0 , т.к.1 = fn0 (1, 2, . . . , 2) = fn1 (1, . . . , 1, . . .) = 0.Значит, B — неизбыточная система.

Отсюда B — базисзамкнутого класса A.Особенности многозначных логикМощность множества замкнутых классов в Pk при k ≥ 3Теорема 3. В Pk при k ≥ 3 существует континум замкнутыхклассов.Доказательство. Пусть k ≥ 3. Рассмотрим множествофункций {f2 , f3 , . . .} ⊆ Pk из доказательства теоремы Мучника.Для каждой бесконечной возрастающей последовательностинатуральных чиселν = n1 , n2 , . .

. ,где n1 ≥ 2, построим замкнутый классAν = [{fn1 , fn2 , . . .}].Тогда, если последовательности ν1 и ν2 различны, тоAν1 6= Aν2 .Значит, построены континум различных замкнутых классов вPk при k ≥ 3.Э. Пост доказал, что в P2 существует только счетное числозамкнутых классов.Особенности многозначных логикЛитература к лекции1. Яблонский С.В. Введение в дискретную математику. М.:Высшая школа, 2001.

Ч. I, гл. 2, стр. 65–69.Особенности многозначных логикКонец лекции.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций