2 (1132838), страница 5
Текст из файла (страница 5)
Завершая примеры выводимостей, докажем,что ΠK DK OΠt1,& , t&,∨ , tA|⇒ tΠ .∨ , t∨ , t∨Действительно,x1 ∨ x1 x2 7→ x1 (x2 ∨ x2 ) ∨ x1 x2 7→ x1 ((x2 ∨ x2 ) ∨ x2 )tΠK1,&tD&,∨|⇒ x1 ((x2 ∨ x2 ) ∨ x2 ) 7→ x1 (x2 ∨ x2 ) 7→ x1 .KtA∨ ,t∨tOΠ∨tΠK1,&ПоложимΠK ΠKM A K OΠ Dτ осн = tM& , t¬ , t& , t& , t& , t&,∨ , t1,& , t0,& ,Aτ A = tA& , t∨ ,Kτ K = tK& , t∨ ,OΠ,τ OΠ = tOΠ& , t∨DDDτ = t&,∨ , t∨,& ,ΠKΠK ΠK ΠKτ= tΠK0,& , t1,& , t0,∨ , t1,∨ ,τeосн = τ M , τ A , τ K , τ OΠ , τ D , τ ΠK , tΠ .Систему τ осн будем называть системой основных тождеств,а систему τeосн — расширенной системой основных тождеств. Рассмотренные выше примеры выводимостей доказывают следующее утверждение.Лемма 3.1.
Система τeосн выводима из системы τ осн .Покажем теперь, что с помощью ЭП на основе системытождеств τ осн из любой формулы можно получить совершенную ДНФ или формулу x1 x1 . Введем для этого некоторые понятия, характеризующие формулы, появляющиесяна промежуточных этапах указанного ЭП.
ПроизвольнуюВведение29конъюнкцию букв, содержащую, в общем случае, повторяющиеся или противоположные буквы, будем называть обобщенной ЭК (ОЭК), а дизъюнкцию таких конъюнкций, содержащую, в общем случае, повторяющиеся «слагаемые», —обобщенной ДНФ (ОДНФ). Обычную ЭК (ДНФ) и формулуx1 · x1 будем считать канонической ОЭК (соответственно канонической ОДНФ), а совершенную ДНФ и формулу x1 · x1— совершенными ОДНФ. Напомним (см.
§2), что формула,в которой все ФС ¬ применяются только к БП и нет двухпоследовательно применяемых ФС ¬, называется формулойс поднятыми отрицаниями.Пусть формула F (x1 , . . . , xn ) реализует ФАЛ f (x1 , . . . , xn ).Докажем существование ЭП видаF |⇒ F0τMbF00 |⇒ F|⇒{KtD&,∨ ,t&}τ ΠΠeF,|⇒{ΠΠtD&,∨ ,τ(3.2)}где τ ΠΠ = τ A , τ K , τ ΠK , τ OΠ , tΠ , F0 — формула с поднятыbиFe — каноними отрицаниями, F00 — обобщенная ДНФ, а Fческая и совершенная ОДНФ ФАЛ f соответственно. Действительно, поднятие отрицаний, то есть переход от F к F0в (3.2) (см.
§2) можно осуществить применением тождествMMtM¬ , t& и t∨ к подформулам вида (F1 ), (F1 · F2 ) и (F1 ∨ F2 )соответственно до тех пор, пока все такие подформулы небудут «устранены». Переход от F0 к F00 в (3.2), который называется раскрытиемno скобок, осуществляется применениемDKтождеств t&,∨ , t& к подформулам вида F1 · (F2 ∨ F3 ) или(F1 ∨ F2 ) · F3 до тех пор, пока они встречаются в преобразуемой формуле.b в (3.2), который называется привеПереход от F00 к Fдением подобных, выполняется в три этапа.
На первом этапе каждая ОЭК K 00 из ОДНФ F00 преобразуетсяв канониnoOΠΠKK , аческую ОЭК K с помощью тождеств t& , t0,& , tA,t& &30Введениетакже тождестваxi · xi = x1 · x1 ,(3.3)которое выводится из них следующим образом:xi · xi 7→ (x1 · x1 ) · (xi · xi ) 7→ (xi · xi ) · (x1 · x1 ) 7→ x1 · x1 .tΠK0,&tK&tΠK0,&bНа втором этапе полученная формула F̌ преобразуется в Fпутем «устранения» повторных вхождений равных элементарных конъюнкций или подформул x1 · x1 с помощью тождеств τ A , τ K , tOΠи, в случае f 6≡ 0, последующего«устра∨ A K ΠKнения» ОЭК x1 · x1 с помощью тождеств t∨ , t∨ , t0,∨ .Заметим, что первые два этапа приведения подобных,на которых происходит приведение повторений БП в ОЭК иb Однако, для уменьЭК, уже дают нам искомую формулу F.шения числа шагов в последующих ЭП можно выполнитьтретий этап приведения подобных — этап приведения поглощений ЭК.
На каждом шаге этогоэтапа в полученнойДНФ с помощью тождеств τ A , τ K выделяется подформула вида K 00 ∨ K 00 · K, где K 00 и K — некоторые ЭК, а затемЭК K 00 · K «устраняется» с помощью ЭПK 00 ∨ K 00 · K 7→ K 00 .tΠЗаметим также, что раскрытие скобок и различные этапыприведения подобных можно чередовать друг с другом приbЭП подформул формулы F0 или формул F00 , F.beПереход от F к F в (3.2) выполняется в два этапа. Сначаb которая имеет ранг r, где r = n − q <b из F,ла каждая ЭК Kn, и не содержит букв БП xi1 , . .
. , xiq , приводится к ее соe от БП X (n) в результате следующеговершенной ДНФ KЭП:b |⇒ Kb (xi ∨ xi ) · · · xiq ∨ xiq |⇒ K.eK11tΠK1,&tD&,∨Введение31Затем в полученной ОДНФ устраняются повторные вхождения слагаемых так, как это делалось ранее при переходеb и в результате мы приходим к совершенной ОДНФот F̌ к F,e Таким образом, доказано следующее утверждение.F.Лемма 3.2. Любую формулу F (x1 , . . .
, xn ), реализующуюФАЛ f , с помощью ЭП на основе системы тождеств τ оснможно преобразовать в совершенную ОДНФ ФАЛ f от БПX (n).Рассмотрим описанные выше ЭП на примере формулыF = (x1 ∨ x2 ) · (x1 · x3 ) · (x2 ∨ x3 ) ,для которойF 7→ (x1 ∨ x2 ) · (x1 ∨ x3 ) · (x2 ∨ x3 )tM&F0|⇒{bFx1 x2 x3 ∨ x1 x2 ∨ x1 x2 x3 ∨ x2 x3ΠΠ \tΠtD&,∨ ,τ|⇒= F0 ,b= F̌ = F,}x1 x2 ∨ x2 x3b 0,=Fx1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3e= F.{τ A ,τ K ,tΠ }b0F|⇒{ΠΠtD&,∨ ,τ}Теорема 3.1. Система τ осн — полная система тождеств.Доказательство.
Пусть F0 и F00 — эквивалентные формулы,реализующие равные ФАЛ f 0 и f 00 соответственно, а наборx (n) = x содержит все различные БП, встречающиеся в F0e — совершени F00 . Пусть, далее, ФАЛ f (x) равна f 0 и f 00 , а Fная ОДНФ ФАЛ f от БП X (n). В силу леммы 3.2, имеетместо ЭПe |⇒ F00 ,F0 |⇒ Fτ оснкоторое доказывает теорему.τ осн32Введение§4Задание формул графами, схемы из функциональных элементов. Оценка числа формул и схем в базисе {&, ∨, ¬}Рассмотрим теперь более общую по сравнению с формулами модель — модель схем из функциональных элементов(СФЭ), в которой последовательность операций суперпозиции базисных ФАЛ задается с помощью ориентированногоациклического графа, обобщающего дерево, и где возможномногократное использование промежуточных результатов.По существу СФЭ получается из системы деревьев (системы формул) в результате отождествления некоторых изоморфных поддеревьев (совпадающих подформул).Пусть Z — счетный упорядоченный алфавит (выходных)БП, который не имеет общих БП с алфавитом X.
Сопоставим каждому функциональному символу (ФС) ϕi , i =1, . . . , b, функциональный элемент (ФЭ) Ei , имеющий ki входов, причем входу с номером j соответствует j-я БП xj ФАЛϕi , где j = 1, . . . , ki , и один выход, на котором эта ФАЛ реализуется (см. рис. 4.1a). Упрощенный вариант изображенияФЭ Ei в виде вершины графа с пометкой ϕi , в которую входят ki упорядоченных, то есть пронумерованных числами1, .
. . , ki дуг, показан на рис. 4.1b. При этом предполагается,что дуга с номером j, 1 6 j 6 ki , соответствует j-му входу ФЭ Ei . В дальнейшем мы, как правило, не будем делатьразличий между функциональным символом ϕi и функциональным элементом Ei .Определение. Схемой из функциональных элементов надбазисом Б называется ориентированная ациклическая упорядоченная сеть Σ, входная выборка которой состоит из всехистоков Σ, а вершины помечены следующим образом:1. каждому входу (выходу) Σ сопоставлена БП из X (соответственно Z), являющаяся пометкой связанной сВведение33x1 . .
. xki••Eix1 . . . xk i••ϕia)Eiki1•ϕib)Рис. 4.1: функциональный элемент Eiним вершины, причем различным входам (выходам)сопоставлены различные БП, а упорядоченность вершин во входной и выходной выборках Σ определяетсяупорядоченностью сопоставленных им БП;2. каждая отличная от истока вершина v схемы Σ помечена ФС ϕi , где ki = d+Σ (v).Заметим, что в общем случае вершины в выходной выборке СФЭ могут повторяться, то есть одной и той же выходной вершине может быть сопоставлено несколько БП изZ. Если множество X = {xi1 , . .
. , xin } (Z = {zj1 , . . . , zjm }) состоит из всех входных (соответственно выходных) БП СФЭΣ, перечисленных в порядке возрастания их номеров в алфавите X (соответственно Z), то, в соответствии с §1, будемзаписывать СФЭ Σ в виде Σ = Σ (X; Z) или Σ = Σ (x; z),где x = (xi1 , . . . , xin ) и z = (zj1 , . . . , zjm ) — наборы БП, соответствующие множествам X и Z.Схема Σ, которая получается из дерева D, связанного сформулой F из UΦБ , в результате отождествления листьев содинаковыми пометками и приписывания его корню выходной БП из Z, называется квазидеревом, соответствующимформуле F. Заметим, что указанное квазидерево Σ одно-34Введениеx1x2•1&x1•21 •2•{2∨x3# ∨•{ 2•2•1 1&1x2••1• ∨z1•#1¬&•u)∨x3•2∨∨&vu)∨u¬∨a)z1b)Рис. 4.2: СФЭ, полученная из квазидерева на рис. 2.2bзначно определяет формулу F и является СФЭ над базисомБ.
Из этого квазидерева путем «отождествления» (наложения) его изоморфных квазиподдеревьев можно получать идругие СФЭ, задающие формулу F. На рис. 2.2b показаноквазидерево над базисом Б0 с входными БП x1 , x2 , x3 и выходной БП z1 , которое получено из дерева, сопоставленногоформуле (2.3) и изображенного на рис. 2.2a. На рис. 4.2aприведена СФЭ, полученная из данного квазидерева в результате отождествления двух его изоморфных квазиподдеревьев, а на рис. 4.2b дано более «наглядное» изображениеэтой СФЭ в виде системы соединенных соответствующимобразом ФЭ.Обозначим через UCБ множество всех СФЭ над базисомБ, и пусть UC = UC.Заметим,что система квазидеревьевБ0с общими входами, соответствующая системе формул надВведение35базисом Б, является СФЭ над Б, если выходам этих квазидеревьев приписаны различные выходные БП.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
