6. Многозначные логики. Теорема Яблонского. Теорема Слупецкого (Слайды к лекциям), страница 2
Описание файла
Файл "6. Многозначные логики. Теорема Яблонского. Теорема Слупецкого" внутри архива находится в папке "Слайды к лекциям". PDF-файл из архива "Слайды к лекциям", который расположен в категории "". Всё это находится в предмете "дискретные модели управляющих систем" из Аспирантура и докторантура, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 2 страницы из PDF
. , ψn (β)) = f (a1j , . . . , anj ) = sj .Индуктивный переход обоснован.Существенные функцииКритерии полнотыШефферовы функцииКритерий полноты СлупецкогоТеорема 5 (Слупецкого). Пусть k ≥ 3, A ⊆ Pk и множество Aсодержит все функции одной переменной.Тогда система A полна в Pk в том и только в том случае, когдаона содержит существенную функцию, принимающую все kзначений.Существенные функцииКритерии полнотыШефферовы функцииВерен ли критерий полноты в P2 ?Верны ли эти критерии полноты в P2 ?Нет.
Рассмотрим множествоA = {0, 1, x, x̄, x ⊕ y } ⊆ P2 .Система A содержит все функции одной переменной исущественную функцию x ⊕ y , принимающую два значения.Но система A не является полной в P2 , так как A ⊆ L.Существенные функцииКритерии полнотыШефферовы функцииШефферова функцияФункция f (x1 , . . . , xn ) ∈ Pk называется шефферовой, если[{f }] = Pk .Примеры. Штрих Шеффера x/y ∈ P2 , стрелка Пирсаx ↓ y ∈ P2 , функция Вебба Vk (x, y ) ∈ Pk .Существенные функцииКритерии полнотыШефферовы функцииШефферовы функцииТеорема 6 (критерий шефферовости функции). Пустьk ≥ 3 и f (x1 , . . .
, xn ) ∈ Pk .Функция f является шефферовой в Pk тогда и только тогда,когда формулами над ней можно выразить все функции однойпеременной, принимающие не более (k − 1) значения.Доказательство.Необходимость очевидна.Существенные функцииКритерии полнотыШефферовы функцииШефферовы функцииДоказательство.Докажем достаточность.1) Если функция f не принимает какое-то значение v ∈ Ek , тоиз нее нельзя получить константу v — противоречие.
Значит,функция f принимает все k значений.2) Если функция f не является существенной, то по п. 1) она —перестановка, и из нее можно получить только перестановки —противоречие. Значит, функция f — существенная.Тогда по критерию полноты Яблонского система A = {f } —полна в Pk .Существенные функцииКритерии полнотыШефферовы функцииВерен ли критерий шефферовости функции в P2 ?Верен ли этот критерий шефферовости функции в P2 ?Существенные функцииКритерии полнотыШефферовы функцииВерен ли критерий шефферовости функции в P2 ?Да. Пусть f (x1 , .
. . , xn ) ∈ P2 и из f формулами можно выразитьконстанты 0 и 1. Проверим, что f ∈/ T0 , T1 , L, S, M.Получаем:1) f ∈/ T0 , т.к. из нее формулами можно получить 1 ∈/ T0 , аT0 — замкнутый класс;2) f ∈/ T1 , т.к. из нее формулами можно получить 0 ∈/ T1 , аT1 — замкнутый класс;3) f ∈/ S, т.к. из нее формулами можно получить 0 ∈/ S, а S —замкнутый класс;4) f ∈/ M, т.к. f ∈/ T0 , f ∈/ T1 ;5) f ∈/ L, т.к. если предположить, что f ∈ L, то из f ∈/ T0 иf ∈/ T1 будет следовать f ∈ S, что противоречит f ∈/ S.Значит, по теореме Поста система {f } — полна в P2 , т.е. f —шефферова функция.Существенные функцииКритерии полнотыШефферовы функцииЛитература к лекции1. Яблонский С.В.
Введение в дискретную математику. М.:Высшая школа, 2001. Ч. I, гл. 2, стр. 56–65.Существенные функцииКритерии полнотыКонец лекцииШефферовы функции.
