Weakly central clones and completeness problem for them.pdf Проблема полноты и критериальные системы. Пусть E - конечное множе-ство. Через PE обозначается множество функций f : En ^ E при всевозможных це-лых положительных n. Классы таких функций, замкнутые операциями суперпозции исодержащие селекторные функции, называются клонами, а клоны, включающие мно-жество A С PE, - A-клонами.Будем интересоваться проблемой полноты в A-клоне (иначе - проблемой A-полно-ты в клоне) B, состоящей в описании всех его A-порождающих подмножеств, порож-дающих его с использованием операций суперпозиции, селекторов и функций из мно-жества A. Инструментом решения этой проблемы является A-критериальная система.Так называется система S A-клонов, собственным образом содержащихся в клоне B,если всякий A-клон, собственным образом содержащийся в клоне B, можно расши-рить до некоторого клона из S. A-критериальная система S называется безызбыточ-ной, если она не содержит пары сравнимых по включению клонов и совпадает тогдас системой S(A, B) всех максимальных A-клонов среди строго содержащихся в B,в остальных случаях лишь включённой в S.Обозначим через Пе множество предикатов p : En ^ {И,Л} при всевозможныхнатуральных n. Неинвариантный для клона B предикат p из Пе называется B-пре-дельным [1], если всякий отличный от p предикат, полученный из него проектиро-ванием, отождествлением переменных, B-сужением (пересечением с инвариантнымдля B предикатом) или симметризацией (пересечением с перестановочно эквивалент-ным предикатом), уже инвариантен для клона B. Обозначим через Л ^ , B) множествоинвариантных для A B-предельных предикатов и через TV(A,B) -множество клоновB П polE(p), где p G Л ^ , B). В [1] доказанаТеорема 1. Система ^V(A, B) является A-критериальной для клона B. Эта систе-ма конечная, если клон B обладает конечным A-порождающим подмножеством.Заметим, что теорема 1 не исключает возможной избыточности системы TV(A,B).Слабоцентральные клоны. Пусть c - некоторый элемент из множества E. Пре-дикат p из Пе назовём с-слабоцентральным, если в любом удовлетворяющем ему на-боре замена любой компоненты значением c приводит к набору, также удовлетворяю-щему p. Для любого множества Y с-слабоцентральных предикатов из Пе клон polE(Y)также называется с-слабоцентральным. Иными словами, произвольный клон являетсяс-слабоцентральным, если он включает (наименьший по включению) клон polE (WE),описываемый множеством WE всех с-слабоцентральных предикатов. (Интересно, чтоэто множествозамкнуто операциями проектирования, подстановки переменных, конъ-юнкции и даже дизъюнкции, но не содержит диагоналей, кроме тривиальных.) В дво-ичном случае такими наименьшими клонами polE (WE) при различных с из множестваE = {0,1} являются клоны неразделённых либо разделённых булевых функций. Сла-боцентральные клоны обладают рядом интересных свойств и допускают ряд равно-сильных определений.Частным случаем слабоцентральных клонов являются определяемые ниже клонысохранения с-системы множеств. Назовём с-системой систему е подмножеств множе-ства E, обладающую следующими свойствами:1) наследственностью: если некоторое множество принадлежит системе е, то ивсякая его часть принадлежит е;2) слабой центральностью по с: если множество H принадлежит системе е, томножество H U {с} также принадлежит ей.Обозначим через QE(е) клон функций из РЕ , сохраняющих систему е, и черезФе(е) -клон функций, сохраняющих её по некоторой переменной. Несложно понять,что клоны Qe(е) и Фе(е) являются с-слабоцентральными.Введённые клоны имеют важные приложения, отметим следующие два.Пример 1. Пусть E - конечная верхняя полурешётка и е - система её подмно-жеств с нижней гранью. Тогда клон Qe (е) совпадает с клоном квазимонотонных функ-ций на полурешётке E, введённых Г. П. Агибаловым [2], а клон Фе(е) совпадает с кло-ном слабосущественных квазимонотонных функций из [3].Пример 2. Как клон сохранения некоторой с-системы можно определить любой(предполный по теореме Розенберга) клон функций из Ре , сохраняющих произвольныйотличный от диагонали центральный вполне рефлексивный симметричный предикат.Проблема полноты в слабоцентральном клоне. Из-за указанных приложенийслабоцентральных клонов представляется важной проблема полноты в них.Теорема 2. Пусть A и B - с-слабоцентральные клоны, такие, что A С B. Тогдамножество TV(A, B) является б е з ы з б ы т о ч н о й A-критериальной системой для кло-на B; в частности, для произвольных предикатов p и q из Л ^ , B) строгое включениеB П polE(p) С B П polE(q) невозможно. Более того, для произвольных предикатов p и qиз Л ^ , B) равенство клонов B П polE(p) = B П polE(q) равносильно перестановочнойэквивалентности этих предикатов.Сформулированная теорема сводит задачу построения безызбыточной A-крите-риальной системы в клоне B для слабоцентральных клонов A и B к нахождениюB-предельных предикатов из Л ^ , B). Помимо этого, имеет местоСледствие 1. Слабоцентральный клон обладает безызбыточной критериальнойсистемой.Отметим также, что доказанная в [3] теорема легко обобщается как теорема оФе(е)-полноте в клоне Qe(е) для произвольной с-системы е.

Скачать электронную версию публикации