Ответы на вопросы к экзамену 2011
.pdf
C00 Cn0 Cnn 1
Cn1 n
Cnk Cnn k
Ck Cr Cr Ck r , где |
0 r k n |
n k n n r |
|
Доказательство.
Ck Cr |
n! |
|
k! |
|
n! |
||
|
|
|
|
|
|||
n k |
(n k)!k! |
|
(k r)!r! |
|
(n k)!(k r)!r! |
||
|
|
|
|||||
Cr Ck r |
|
|
n! |
|
|
|
|
|
|
(n r)! |
|
|
|
n! |
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
n |
|
n r |
(n |
r)!r! |
|
(n r |
k r)!(k r)! |
|
|
(n k)!(k r)!r! |
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
5. Ck |
|
Ck 1 |
Ck |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
n 1 |
|
n 1 |
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
C k |
C k 1 |
|
|
(n 1)! |
|
|
|
|
(n 1)! |
|
|
|
|
(n 1)! |
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
n 1 |
|
|
n 1 |
|
(n k 1)!k! |
|
|
(n 1 k 1)!(k |
1)! |
(n k 1)!k! |
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
(n 1)!(n k k) |
|
(n 1)!n |
|
n! |
|
C k |
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
(n k)!k! |
|
|
(n k)!k! |
(n k)!k! |
|
n |
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
(n 1)!
(n k)!(k 1)!
Размещениями с повторениями из n элементов по k называются
кортежи длины k , составленные из множества A , где A n . Обозначается Ank Формула Ank nk
Пример. Сколько двухзначных чисел можно составить из элементов
множества A {3,4,5}, если число может состоять из 2-х цифр.
33,34,35,43,44,45,53,54,55.
|
A2 |
|
|
3! |
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|||||
3 |
|
(3 |
2)! |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
A2 |
32 |
9 |
|
|
|
|
|
|
|
|
|||
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Перестановкой |
с повторениями |
состава |
(n1,....,nk ) из элементов |
|||||||||||
(a1,....,ak ) |
|
|
|
|
|
|
|
|
|
|
|
|
||
называют любой кортеж длины n n1 n2 |
... nk , в которых элемент |
|||||||||||||
a1 входит n1 раз, a2 - n2 раза,….., ak - nk раз. |
|
|
||||||||||||
Обозначают P(n1 , n2 ,..., nk ) |
|
|
|
|
|
|||||||||
Формула P(n1 , n2 |
,..., nk ) |
n! |
|
|
(n1 n2 ... nk )! |
|||||||||
n1!n2 !...nk |
|
n1!n2 !...nk ! |
|
|||||||||||
|
|
|
|
|
|
|
|
|
! |
|||||
Пример.
Сколько слов можно получить, переставив буквы в слове «математика»?
30
Составим комплект |
~ |
A {а, а, а, е, и, к, м, м, т, т} .Его функция экз-ти |
~ [311122] . Значит, при перестановке букв получится:
A
P(3,1,1,1,2,2) |
(3 1 1 1 2 2) |
|
10! |
|
151200 слов. |
|
|
|
|||
3!1!1!1!2!2! |
|
3!1!1!1!2!2! |
|
||
Сочетания с повторениями. |
Пусть имеются предметы n видов и из них |
||||
составляется набор, содержащий k |
элементов, т.е. различными исходами будут |
||||
все возможные наборы длины |
k , |
отличающиеся составом, и при этом |
|||
отдельные наборы могут содержать повторяющиеся элементы. Такие наборы называются сочетаниями с повторениями и их число равно:
|
C k |
C k |
|
|
|
|
|
|
|
|
n |
n k 1 |
|
|
|
|
|
|
|
Пример. |
|
|
|
|
|
|
|
||
Сколько наборов из 7 элементов можно составить из элементов |
|||||||||
множества A {1,3,5,7} , |
k 7, n 4 : |
||||||||
|
|
|
C 7 |
10! |
|
|
10 9 8 |
120 . |
|
|
C 7 |
C 7 |
|||||||
|
|
|
|||||||
4 |
4 7 1 |
10 |
7!3! |
|
1 2 3 |
||||
|
|
|
|
|
|||||
Вопрос №34. Биномиальные коэффициенты. Бином Ньютона.
(a b)n Cn0 anb0 Cn1an 1b1 Cn2 an 2b2 ...Cnn 2a2bn 2 Cnn 1a1bn 1 Cnn a0bn ;
Cn0 ,Cn1 ,...,Cnn - биномиальные коэффициенты. Свойства коэффициентов:
Если a b 1, то (1 1)n |
C0 |
C1 |
.... Cn 1 |
Cn 2n |
|||||||
|
|
|
|
|
|
n |
|
n |
|
n |
n |
Если a 1, b 1, |
то C0 |
C1 |
C2 |
C3 |
.... ( 1)n Cn 0 |
||||||
|
|
|
n |
|
n |
|
n |
|
n |
|
n |
Треугольник Паскаля: |
|
|
|
|
|
|
|
||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
|
|
|
|
|
|
|
|
|
1 |
2 |
|
1 |
|
|
|
|
|
|
|
|
1 |
3 |
3 |
|
1 |
|
|
|
|
|
|
1 |
4 |
6 |
|
4 |
|
|
1 |
|
|
|
|
1 |
5 |
10 |
10 |
|
5 |
|
|
1 |
|
|
|
и т.д.
Вопрос №35. Алфавитное кодирование. Таблица кодов.
Кодированием называют отображение произвольного множества А в множество конечных последовательностей в некотором алфавите В, декодирование - обратное отображение.
Теория кодирования представляет собой один из разделов дискретной математики, в котором рассматривается процесс представления информации в
31
определѐнной стандартной форме и обратный процесс восстановления информации по этому представлению.
|
Пример. |
|
1) |
Представление десятичных чисел двоичным кодом |
|
2) |
Уравнение |
кодирует прямую. |
|
Алфавитное |
кодирование – это представление информации в |
стандартной форме, при которой элементарным синтаксическим единицам языка сообщений последовательно сопоставляется кодовые комбинации
символов из некоторого заданного алфавита. |
|
|
|
|
|
|||||
|
Пример. |
|
|
|
|
|
|
|
|
|
|
Азбука Морзе: буквам сопоставляются слова в алфавите из 3-х символов |
|||||||||
{ ,-, } , где |
-пробел . |
|
|
|
|
|
|
|
||
|
Пусть задан алфавит сообщений A {a1 , a2 ,..., an }, состоящий из конечного |
|||||||||
числа |
букв. |
Конечная |
последовательность букв из ai |
ai |
|
....ai |
|
называется |
||
|
|
|
|
|
1 |
|
2 |
|
k |
|
словом |
в алфавите |
A , |
а число k - длиной слова . Если |
k 0 , то слово |
||||||
называется пустым и обозначается |
. |
|
|
|
|
|
||||
|
A* - множество всех непустых слов конечной длины в алфавите A . |
|||||||||
|
Если |
S A* , |
то |
слова из |
S называются сообщениями, |
а объект, |
||||
порождающий слова из |
S - источником сообщений. Источником может быть |
|||||||||
человек, автомат и т.д. |
|
|
|
|
|
|
|
|||
|
Пусть, кроме алфавита A , задан ещѐ алфавит B {b1 , b2 ,..., bm } . Зададим |
|||||||||
отображение f ,которое каждому слову S ставит в соответствие слово B* , где B* - множество всех непустых слов конечной длины в алфавите В.
Слово будем называть кодом сообщения , а процесс перехода от к слову - кодированием.
f : A* B*
Алфавитное кодирование определяется следующим образом. Во
множестве B* выбираются некоторым образом r слов |
, |
,...., |
r |
, |
называемые |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
|
|
|
|
элементарными кодами. |
|
|
|
|
|
|
|
|
|
|
|
|
||||
По определению получаем, |
|
что f (ai ) i ,i 1,2,...r . |
Тогда |
|
код любого |
|||||||||||
слова i i |
.... i |
A* |
есть следующее слово: |
|
|
|
|
|
|
|||||||
1 |
2 |
k |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( ) f ( i |
) f ( i |
2 |
).... f ( i |
k |
) i |
i |
2 |
.... i |
p |
|
|
|
|
|
|
|
|
1 |
|
|
1 |
|
|
|
|
|
|
|
|
||||
Схема, определяющая отображение f на буквах алфавита A , называется схемой кодирования, обозначается и оформляется в виде таблицы:
32
Множество кодовых слов { 1, 2 ,..., r } будем обозначать C( )
Описание задач в примерах. Тип 1. Кодирование.
( ).
Схема алгоритма кодирования обладает свойством префикса, если ни один элементарный код не обладает множеством другого кода.
Пример. ( ) { |
} – не обладает свойством префикса. |
( ) * |
+ – обладает свойством префикса. |
Тип 2. Теория чисел (НОК, НОД). |
|
Первый способ. |
|
, |
, |
|
. |
|
. |
.
Нахождение НОД – выбираем минимальные из степеней.
.
Нахождение НОК – выбираем максимальные из степеней.
.
Второй способ (алгоритм Евклида).
, .
Число над 0 – НОД.
Список теорем для сдачи. Утверждение 5.2.
Для любого допустимого потока в транспортной сети D и любого множества V1 V, где v1 V1, vn V1, выполняется неравенство c( X (V1 )) , т.е. величина любого допустимого потока в сети D (в том числе и максимального) не превышает пропускной способности любого разреза сети (в том числе и минимального).
Доказательство. С учетом того, что все вершины в , за исключением , являются промежуточными, а ( ) , имеем
33
̅ ∑ ( )
( )
∑ ( |
) |
∑ [ ∑ ( ) ∑ ( )] |
|||||
|
( ) |
|
* |
+ |
( |
) |
( ) |
∑ [ |
∑ |
( |
) ∑ |
( |
)] |
|
|
|
( |
) |
|
( ) |
|
|
|
∑ |
∑ |
( ) |
∑ ∑ |
( |
) |
|
|
|
( ) |
|
|
( |
) |
|
|
|
∑ |
( ) |
|
∑ |
|
( ) |
|
*( |
) |
+ |
*( |
) |
+ |
|
|
|
∑ |
( ) |
|
∑ |
|
( ) |
|
*( |
) |
+ |
*( |
) |
+ |
|
|
|
∑ |
|
( ) |
∑ ( ) |
∑ ( ) ( ( )) |
||
*( |
) |
̅ + |
|
( |
) |
|
( ) |
Теорема 5.1 (теорема Форда-Фалкерсона).
Пусть D – транспортная сеть, – допустимый поток в этой сети, V1 – множество вершин v V таких, что длина минимального пути из v в vn в орграфе приращений I(D, ) равна нулю. Тогда, если v1V1, то – максимальный поток,
величина которого равна c( X (V1)) . |
|
|
|
|
|
|
|
|
||||||||
|
Доказательство. Пусть |
̅ |
|
. Тогда (см. доказательство предыдущего |
||||||||||||
утверждения) выполняется равенство |
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
̅ |
|
∑ |
|
( ) |
|
∑ |
|
( ) |
|
|
|
||
|
|
|
|
*( |
) |
|
+ |
|
|
*( |
) |
+ |
|
|
|
|
|
Если |
|
( |
) |
, |
, |
̅ , |
то |
( |
) |
, так как в противном |
|||||
случае, используя доказательство предыдущего утверждения, |
имеем |
( ) |
, |
|||||||||||||
где |
( |
), |
а следовательно, |
в |
силу |
|
|
в |
( |
) |
существует |
путь |
||||
нулевой длины из |
в |
, что противоречит условию |
̅ |
. Но тогда из |
||||||||||||
формулы предыдущего утверждения получаем |
|
|
|
|
|
|
||||||||||
̅ |
|
∑ |
|
( ) |
|
∑ |
|
( ) |
|
|
∑ |
( ) |
||||
|
*( |
) |
+ |
|
|
*( |
) |
|
+ |
|
|
*( |
) |
̅ |
+ |
|
|
Заметим, что если |
|
( |
) |
, |
|
, |
̅ |
, то |
( ) |
(так как при |
|||||
( ) |
в силу |
|
в ( |
|
) существовал бы путь нулевой длины из |
в , |
||||||||||
что |
противоречит |
условию |
|
̅ |
), |
а |
следовательно, |
согласно |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
34 |
( ) { |
( |
) |
( |
) |
( ) |
|
( ). |
Но тогда |
из |
вышестоящей формулы |
|||||
( |
) |
( |
) |
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||
получаем ̅ |
( ( |
)). Поскольку величина любого допустимого потока в |
|||||||||||||
транспортной сети |
не превосходит ( |
( |
)) (см. предыдущее утверждение). |
||||||||||||
|
Теорема 6.2 (о приведении к ДНФ). |
|
|
|
|
|
|
||||||||
|
Для любой формулы А можно найти такую формулу В, находящуюся в |
||||||||||||||
ДНФ, что |
. Формула В называется дизъюнктивной нормальной формой |
||||||||||||||
формулы А. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Доказательство. Доказательство теоремы разделяется на 3 этапа. |
|
|||||||||||||
|
1) Для формулы |
строим такую формулу |
, что |
|
|
и в |
не |
||||||||
|
содержится символов |
, . |
|
|
|
|
|
|
|
|
|||||
|
2) Докажем теперь, что для формулы |
можно найти формулу |
|||||||||||||
|
такую, |
что |
|
|
, |
и в |
|
отрицание находится только перед |
|||||||
|
переменными. Такая формула называется формулой с тесными |
||||||||||||||
|
отрицаниями. Докажем это утверждение индукцией по числу n |
||||||||||||||
|
логических символов формулы . |
|
|
|
|
|
|
||||||||
|
Если |
|
, то |
|
есть какая-то переменная |
. В качестве |
|||||||||
|
нужно взять . |
|
|
|
|
|
|
|
|
|
|
|
|||
|
Пусть утверждение выполняется для всех формул |
|
с числом |
||||||||||||
|
символов меньше |
. |
Пусть в формуле |
содержится точно |
|||||||||||
|
логических символов. Рассмотрим следующие случаи: |
|
|
|
|||||||||||
|
|
|
|
имеет вид |
|
. Тогда в |
, |
логических символов |
|||||||
|
|
|
меньше, чем . Поэтому существуют формулы |
, |
|||||||||||
|
|
|
такие, |
что |
|
|
, |
и |
в |
, |
|
отрицание |
|||
|
|
|
встречается только перед переменными. Ясно, что |
|
|||||||||||
|
|
|
равносильна |
|
и |
является |
формулой |
с |
тесными |
||||||
|
|
|
отрицаниями; |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
имеет |
вид |
|
. Доказательство |
аналогично |
|||||||
|
|
|
предыдущему случаю; |
|
|
|
|
|
|
||||||
|
|
|
|
имеет вид ̅̅̅. Тогда |
|
и |
в |
логических |
|||||||
|
|
|
символов |
меньше, |
|
чем . |
Поэтому |
к |
применимо |
||||||
|
|
|
индуктивное предположение; |
|
|
|
|
|
|
||||||
|
|
|
|
имеет |
|
̅̅̅̅̅̅̅̅̅̅̅ |
|
̅̅̅ ̅̅̅ |
и |
в ̅̅̅, ̅̅̅ |
|||||
|
|
|
вид ( |
|
). Тогда |
||||||||||
|
|
|
логических символов меньше, чем |
. Поэтому существуют |
|||||||||||
|
|
|
такие формулы |
, |
, что ̅̅̅ |
, ̅̅̅ |
и в |
, |
|||||||
|
|
|
отрицание встречается только перед переменными. Ясно, |
||||||||||||
|
|
|
что |
|
|
и |
|
является формулой с тесными |
|||||||
|
|
|
отрицаниями; |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
35 |
|
|
|
имеет |
вид |
̅̅̅̅̅̅̅̅̅̅̅ |
Тогда |
|
̅̅̅ |
̅̅̅, |
и далее |
||||||
|
|
( |
|
). |
|
|||||||||||
|
|
поступаем, как в предыдущем случае. |
|
|
|
|
||||||||||
|
При практическом преобразовании встречающиеся в формуле |
|||||||||||||||
|
отрицания просто передвигают к переменным, используя законы |
|||||||||||||||
|
де Моргана и уничтожая пары стоящих рядом отрицаний, если |
|||||||||||||||
|
таковые встречаются. |
|
|
|
|
|
|
|
|
|
|
|||||
|
Пример. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
̅̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ |
̅̅̅̅̅̅̅̅̅̅̅ |
|
̅̅̅) |
( |
̅̅̅) |
(̅̅̅ ̅̅̅) |
|||||||||
|
.( |
̅̅̅) |
( |
̅̅̅)/ |
( |
|
̅) ( |
|||||||||
|
̅̅̅̅̅̅̅ ̅̅ |
|
|
|
|
|
|
̅̅̅̅̅̅̅ |
̅̅ |
̅̅̅̅̅̅̅ ̅̅ |
|
|
|
|||
|
(̅̅̅ ̅̅̅) (̅̅̅ |
) |
|
(̅̅̅ |
) |
(̅̅̅ |
) |
|
|
|
|
|
|
|||
|
3) Полученную |
формулу |
|
можно |
считать |
построенной |
из |
|||||||||
|
переменных и их отрицаний с помощь многочленных конъюнкций |
|||||||||||||||
|
и дизъюнкций. Применив теперь общую дистрибутивность & |
|||||||||||||||
|
относительно |
|
, |
последовательно |
|
преобразуем |
формулу |
|||||||||
|
(аналогично приведению выражения, составленного из |
|||||||||||||||
|
переменных с помощью сложения и умножения, к виду |
|||||||||||||||
|
многочлена). Заметим, |
что |
при |
этом |
|
будет |
аналогично |
|||||||||
|
сложению, а & - умножению. Полученная в результате |
|||||||||||||||
|
преобразований формула B будет удовлетворять требованиям |
|||||||||||||||
|
доказываемой теоремы. |
|
|
|
|
|
|
|
|
|
|
|||||
Теорема 6.3 (о приведении к КНФ). |
|
|
|
|
|
|
|
|
||||||||
Для любой формулы |
можно найти такую формулу |
, что |
находится |
|||||||||||||
в КНФ и |
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Формула |
называется конъюнктивной нормальной формой формулы . |
|||||||||||||||
Первое доказательство. |
Пусть |
|
|
и |
не содержит символов |
, . |
||||||||||
Пусть |
– ДНФ для |
. Тогда |
|
находится в КНФ и, кроме того, по принципу |
||||||||||||
двойственности |
|
( ) |
|
|
|
. Значит, |
|
удовлетворяет |
условиям |
|||||||
теоремы.
Второе доказательство. Применив первые два этапа из доказательства
теоремы о |
ДНФ, |
получим формулу |
, равносильную , не содержащую |
|
символов |
, |
и |
содержащую отрицания только перед переменными. |
|
Преобразуем теперь |
как алгебраическое выражение, считая на этот раз & |
|||
аналогом сложения, а - аналогом умножения и применяя дистрибутивность
относительно &. Приведение формулы |
к виду многочлена даст на этот раз |
КНФ. |
|
Теорема 6.4. |
|
36
Пусть формула |
зависит от списка переменных ( |
) и |
не |
тождественно-ложная формула. Тогда существует такая формула |
, что |
|
|
инаходится в СДНФ относительно списка этих переменных.
|
Доказательство. Согласно теореме о приведении к ДНФ существует |
||||
формула |
такая, что |
и |
находится в ДНФ. При этом можно считать, |
||
что |
зависит от списка |
переменных ( |
) (в процессе приведения |
||
формулы к ДНФ новые переменные не появляются). Будем исходить из этой формулы и просматривать ее дизъюнктивные члены, то есть элементарные конъюнкции:
1) Пусть в элементарную конъюнкцию одновременно входят какаянибудь переменная и ее отрицание. Если это единственная элементарная конъюнкция формулы, то она на всех оценках принимает значение «Л», а следовательно, и вся формула, что невозможно, так как предполагается, что формула не тождественно ложная.
Значит, имеются другие элементарные конъюнкции, и формула (после некоторых перестановок) будет иметь вид
|
|
( |
̅̅̅̅ |
) |
|
|
где |
– остальные члены элементарной конъюнкции, а |
– |
||||
остальные |
дизъюнктивные |
члены |
всей формулы. |
Но |
||
( |
̅̅̅̅ ) |
, поскольку |
первый |
дизъюнктивный |
член |
|
левой части при всех оценках принимает значение «Л». Следовательно, наша формула равносильна , а рассматриваемую элементарную конъюнкцию можно отбросить. Поскольку не тождественно ложная, то после всех таких шагов всегда останутся какие-то не отброшенные элементарные конъюнкции.
2)Пусть в некоторой элементарной конъюнкции некоторая переменная (или ̅̅̅̅) встречается несколько раз. Тогда в илу
идемпотентности (равносильности 2) можно оставить только одно вхождение (или ̅̅̅̅).
3) После проведенной обработки каждая элементарная конъюнкция будет содержать какую-нибудь переменную не более одного раза (включая ее вхождение под знаком отрицания); при этом
возможны следующие варианты: |
|
|
|
|
а. конъюнкция |
содержит |
в |
качестве |
своего |
конъюнктивного члена один раз |
и ни разу ̅̅̅̅. |
|
||
37
б. конъюнкция |
содержит один раз ̅̅̅̅ |
и не содержит ни |
|
разу . |
|
|
|
в. конъюнкция |
не содержит ни |
, ни ̅̅̅̅. |
|
В последнем случае |
мы заменяем |
на ( |
) ( ̅̅̅̅) по |
основной равносильности 14 (первой формуле расщепления). Эту операцию следует проводить до тех пор, пока для каждой
элементарной конъюнкции и каждой переменной |
не будут |
выполнены условия «а» или «б». |
|
4)Переупорядочим в каждой элементарной конъюнкции ее конъюнктивные члены таким образом, чтобы на l-ом месте в ней
стояла |
или ̅̅̅̅. |
5)Если в преобразованной формуле повторяется одна и та же элементарная конъюнкция, то, пользуясь основной равносильностью 5 (идемпотентностью), выбрасываем все ее вхождения, кроме одного.
Теорема 6.6. |
|
|
|
Пусть формула А зависит от списка переменных ( |
) |
и А не |
|
тождественно-истинная. Тогда существует такая формула В, что |
|
и В |
|
находится в СКНФ относительно списка этих переменных. |
|
|
|
Доказательство. Пусть уже находится в КНФ. По условию |
на какой- |
||
то оценке принимает значение «Л». Тогда |
на двойственной |
оценке |
|
принимает значение «И» о по теореме о СДНФ существует такая формула , что и находится в СДНФ. По принципу двойственности и находится в СКНФ.
Можно доказать эту теорему по аналогии с доказательством теоремы о
СДНФ. |
При |
|
этом |
применяются |
равносильности |
|
( |
̅̅̅̅ ) |
, |
|||||||||||
( |
) ( |
̅̅̅̅) |
|
и законы идемпотентности. |
|
|
|
|
|
|
|
|
|
|||||||
Теорема 6.9. (о разложении функции по переменным) |
|
|
|
|
||||||||||||||||
Каждую булеву функцию |
f (x1 , , xn ) |
при любом k (1 ≤ k ≤ п) можно |
||||||||||||||||||
представить в следующей форме |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
f (x , , x |
, x |
k 1 |
, , x |
) |
|
x 1 x k |
f ( |
, , |
k |
, x |
k 1 |
, , x |
n |
) , |
|
||||
|
1 |
k |
|
|
n |
( 1 |
, , k ) |
1 |
k |
1 |
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
где дизъюнкция берется по всевозможным наборам значений |
||||||||||||||||||||
переменных x1 , , xk . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
Доказательство. |
|
Рассмотрим |
произвольный |
|
|
набор |
|
|
переменных |
|||||||||||
( |
) и покажем, |
что левая и правая части соотношения ( ) принимают на |
||||||||||||||||||
нем одно и то же значение. Левая часть дает |
( |
|
) Правая – |
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
38 |
|
|
|
( |
) |
|
|
( |
) |
|
|
|
|
|
|
|
|
( |
) |
( |
) |
|
Следствие 6.1 |
|
|
|
|
|
|
В качестве следствий получаем два специальных случая разложения. |
|||||
|
Разложение по переменной: |
|
|
|
||
|
( |
) |
( |
) ̅̅̅ ( |
|
) |
|
Функции ( |
|
) и ( |
) называются компонентами |
||
разложения. Данное разложение полезно, когда какие-нибудь свойства булевых функций устанавливаются по индукции.
Разложение по всем n переменным: |
|
|
|
|
|
|
||||||||
|
|
( |
|
) |
|
|
|
|
|
|
( |
) |
|
|
|
|
|
|
|
( |
) |
|
|
|
|
|
|
|
|
При |
( |
|
) |
оно может быть преобразовано: |
|
|
|
|||||||
|
|
|
|
|
|
( |
|
) |
|
|
|
|
|
|
( |
|
) |
|
|
|
|
|
|
|
( |
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
( |
) |
|
|
|
В результате окончательно получим |
|
|
|
|
|
|
||||||||
|
|
|
( |
|
|
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( |
|
) |
|
|
|
|
|
|
|
|
|
|
|
|
( |
|
) |
|
|
|
|
|
|
Такое разложение носит название СДНФ. |
|
|
|
|
||||||||||
Теорема 6.10 (о СДНФ булевой функции). |
|
|
|
|
||||||||||
Для |
любой булевой |
функции |
f (x1 , , xn ) , |
отличной |
от |
константы |
0, |
|||||||
справедливо следующее представление |
|
|
|
|
|
|
|
|
||||||
f (x , , x |
) |
|
x 1 |
x n . |
|
|
|
|
|
|
|
|
||
1 |
n |
( 1 |
, , n ) |
1 |
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
f ( 1 , , n ) 1 |
|
|
|
|
|
|
|
|
|
|
||
Доказательство. |
Пусть |
функция f (x1 , , xn ) |
отлична |
от |
константы |
0. |
||||||||
Напишем разложение этой функции по k = n переменным |
|
|
|
|||||||||||
f (x , , x |
) |
|
x 1 x n f ( |
, , |
n |
) , |
|
|
|
|
||||
1 |
n |
( 1 |
, , n ) |
1 |
|
n |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
что можно переписать в эквивалентном виде, согласно следствию 6.1.
|
|
x 1 |
x n f ( |
, , |
n |
) |
|
|
x 1 |
x n f ( |
, , |
n |
) . |
||
( 1 |
, , n ) |
1 |
n |
1 |
|
|
( 1 |
, , n ) |
1 |
n |
1 |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
||||
f ( 1 , , n ) 1 |
|
|
|
|
|
|
f ( 1 , , n ) 0 |
|
|
|
|
|
|
||
Учитывая, что в первой дизъюнкции все значения функции равны 1, а вторая обнуляется из-за того, что все значения функции в ней равны 0, получаем утверждение теоремы, т.е.
f (x , , x |
n |
) |
|
x 1 |
x n . |
1 |
( 1 |
, , n ) |
1 |
n |
|
|
|
|
|
||
|
|
f ( 1 , , n ) 1 |
|
|
|
39