3. Существенные функции. Три леммы о существенных функциях. Критерий полноты Яблонского. Критерий полноты Слупецкого. Шефферовы функции (1124129), страница 2

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

Текст из файла (страница 2)

Докажем по критерию, что системаA = {j0 (x), x + y } — полна в Pk при k ≥ 3.1. Покажем, что из системы A можно получить все функцииодной переменной.В самом деле, |x + .{z. . + x} = 0, j0 (0) = 1, 1 + 1 = 2, 2 + 1 = 3 иkт.д. — все константы построены.Теперь x − a = x + (k − a), где a ∈ Ek , и ja (x) = j0 (x − a).Тогда запишем произвольную функцию f (x) ∈ Pk1 в 1-й формеи получим:XXf (x) =f (a)ja (x) =j (x) + . . .

+ ja (x) .|a{z}a∈Eka∈EkВсе функции одной переменной построены.f (a)Существенные функцииКритерии полнотыШефферовы функцииПолнота системы {j0 (x), x + y } в Pk при k ≥ 3Пример (продолжение).2. Теперь заметим, что x + y ∈ A — существенная функция,принимающая все k значений.Значит, система A = {j0 (x), x + y } — полна в Pk при k ≥ 3.При k = 2 система {j0 (x) = x̄, x + y = x ⊕ y } ⊆ 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.Существенные функцииКритерии полнотыКонец лекцииШефферовы функции.

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

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