6. Многозначные логики. Теорема Яблонского. Теорема Слупецкого (Слайды к лекциям)

Лекция: Существенные функции. Три леммы осущественных функциях. Критерий полнотыЯблонского. Критерий полноты Слупецкого.Шефферовы функции.Лектор — доцент Селезнева Светлана Николаевна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 (β), . .