7. Многозначные логики. Особенности многозначных логик (Слайды к лекциям)
Описание файла
Файл "7. Многозначные логики. Особенности многозначных логик" внутри архива находится в папке "Слайды к лекциям". PDF-файл из архива "Слайды к лекциям", который расположен в категории "". Всё это находится в предмете "дискретные модели управляющих систем" из Аспирантура и докторантура, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Лекция: Особенности многозначных логик.Замкнутый класс, базис замкнутого класса.Теоремы Янова и Мучника о существовании вмногозначных логиках замкнутых классов безбазиса и замкнутых классов со счетным базисом.Лектор — доцент Селезнева Светлана Николаевна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.Особенности многозначных логикКонец лекции.
