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

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

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

Лекция 3. Существенные функции. Три леммы осущественных функциях. Критерий полнотыЯблонского. Критерий полноты Слупецкого.Шефферовы функции.Лектор — Селезнева Светлана Николаевнаselezn@cs.msu.suфакультет ВМК МГУ имени М.В. ЛомоносоваЛекции на сайте http://mk.cs.msu.suСущественные функцииКритерии полнотыШефферовы функцииСущественные функцииФункция f (x1 , . . .

, xn ) ∈ Pk , k ≥ 3, называется существенной,если она существенно зависит не менее, чем от двухпеременных.Примеры. x + y , x · y , max(x, y ) ∈ Pk .Существенные функцииКритерии полнотыШефферовы функцииЛемма о трех наборахЛемма 1 (о трех наборах). Пусть k ≥ 3. Еслиf (x1 , . . .

, xn ) ∈ Pk — существенная функция, принимающая l,l ≥ 3, значений причем (без ограничения общностирассуждений) x1 и x2 — ее существенные переменные, тонайдутся 3 набораα = (a1 , a2 , a3 , . . . , an ) ∈ Ekn ,β = (b1 , a2 , a3 , . . . , an ) ∈ Ekn ,γ = (a1 , c2 , c3 , . . .

, cn ) ∈ Ekn ,на которых функция f принимает три различных значения.Существенные функцииКритерии полнотыШефферовы функцииЛемма о трех наборахДоказательство.Т.к. x1 — существенная переменная функции f (x1 , . . . , xn ),найдутся такие значения a2 , . . . , an ∈ Ek , что впоследовательностиf (0, a2 , .

. . , an ), f (1, a2 , . . . , an ), . . . , f (k − 1, a2 , . . . , an )встречаются не менее двух различных значений.Существенные функцииКритерии полнотыШефферовы функцииЛемма о трех наборахДоказательство. Возможны два случая.1. В этой последовательности встречаются не все различныезначения функции f .Т.е. найдется такой набор γ = (a1 , c2 , .

. . , cn ) ∈ Ekn , чтозначение f (γ) отлично от любого значения в этойпоследовательности.Тогда пусть α = (a1 , a2 , . . . , an ) ∈ Ekn .Выберем такое значение b1 ∈ Ek , чтобы дляβ = (b1 , a2 , . . . , an ) ∈ Ekn выполнялось неравенство f (α) 6= f (β).Такое b1 всегда можно найти.Наборы α, β, γ — искомые.Существенные функцииКритерии полнотыШефферовы функцииЛемма о трех наборахДоказательство.2.

В этой последовательности встречаются все различныезначения функции f .Т.к. x2 — существенная переменная функции f , найдутся такиезначения a1 , c3 , . . . , cn ∈ Ek , чтоf (a1 , x2 , c3 , . . . , cn ) 6= Const.Т.е. найдется такое значение c2 ∈ Ek , что дляα = (a1 , a2 , a3 , . . . , an ) ∈ Ekn и γ = (a1 , c2 , c3 , . . . , cn ) ∈ Ekn верноf (α) 6= f (γ).Тогда выберем такое значение b1 ∈ Ek , чтобы дляβ = (b1 , a2 , .

. . , an ) ∈ Ekn выполнялись неравенстваf (α) 6= f (β) и f (γ) 6= f (β).Такое b1 всегда можно найти.Наборы α, β, γ — искомые.Существенные функцииКритерии полнотыШефферовы функцииЛемма о трех наборахПример. Рассмотрим существенную функциюf (x, y ) = x + y ∈ P5 , принимающую 5 различных значений.Тогда искомые наборы, например, следующие:α = (0, 0),β = (1, 0),γ = (0, 2).Проверим:f (α) = 0,f (β) = 1,f (γ) = 2.Существенные функцииКритерии полнотыШефферовы функцииОсновная леммаЛемма2 (основная). Пусть k ≥ 3. Если f (x1 , . .

. , xn ) ∈ Pk —существенная функция, принимающая l, l ≥ 3, значений, тонайдутся такие множества Gi , Gi ⊆ Ek , i = 1, . . . , n, что1) |Gi | ≤ l − 1 для каждого i = 1, . . . , n;2) на множестве G1 × . . . × Gn ⊆ Ekn функция f принимает все lсвох различных значений.Существенные функцииКритерии полнотыШефферовы функцииОсновная леммаДоказательство. Пусть (без ограничения общностирассуждений) x1 и x2 — существенные переменные функции f .Тогда по лемме 1 найдутся наборыα = (a1 , a2 , . . . , an ) ∈ Ekn ,β = (b1 , a2 , . . .

, an ) ∈ Ekn ,γ = (a1 , c2 , . . . , cn ) ∈ Ekn ,на которых функция f принимает три различных значения.Пусть на наборах δ j = (d1j , d2j , . . . , dnj ) ∈ Ekn , j = 4, . . . , l,функция f принимет оставшиеся (l − 3) различные значения.Существенные функцииКритерии полнотыШефферовы функцииОсновная леммаДоказательство. Тогдаx1a1b1a1d14x2a2a2c2d24x3a3a3c3d34αβγδ4...δ l d1l d2l d3lG1 G2 G3. .

. xn f (x1 , . . . , xn ). . . anz1. . . anz2. . . cnz3. . . dn4z4....... . . dnlzl. . . GnТ.е. множество Gi состоит из элементов столбца по переменнойxi , i = 1, . . . , n.Множества G1 , . . . , Gn — искомые.Существенные функцииКритерии полнотыШефферовы функцииОсновная леммаПример. Рассмотрим существенную функциюf (x, y ) = x + y ∈ P5 , принимающую 5 различных значений.Тогда на следующих наборах:α0α1α2α3α4=====(0, 0),(1, 0),(0, 2),(0, 3),(0, 4),функция f (x, y ) = x + y принимает 5 различных значений.Существенные функцииКритерии полнотыШефферовы функцииЛемма о квадратеЧетверку наборов вида(a1 , .

. . , ai−1 , bi , ai+1 , . . . , aj−1 , bj , aj+1 , . . . , an ),(a1 , . . . , ai−1 , bi , ai+1 , . . . , aj−1 , cj , aj+1 , . . . , an ),(a1 , . . . , ai−1 , ci , ai+1 , . . . , aj−1 , bj , aj+1 , . . . , an ),(a1 , . . . , ai−1 , ci , ai+1 , . . . , aj−1 , cj , aj+1 , . . . , an ),назовем квадратом.Существенные функцииКритерии полнотыШефферовы функцииЛемма о квадратеЛемма 3 (о квадрате).

Пусть k ≥ 3. Если f (x1 , . . . , xn ) ∈ Pk— существенная функция, принимающая l, l ≥ 3, значений, тонайдется квадрат, на котором функция f какое-то своезначение принимает ровно в одной его точке.Существенные функцииКритерии полнотыШефферовы функцииЛемма о квадратеДоказательство. Пусть (без ограничения общностирассуждений) x1 и x2 — существенные переменные функции f .Тогда по лемме 1 найдутся наборыα = (a1 , a2 , . . .

, an ) ∈ Ekn ,β = (b1 , a2 , . . . , an ) ∈ Ekn ,γ = (a1 , c2 , . . . , cn ) ∈ Ekn ,на которых функция f принимает три различных значения u, vи w соответственно.Существенные функцииКритерии полнотыШефферовы функцииЛемма о квадратеДоказательство. Тогда рассмотрим последовательностьквадратов:НаборыЗначения fна них(a1 , a2 , a3 , . . . , an−1 , an ) (b1 , a2 , a3 , . . . , an−1 , an ) {u, v}(a1 , c2 , a3 , . . .

, an−1 , an ) (b1 , c2 , a3 , . . . , an−1 , an ) {u, v}(a1 , c2 , c3 , . . . , an−1 , an ) (b1 , c2 , c3 , . . . , an−1 , an ) {u, v}.........(a1 , c2 , c3 , . . . , cn−1 , an ) (b1 , c2 , c3 , . . . , cn−1 , an ) {u, v}(a1 , c2 , c3 , . . . , cn−1 , cn ) (b1 , c2 , c3 , . . . , cn−1 , cn ) {w, ?}Если искомый квадрат не был получен ранее, он обязательнопоявится на заключительном шаге.Существенные функцииКритерии полнотыШефферовы функцииЛемма о квадратеПример. Рассмотрим существенную функциюf (x, y ) = x + y ∈ P3 , принимающую 3 различных значения.Тогда на следующем квадрате:(0, 0), (1, 0), (0, 2), (1, 2)функция f (x, y ) = x + y принимает значение 1 только в однойточке (на наборе (1, 0)).Существенные функцииКритерии полнотыШефферовы функцииКритерий полноты ЯблонскогоТеорема 4 (С.В.

Яблонского) Пусть k ≥ 3, A ⊆ Pk имножество A содержит все функции одной переменной,принимающие не более (k − 1) значения.Тогда система A полна в Pk в том и только в том случае, когдаона содержит существенную функцию, принимающую все kзначений.Существенные функцииКритерии полнотыШефферовы функцииКритерий полноты ЯблонскогоДоказательство.Необходимость. Пусть A — полная система.1) Если она не содержит существенную функцию, то изсистемы A не получить никакую функцию с более, чем одной,существенной переменной.2) Если в ней существенные функции, принимающие не все kзначений, то из системы A не получить никакую функцию,принимающую все k значений.Необходимость обоснована.Существенные функцииКритерии полнотыШефферовы функцииКритерий полноты ЯблонскогоДоказательство.Достаточность.

Пусть f (x1 , . . . , xn ) ∈ A — существеннаяфункция, принимающая k значений.Докажем, что произвольную функцию g (y1 , . . . , ym ) ∈ Pkможно построить формулой над функциями системы A.Доказательство проведем индукцией по числу l, l ≤ k,значений, которые принимает функция g .Существенные функцииКритерии полнотыШефферовы функцииКритерий полноты ЯблонскогоДоказательство.Базис индукции: l = 2.Пусть функция g (y1 , . . . , ym ) ∈ Pk принимает 2 значенияs, t ∈ Ek , s < t.По лемме о квадрате для существенной функции f (x1 , .

. . , xn )найдется квадрат(a1 , . . . , ai−1 , bi , ai+1 , . . . , aj−1 , bj , aj+1 , . . . , an ),(a1 , . . . , ai−1 , bi , ai+1 , . . . , aj−1 , cj , aj+1 , . . . , an ),(a1 , . . . , ai−1 , ci , ai+1 , . . . , aj−1 , bj , aj+1 , . . . , an ),(a1 , . . . , ai−1 , ci , ai+1 , . .

. , aj−1 , cj , aj+1 , . . . , an ),на котором функция f некоторое свое значение u принимаетровно в одной точке, например, в точке (bi , bj ).Т.к. система A содержит все константы, построим функциюϕ(xi , xj ) = f (a1 , . . . , ai−1 , xi , ai+1 , . . . , aj−1 , xj , aj+1 , . . .

, an ).Существенные функцииКритерии полнотыШефферовы функцииКритерий полноты ЯблонскогоДоказательство. Рассмотрим функцииbi , z = s,bj , z = s,ψ1 (z) =; ψ2 (z) =ci , z = t,cj , z = t,иψ0 (z) =s, z = u,t, z =6 u.Отметим, что ψ0 , ψ1 , ψ2 ∈ A.Тогда можно построить функцию максимума из элементов s, t:max s,t (x, y ) = ψ0 (ϕ(ψ1 (x), ψ2 (y ))).Аналогично можно построить функцию минимума изэлементов s, t: mins,t (x, y ).Существенные функцииКритерии полнотыШефферовы функцииКритерий полноты ЯблонскогоДоказательство. Отметим, что для функцийt, z = i,s,tji (z) =s, z 6= i.верно jis,t ∈ A, i ∈ Ek .Тогда аналогично 1-й форме получаем:g (y1 , .

. . , ym ) =maxσ=(σ1 ,...,σm )∈EkmБазис индукции обоснован.s,tmins,t (jσs,t1 (x1 ), . . . , jσs,tm (xm ), g (σ)).Существенные функцииКритерии полнотыШефферовы функцииКритерий полноты ЯблонскогоИндуктивный переход. Пусть все функции из Pk , принимающиене более (l − 1) значения, уже построены.Рассмотрим функцию g (y1 , . . . , ym ) ∈ Pk , принимающую ровноl значений: s1 , . . . , sl .По основной лемме для существенной функции f (x1 , . .

. , xn ),принимающей l значений, найдутся такие множества Gi , что|Gi | ≤ l − 1 и на множестве G1 × . . . × Gn функция f принимаетl различных значений.Если l < k, то при необходимости дополнительной функциейψ(z) ∈ A переведем эти значения в s1 , . . . , sl .Пустьf (a1j , . . . , anj ) = sj , j = 1, . . . , l,где (a1j , . .

. , anj ) ∈ G1 × . . . × Gn .Существенные функцииКритерии полнотыШефферовы функцииКритерий полноты ЯблонскогоПоложимψi (b1 , . . . , bm ) = aij ,если g (b1 , . . . , bm ) = sj , i = 1, . . . , n.Заметим, что ψ1 , . . . , ψn уже построены.Тогдаg (y1 , . . . , ym ) = f (ψ1 (y1 , .

. . , ym ), . . . , ψn (y1 , . . . , ym )).В самом деле, если β ∈ Ekm и g (β) = sj , тоsj = g (β) = f (ψ1 (β), . . . , ψ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.Существенные функцииКритерии полнотыШефферовы функцииПолнота системы {j0 (x), x + y } в Pk при k ≥ 3Пример.

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

Тип файла PDF

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

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

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