Фотиади Э.Э. (ред.) Геология и математика
Подождите немного. Документ загружается.
во
r
лава
11.
.классификации
Оп
р
е
Д
е
л
е
н и
е
1.
Пусть
F
и)
-
формула,
имеющал
дизъюнктивный
нормальный
вид
ри)
=PIV
P
2V
... V
P
k.
Опе
рацией
вычеркивания
ар
гу
мента
X~;
в
формуле
F (f)
будем
нааывать
преобразование
формулы
F
и)
в
формулу
F
ч
(f) =
=
P~VP~
V
...
V
P~,
где
элементарные
конъюнкции
P~,
i =
= 1,2, ... ,
k,
получаются
из
элементарных
конъюнкций
Р
;
пу-
тем
вычеркивания
аргумента
X~
i
.
Очевидно,
функция
'Ф,
задава
ем
ая
формулой
F xt
и),
зависит
от
аргументов
X
1
,
Х2,
•••
,
Xi-l,
Xi+l,.·.,
Х
т
•
Л
е
м
м
а
1.
Если
формулы
P(f)
и
р2
и)
имеют
диз'Ьюn,,
тивnый
nорма
лъ
nый
вид
и
задают
одnу
и
ту
же
бу
ле
ву
фуn"цию
,
f
(X
1
,
Х2,···'
Х
т
),
то
фор"'tулы
p~
;
и)
и
F;i
(f)
задают
одnу
и
ту
же
бул
е
ву
фуn"цию
'Ф
(X
1
,
Х2,
•
••
, X
i-
l,
Xi+l,
.
•.
,
Х
т
).
Д
О
К
а
з
а
т
е
л
ь
с
т в
о.
В
формулах
Ри)
и
Р
2
и)
сгруп
пируем
элементарные
конъюнкции,
содержащие
Xi,
а
также
'
~
и
не
содержащие
данный
аргумент.
В
результате
вынесения
за
скобки
аргумента
X~;
формулы
Ри)
и
F2(f)
примут
вид:
Fl
и)
=
x
,
t~
V
Xi
t;
V
t
~,
F2
и)
=
x;/~
V
x,
t;
V
t;.
(2.4.1}
(2.4.2)
Умножим
каждое
из
выражений
t;
и
f;
на
выражение
(Xi
VX
;),
тогда
формулы
(2.4.1)
и
(2.4.2)
примут
вид:
Fl
и)
=
Х
;
(I~
V t;) V
Xi
(1; V t;),
F2
(1)
=
Х
;
(I~
V
t~)
V
Xi
(1; V t;
).
(2.4.3)
(2.4.4}
Формулы
P(f)
и
р
2
т
по
условию
задают
одну
и
ту
же
булеву
функцию
t.
Сл
ед
овательно,
из
формул
(2.4.3)
и
(2.4.4)
следуют
равенства:
t~
V
t~
=
t~
V
t;,
t;
V
t;
=
t;
V
t;.
(2.4.5).
(2.4.6)
в
результате
логич
е
ского
сложения
левых
и
правых
ча
стей
равенств
(2.4.5) (2.4.6)
получим
новое
равенство
(2.4.7)
Левая
часть
равенства
(2.4.7)
есть
результат
операции
вычер
кивания
аргумента
X~;
в
формуле
рl
и),
т
.
е.
формула
F~
(f)~
правая
часть
равенства
(2.4.7)
есть
формула
Р;;
и).
'§
4.
](
рtшеnulO
осnо
в
l{ЫХ
задач
61
л
е
м
м
а
2.
Операции
вычер,"иван,ия
ар
г
умен,mов
X?i
и
xjj
ц,з
формулы
F (f)
,"оммуmаmи8н,ы
,
m.
е
.
F
х.х.
(f)
= F
х
·х.
(f).
t , , t
д
о
к
а
з
а т
е
л
ь
с т
в
о.
Представим
формулу
F (f)
в
виде
•
Тогда
Из
леммы
1
следует,
что
применение
операции
вычерки
вания
аргумента
X~;
к
любой
из
ДНФ,
задающей
булеву
функ
цию
/,
дает
в
результате
ДНФ
Fxi(f) ,
задающую
одну
и
ту
же
булеву
функцию
'Ф.
Функцию
'Ф
будем
обозначать
через
'Ф
=
=/Xi(X
1
,
Х2,
•.•
,
Х
т
).
Из
лемм
1
и
2
следует,
что
применение
операции
вычерки-
вания
совокупности
аргументов
{X~
i
"
X~.
i
.
,
•••
, x
Oik
}
К
любой
k
функции
/
дает
в
результате
ДНФ
F x
i,
x
i,
..
. Xi
k
(f),
задаю-
щую
одну
и
ту
же
булеву
функцию
'Ф,
причем
результат
не
за
висит
от
последовательности
вычеркивания.
Аналогично
пр
е
.
дыдущему
введем
обозначение
'Ф
=
/Х
.
х.
'" xi"
(Х
1
,
Х2,.
••
,
Х
т
).
1.
1.2
4.
Обратимся
к
постановке
логической
задачи.
Задано
множество
булевых
функций
:
/1,
/2,
...
,/N,
.
зависящих
от
аргум
е
нтов
Х
1
,
Х2'
••• '
Х
т
•
Все
функции
попарно
ортогональны
/i
&
/
З
=
О,
i,
j = 1,2, ... ,
N;
i
=1=
j.
В
{
О' О
'
Oi ,,}
ычеркивание
совокупности
аргум
е
нтов
Xi,t"
Х
.
" ,
•••
,
Х
.
"
'"
в
функциях
/i
будем
называть
допустимым
вычеркиванием,
.
если
функции
.1,1
-
/1
.
.h
'l
_
/2
. .
."N
_
/N
't'
- x
itxi
," 'x
i k
,
't' - x
i.tXi"
"x
ik'
...
''''
-
xi
..
xiz
",x
ik
попарно
ортогональны.
В
нротивном
случае
вычеркивание
бу
дем
называть
недопустимым.
Требуется
найти
все
совокупности
Х
;
= {Xl'
Х
2
,
•••
,
Х
т
}
'"
{X
i" X
i"
•••
, Xi,,}
ос
соблюдением
следующих
условий:
62
Глава
11.
Классuфu1tаЦUrt
(1)
вычеркивание
совокупности
аргум
е
нтов
''',
X
ai k
}
допустимо.
',.
(2)
если
XCX
j
,
то
выч
е
ркивание
множества
аргум
е
нтов:
{х
1
,
Х2,
.••
,
х
т
}""Х
недопустимо.
5.
Вначале
решим
логическую
.
задачу
для
N =
2.
Пусть
функции
р
и
12
заданы
в
виде
ДНФ
формулами:
F
(р)
=
Р
1
V
Р
2
V
...
V P
k
"
Р(Р)
=
P~
V
P; V
···
v
P
~,
.
Рассмотрим
две
элементарны
е
конъюнкции
О
н)'
,
Х
•
и"
,
(2.4.8»
(2.4.9)
Выделим
все
аргументы
Xj " Xj "
.••
, X
j,
.,
каждый
из
которых
вхо
дит
в
одну
из
конъюнкций
Р,
Р*
б
е
з
отрицания
(а
= 1),
а
в
дру
гую
-
под
знаком
отрицания
(а
=
О)
.
Из
выдел
е
нных
аргу
ментов
образуем
элементарную
дизъюнкцию
С
= Xj , V
Xj
,
\;
'
•.•
V
Xj
,.,
Описанную
выше
операцию
формирования
элем
е
нтарной
дизъюнкции
С
из
двух
элем
е
нтарных
конъюнкций
Р
и
Р*
бу
дем
называть
операцией
W
и
обозначать
с
= W (P,
Р
*
).
Если
в
конъюнкциях
Р
и
Р*
нет
ар
г
ументов,
входящих
в
одну
'
из
них
без
отрицания
(а
= 1),
а в
д
ругую
-
под
знаком
отри
цания
(а
=
О),
т.
е.
конъюнкции
Р
и
Р*
н
е
ортогональны,
то
по-
ложим
W(P,
Р
* )
= 1.
Применим
операцию
W(P
i
,
Р
;
),
i = 1,2,
..
. , k
1
,j
= 1,2, .
..
, k2,
ко
всем
возможным
парам
элементарных
конъюнкций
и30
формул
(2.4.8)
и
(2.4.9).
Из
полученных
элементарных
дизъюнк
ций
образуем
RНФ
некоторой
функции
М
(11,
12
),
которую
бу
дем
называть
минимизирующеЙ.
Ниже
будет доказано,
что
·
функция
М
(Р,
р)
зависит
только
от
функций
jl
и
12
И
не
зави
сит
от
выбора
ДНФ
дЛЯ
функций
11
И
12.
Минимизирующая
функция
зада
е
тся
формулой
F
(М
(jl,
р))
=
с
1&C
2
& ...
&C
k
,k
••
§ 4. [{
р
е
ш
ени
ю
о с
но
в
ных
аадач
63
Очевидно,
что
минимизирующая
функция
принадл
е
жит
классу
монотонных
функций.
Л
е
м м
а
3.
J
Vlиии~tuаиРУlOщая
фующия
'
ие
зави
с
ит
о
т
в
ыбора
ДНФ
д
л
я
фующий
j1
и
р
.
Д
о
к
а
з
а т
е
л
ь
с т
в
о.
Пр
е
дставим
булевы
функции
f
(Х
1
,
Х2,""
Х
т
)
и
12
(Х
1
,
Х
2
,
•.•
,
Х",)
в
СДНф
F
(р)
= P
1
V
Р
2
V
...
V
P"j'
F
(р)
=
P~
V
Р;
V
...
V
P
~,
(2.4.10)'
(2.4.11)
и
построим
для
НИХ
минимизирующую
функцию
М
и1,
12).
в
ре
зультате
получим
формулу
(2.4.12)
Пусть
формулы
(2.4.10)
и
(2.4.11)
имеют
эквивал-ентны
е
ДНФ
·
F'
(р)
=
P~
V
Р;
V
...
V
P~"
F"
(р)
=
P~
V
Р
;
V ... V
P~
'''
.
(2.4.13)·
(2.4.14)
Построенная
для
них
минимизирующая
функция
М'
(fl,
()
.
имеет
вид
F
(М'
иl,
12» =
c~
&
c~
&
...
&
c~,
"'"
1 2
(2.4.15),
Очевидно,
что
число
k~k;
из
(2.4.14)
не
более
числа
k
1
k
2
из
(2.4.12).
Рассмотрим
i-й
конъюнктивный
чл
е
н
формулы
(2.4.15)
с:
=
Xj,
\/
Х
з
,
V .. . V X
j,
.. , i =
1,
2' .
...
'
k~k;.(2.4.16
)
,
. t
Формула
(2.4.16)
есть
результат
операции
W
(Р:,
Р
;
)
над
двумя
дизъюнктивными
нормальными
членами
P~
и
Р
;
из
·
фор
мул
(2.4.13»
и
(2.4.14).
:Конъюнкция
Р:
(Р
;
)
из
формулы
(2.4.13)'
(соответственно
(2.4.14»
эквивалентна
некоторой
части
формулы
(2.4.10)
(соот
ветственно
(2.4.11»
Р:
= Pi , V Pi , V
...
V
P;
v
'"
Р
;
= P
J
,
V P
J
,
\/
.
..
V P;v
'"
(2.4.17),
(2.4.18),
Произведем
операцию
W
(Р
и
,
Рд,
и
= i
1
.,
i
2
,
•••
, i
v
,;
t =
.=
jl,
j2'
...
, j
v"
,
над
всеми
возможными
парами
из
формул
(2
.4.
17~
Глава
11.
КлассuфU1>ацuu
и
(2.4.18).
В
результате
получим
часть
конъюнктивных
членов
формулы
(2.4.12).
Среди
них
всегда
найдется
дизъюнкция,
сов
падающая
с
формулой
(2.4.18),
так
как
имеют
место
равенства
(2.4.17)
и
(2.4.18).
Следовательно,
любой
конъюнктивный
член
формулы
(2.4.15)
всегда
встречается
в
формуле
(2.4.12).
Теперь
рассмотрим
i-й
конъюнктивный
член
формулы
(2.4.12)
C
i
=
Xj.
V X
j,
V
...
V X
jr"
i = 1, 2,
..
. , k
1
,
k
2
(2.4.19)
\
Формула
(2.4.19)
есть
результат
операции
W (P
i
,
P
j
)
над
дву
мя
дизъюнктивными
нормальными
членами
'P
i
и
Р
;
из
формул
(2.4.10)
и
(2.4.11).
Ранги
данных
КОНЪЮНIщий
равны
т.
Выберем
из
формулы
(2
.4.13)
конъюнкцию
P~,
поглощаю
щую
элементарную
конъюнкцию
P
i
из
формулы
(2.4.10),
а
из
формулы
(2.4.14)
элементарную
конъюнкцию
Р;,
поглощающую
элементарную
конъюнкцию
Р
;
из
формулы
(2.4.11).
Применим
к
конъюнкциям
P
~
и
Р;
операцию
W
(P~,
Р;).
В
результате
получим
дизъюнкцию
C~
=
Х
з
•
V
Х
з
,
V
...
V X
Sr
•
(2.4.20)
Любой
из
аргументов,
встречающи
йся
в
формуле
(2.4.20),
встре
чается
и
в
формуле
(2.4.19).
Поэтому
r < r j,
и
дизъюнкция
C
i
(2.4.19)
либо
совпадает
с
дизъюнкцией
C~
(2.4.20),
когда
r =
ri,
либо
поглощает
ее,
когда
r < ri'
"Поглощая
дизъюнкцию
C~
(2.4.20),
дизъюнкция
С
!
(2.4.19)
поглощает
и
функцию
М
(fl, /2),
записанную
формулой
(2.4.12),
так
как
C
i
-
конъюнктивный
нормальный
член
в
формуле
(2.4.12).
Выберем
все
конъюнктивные
члены
формулы
(2.4.12),
ко
торые
не
совпадают
с
членами
формулы
(2.4.15)
и,
по
доказан
ному,
поглощают
функцию
М'
и1,
/2).
в
силу
последнего
утверждения
функцию
М'
(р,
f)
мож
во
логически
умножить
на
все
поглощающие
функции,
соответ
ствующие
выбранным
конъюнктивным
членам.
Функция
от
этого
не
изменится,
зато
формула
(2.4.15)
обратится
в
формулу
(2.4.12).
Т
е
о
р
е
м
а
1.
Пусть
задаnы
две
ортогоnальnые
фующuu
f
(Х
1
,
Х2,''''
Х
т
)
и
/2
(Х
1
,
Х2,""
х
т
).
Фующuu
-фl
=
/~;
(Х
1
,
Х2,
...
...
,
Х
т
)
u\jJ2=/;i(X
1
'
Ха,
...
,
Х
т
),
1 < i <
т,
будут
ортогоnалъnы
mО2да
u
только
тогда,
1f,огда
м,unuм,uauрующая
фующuя
М
(fl,
§
4.
К
решению
основных
вадач
6б
/2)
не
обращается
в
тождественный
нуль
при
Х;
=
О:
М
(р,
f2)
\
х.
=о
$
О.
t
(2.4.21)
д
о
к
а
3
а
т
е
л
ь
с
т в
о.
Необходимость.
Пусть
функции
'1'1
И
'1'2
ортогональны.
Предположим,
что
М
(1\
f)
=
О
при
Х
;
=
О.
Ввиду
того,
что
RНФ,
не
содержащая
аргументов
под
знаком
отрицания,
тождественно
равна
нулю
тогда
и
только
тоГДа,
когда
среди
ее
конъюнктивных
членов
найдется
тожде
ственный
нуль,
получим,
что
RНФ
(2.4.22)
минимизирующей
функции
М
(р,
f)
содержит
член
вида
(2.4.23)
Элементарная
дизъюнкция
С
;
(2.4.23)
ес
ть р
езул
ьтат
приме
нения
операции
W
(Р,
Р*),
гд
е
Р
-
один
из
членов
ДНФ
F
(Р),
Р*
-
один
из
членов
ДНФ
F
(р).
Отсюда
(2.4.24)
Следовательно,
функции
'1'1
и
'1'
2
неортогональны.
Получ
ен
ное
противоречие
показывает,
что
условие
(2.4.21)
выпол
няется.
Достаточность.
Пуст
'
ь
условие
(2.4.21)
соблюдается
.
Тог
да
RНФ
(2.4.22)
не
содержит
конъюнктивного
члена
С
;
вида
(2.4.23).
Поэтому
для
любой
пары
конъюнкций
Р
и
Р*
условие
(2.4.24)
не
выполняется.
Следовательно,
функции
'1'1
и
'1'2
орто
гональны.
С
л
е
Д
с
т в
и
е.
Пусть
заданы
ортогональные
функции
fl
(X
1
,
Х2,
'
'''
Х
т
)
И
/2
(Х
1
,
Х2,"
"
Х
т
).
Функции
'l'1=/~
i
,ч
,,"
Х
i
k
(Х
1
,
Х2"",
Х
т
)
и
'1'
2 =
/fч,ч
.
...
х
".
(X
1
,
Х
2
"",
Х
т
),
Xi"
Xi21
...
•• • ,
Xi/(E{X
1
,
Х2,""
х
т
}
,
будут
ортогональны
тогда
и
только
тогда,
когда
минимизирующая
функция
М
(Р,
f)
не
обращается
в
тождественный
нуль
при
Xi , =
Xi.
= ... =
Xi/(
=
О:
М
(р,
f2
)/x
i
t
=
Xi
, =
..
. =
Х
;
,.
$0.
Т
е
о
р
е
м
а
2.
Пусть
заданы
две
орто
г
ональные
функ,ции
fl
(Хl'
Х2'
•••
,
Х
т
)
И
f2
(Xl'
Х2'
••
• ,
Х
т
).
Построим
ДНФ
минимизирующей
Функ,ции
М
(р,
f)
F
(М
(11,
f2»
=
Рl
V
Р?
V
...
v
Р/,
(2.4.25)
5
ГеОЛОГl1R
и м
ате
матик
а
66
Глава
11.
Классuфu"ацuu
которая
н,е
содержит
nо
г
лощаемых
член,ов
и
н,е
содержит
аргу
J.teumoe
под
зн,аК О
J.t
отрицан,ия.
R
аждый
из
ч
л
ен,ов
фОРJ.tУ
Л
Ы
(2.4.25)
будет
состоятъ
из
совокуnн,ости
ар
г
умен,тов
X
j
=
{X
s
.,
Х.,
, ...
. . . ,
х
,
),
удовлетворяющей
условиям
ло
г
ической
задачи.
Дру
г
их
совокуnн,остей,
решающих
ло
г
иче
с
кую
задачу,
н,е
существует.
Д
о
к
а
з
а
т
е
л
ь
с
т в
о.
Пусть
совокупность
аргумен-
тов
X
j
= {x
s
"
Х
."
...
,
Х
г
)
удовлетворяет
условиям
логической
задачи.
Применим
операцию
вычеркивания
совокупности
ар
гументов
{X
i
.,
X
i"
...
,
Xi
k
} =
{Х
1
,
Х2,
...
,
xm}"X
j
к
функциям
/1
И
/2.
С
огласно
следствию
из
теоремы
1,
минимизирующая
функция
М
(/1,
/2)
не
обращается
в
тождественный
нуль
при
Xi,
= X
i,
= ... =
Xi"
=
О.
Построим
ДНФ
функции
М
(/1,
f)
без
поглощаемых
членов
(2.4.26)
При
Xi, =
Xi,
=
..
, =
х
;
к
=
О
формула
(2
.4.26)
будет
иметь
вид
F
(М
(11,
р»
= P
t
,
V P
t
,
V
...
V P
tu
=1=
о,
t
u
<, k
1
.
(2.4
.27)
Формула
(2.4.27)
содержит
только
аргументы
Х
8
"
Х."
...
,
Х
•
•
,. j
Если
из
функций
j1
и
r
дополнительно
вычеркнуть
аргумент
X~ik+l
X~ik+1
Е
{Xi
. ,
Xi
"
...
, Xi".},
то
функция
М
(/\
/2)
обратится
'/(
+
1'
'К
+
1
"
В
тожд
е
ственный
нуль
при
Xi, =
Xi
, = ... =
ХikЧ
=
О
(соглас-
но
следствию
из
теоремы
1),
т. е.
все
конъюнкции
P
ti
,
i=1,
2,
...
...
,и,
содержат
аргумент
Xik
+
1'
Следовательно,
все
дизъюнкти
вн
ые
члены
формулы
(2.4.27)
равны
между
собой:
Итак,
для
любой
совокупности
аргументов
{X
s1
,
Х."
..
, X
Srj
} ,
удовлетворяющей
условиям
логической
задачи,
среди
непогло
щенных
членов
ДНФ
функции
М
(/I,
/2),
не
содержащей
аргу
ментов под
знаком
отрицания,
найдется
дизъюнктивный
член
P
r
,
1 <, t < k
1
,
с
оставленный
и
з
аргументов
данной
сuвокуп
ности.
§ 4. R
решению
осногных
аадач
67
Рассмотрим
формулу
(2.4.25).
ДОI<ажем,
что
СОВОI<УПНОСТЬ
аргументов
{Х
Б
"
Х
Б
"
•••
,
Х.},
составляющая
ДИЗЪЮНI<ТИВНЫЙ
"l
член
(2.4.2
8)
формулы
(2.4.25),
удовлетворяет
условиям
логичеСI{ОЙ
задачи.
При
Xi,
= X
i,
=
'"
= X
ik
=
О,
{Xi
" Xi"
.•
. ,
Xi
k} =
{Хl'
Х2,
•••
•••
,
Хт}"-{Х
Б
"
Х
Б
"
•••
, X
S
rt
}
формула
(2.4.25)
примет
вид
(2.4.29)
ввиду
свойств
формулы
(2.4.25).
Фующия,
задаваемая
форму
лой
(2.4.29),
не
равна
тождественно
нулю.
Если
в
формуле
F
(М
(Р,
/2»
дополнительно
приравнять
нулю
аргумент
Xi,
Х;
$.
{X
i"
Xi"
..•
, X
ik
}'
то
фУНI<ЦИЯ
М
(11,
р)
обратится
в
тожде
ственный
нуль.
Предыдущие
рассуждения
ПОI<азывают,
что
СОВОI<УПНОСТЬ
аргументов
{Х
Б
"
X
s
"
•••
, X
Sr
l
},
составляющих
непоглощенную
I<ОНЪЮНI<ЦИЮ
P
t
(2.4.29),
удовлетворяет
условиям
логичеСI<ОЙ
задачи.
Теорема
2
дает
решение
основной
задачи
для
N = 2.
6.
Перейдем
I<
решению
задачи
для
N >
2.
Пусть
задан
I<ортеж
попарно
ортогональных
фУНI<ЦИЙ
[84]
(2.4.30)
зависящих
от
аргументов
X
1
,
Х
2
,
""
Х
т
.
Образуем
из
фУНI<ЦИЙ
(2.4.30) N - 1
пар
фУНI<ЦИЙ
следующим
образом:
/1
и
<pt
=
j2
v
/3
V
...
V
fN,
)
f.2
~.
<р.
2
.•
j3.
~
:4
:'
...
:
'!
/~'
fN-1
и
<pN-1
=
fN,
(2.4.31)
Фующии
fi
и
'ljJi,
i = 1,2, ... , N -
1,
ортогональны.
I\ОНЪЮНI<ЦИЮ
минимизирующих
фУНI<ЦИЙ
М
(11,
<р1),
М
(12,
<р2),
.••
,
М
(fN-1,
<pN-l)
будем
называть
минимизирующей
фУНI<цией
для
I<ортежа
ФУНI<
ций
(2.4.30)
и
обозначать
через
М
(1\
f2,
...
, /N).
М
(р,
/\
.•.
,/N)
=
М
и1,
<pl)
&
М
(12,
<pl)
&
...
&
М
(fN-t,
<p
N-l
).
(2.4.:32)
'5.
.J
68
Г
...
ава
11. R
...
ассuфU1Оацuu
3
а
м
е
ч
а
н и
е.
Ввиду
того,
что
при
построении
функции
М
(/1, /2,
...
,
/N)
каждая
элементарная
конъюнкция
Р; из
ДНФ
F
(/),
i = 1, 2, ...
,N,
участвует
в
операции
W (P
j
,
Р;)
со
всеми
влементарными
конъюнкциями
Р;
из
ДНФ
F
(Р),
F
(f),
...
. •• , F
(/-),
F (/+1),
...
, F (fN),
минимизирующая
функция
М(/l,
r,
...
,
/N)
зависит
только
от
функций
/\
f,
... ,
fN
и
не
зависит
от
их
перенумерации.
т
е
о
р
е
м
а
3.
Пусть
ааданы
попарно
ортогональн,ы,е
фующuu
/1
(Х1
,
Х2
,
•••
,
Х
т
).
/2
(Хl,
Xz,
•••
,
Х
т
),
•••
,
fN
(Хl'
Xz,
•••
,Х
т
).
Фующuu
'Ф
1
=
/~.,
(Х
1
,
Xz,
...
,
Х
m
),
'ФZ
=
/;
1
(Х1'
Xz,
...
,
х
т
),
...
.
...
'ФN=/:'
(Хl'
X z ,
...
,
Х
т
),
1< i<
m,
будут
попарно
ортогональ-
\
1m
то
гд
а и
то
льYi,О
тогда,
по
г
да
"'tuнu,м,uаuрующая
фунYi,ЦUЯ
М(Р,
f,
...
,
/N)
не
обращается
в
тождественный
нуль
при
Xi=
О:
(2.4.33)
д
о
к
а
з
а
т
е
л
ь
с т в
о.
Образуем
из
функций
jl,
р,
...
...
,/Nмножество пар
(2.4.31)
и
построим
минимизирующую
функ-
цию
М (/1, /2, ... , /N) (2.4.32).
Функции
/~
!
и
<P
~i
'
i = 1. 2 ,
...
.•. , N -
1,
согласно
теореме
1,
ортогональны.
Отсюда
следует
справедливость
теоремы
3. . .
с
л
е
Д
с
т в
и
е.
Пусть
заданы
попарно
ортогональные
функции
jl
(Хl'
Х
2
,
•••
,
Х
т
).
/2
(
Хl
'
Х2,
•
••
,
х
т
)
•
•••
,
fN
(
Х
1'
Х2'
•••
,
Х
т
)
Функции
'Ф
1
= k
Х·
'''Х·
(Х
1
,
Х
2
'
•••
,
Х
m
),
'Ф
1
=
'1.
L2
1к
=
t;
.
х
.
...
х'
(Х
1
,
X
Z
'
4'"
Х
m
),
·
•••
,
'Ф
N
=
/~,X
i2"
·
Xi
...
(Х
1
,
х
2
,,,
.,
Х
m
),
11
12
tk
1\
Xi"X
i ••
•••
, X ik
Е{Х
1
,
Х
2
"'"
х
т
},
будут
попарно
ортогональны
тогда
и
только
тогда,
когда
минимизирующая
функция
М
(Р,
r,
...
jN)
не
обращается
в
тож
дес
твенный
нуль
при
Xi,
= X
i,
=
=
...
=
Xik
=
О:
М
(/1,
/2
••••
,
fN)
I
Хi,=Жi'=
.
"
=Хi,,=О
$0.
(2.4.34)
Т
'
е
·
о
,
р
е
м
а
4.
Пусть
заданы
попарно
орmогонмьн,ые
rfiуn1ЩUU
§ 4. R
реше/-/'ию
ос/-/'ов/-/'ых
гада"
69
Построим
ДНФ
минимизирующей
фУn1щии
М
(/1, 1
2,
... ,
IN)
F
(М
(11, /2,
..•
,
fN»
=
Р
1
V
Р
2
V
...
V
Р/,
(2.4.35)
"оторая
не
содержит
nоглощаемых
чл
ен
ов
и
не
содержит
аргу
ментов
под
знаком
отрицания.
Каж
ды
й
член
формулы
(2.4.35)
Р
;
=
Хз,Х
з
••
••
X
8r
., j = 1, 2, .
..
,
[,
/'; <
т,
J
будет
состоять
и
з
со
в
окупности
аргументов
Х
;
=
{Х
а"
Ха
.
,
...
...
, x
sr
},
удовл
е
т
во
ряющей
условиям
логической
задачи.
Других
J
совокупностей,
решающих
основную
задачу,
не
существует.
Доказательство
теоремы
4
аналогично
доказательству
теоремы
2
(при
этом
необходимо
использовать
следствие
из
тео
ремы
3).
Теперь
дадим
алгоритм
решения
основной
задачи
для
по
парно
ортогональных
функций
р,
12, ... ,
IN.
ОН
состоит из
сле
дующих
пунктов:
а)
построение
:КНФ
минимизирующей
функции
М
(/1, 12,
...
. . . , IN), N > 2,
Ь)
преобразование
:КНФ
монотонно
й
функции
М
(/1, 12,
...
... ,/N)
посредством
раскрытия
скобок
в
ДНФ,
с
последующим
удалением
поглощаемых
членов.
Построенная
таким
образом
ДНФ
будет
удовлетворять
условиям
теоремы
4.
:Каждый
дизъюнктивный
член
получен
ной
ДНФ
будет
состоять
из
аргументов
иском
о
й
совокупности
аргументов
{Х
в
"
Х
в
.
,.
..
,
Х
з
}.
Заметим,
что
прежде
чем
приступить
~r
К
осуществлению
пункта
а),
функции
р,
1
2,
... ,
IN
могут
быть
приведены
к
МДНФ,
так
как
минимизирующая
функция
М
(/1, 1
2,
... ,
IN)
не
зависит
от
выбора
ДНФ
дЛЯ
функций
Р,
12, ...
...
,fn
(лемма
3).
7.
Рассмотрим
операцию
раскрытия
скобок
в
монотонной
:КНФ
.
Пусть
задана
:КНФ
монотонной
функции
1
(Х
1
,
Х
2"'"
Х
т
)
F
(1)
=
С
1 &
С
2 &
...
&
С
'"
где
С
;
= Xi;V
Xt
,V
...
V X;
rj;
j = 1, 2,
...
, k,
rj
<
т.
Требуется
построить
ДНФ
функции
1
F (1) .
Р
1
V
Р
2
V
.•.
V
Р;,
(2.4.36)
(2.4.37)
где
Р;=
Х
З
,
Xs,,,,X
sr
. , j =
1,2,
... ,
1,
rj
<
т,
удовлетворяющую
J
следующим
свойствам:
формула
(2.4.37)
не
содержит
погло-
щаемых
членов
и
не
содержит
аргументов
под знаком
отри
цания.