Пак Г.К. - Дискретная математика

Выбрать r из n разных объектов можно Cnr способами. Имеется r! возможностей упорядочить объекты каждого сочетания. Согласно пра-

вилу умножения имеется r!Cnr возможностей выбрать и разместить по r

2.С помощью формулы Паскаля докажитеформулу(4) подсчета Cnr.

3.Сколькими способами можно распределить 12 различных предметов между тремя лицами так, чтобы каждый получил по четыре

предмета? (Ответ: С124 C84 = 34650).

4. Сколькими способами можно разместить в ряд p qшаров, из

которых p белых и q черных (p > q), при условии, что черные шары не могут лежать рядом. Ответ: Cpq q.

2.3.Бином Ньютона

Заметим, что

(1 t1)(1 t2) (1 tn) 1 (t1 t2 tn) (t1t2 t1t3 tn 1tn)

При t t1 t2 tn имеем

При t b/a – получим бином Ньютона:

Здесь в качестве коэффициентов стоят Cnr , поэтому эти числа

C0,C1,C2, ,Cnr называют биномиальными коэффициентами. Свойства бинома Ньютона:

1)степени a убывают в слагаемых правой части от n до 0;

2)степени b возрастают от 0 до n;

3)в каждом слагаемом сумма степеней a и b равна n;

4)коэффициенты Cnr , при an rbr симметричны относительно середины суммы.

При a = b = 1 из формулы Ньютона получим

s 0

6) CnkCkm CnmCnт mк ;n 1;k n;m k.

n

Указание к 1). Продифференцировать равенство ( 1 ) (1 x)n Cnk xk.

k 0

Решение 6). Выбираем к-подмножества в множестве из n элементов, а в нем выбираем m элементов (рис. 2.1). Это можно сделать CnkCkm способа-

ми. С другой стороны, можно выбрать вначале множество из m элементов, а потом выбираем те, которые не входят в множествоиз k элементов.

2.4. Размещения с повторениями

Упорядоченная выборка, в которой элементы могут повторяться, называется размещением с повторениями. Число всех размещений с

повторениями из n пo r будем обозначать Unr. По определению Un0 1. 22

ТЕОРЕМА. Unr. nr .

Доказательство проведем методом полной математической ин-

дукции по переменной r. Очевидно, что Un1 n. Предположим, что для r k справедливо равенствоUnk nk. Пусть r k 1. С помощью правила умножения можно доказать равенство

элементов равно2n.

Доказательство. Выберем подмножество. Если элемент принадлежит подмножеству, то кодируем эту ситуацию символом 1, а если не принадлежит, то символом 0. Элементы исходного множества пронумеруем. Тогда каждому подмножеству ставится во взаимнооднозначное соответствие размещение с повторениями из двух элементов 0 и 1 по n.

Таких размещений 2n, поэтому и подмножеств 2n.■

n

С другой стороны, таких подмножеств Сnr и, тем самым, фор-

r 0

мула (3) из предыдущего параграфа доказана вторым способом.

Упражнение

Сколько существует различных функций из X вY, если card X m, cardY n?

Ответ: nm.

2.5. Сочетания с повторениями

Неупорядоченная выборка, в которой элементы могут повторяться, называется сочетанием с повторениями. Число всех сочетаний с

повторениями из n по r будем обозначать Cnr (П).

n k 1. Докажем с помощью индукции по r равенство Ckr 1(П) Ckr r . При r = 1 имеем Ck1 1(П) k 1, Ckr 1 r 1 Ck1 1 1, т.е. база индукции

есть. Пусть формула верна при r = s , т.е. Cks 1(П) Cks s.. Тогда при r = s + 1 по формуле ( 1 ) и гипотезе индукции

Cks 11(П) Cks 1(П) Cks 1(П) Cks s Cks 1s Cks 1s 1 C(sk 11) (s 1) 1.

2.6. Принцип включения и исключения

ТЕОРЕМА. Пусть имеется N объектов и свойства a1, ..., an. Обозначим

ектов, не обладающих ни одним из свойств, (a1 an ) определяется по

формуле включения и исключения:

Доказательство. Проведем индукцию по числу свойств. Приn = l имеем

Рассмотрим множество тех объектов, которые обладают свойством an. Среди них не обладают свойствами a1, ..., an-1, элементы, число которых вычисляется следующим образом:

3адача о беспорядках. Сколько существует перестановок i1i2 in чисел

1, 2, ..., n таких, что ik k для всех k = 1, 2, ..., n?

Решение. Общее число перестановок N n! Число перестановок, в которых 1 стоит на своем месте (n 1)!, число 2 стоит на своем месте

(n 1)!... Число перестановок, в которых элементы i и j стоят на своих местах (n 2)! Отсюда по формуле включений и исключений получаем ответ на заданный вопрос:

( 1)n 1 | A1 An |.

Для доказательства применить формулу включения и исключения или провести индукцию по n.

Упражнения

1.Докажите, что n! nn Cn1(n 1)n Cn2(n 2)n .

2.Найдите количество чисел, не делящихся на 3, 7, 11 в первой тысяче натурального ряда.

3.Найдите сумму всех целых чисел от 1 до 1000, которые не делятся на 5 и на 7.

25

ГЛАВА 3. БУЛЕВЫ ФУНКЦИИ

3.1. Алгебра высказываний

Высказывание – предложение, о котором можно сказать, истинно оно или ложно. При этом оно не может быть одновременно истинным и ложным.

Отрицанием высказывания A называется такое высказывание, которое истинно тогда и только тогда, когда A ложно. Обозначается

оно через A или A . Читается «не A ». Операция отрицания унарная.

Операции, которые будут рассматриваться далее, бинарные. Конъюнкцией двух высказываний A и B называется такое третье

составное высказывание, которое истинно тогда и только тогда, когда A и B истинны одновременно. Для конъюнкции применяются обозна-

составное высказывание, которое истинно тогда и только тогда, когда одно из высказываний A и B истинно или оба высказывания истинны одновременно. Обозначение: A B, (логическая сумма). Читается

« A или B ».

Импликацией двух высказываний A и B называется такое третье составное высказывание, которое ложно тогда и только тогда, когда А истинно, а B ложно. Обозначение A B. Читается «из A следует B ».

Здесь A называют посылкой, а B – следствием.

Эквиваленцией двух высказываний A и B называется такое третье составное высказывание, которое истинно тогда и только тогда, когда высказывания A и B одновременно истинны или ложны. Обозначение A B.Читается « A тогда и только тогда, когда B », «для A необходимо и достаточно B ».

Действия над высказываниями можно описать с помощью таблиц истинности. В них буква «И» соответствует значению «истина», а буква «Л» значению «ложь».

Заметим, что двуместная операция дизъюнкции соответствует союзу «или». Но в обычной речи союз «или» употребляется, по крайней мере, в двух различных смыслах: неальтернативное неисключающее

26

«или» и альтернативное исключающее «или». В нашем случае дизъюнкция соответствует высказыванию первого типа.

3.2. Функции алгебры логики

Функция y f (x1, ,xn)называется n-местной булевой функци-

ей, если каждая переменная принимает только два значения 0 или 1 и функция принимает значения в этом же множестве {0; 1}. Булевой функцию называют в честь ирландского математика Джорджа Буля (1815–1864), работавшего в университете города Корк, отца писательницы Этель Лилиан Войнич. С именем Буля связана революция в логике, она приобрела письменность, появился новый тип алгебры. Другие имена, связанные с этой теорией: Аристотель, Раймундо Луллий (исп. философ, монах-отшельник XII-XIII вв.), Б. Спиноза, Н. Винер. Булевые функции называют также функциями алгебры логики или, более полно, алгебры двузначной логики.

Булеву функцию можно задать таблицей:

Всюду в дальнейшем наборы значений переменных x1, , xn булевой функции будем располагать в стандартном порядке, при котором набор 1, , n представляет собой двоичную запись своего номера в n разрядах (нумерация начинается с нуля), т.е.

n 1

( ) i 2n i

i 1

Упражнение

Какой номер у набора значений переменных булевой функции (11101)? Номером какого набора значений переменных булевой функции от пяти переменных является число 18?

Единый способ записи наборов значений переменных дает возможность записывать функции лишь в виде столбца ее значений. На-

пример, x& y = (0001), x y = (0111), h = (00010111). Нульместные функции 0 и 1 называются соответственно тождественным нулем и тождественной единицей. Функция f (x) x называется тождест-

27

венной функцией. Функция f (x) x называется отрицанием x . Все

одноместные функции можно свести в таблицу:

x y называется суммой по модулю 2 или альтернативной дизъюнкци-

ей и читается “ x плюс y по модулю 2”. Эквивалентность x y часто

обозначается также x y, x ~ y, x y. Импликация в некоторых книгах обозначается также x y, x y и часто читается «x имплицирует

y». Функция x y называется штрихом Шеффера. Функция x у называется стрелкой Пирса, функцией Пирса. Все эти функции называют

элементарными. Символы , &, , , , , , называют логическими связками.

Две функции называются равными, если они принимают одинаковые значения на одних и тех же наборах значений переменных.

Говорят, что f(x1,…, xn ) существенно зависит от переменной x1, если существует такой набор значений переменных x2 = 2,…, xn = n, что

f(0, 2,…, n) f(1, a2,…, an). Переменные, от которых функция зависит существенно, называются существенными, остальные – фиктивными. Отождествляем функции, из которых добавлением фиктивных переменных можно получить одну и ту же функцию.

ТЕОРЕМА. Числовсех различных n-местных булевых функций равно22n.

которое само является формулой. Для сокращения записи формул обычно принимаются следующие соглашения:

а) внешние скобки у формул опускаются; б) формула A записывается в виде A; в) формула A &B записывается в виде AB;

г) связка считается сильнее любой двуместной связки; д) связка & считается сильнее любой другой двуместной связки.

В соответствии с этим договоримся, что логические операции выполняются в следующем порядке:

1)конъюнкция,

2)дизъюнкция,

3)импликация и эквиваленция в порядке их записи,

4)если часть формулы заключена в скобки, то сначала производится действие в скобках,

5)если над частью формулы стоит знак отрицания, то он заменяет собой скобки, в которые заключена эта часть формулы.

где верхние символы указывают местность (арность) символов. Если арности из контекста известны, то верхние индексы будем опускать.

соответствующих им функций. Суперпозицией над множеством Р на-

зывается всякая функция F, которую можно реализовать формулой над множеством Ф.

Формула алгебры логики называется выполнимой, если существует набор значений переменных, на которых реализуемая ею функция принимает значение 1, и опровержимой, если 0. Формула называется

30

тождественно истинной или тавтологией, если она реализует функцию «тождественная единица», и тождественно ложной, если 0. Проблема разрешимости заключается в задаче: указать алгоритм, позволяющий для каждой формулы выяснять, является ли она тождественно истинной. Ответ на этот вопрос можно дать после изучения нормальных форм.

Упражнение

Являются ли формулы тождественно истинными:

1)((x y) z)(x yz);

2)((x y)z ((x z) y)|(x(yz));

3)(x y) ((x z) y z).

3.4. Алгебра Буля

Непустое множество U с тремя операциями +, , ' (сложение,

умножение, дополнение) называется алгеброй Буля, если выполняются следующие условия:

1)a + b = b + a, ab = ba, a, b U;

2)a (b c) (a b) c, a(bc) (ab), a, b U;

по отношения к обеим операциям;

5)(ab)' (a)' (b)', (a b)' (a)'(b)', законы двойственности деМоргана;

6)(a')' a.

Нейтральный элемент 1 операции умножения называется универсальным элементом алгебры Буля.

Примеры.

3) Контакты электрических сетей, если трактовать + как параллельное соединение контактов, последовательное соединение контактов, 1 –

есть ток в цепи, 0 – нет тока в цепи, x' x – размыкание контакта x.

4){0; 1}, a + b = max {a, b}, a b= min {a, b}, 0' 1, 1' 0.

5)Множество делителей числа n, если a + b = НОК (a, b),

a b = НОД (a, b), a' n . a

6) Сегмент [x , y], где a + b = max {a, b}, a b = min {a, b},0 x,

1 y, a' –точка, симметрическаясточкойаотносительносерединысегмента.

3.5. Эквивалентные формулы

Формулы алгебры логики A и B называются эквивалентными, если на всяком наборе значений переменных (входящих хотя бы в одну из формул A и B ) значения функций A и B совпадают, т.е. ес-

ли A B . Приведем основные эквивалентности.

1)xy yx, x y y x, y x x y, (x y y x), xy yx, x y y x

(законы коммутативности).

дистрибутивности).

4)x y x y,x y xy (законы двойственности де Моргана).

5)xy xy x,(x y)(x y) x(правила склеивания).

6)x (xy) x,x(x y) x(правила поглощения).

7)(xz) (yz) (xz) (yz) (xy)(правило обобщенного склеивания).

8)x & x = x , x x = x (законы идемпотентности).

9) x&0 0, x 0=x, x &1 = x , x 1 =1, (x 0)=x ,(x 1) 1, ( x 1)=x , (x 0) x (свойства относительноконстант).

10)x x 1(закон исключенного третьего).

11)x & x = 0 (закон противоречия).

12)(x x) 1, (x x) 1(унипотентности).

13)x x (закон двойного отрицания).

14)x x 0, x x 1, (x y) 1 x xy,

xy x y xy, (x y) 1 x y.

15)(x y) x y (замена импликации).

(x y) (x y)(y x) x y xy (замена эквиваленции).

(x y) xy xy.

Для примера докажем свойство замены импликации: составим расчетную таблицу, в которую включаются все промежуточные вычисления.

Некоторые из формул можно доказывать алгебраически с помощью уже

x y x (xy xy) (x xy) xy x(1 y) xy x xy.

Эквивалентные формулы используются при упрощении формул.

x3(x1 x2) x2(x1 x3) x1x3 x2x3 x1x2 x2x3 x1(x2 x3) x2x3.

3.6.Элементарная конъюнкция. Элементарная дизъюнкция

Всилу ассоциативности конъюнкции в выражениях (x& y)& z и

x&(y& z) скобки можно не писать, поэтому считаем запись x& y& z,

имеющей смысл. Индуктивно получает смысл запись x1 & &xn. Ана-

логично, считаем имеющей смысл и запись x1 x1 … xn (т.е. из дву-

местных операций получены с помощью свойства ассоциативности n-местные). Будем полагать, что

33

ТЕОРЕМА. Конъюнкция букв тождественно ложна тогда и только тогда, когда в неевходит хотя бы одна переменная вместе со своим отрицанием. Доказательство. Пусть конъюнкция букв тождественно ложна, но

такой переменной в ней нет. Придадим переменным, которые входят в эту конъюнкцию, значение 1, а тем переменным, которые входят в нее под знаком отрицания, 0. На этом наборе значений переменных конъюнкция примет значение 1, а это противоречит условию, т.е. наше предположение неверно.

Пусть в конъюнкцию К входит переменная t вместе со своим отрицанием. Применив закон коммутативности конъюнкции, мы при-

ведем ее к виду K (t &t)& K1 0& K1 0.

ТЕОРЕМА. Дизъюнкция букв тождественно истинна тогда и только тогда, когда существует хотя бы одна переменная, которая входит в нее вместе со своим отрицанием.

Доказывается аналогично.

Конъюнкция букв называется элементарной, если все переменные, входящие в ее различные буквы, различны. Дизъюнкция букв называется элементарной, если все переменные, входящие в ее различные буквы, различны. Количество букв, входящих в элементарную конъюнкцию (ЭК) или элементарную дизъюнкцию (ЭД), называется рангом ЭК или ЭД соответственно. Число 1 считается ЭК ранга 0. Буква считается ЭК или ЭД ранга 1. Число 0 считается ЭД ранга 0. Любую конъюнкцию букв, не являющуюся тождественно ложной, можно привести к виду элементарной, а любую дизъюнкцию букв, не являющуюся тождественно истинной, можно привести к виду элементарной также. Для этого надо применить свойства коммутативности, идемпотентности и ассоциативности конъюнкции и дизъюнкции.

Упражнения

1.Докажите: x 1 x , x 0 x.

2.Докажите, что а) число всех различных n-местных ЭК равно

3n, б) число всех различных n-местных ЭК ранга n равно 2n.

3.7. Совершенная дизъюнктивная нормальная форма

Дизъюнкция различных элементарных конъюнкций называется

дизъюнктивной нормальной формой (ДНФ). Количество ЭК, входящих в ДНФ, называется ее длиной. Сумма рангов ЭК называется сложно-

стью ДНФ.

34

ТЕОРЕМА. Число всех различных ДНФ от n-переменных равно 23n. Доказательство. В ЭК переменная может входить под знаком отрицания (ситуации присваиваем код 0), может входить сама (код 1); может не входить ни сама, ни под знаком отрицания (код 2).Таким образом, каждой ЭК от n переменных ставится во взаимооднозначное соответствие размещение с повторениями из трех элементов 0, 1, 2 по n местам.

Таких размещений 3n,а поэтому и ЭК столько же. Любое подмножест-

во ЭК из множества всех 3n ЭК определяет ДНФ, а число всех под-

множеств этого множества равно 23n.

Если в ДНФ все ЭК имеют один и тот же ранг, равный числу переменных, от которых зависит ДНФ, то она называется совершенной (СДНФ).

ТЕОРЕМА о разложении булевой функции по одной переменной. f (x1,...,xn) x1 f (0,x2,...,xn) x1 f (1,x2,...,xn)

Доказательство. Проверяем, какие значения принимают функции, стоящие справа и слева, вначале на любом наборе значений переменных, начинающимся с нуля, а затем на наборе, начинающимся с единицы. ТЕОРЕМА о разложении булевой функции по двум переменным.

f (x1,...,xn) x1x2 f (0,0,x3,...,xn) x1x2 f (0,1,x3,...,xn ) x1x2 f (1,0,x3,...,xn)x1x2 f (1, 1,x2,...,xn).

Доказательство. Применить дважды предыдущую теорему. Можно доказать также, проверяя, какие значения принимают функции, стоящие справа и слева, вначале на любом наборе значений переменных, начинающимся с двух нулей 0, 0,x3,..., xn , затем на наборе вида

0,1,x3,...,xn , затем на наборе вида 1, 0,x3,...,xn , а затем на наборе вида

1,1,x3,...,xn .

ТЕОРЕМА о разложении булевой функции по переменным. Любую булеву функцию f (x1,...,xn) можно представить в виде

1, , s

i 0, 1

где знак сокращенной дизъюнкции берется по всем двоичным наборам

1,..., s

Доказательство. Можно провести индукцию по s. А можно проверить равенство непосредственно на всех наборах значений переменных. Для этого заметим, что

1)1 , где , {0; 1};

2)11 ss 1 i i i ;

35

0,если i i,

3)11 ss f ( 1,..., s, s 1..., n) f ( 1,..., n),если i i;

4)V11 s s f ( 1, , s, s 1, , n ) f ( 1,..., n ).

1, , s

ТЕОРЕМА. Для любой функции, не являющейся тождественно ложной, существует и притом единственная СДНФ.

Доказательство. Из теоремы о разложении булевой функции по переменным при s = n следует

мое из дизъюнкции удаляется, а если 1, то слагаемое приобретает вид

Следовательно, мы представили булеву функцию в виде СДНФ. Так как числа различных n-местных булевых функций и СДНФ совпадают, то представление булевой функции в виде СДНФ возможно лишь единственным образом.

Следствие. Любую булеву функцию, не являющуюся тождественно ложной, можно представить в виде суперпозиции &, , , причем отрицание относится только к переменным.

Формула (3) позволяет по таблице истинности булевой функции строить ее СДНФ.

Пример. Привести к СДНФ функцию f = (10001110).

Таблица 3.7

2)С помощью законов двойственности отнести знаки только к переменным (тесное отрицание).

3)С помощью закона дистрибутивности & относительно перейти к дизъюнкции конъюнкций.

4)Воспользоваться законами идемпотентности & и .

Пример.

(x& y x)&(x& y y) (xy x)(xy y) (xyx)(xyy) (xy)(xy) xy.

Упражнение

Приведите к СДНФ функцию x (y z).

Ответ: xyz xyz xyz xyz .

3.8. Совершенная конъюнктивная нормальная форма

Конъюнкция различных элементарных дизъюнкций называется

конъюнктивной нормальной формой (КНФ). Все определения и факты,

приведенные для ДНФ и СДНФ, с соответствующими изменениями переносятся на КНФ и СКНФ. Таким образом, имеют место двойственные утверждения:

f (x1,...,xn ) (x1 f (0,x2,...,xn ))(x1 f (1,x2,...,xn )),

КНФ называется совершенной (СКНФ), если ранги всех ЭД, входящих в нее, равны между собой и равны числу переменных, над которыми берется форма.

ТЕОРЕМА. Для любой функции, не являющейся тождественно истинной, существует и притом единственная, эквивалентная ей СКНФ.

числа всех различных n-местных булевых функций и СКНФ от тех же переменных совпадают, то представление булевых функций в виде СКНФ возможно единственным образом.

Пример. Построить СКНФ для f = (10001110).

f x1,x2,x3 (x10 x20 x31 )(x10 x21 x30 )(x10 x21 x31 )(x11 x21 x31 )

(x1 x2 x3)(x1 x2 x3)(x1 x2 x3)(x1 x2 x3).

Упражнение

Приведите к СКНФ функции

Ответ: 1) x y ; 2) (x y z)(x y z).

37

3.9. Принцип двойственности

Функцию f *(x1,...,xn) f (x1,..., xn) называют двойственной функ-

(x)* x x , (x y)* (x y)* xy.

Ясно, что ( f *)* f , т.е. функции f * и f двойственны друг другу.

ТЕОРЕМА. Если булева функция записана в виде суперпозиции , ,, то двойственная ей получается заменой каждой дизъюнкции на конъюнкцию, а каждой конъюнкции на дизъюнкцию.

Доказательство проведем методом полной математической индукции по числу операций над переменными. Без ограничения общности можно считать, что отрицание относится только к переменным. База индук-

Право перехода. Пусть дана функция f(x1,...,xn ), полученная с по-

мощью s 1операции , , . Если, например, последняя операция конъюнкция, т.е. f g &h, то

f* g(x1, ,xn)&h(x1, ,xn) g(x1, ,xn)&h(x1, ,xn) g* &h*.

По гипотезе индукции g* и h* можно получить заменой в g и h соответственно каждой & на и наоборот, т.е. f* может быть получена из f таким жеобразом.■

Упражнения

1.Докажите, что если б.ф. f является суперпозицией б.ф. g1, …, gs, то f* является суперпозицией той же структуры функций g1*, …, gs*.

2.Докажите, что ( x у) =x у, ( x у) = x у, ( x у) = (y x), h = h, где h( x , y, z) = xy xz yz.

3.10. Полином Жегалкина

Если в ЭК нет отрицаний переменных, то она называется монотонной элементарной конъюнкцией (Мон. ЭК). Например, 1, x , y, xy – все монотонные ЭК от переменных x , y; или 1, х, y, z, xy, xz, yz, xyz – все Мон. ЭК от переменных x , y, z. Сумма по модулю 2 различных монотонных элементарных конъюнкций называетсяполиномом Жегалкина.

ТЕОРЕМА. Любую булеву функцию можно представить в виде полинома Жегалкина, причем, единственным образом с точностью до коммутативности & и .

38

Доказательство. Представим б.ф. в виде СДНФ или СКНФ. С помощью тождеств x y x y xy, x x 1 заменим все значки и , т.е.

б.ф. представим в виде суперпозиции &, , 0, 1 – в виде полинома Жегалкина. Так как число всех различных полиномов Жегалкина от

x1, ,xn равно 22n , т.е. числу всех различных n-местных б.ф., то лю-

бую б.ф. представить в виде полинома Жегалкина можно лишь единственным способом. ■

Пример. Представьте в виде полинома Жегалкина f = x y.

f = x y = x y x y = x 1 y 1 (x 1)(y 1)=xy 1.

Пример. Найдите полином Жегалкина для функции f = (11111000). Решение. Применим метод неопределенных коэффициентов.

Упражнение

Привести двумя способами (алгебраическими преобразованиями и методом неопределенных коэффициентов) к виду полинома Жегалки-

на h = xy xz yz.

39

ГЛАВА 4. ЗАМКНУТЫЕ КЛАССЫ И ПОЛНОТА

4.1. Замыкание множества булевых функций

Замыканием множества булевых функций N называется множество

N всех суперпозиций функций из множества N . Свойства замыканий:

1)N N ;

2)N = N ;

3)N1 N2 N1 N2 ;

4)N1 N2 N1 N2 .

Доказательство. Свойство 1) имеет место при условии, что булевые функции из множества N мы рассматриваем как результат применения операции суперпозиции.

2) f N f = C(h1,…,hn), hi N , 1 i n hi = Ci(g1,…,gm), gj N, 1 j m f =C(C1(g1,…,gm),…,Cn(g1,…,gm)) f N N N .

Обратное включение следует из свойства 1.

3) f N1 f =C(g1,…,gm), gi N1 gi N2, i =1,m f N2

N1 N2 .

4)f N1 N2 f = C(g1, …,gn), gi N1 gi N2, gi N1 N2 f N1 N2 N1 N2 N1 N2 .■

Множество N называется замкнутым, если N = N. Для доказательства замкнутости множества, очевидно, достаточно доказать, что любая суперпозиция функции из множества вновь функция из этого же

множества. Пять важнейших замкнутых классов: Т0 = f f(0,…, 0) = 0 ,

Т1 = f f(1,…, 1) = 1 , L = f f = 0 1x1 … nxn, i = 0 1 , M –

класс монотонных булевых функций, S = f f = f* . Обозначим через Р2 множество всех булевых функций. Класс N булевых функций называется полным, если N = Р2. Для доказательства полноты класса, очевидно, достаточно доказать, что любую булеву функцию можно представить в виде суперпозиции функций из этого класса. Множество булевых функций называется независимым, если ни одна из них не является суперпозицией остальных функций этого множества. Полная независимая система булевых функций называется базисом Р2. Функции конъюнкция, дизъюнкция и отрицание образуют полный класс, но не базис, так как дизъюнкция – суперпозиция конъюнкции и отрицания. Система 0, 1, , полна, так как любую булеву функцию можно представить в виде полинома Жегалкина.

ТЕОРЕМА. Если каждая булева функция полного класса может быть представлена в виде суперпозиции булевых функций другого класса, то и этот класс полный.

Доказательство. Даны два класса булевых функций N1 = f1, … и N2 = g1,… . Первый класс полный, и каждая его функция – суперпозиция функции второго класса.

40