Ложкин С.А. Лекции по основам кибернетики
Подождите немного. Документ загружается.
§2. Эквивалентные преобразования формул 71
его ЭП вида
F ⇒
{
τ ,τ
B
Б
,τ
C
Б
}
b
F.
На рис. 1.4 показано ЭП СФЭ из U
C
, которое моделирует
ЭП (1.1) для формул из U
Φ
.
Из описанного выше способа «моделирования» ЭП
формул с помощью ЭП СФЭ, а также способа перехода от
формул к СФЭ и обратно на основе ЭП с помощью тождеств
τ
B
Б
, τ
C
Б
вытекает справедливость следующего утверждения.
Теорема 1.1. Если τ — конечная полная система
тождеств для ЭП формул из U
Φ
Б
, то
τ, τ
C
, τ
B
—
конечная полная система тождеств для ЭП СФЭ из U
C
Б
.
Заметим, что вопрос о существовании кон ечно й полной
системы тождеств (КПСТ) является одним из основных
вопросов, связанных с изучением ЭП схем из заданного
класса U.
§2 Эквивалентные преоб разования формул
базиса {&, ∨, ¬}. Полнота системы основных
тождеств. Теорема перехода
В данном параграфе будем рассматривать только формулы
над базисом Б
0
, называя их просто формулами. Заметим,
что имеют место (см., в частности, ??–?? главы 1, §2 главы 2,
а также §1) следующие тождества ассоциативности
t
A
◦
: x
1
◦ (x
2
◦ x
3
) = (x
1
◦ x
2
) ◦ x
3
,
тождества коммутативно сти
t
K
◦
: x
1
◦ x
2
= x
2
◦ x
2
и тождества отождествления БП
t
OΠ
◦
: x ◦ x = x,
72 Глава 3. Эквивалентные п реоб разова ния
где ◦ ∈ {&, ∨}, тождества дистрибутивности «◦»
относительно «»
t
D
◦,
: x
1
◦ (x
2
x
3
) = (x
1
◦ x
2
) (x
1
◦ x
3
)
и тождества («правила») де Моргана
t
M
¬
: (x
1
) = x
1
, t
M
◦
: (x
1
◦ x
2
) = (x
1
) (x
2
) ,
где (◦, ) ∈ {(&, ∨) , (∨, &)}, тождества подстановки
констант
1
t
ΠK
0,&
: x
1
(x
2
· x
2
) = x
2
· x
2
, t
ΠK
1,&
: x
1
(x
2
∨ x
2
) = x
1
,
t
ΠK
0,∨
: x
1
∨ x
2
· x
2
= x
1
, t
ΠK
1,∨
: x
1
∨ (x
2
∨ x
2
) = x
2
∨ x
2
,
а также тождество поглощения
t
Π
: x
1
∨ x
1
x
2
= x
1
,
тождество обобщенного склеивания
t
OC
: x
1
x
2
∨ x
1
x
3
= x
1
x
2
∨ x
1
x
3
∨ x
2
x
3
и другие.
Примером ЭП формул с помощью введенных тождеств
является ЭП (1.1). Докажем, д алее, что
t
M
&
, t
M
¬
⇒|
t
M
∨
и
t
K
&
, τ
M
⇒|
t
K
∨
,
где τ
M
=
t
M
&
, t
M
¬
, t
M
∨
. Действительно,
x
1
∨ x
2
⇒|
t
M
¬
x
1
∨
x
2
7→
t
M
&
(x
1
) · (x
2
) 7→
t
M
¬
x
1
· x
2
1
В отличие от тождеств (??)–(??) главы 1 данные тождества
подстановки констант ориентированы на базис Б
0
, где роль константы
0 (константы 1) играет формула вида x
i
· x
i
(соответственно x
i
∨ x
i
).
§2. Эквивалентные преобразования формул 73
и
x
1
∨ x
2
7→
t
M
¬
x
1
∨ x
2
7→
t
M
∨
x
1
· x
2
7→
t
K
&
x
2
· x
1
⇒|
t
M
&
, t
M
¬
x
2
∨ x
1
.
Аналогичным образом доказывается, что
t
A
&
, τ
M
⇒|
t
A
∨
,
t
OΠ
&
, τ
M
⇒|
t
OΠ
∨
,
t
D
&,∨
, τ
M
⇒|
t
D
∨,&
и
t
ΠK
σ,&
, τ
M
⇒|
t
ΠK
σ,∨
,
где σ ∈ {0, 1}. Завершая примеры выводимостей, докажем,
что
t
ΠK
1,&
, t
D
&,∨
, t
A
∨
, t
K
∨
, t
OΠ
∨
⇒| t
Π
.
Действительно,
x
1
∨ x
1
x
2
7→
t
ΠK
1,&
x
1
(x
2
∨ x
2
) ∨ x
1
x
2
7→
t
D
&,∨
x
1
((x
2
∨ x
2
) ∨ x
2
)
⇒|
t
A
∨
,t
K
∨
x
1
((x
2
∨ x
2
) ∨ x
2
) 7→
t
OΠ
∨
x
1
(x
2
∨ x
2
) 7→
t
ΠK
1,&
x
1
.
Положим
τ
осн
=
t
M
&
, t
M
¬
, t
A
&
, t
K
&
, t
OΠ
&
, t
D
&,∨
, t
ΠK
1,&
, t
ΠK
0,&
,
τ
A
=
t
A
&
, t
A
∨
,
τ
K
=
t
K
&
, t
K
∨
,
τ
OΠ
=
t
OΠ
&
, t
OΠ
∨
,
τ
D
=
t
D
&,∨
, t
D
∨,&
,
τ
ΠK
=
t
ΠK
0,&
, t
ΠK
1,&
, t
ΠK
0,∨
, t
ΠK
1,∨
,
eτ
осн
=
τ
M
, τ
A
, τ
K
, τ
OΠ
, τ
D
, τ
ΠK
, t
Π
.
Систему τ
осн
будем называть системой основных
тождеств, а систему eτ
осн
— расширенной системой
основных тождеств. Рассмотренные выше примеры
выводимостей доказывают следующее утверждение.
74 Глава 3. Эквивалентные п реоб разова ния
Лемма 2.1. Система eτ
осн
выводима из системы τ
осн
.
Покажем теперь, что с помощью ЭП на основе
системы тождеств τ
осн
из любой формулы можно получить
совершенную ДНФ или формулу x
1
x
1
. Введем для
этого некоторые понятия, характеризующие формулы,
появляющиеся на промежуточных этапах указанного ЭП.
Произвольную конъюнкцию букв, содержащую, в общем
случае, повторяющиеся или противоположные буквы, будем
называть обобщенной ЭК (ОЭК), а дизъюнкцию таких
конъюнкций, содержащую, в общем случае, повторяющиеся
«слагаемые», — обобщенной ДНФ (ОДНФ). Обычную ЭК
(ДНФ) и формулу x
1
·x
1
будем считать канонической ОЭК
(соответственно канонической ОДНФ), а совершенную ДНФ
и формулу x
1
·x
1
— совершенными ОДНФ. Напомним (см. §2
главы 2), что формула, в которой все ФС ¬ применяются
только к БП и нет двух последовательно применяемых ФС
¬, называется формулой с поднятыми отрицаниями.
Пусть формула F (x
1
, . . . , x
n
) реализует ФАЛ
f (x
1
, . . . , x
n
). Докажем существование ЭП вида
F ⇒|
τ
M
F
0
⇒|
{
t
D
&,∨
,t
K
&
}
F
00
⇒|
τ
ΠΠ
b
F ⇒|
{
t
D
&,∨
,τ
ΠΠ
}
e
F, (2.1)
где τ
ΠΠ
=
τ
A
, τ
K
, τ
ΠK
, τ
OΠ
, t
Π
, F
0
— формула с
поднятыми отрицаниями, F
00
— обобщенная ДНФ, а
b
F и
e
F —
каноническая и совершенная ОДНФ ФАЛ f соответственно.
Действительно, поднятие отрицаний, то есть переход от
F к F
0
в (2.1) (см. §2 главы 2) можно осуществить
применением тождеств t
M
¬
, t
M
&
и t
M
∨
к подформулам вида
(F
1
), (F
1
· F
2
) и (F
1
∨ F
2
) соответственно до тех пор, пока
все такие подформулы не будут «устранены». Переход
от F
0
к F
00
в (2.1), который называется раскрытием
скобок, осуществляется применени ем тождеств
n
t
D
&,∨
, t
K
&
o
к
§2. Эквивалентные преобразования формул 75
подформулам вида F
1
·(F
2
∨ F
3
) или (F
1
∨ F
2
)·F
3
до тех пор,
пока они встречаются в преобразуемой формуле.
Переход от F
00
к
b
F в (2.1), который называется
приведением подобных, выполняется в три этапа.
На первом этапе каждая ОЭК K
00
из ОДНФ F
00
преобразуется в каноническую ОЭК K с помощью тождеств
n
t
OΠ
&
, t
ΠK
0,&
, t
A
&
, t
K
&
o
, а также тождества
x
i
· x
i
= x
1
· x
1
, (2.2)
которое выводится из них следующим образом:
x
i
· x
i
7→
t
ΠK
0,&
(x
1
· x
1
) · (x
i
· x
i
) 7→
t
K
&
(x
i
· x
i
) · (x
1
· x
1
) 7→
t
ΠK
0,&
x
1
· x
1
.
На втором этапе полученная формула
ˇ
F преобразуется
в
b
F путем «устранения» п овтор ных вхождений равных
элементарных конъюнкций или подформул x
1
·x
1
с помощью
тождеств
τ
A
, τ
K
, t
OΠ
∨
и, в случае f 6≡ 0, последующего
«устранения» ОЭК x
1
·x
1
с помощью тождеств
t
A
∨
, t
K
∨
, t
ΠK
0,∨
.
Заметим, что первые два этапа приведения подобных,
на которых происходит приведение повторений БП в ОЭК
и ЭК, уже дают нам искомую формулу
b
F. Однако,
для уменьшения числа шагов в последующих ЭП можно
выполнить третий этап приведения подобных — этап
приведения поглощений ЭК. На каждом шаге этого этапа в
полученной ДНФ с помощью тождеств
τ
A
, τ
K
выделяется
подформула вида K
00
∨K
00
·K, где K
00
и K — некоторые ЭК,
а затем ЭК K
00
· K «устраняется» с помощью ЭП
K
00
∨ K
00
· K 7→
t
Π
K
00
.
Заметим также, что раскрытие скобок и различные этапы
приведения подобных можно чередовать друг с другом при
ЭП подформул формулы F
0
или формул F
00
,
b
F.
76 Глава 3. Эквивалентные п реоб разова ния
Переход от
b
F к
e
F в (2.1) выполняется в два этапа.
Сначала каждая ЭК
b
K из
b
F, которая имеет ранг r, где r =
n−q < n, и не содержит букв БП x
i
1
, . . . , x
i
q
, приводится к ее
совершенной ДНФ
e
K от БП X (n) в результате следующего
ЭП:
b
K ⇒|
t
ΠK
1,&
b
K (x
i
1
∨ x
i
1
) ···
x
i
q
∨ x
i
q
⇒|
t
D
&,∨
e
K.
Затем в полученной ОДНФ устраняются повторные
вхождения слагаемых так, как это делалось ранее при
переходе от
ˇ
F к
b
F, и в результате мы приходим к
совершенной ОДНФ
e
F. Таким образом, доказано следующее
утверждение.
Лемма 2.2. Любую формулу F (x
1
, . . . , x
n
), реализующую
ФАЛ f, с помощью ЭП на основе системы тождеств τ
осн
можно преобразовать в совершенную ОДНФ ФАЛ f от БП
X (n).
Рассмотрим описанные выше ЭП на примере формулы
F = (x
1
∨ x
2
) · (x
1
· x
3
) · (x
2
∨ x
3
) ,
для которой
F 7→
t
M
&
(x
1
∨ x
2
) · (x
1
∨ x
3
) · (x
2
∨ x
3
) = F
0
,
F
0
⇒|
{
t
D
&,∨
,τ
ΠΠ
\t
Π
}
x
1
x
2
x
3
∨ x
1
x
2
∨ x
1
x
2
x
3
∨ x
2
x
3
=
ˇ
F =
b
F,
b
F ⇒|
{τ
A
,τ
K
,t
Π
}
x
1
x
2
∨ x
2
x
3
=
b
F
0
,
b
F
0
⇒|
{
t
D
&,∨
,τ
ΠΠ
}
x
1
x
2
x
3
∨ x
1
x
2
x
3
∨ x
1
x
2
x
3
∨ x
1
x
2
x
3
=
e
F.
Теорема 2.1. Система τ
осн
— полная система тождеств.
§2. Эквивалентные преобразования формул 77
Доказательство. Пусть F
0
и F
00
— эквивалентные формулы,
реализующие равные ФАЛ f
0
и f
00
соответственно, а набор
x (n) = x содержит все различные БП, встречающиеся в
F
0
и F
00
. Пусть, далее, ФАЛ f (x) равна f
0
и f
00
, а
e
F —
совершенная ОДНФ ФАЛ f от БП X (n). В силу леммы
2.2, имеет место ЭП
F
0
⇒|
τ
осн
e
F ⇒|
τ
осн
F
00
,
которое доказывает теорему.
Следствие. Система тождеств
τ
осн
, τ
B
, τ
C
— КПСТ
для ЭП СФЭ из U
C
.
Рассмотрим далее вопросы струк турного моделирования
формул в различных базисах. Пусть помимо базиса Б =
= {ϕ
i
}
b
i=1
у нас имеется другой конечный полный базис
Б
0
= {ϕ
0
i
}
b
0
i=1
, и пусть формула Φ
0
i
x
1
, . . . , x
k
0
i
из U
Φ
Б
0
, где
k
0
i
> k
i
, реализует ФАЛ ϕ
i
, i = 1, . . . , b. Заметим, что
в случае k
0
i
> k
i
БП x
k
i
+1
, . . . , x
k
0
i
являются фиктивными
БП формулы Φ
0
i
. При этом будем считать, что если ϕ
i
—
константа и, сл едоват ельн о, k
i
= 1, то имеет место равенство
k
0
i
= 2, а формула Φ
0
i
зависит только от БП x
2
. Положим
Φ
0
=
Φ
0
1
, . . . , Φ
0
b
, Π
0
=
Π
0
1
, . . . , Π
0
b
,
где Π
0
i
— тождество вида ϕ
i
= Φ
0
i
, i = 1, . . . , b, и формулы
из Φ
0
(тождества из Π
0
) будем называть формулами
(соответственно тождествами) перехода от базиса Б к
базису Б
0
.
Для формулы F, F ∈ U
Φ
Б
, обозначим через Π
0
(F)
формулу над базисом Б
0
, которая получается из F заменой
каждой ее подформулы вида ϕ
i
(F
1
, . . . , F
k
i
) формулой
Φ
0
i
F
1
, . . . , F
k
i
, x
k
i
+1
, . . . , x
k
0
i
, то есть является результатом
78 Глава 3. Эквивалентные п реоб разова ния
подстановки фо рмулы F
j
вместо БП x
j
в формулу Φ
0
i
для
всех j, j = 1, . . . , k
i
. Переход от формулы F к формуле Π
0
(F)
будем называть структурным моделированием формулы F
в базисе Б
0
на основе формул перехода Φ
0
или, иначе, на
основе тождеств перехода Π
0
. Заметим, что этот переход
является специальным ЭП вида
F ⇒
Π
0
Π
0
(F)
для формул над базисом Б∪Б
0
. Отсюда следует, в частности,
что в результате указанного структурного моделирования
обеих частей тождества t, являющихся формулами из U
Φ
Б
,
получается тождество t
0
для формул из U
Φ
Б
0
, которое мы
будем обозначать через Π
0
(t). Множество формул вида
Π
0
(F), где F ∈ F ⊆ U
Φ
Б
, будем обозначать через Π
0
(F), а
множество тождеств вида Π
0
(t), где t ∈ τ — тождество над
U
Φ
Б
, — через Π
0
(τ).
Рассмотрим теперь вопр осы моделирования ЭП формул
в базисе Б с помощью ЭП формул базиса Б
0
. Пусть Φ
0
=
(Φ
0
1
, . . . , Φ
0
b
) — система формул перехода от базиса Б к
базису Б
0
, а Π
0
= (Π
0
1
, . . . , Π
0
b
) — система тождеств перехода,
связанная с Φ
0
. Заметим, что любое ЭП для формул из U
Φ
Б
,
имеющее вид
F ⇒
τ
b
F, (2.3)
может быт ь «промоделировано» с помощью ЭП для формул
из U
Φ
Б
0
вида
F
0
⇒
τ
0
b
F
0
, (2.4)
где F
0
= Π
0
(F),
b
F
0
= Π
0
(
b
F) и τ
0
= Π
0
(τ). Действительно,
пусть ЭП (2.3) является однократным ЭП на основе
тождества t, t ∈ τ, которое имеет вид
t : A (x
1
, . . . , x
q
) = B (x
1
, . . . , x
q
) ,
§2. Эквивалентные преобразования формул 79
и пусть формула
b
F пол учается в результате замены
подформулы A (F
1
, . . . , F
q
) формулы F формулой
B (F
1
, . . . , F
q
). Тогда тождество t
0
= Π
0
(t) имеет вид
t
0
: A
0
(x
1
, . . . , x
1
) = B (x
1
, . . . , x
q
) ,
где A
0
= Π
0
(A) и B
0
= Π
0
(B), а формула
b
F
0
может
быть получен а из формулы F
0
в результате замены ее
подформулы A
0
F
0
1
, . . . , F
0
q
, где F
0
j
= Π
0
(F
j
) для всех
j, j ∈ [1, q], формулой B
0
F
0
1
, . . . , F
0
q
. Моделирование
кратного ЭП вида (2.3) с помощью кратного ЭП вида (2.4)
осуществляется путем последовательного моделирования
однократных ЭП, составляющих ЭП (2.3).
Описанное выше моделир ован ие позволяет выполнять
ЭП для тех эквивалентных формул из U
Φ
Б
0
, которые
принадлежат множеству Π
0
U
Φ
Б
, то есть являются
«моделями» формул из U
Φ
Б
, н а основе системы тождеств
Π
0
(τ), являющихся «моделями» тождеств из τ. Для того
чтобы проводить ЭП для произвольных формул из U
Φ
Б
0
с
использованием системы тождеств Π
0
(τ), выберем какую-
либо систему фор мул перехода Φ = (Φ
1
, . . . , Φ
b
0
) от базиса
Б
0
к базису Б и рассмотрим связанную с ней систему
тождеств переход а Π = (Π
1
, . . . , Π
b
0
). Пусть
ˇ
Π — система
тождеств вида
ˇ
Π = Π
0
(Π) для ЭП формул из U
Φ
Б
0
, которая
получается в результате структурного моделирования
правых частей тожд еств из Π на основе системы тождеств
Π
0
. Для произвольной формулы F
0
, F
0
∈ U
Φ
Б
0
, положим
ˇ
Π
F
0
= Π
0
(Π (F))
и заметим, что
F
0
⇒
ˇ
Π
ˇ
F
0
=
ˇ
Π
F
0
,
ˇ
F
0
∈ Π
0
U
Φ
Б
.
В силу сказанного выше, отсюда вытекает справедливость
следующего утверждения.
80 Глава 3. Эквивалентные п реоб разова ния
Теорема 2.2 (теорема перехода). Пусть τ — КПСТ для
ЭП формул из U
Φ
Б
, а Π
0
и Π — системы тождеств для
перехода от базиса Б к базису Б
0
и от баз иса Б
0
к базису Б
соответственно. Тогда система тождеств {Π
0
(τ) , Π
0
(Π)}
является КПСТ для ЭП формул из U
Φ
Б
.
Следствие. Из системы тождеств τ
осн
для ЭП формул
из U
Φ
(см. § 2) указанным в теореме способом можно
получить КПСТ для ЭП формул в любом базисе Б.
§3 Эквивалентные преобразования контактных
схем. Основные тождества, вывод
вспомогательных и обобщенных тождеств
Рассмотрим вопросы ЭП для КС из U
K
с неразделенными
(бесповторными) полюсами. В соответствии с §1, ?? главы 2
эквивалентность КС Σ
0
= Σ
0
(x
1
, . . . , x
n
; a
1
, . . . , a
m
) и
Σ
00
= Σ
00
(x
1
, . . . , x
n
; a
1
, . . . , a
m
) означает, что для любых
i и j из отрезка [1, m] ФАЛ проводимости от a
i
к a
j
в
КС Σ
0
равна ФАЛ пров одимости от a
i
к a
j
в КС Σ
00
.
На рис. 3.1a–3.1e и 3.1f приведены пары эквивалентных
КС, образующие тождества t
1
–t
5
и t
(m)
6
, m = 1, 2, . . .,
соответственно, которые мы будем называть основными
тождествами для ЭП КС.
Определим подстановку для КС как переименование (с
возможным отождествлением и инвертированием) БП, а
также переименование (с возможным отождествлением
и снятием) полюсов. Заметим, что применяя одну
и ту же подстановку к двум эквивалентным КС,
мы получим эквивалентные КС. Действительно, для
переименования БП и переименования без отождествления
полюсов это очевидно, а в случае отождествления
полюсов эквивалентность получаемых КС вытекает
из того, что матрица достижимости КС, являющейся