Содержание к диссертации
Введение
Глава 1. Классификация конечных детерминированных автоматов и алгебра композиции автоматов
1.1. Классификация конечных автоматов по свойствам комбинационных частей 14
1.2. Алгебра композиции автоматов 25
1.3. Свойства классов автоматов, как свойства их комбинационных компонент 35
Глава 2. Установочная задача для автоматов, метод распознавания автомата с зацикливанием изменений состояний
2.1. Необходимое и достаточное условие существования решения установочной задачи 44
2.2. Функционирование автомата с изменениями состояний в циклах 48
2.3. Математическая модель процесс зацикливания автомата 58
Глава 3. Метод решения установочной задачи на основе изменений состояний в цикле
3.1. Матричный метод построения решения установочной задачи 64
3.2. Теорема о связи решения установочной задачи для модели зацикливания автомата 68
3.3. Метод построения циклов графа Gp 78
Глава 4. Достаточные условия для выбора периодических последовательностей, методы зацикливания
4.1. Множество конституэнт единицы комбинационной части автомата и пары автоматов 87
4.2. Граф, определяющий совмещение конституэнт единицы в функциях переходов и выходов автоматов 93
4.3. Достаточные условия для распознавания автоматов методом зацикливания 103
Заключение 111
Список литературы 112
Приложение 117
- Алгебра композиции автоматов
- Функционирование автомата с изменениями состояний в циклах
- Теорема о связи решения установочной задачи для модели зацикливания автомата
- Граф, определяющий совмещение конституэнт единицы в функциях переходов и выходов автоматов
Введение к работе
Конечные детерминированные автоматы составляют один из важнейших классов математических моделей для динамических систем с конечным множеством состояний. Конечные автоматы не только используются для представления функционирования реальньж систем (технических, биологических, экономических, организационных и т.п.), но и включается как важнейшая компонента в более сложные дискретные детерминированные математические модели, например, машины Тьюринга и автоматы с магазинной памятью. Практическое и теоретическое значение автоматньж моделей в решении задач проектирования и технического диагностирования, познания процессов формирования и передачи сигналов в биологических системах, систематизации и оптимизации управляющих воздействий в экономике и т.д. стало причиной интенсивных исследований по теории автоматов. Исследованию теории автоматов, а также вопросам их возможного применения в различных отраслях науки и техники посвящено большое количество работ отечественных и зарубежных авторов. Следует отметить исследования Дж, фон Неймана, АГилла, В.М.Глушкова, С.В.Яблонского, П.П.Пархоменко, В.Б.Кудрявцева, БАТрахтенброта, АМ.Богомолова, М.Ф.Каравая, Д.В Сперанского, ВАТвердохлебова, ААСытника.
Разнообразие возникших задач, подходов к их решению, научных позиций исследователей привело к выделению классов автоматов (автоматы типов Мили и Мура, автоматы Медведева, автономные автоматы, автоматы с конечной глубиной памяти, (n, т, 1) -автоматы и т.д.), а также к разработке различных математических способов их задания (табличное задание, графы автоматов, автоматные матрицы, логические уравнения, формулы языка регулярных выражений, задание автомата композицией автоматов).
Потребность в использовании моделей в виде конечных детерминированных автоматов для реальньж объектов с большим числом состояний привела к развитию теории структурных автоматов, в которой абстрактная форма автомата A = (S, X, Y, 8, X), где S, X и Y - соответственно множества состояний, входньж и вьжодньж сигналов, а 8 и X функции переходов 8 : S х X -» S и вьжодов X : S х X —> S , заменялась структурной формой, то есть, композицией преобразователей сигналов и элементов памяти.
Первое, принципиально важное, представление абстрактного автомата на пути к его структурному заданию, определяется следующей схемой:
Комбинац. часть
у = X (s, х) s' = 5 (s, х)
Структурная декомпозиция абстрактного автомата осуществляется на основе синтеза комбинационной части как суперпозиции функций алгебры логики и реализации памяти элементами задержки сигналов. Структурная форма задания конечных детерминированных автоматов принципиально повысила эффективность приложений теории автоматов и представила новые возможности для теоретических исследований. В частности, в диссертации декомпозиция автомата на комбинационную часть и память используется с целью применения развитого математического аппарата алгебры логики.
В качестве средства разделения множества состояний автомата на подмножества используется приложение периодических последовательностей входных сигналов. Как
показано A.M. Богомоловым и В.А. Твердохлебовым, в этом
БИБЛИОТЕКА !
СПетсрбург '
ское изменение состояний. Состояния, не вошедшие в циклы, можно исключить из анализа и оставить для анализа только состояния, не вошедшие в циклы.
Выбор периодов в периодических последовательностях входных сигналов оказался, связанным с рядом нерешенных в теории вопросов, которые и стали предметом исследования. Кроме этого, потребовалось разработать критерии эффективного (для распознавания автоматов) изменения состояний в циклах, методы построения и реализации соответствующих экспериментов с автоматами, формальный аппарат постановки задач и представления результатов.
В литературе существуют отдельные, без существенного теоретического обобщения результаты. В частности, работы по кольцевому тестированию и диагностированию памяти и регистров на основе циклических сдвигов. В диссертации эти результаты обобщены в формальные постановки и предположения и принципах функционирования автоматов в режиме циклического изменения состояний.
Целью диссертации является исследование проблемы, как можно судить по анализу специальной литературы, впервые ставшей предметом систематического рассмотрения в теории автоматов: разделение множества состояний автомата на два подмножества - подмножество состояний, анализ которых можно исключить, и подмножество состояний, на которых ограниченные функции переходов и выходов автомата сохраняют специфику функционирования. Указанная цель конкретизирована через решение следующих задач:
1. Описание и обоснование классификации конечных детерминированных автоматов на основании учета специфических свойств комбинационных частей автоматов.
-
Построение и обоснование математической модели процесса зацикливания автомата. Изучение функционирование автомата с изменениями состояний в циклах. Решение установочной задачи для автоматов с зацикливанием.
-
Получение достаточных условий для выбора периодических последовательностей и методы зацикливания. Получение и обоснование метода распознавания на основе зацикливания.
Методы и средства исследования. В диссертационной работе используются алгебраические методы дискретной математики, математический аппарат теории полугрупп, теории множеств и теории автоматов.
Научная новизна. В диссертационной работе разработаны теоретические основы исследования проблем выбора периодов в периодических последовательностях входных сигналов. Кроме этого, разработаны критерии эффективного (для распознавания автоматов) изменения состояний в циклах, методы построения и реализации соответствующих экспериментов с автоматами, формальный аппарат постановки задач и представления результатов.
Практическая и теоретическая ценность. Работа носит теоретический характер, разработаны новые положения, развивающие классические результаты в области синтеза, анализа и организации целенаправленного поведения конечных детерминированных автоматов как математической модели дискретных систем с памятью.
Апробация работы и публикации. Основные результаты диссертации докладывались на Международной конференции «Компьютерные науки и информационные технологии» (Саратов. 2002 г.), на Всероссийской конференции "Телематика - 2001 (Санкт-Петербург, 2001), на Всероссийской конференции "Телематика - 2003 (Санкт-Петербург, 2003), на семинарах в Саратовском государственном университете, в Саратовском государственном социально-экономическом университете, в Институте проблем точной механики и управления РАН, в Центральном научно-исследовательском институте измерительной аппаратуры. По теме диссертации опубликовано 5 статей.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы (68 наименований) и двух приложений. Объем работы 143 страницы машинописного текста.
Алгебра композиции автоматов
Представление абстрактного конечного детерминированного автомата А = ( S, X, У, 5, X ) в виде канонической структуры (композиции двух компонент - комбинационной части и памяти) требует пояснений. Пусть S = (Е2 ) и память размещена в структурном автомате, которому соответствует автомат А , в различных частях структуры в виде К двоичных задержек 3/, 32, ..., Зк (см. рис. 4) Входные узлы Сл], С 2,..., Cv„ и выходные узлы С}, С2, Сп задержек сигнала на такт могут быть как внутренними, так и внешними узлами в структуре автомата. В работе В.М. Глушкова ( [26] , гл.III 1), приведены «условия правильности построения схем». В основу этих условий положены правила отождествления узлов (логических элементов и элементов памяти), которые позволяют построить схему, реализующую конечный детерминированный автомат. Внешние входные узлы схемы и внутренние узлы схемы, являющиеся выходными узлами автоматов Мура, полагаются задающими узлами схемы, в которых в каждый рассматриваемый момент времени сигнал имеется. В остальных узлах схемы сигналы определяются сигналами в задающих узлах и цепочками прохождений сигналов через элементы схемы. Следующее условие (В.М. Глушков, [26 ] с.176) определяет наличие сигналов во всех узлах схемы: 1. Для любого узла схемы должна иметься цепь, состоящая из некоторого множества (может быть пустого) автоматов Мили, начинающаяся каким-либо задающим узлом и кончающаяся данным узлом. Корректность определения сигналов в узлах достигается соблюдением правил. 2.
Любой узел схемы должен быть отождествлен (соединен) не более, чем с одним внешним входным или внутренним выходным узлом. 3. Любая нетривиальная (содержащая не менее одного автомата) петля в схеме должна содержать в своем составе хотя бы один автомат Мура. В связи с тем, что используемая классификация автоматов базируется на выделенной комбинационной части и решение исследуемых задач использует выделенную комбинационную часть автомата, придадим правилам композиции специальный вид. Необходимость в таком специальном виде операций синтеза структурных автоматов определяется следующими причинами. В основу построения эксперимента по распознаванию автомата в заданном семействе структурных конечных детерминированных автоматов (например, при интерпретации семейства автоматов как математического описания класса рассматриваемых дефектов) положена декомпозиция задачи распознавания на три задачи: - задачу локального проявления дефекта на элементе, предполагаемым неисправным; - задачу управления локальным проявлением дефекта (управления внешними входными сигналами); - задачу наблюдения проявлением дефекта на внешних выходах автомата. Для решения второй и третьей из указанных в декомпозиции задач требуется анализ сигналов на внутренних узлах структурного автомата.
Известные правила правильного синтеза автоматов не ориентированны на «наблюдения» и «управление» с использованием внутренних узлов структурного автомата. Для систематизации действий по фиктивному выводу внутренних узлов предназначен введенный набор операций. Кроме этого, эффективность анализа сигналов во внутренних узлах структурного автомата для поиска входных слов для зацикливания изменений состояний повышается с использованием фиктивных входов и выходов во внутренние узлы. По возможностям управлять состоянием задержки сигнала и наблюдать выход задержки могут быть определены четыре типа задержек: - ненаблюдаемые и неуправляемые; - наблюдаемые и неуправляемые; - ненаблюдаемые и управляемые; наблюдаемые и управляемые. Наблюдаемость выхода задержки означает, что ее выходной узел является внешним выходным узлом автомата. Если входной узел задержки оказывается внешним входным узлом автомата, то задержка полагается управляемой. В связи с этим получаем следующую таблицу совмещения наблюдаемости и управляемости в зависимости от расположения задержки сигнала в структуре автомата:
Функционирование автомата с изменениями состояний в циклах
Исследуется задача распознавания автомата в заданном конечном семействе КДА а = {Ai}iel , где для каждого і є I АІ ( St, X, Y, 8 І , ЛІ), средствами условного эксперимента со специальным типом функционирования - функционирования на основе приложения чередующихся периодических входных последовательностей Для интерпретации в приложениях в условия задачи неявно включается предположение о том, что автоматы из семейства а имеют множества состояний Si, і el, с большим числом элементов. Разрабатываемый метод распознавания ориентируется на обоснованное сокращение множества состояний, реакции на которые учитываются при реализации метода распознавания (а не при построении распознающего эксперимента). Теорема 13 в отличие от теоремы 8 Э.Мура [1] явно выделяются свойства, на которых базируется решение установочной задачи; - совпадение р - приемников у различных состояний автомата; - несовпадение наблюдаемых реакций на одно и то же входное слово для различных состояний. Первое свойство в частных случаях позволяет решать установочную задачу без наблюдения выходных слов. Критерием такого решения установочной задачи является условие Второе свойство оказывается основным и существенным при сведении распознавания автомата в заданном семействе автоматов к установочной задаче для "расщепляемого" (по А.Гиллу) автомату для семейства. В теореме 13 представлены оба случая проявления свойств состояний автоматов. Исследованный метод впервые был указан в работе A.M. Богомолова и В.А. Твердохлебова [11] . В этой работе (теорема 23) показана общая структура процесса функционирования конечного детерминированного автомата под воздействиями периодических последовательностей. Здесь же приводится пример исключения из анализа вершин, не входящих в циклы, порождаемые приложением периодических последовательностей. Полного исследования, отвечающего на вопросы: - как выбирать входные слова для формирования периодических входных последовательностей? - для каких автоматов метод эффективен? - как строить эксперимент по распознаванию автомата на основе приложения периодических входных последовательностей? - какими алгоритмами возможна реализация условного эксперимента, построенного на основе этого метода? - как оценить "неполноту11 метода по отношению к методу (теоретически предполагаемому) установочного дерева? На эти и другие вопросы в указанной работе ответов нет.
В ряде дальнейших исследований, рассматриваются технические аспекты контроля и диагностирования с приложением периодических входных последовательностей. Однако окончательной теоретической проработки указанного подхода к диагностированию не содержится. Закономерность связи ограничения воздействий на вход автомата (например, сведением к воздействию периодическими входными последовательностями) с ограничениями на функционирование и реакции автомата отмечалась специалистами по технической диагностике, но систематического исследования, закрывающего проблему, нет. В диссертации разработан метод периодических воздействий на вход автомата с целью выделения фрагментов его функционирования, позволяющих сокращать объем анализируемой информации с наименьшей (для периодических воздействий) потерей эффективности распознавания автомата в заданном семействе автоматов. Специфическим является сокращение анализируемой (и требующей построения) информации как при разработке условного эксперимента, так и информации, используемой при фактическом проведении условного эксперимента. При построении для конечного детерминированного автомата А - ( S, X, Y, S, Л ) графа Gp зацикливания автомата по периодической входной последовательности рт характерными путями в графе являются : - пути с наибольшей длиной mj в цикле графа; - пути длины т = т} + т2 в графе Gp. Информацию о заключительном состоянии автомата, получаемую как наблюдаемую реакцию на входную последовательность рт, представляет слово X ( S ( s, р ), рт2), где s -состояние, рт преемником которого является заключенное состояние. Выходное слово по предположению определяется как проекция слова X (S(s, pmJ),pm2) . Ранее проекцию составляла первая буква, то есть prs X ( S (s, рт ), рт ).
Это не обязательное ограничение. В общем случае будем рассматривать в качестве характеристики заключительного состояния слово При решении задачи распознавания автомата в конечном семействе конечных детерминированных автоматов а = {АІ}ІЄ[ , где для каждого і єі Aj = (Sj ,XsY,5j, Xj) одним из фундаментальных методов является сведение задачи к установочной задаче для расщепляемого (по терминологии А.Гилла [23 ]) автомата В случае, когда множеств состояний S = і ,- расщепляемого автомата з /є/ велико, практическое решение задачи распознавания (например, при техническом диагностировании на основе распознавания автоматов) оказывается невозможным. При сохранении основных идей, на которых построено сведение задачи, можно распознавать конечный детерминированный автомат приближенно с сокращением числа анализируемых состояний представленный конечным недетерминированным автоматом. На принципиальную возможность разработки такого метода указано в работе A.M. Богомолова, В.А. Твердохлебова [ 11 ]. Пусть А = (S, X, Y, S, А) - конечный детерминированный автомат. Как показано в работе [11], для любого входного слова р є X связи состояний из множества состояний S, представленные состояниями и их р
Теорема о связи решения установочной задачи для модели зацикливания автомата
Рассмотрим распознавание автомата в семействе конечных детерминированных автоматов а {А І}} І 3 , заданных таблицами 1—3, с помощью простого условного эксперимента, базирующегося на приложении входных периодических последовательностей. Таблица 1. Средства распознавания ограничим приложением периодических входных последовательностей pi = х2, Р2 = X] х2 и рз = X! х; , а также требованием наблюдать выходные сигналы только для изменения состояний автоматов в циклах. Для этого построим автоматы Q(Aj ,р},р2, подавтоматами которого являются эти автоматы. Множество S/, 52 и 1 состояний автоматов Аі,А2иА3. В один класс разбиения попадают всё те же состояния, для которых при приложении сигнала х первой достигнутой вершиной цикла является одна и та же вершина. Такое разбиение имеет определяющее значение, поэтому уточним его. Определение. Пусть Ai = (S{ , X, У, 8,- , Л ,-), р є X и Gp - граф зацикливания автомата А по периодической входной последовательности с периодом р. Состояния s, s eSj будем называть смежными по циклу графа Gp, если : 1. Для некоторого І, Іє N, 8,- (s, р ) и 5(- (s\ р ) являются вершинами одного и того же цикла Ср . 2. Для некоторого I Г , 8,- (s, р ) = S,- (s\pl ), 5i(s, р1 ) є є { Слр } 81 (s, pl ) - первая вершина цикла достигаемая из СОСТОЯНИЙ S YL S\ У автомата А; по р/ все классы смежных состояний являются одноэлементными. Автомат А2 uopj имеет следующие классы смежных состояний: Все классы смежных состояний автомата А3 по р; являются одноэлементными. Аналогично определяются классы смежных состояний для остальных случаев в рассматриваемом примере.
Заметим, что связь смежных состояний, состояний автомата А, состояний - вершин циклов и выходных слов является более тонкой, чем это может показаться. Пусть s и s\ - смежные вершины в графе Gp , из которых достигается цикл Ср . Предположим, что числа т} и т2 имеют определенный ранее смысл. Предположим далее, что первой достигаемой из s и s" вершиной цикла является вершина s". (Вершины 8(s,pm!) и " не обязательно совпадают) Состояния s и sv характеризуются выходным словом, которое выдается автоматом А при изменении состояний в цикле, начиная с состояния 8 (s, pml), а не с состояния s"". Величина щх наибольшей длины пути в графах Q] ,Q2 и Qb ИЗ ВИСЯЧИХ ВерШИН В ЦИКЛЫ Определяется ПуТЯМИ: Sj6 , Sn , S15 , S24 , S23 , S21 И Аналогично, величины уП\, и ТПі определяются равенствами: Величина щ2 наибольшей длины циклов в графах Q] , Q2 и Q и аналогичных величин щ2 , щ2 определяются равенствами т2р[ =4 ШгрГ МгРг = В связи с этим множества входных и выходных сигналов конструируемого автомата образованы словами в алфавитах X и Y, имеющими вычислительную длину: Построим конечный детерминированный автомат, состояниями которого являются только вершины циклов графов (J , Q и (J . Функция переходов 3 и функция выходов Л определяются таблицей 4. Теорема 14. Пусть A = (S, X, Y, 5 , Я) - конечный детерминированный автомат и Q.{A, р , 1 і г, v) - модель зацикливания автомата А. Тогда любое решение р є {р" , 1 і г } установочной задачи Q для автомата (А, рш , 1 і г , v ) является решением установочной задачи для автомата А. Доказательство. Множество всех входных последовательностей автомата Q ( А, р1" , 1 і г , v ) является подмножеством множества X , входных последовательностей автомата А. Множества состояний рассматриваемых автоматов совпадают. Следовательно, входная последовательность, определяющая решение установочной задачи для автомата С1 ( А, р , 1 і г , v ) однозначно и полностью определяет изменения состояний автомата А. Пусть р % X X установочная входная последовательность для автомата Q ( А, р , 1 і г , v ) . Это означает, что для каждой пары состояния (s,s ) выполняется условие У1 (s, р) = PJ (s\p) или У ( s, р ) Ф ( s\ р ) .
В случае, когда 4у ( s, р ) = W (s\ р ) , очевидно получаем 3 ( s, р) = 3(V, р) (по построению функции !f на основе функции 3) Не нарушая общность предположим, что у у . Выходные слова 7 7 Y ( s, р) и Ч ( s \ р ) могут быть рассматриваться как результаты исключения некоторых букв в словах Л (s, р) и Л (s\ р ) ,а именно, букв, расположенных в словах на одних и тех же местах. Точнее, для некоторых слов (возможно пустых) и},и2, ... , Ut+j ,Vj,V2, ..., vl+I в алфавите Y Y2 (s,p). На основании теоремы каждое решение установочной задачи для конечного детерминированного автомата О. (А, р , 1 і г , v ) , являющегося моделью зацикливания автомата А по входным последовательностям р", 1 і г с наблюдением только v -ых выходных сигналов в циклах, оказывается решением установочной задачи для автомата А. В теореме представлен следующий важный факт: при потере информации в результате - ограничения функционирования автоматов режимов зацикливания; - отсутствия наблюдения выходных сигналов до перехода изменений состояний в цикле; - наблюдения некоторых выходных сигналов при изменении состояний в цикле установочная задача для автомата А в ряде случаев может быть решена.
Граф, определяющий совмещение конституэнт единицы в функциях переходов и выходов автоматов
Построим граф С=(П , R ), в котором множеством вершин Q Элементарные отрицаний), рассматриваемом примере Q = (z, z3 , z, z2 , zx z2 }. Полагаем, что дуга, помеченная парой (Xj х2 , г ) соединяет вершину z, z2 с вершиной z[ z2 , если 1) х, - х2 zl z2 є { hZi hs2 }, 2) для некоторых х/ и х2 х/ z[ -г г є { hsi Є hs2}, где z[ = za\ , z2 - zpi и показатели a , p логической степени логических переменных определяются отношениями 5H(2J -z2, Xj -x2) = a, 6i2(z, -z2t xrx2) = p, где через z, обозначена переменная z; или ее отрицание. Кроме метки (х{ х2 , / ) каждая дуга, исходящая из вершины z, z2 , помечается значением функции A,j : A,j (z z2, х( х2 ). Следовательно, связь каждых двух вершин в графе G представлена диаграммой, изображенной на рис. 29. При построении графа G для анализа вариантов функциони-рования двух автоматов удобно к метке дуги добавлять индекс соответствующего автомата. На основании леммы 3 для любой конституэнты единицы С : С є { hs, hs2} X, (с) 12(с), где С набор значений переменных х}, Х2, z}, z2, соответствующий единичному значению конституэнты С. По введенным правилам построения дуг графа G -(Q ,Rr) вершина z, z2 соединяется дугой с вершиной z[z[ , если во множестве конституэнт {h І Ш h 2} имеется две коституэнты хл хг -zx z2 и х[ х г z\ z 2 , удовлетворяющие условиям, определенным свойствами функций А, і , %г 5л , 5і2 , і = 1,2. Свойства функций Х\ и А,2 определяют Т У принадлежность конституэнт множеству (h 1 Ф h 2} Свойства функций 5;і и 6;2 (і = 1,2) определяют дуги и метки дуг. Дуги, исходящие из вершин рассматриваемого в примере графа, определяются следующими конституэнтами: - вершина z: z2 конституэнтной, определяющей для автомата входной сигнал (0, 0); - вершина z, z2 конституэнтами, определяющими для автомата входные сигналы (0, 0), (1, 0); - вершина гл z2 конституэнтами, определяющими для автомата входные сигналы (0, 1), (1, 0), (1, 1). Соответствующий граф изображен на рис. 30. Рис.30. Граф G с множеством вершин, определяемым множеством конституэнт {{ hZj Ф hs2 }} для автоматов A i и А 2. После рассмотрения примера, поясняющего построение графа G =(l\R ) для пары конкретных автоматов А [ и А 2 , определим граф для пары автоматов в общем виде. Пусть заданы конечные детерминированные автоматы A, Для пары автоматов (At , А2) построим граф G=(Q, R) по следующим правилам. Правило построения множества О. Функциям выходов Х\ и Х2 соответственно автоматов Аі и А2 сопоставим ассоциированные с ними функции алгебры логики h j, где 1 і 2 и 1 j n3 , вида значений х/, х2, хп2, z2i..., znI ПеремеННЫХ Xj, Х2, , Х„2, Z2 Zni Для каждой функции A J- строится СДНФ Л J., і є{0, І}, 1 j щ. В формуле hy производится замена всех вхождений знака «v» на знак «» (сложение по mod 2) и результат замены обозначается /г .
Для каждого j, 1 j щ , определяется сумма h ц h 2j , которую будем называть j-ой характеристической суммой функций X] и Х2 noj-ому выходному каналу. Для каждого j, 1 j щ , полагаем: Для некоторого jo , 1 jo Щ , полагаем Q = Q Y{ Индекс jo назовем индексом графа G по выходу. Правило построения дуг графа G. = (z/-?2 -K-z; ) и z/ z 2 ..... zr!j є д Если z{ z[ -...- z„ Q , то дуга с указанными метками соединяет вершины Zj z2, . ztti и є. Две функции алгебры логики // (х;, х2, . . . , хп) и f2 (xj, х2 , . . ., хп), зависящие от одних и тех же переменных х/, Х2 , . . . , хп , представим в СДНФ hi и h2, а после замены в СДНФ знаков « v » на знак « Ш », выражениями hi и h 2 у у Такая замена задания функций /]и/2 выражениями h і и h 2-Дает ряд преимуществ при анализе свойств функций. Следующая лемма показывает формальную возможность замены. Лемма 4. Пусть f} (х}, х2,. .., хп) - функция алгебры логики, h -СДНФ функции /, a hs - формула, полученная формальной заменой в h знаков «v» на знаки «S». Имеет место равенство: J і (Xj , Х2 ,..., Хп J її [Xj , X2 ,..., XnJ. Доказательство: Пусть/} (x; , x2 , . . . , xn) - формула, определяемая условиями теоремы. Рассмотрим набор значений хj , х2 , . . . , х п переменных х/ , х2, . . . , х„ и соответствующие ему значения левой и правой частей доказываемого равенства. В левой части получаем (Х] , Х2 , . . . , X „). Возможен только один из двух вариантов: /; (х s , х2, . . . , хп)= О или fi (xi , х2 , . . . , хп) - 7. В первом случае в СДНФ h (х} , х2 , . . . , хп) конституэнта % 1 & &... & у " отсутствует, а любая другая конституэнта на наборе х s, х2, . , х„ принимает значение 0, это означает, что в СДНФ входит конституэнта х?[ & х 1 & -& Хп" сумме по модулю 2 h Хп) Й fi (Х[, х2, . . ., хп) выполняется равенство сумма no mod 2 конституант единицы функции f, i l, 2/ Доказательство: На основании леммы: Из определителя операции сложения по mod 2, получаем следующие условия:
