Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс (1083731), страница 2
Текст из файла (страница 2)
Используя последний факт можно, например, получить оценку числа функций от 10 переменных. Всего таких функций будет . Таким образом, при росте числа переменных число функций возрастает очень быстро, и их табличное задание становится неудобным.
2°. Равенство функций. В обычной алгебре справедливо равенство x + y – y = x, несмотря на то, что в левой части записана функция от двух переменных, а в правой — от одной. Таким образом, функции от разного числа переменных могут быть одинаковыми, что даёт повод ввести понятие существенных и фиктивных переменных.
Определение 2. Переменная xi называется существенной переменной функции алгебры логики f (x1, …, xn), если существуют такие
α1, …, αi – 1, αi + 1, …, αnE2, что
f (α1, …,αi – 1, 0, αi + 1,…, αn) f (α1, …, αi – 1, 1, αi + 1, …, αn).
Такие наборы, отличающиеся лишь одной переменной xi, называются соседними по xi. В противном случае переменная xi называется фиктивной.
Если xi — фиктивная переменная функции f, то функция f однозначно определяется некоторой функцией g (x1, …, xi – 1, xi + 1, …, xn). Таблицу любой функции можно расширить введением любого числа фиктивных переменных.
Определение 3. Две функции алгебры логики называются равными, если одну из них можно получить из другой путём добавления и изъятия любого числа фиктивных переменных.
3°. Формулы.
Определение 4. Пусть имеется некоторое множество функций
A = {f1 (…), f2 (…), …, fn (…), …}.
Введем понятие формулы над A:
-
Любая функция из A называется формулой над A.
-
Если f (x1, …, xn) A и для любого i Hi — либо переменная, либо формула над A, то выражение вида f (H1, H2, …, Hn) является также формулой над A.
-
Только те объекты называются формулами над A, которые можно построить с помощью пунктов 1 и 2 данного определения.
Замечание. Среди H1, H2, …, Hn вполне могут быть одинаковые.
4°. Основные эквивалентности.
-
Коммутативность:
x y = y x ;
xy = yx ;
x y = y x ;
x ~ y = y ~ x . -
Ассоциативность:
(x y) z = x (y z) = x y z ;
(xy) z=x (yz)=xyz ;
(x y) z = x (y z) = x y z. -
Дистрибутивность:
(x y) z = (xz) (yz) ;
(x y) z = (xz) (yz) ;
(xy) z = (x z)·(y z).
Законы поглощения.
x x = x
x · x = x
x 1 = 1
x · 1 = x
x 0 = x
x · 0 = 0.
Приоритет конъюнкции выше, чем приоритеты дизъюнкции и суммы по модулю 2. Благодаря этому, часто удаётся опустить ряд ненужных скобок. Имеют место следующие очевидные утверждения:
x1 · x2 · … · xn = 1 i xi = 1,
x1 x2 … xn = 1 i: xi = 1.
Определение 5. x в степени сигма называется функция
x = 1 x = .
§2. Теорема о разложении функции алгебры логики по
переменным. Теорема о совершенной дизъюнктивной нормальной форме
Теорема 1 (о разложении функции алгебры логики по переменным). Для любой функции алгебры логики f (x1, …, xn) и для любого k (1 k n) справедливо следующее равенство:
Доказательство. Для любого набора вычислим значение правой части на этом наборе. Как только хотя бы один из сомножителей будет равен нулю, вся конъюнкция обратится в нуль. Таким образом, из ненулевых конъюнкций останется лишь одна — та, в которой αi = σi для i = 1, …, k, и
а в силу того, что xx = 1, указанное выражение равно f (α1, α2, …, αn). Теорема доказана.
Следствие 1. Разложение произвольной функции алгебры логики по одной переменной имеет вид
Следствие 2 (теорема о совершенной дизъюнктивной нормальной форме). Для любой функции алгебры логики f (x1, x2, …, xn), отличной от тождественного нуля, справедливо следующее представление:
.
Доказательство. Пусть функция f (x1, x2,…, xn) отлична от тождественного нуля. Напишем разложение этой функции по k = n переменным:
что можно переписать в эквивалентном виде
Учитывая, что в первой дизъюнкции все значения функции равны единице, а вторая обнуляется из-за того, что все значения функции в ней равны нулю, получаем утверждение следствия. Следствие доказано.
Теорема 2 (о совершенной конъюнктивной нормальной форме). Для любой функции алгебры логики f (x1, x2, …, xn), отличной от тождественной единицы, справедливо представление
§3. Полные системы. Примеры полных систем
(с доказательством полноты)
Определение. Множество функций алгебры логики A называется полной системой (в P2), если любую функцию алгебры логики можно выразить формулой над A.
Теорема 3. Система A = {, &, ¬} является полной.
Доказательство. Если функция алгебры логики f отлична от тождественного нуля, то f выражается в виде совершенной дизъюнктивной нормальной формы, в которую входят лишь дизъюнкция, конъюнкция и отрицание. Если же f 0, то . Теорема доказана.
Лемма 2. Если система A — полная, и любая функция системы A может быть выражена формулой над некоторой другой системой B, то B — также полная система.
Доказательство. Рассмотрим произвольную функцию алгебры логики f (x1, …, xn) и две системы функций: A = {g1, g2, …} и B = {h1, h2, …}. В силу того, что система A полна, функция f может быть выражена в виде формулы над ней: , где
, то есть функция f представляется в виде
, иначе говоря, может быть представлена формулой над B. Перебирая таким образом все функции алгебры логики, получим, что система B также полна. Лемма доказана.
Теорема 4. Следующие системы являются полными в P2:
Доказательство. 1) Известно (теорема 3), что система полна. Покажем, что полна система
. Действительно, из закона де Моргана
получаем, что
, то есть конъюнкция выражается через дизъюнкцию и отрицание, и все функции системы A выражаются формулами над системой B. Согласно лемме 2 система B полна.
2) Аналогично пункту 1: и из леммы 2 следует истинность утверждения пункта 2.
3) ,
и, согласно лемме 2, система полна.
4) и, согласно лемме 2, система полна.
Теорема доказана.
§4. Теорема Жегалкина о представимости функции алгебры логики полиномом
Определение 1. Монотонной конъюнкцией от переменных x1,…,xn называется любое выражение вида , где s 1, 1 ij n j = 1, 2, …, s, все переменные различны (ij ik, если j k); либо просто 1.
Определение 2. Полиномом Жегалкина над x1, …, xn называется выражение вида
K1 K2 K3 … Kl,
где l 1 и все Kj суть различные монотонные конъюнкции над x1, …, xn; либо константа 0.
Теорема 5 (теорема Жегалкина). Любую функцию алгебры логики f (x1, …, xn) можно единственным образом выразить полиномом Жегалкина над x1, …, xn.
Доказательство. 1) Докажем существование полинома. Система {x · y, x y, 1} полна, следовательно, любую функцию алгебры логики f (x1, …, xn) можно реализовать формулой над {x · y, x y, 1}.
-
Пользуясь дистрибутивностью, раскрываем все скобки в этой реализации и получаем, что f (x1, …, xn) = K1 K2 … Kl, где любая Ki — конъюнкция переменных и единиц.
-
Преобразуем все полученные конъюнкции в монотонные, пользуясь при этом коммутативностью и соотношениями
x · x = x, 1 · 1 = 1 и A · 1 = A. Очевидно, все конъюнкции станут монотонными. -
Преобразуем полученную сумму в полином Жегалкина, пользуясь при этом соотношениями A A = A и A 0 = A. В результате получим либо
либо константу 0.
Существование доказано.
2) Докажем единственность представления. Подсчитаем число различных всевозможных монотонных конъюнкций от n переменных. Для этого составим таблицу вида
где каждой переменной соответствует единица, если она присутствует в монотонной конъюнкции и ноль в противном случае. При этом константе единице поставим в соответствие нулевой набор. Очевидно, что построенное отображение взаимно однозначно. Следовательно, всего различных монотонных конъюнкций от n переменных — 2n. Построим аналогичное взаимно однозначное отображение между всевозможными суммами монотонных конъюнкций и векторами длины 2n — числа конъюнкций. Для этого составим таблицу вида
где под соответствующей монотонной конъюнкцией стоит единица, если она входит в данную сумму, и ноль, если не входит. При этом константе ноль ставится в соответствие нулевой набор. Очевидно, такое отображение взаимно однозначно. Всего таких различных сумм будет столько, сколько существует различных булевых векторов длины 2n, то есть — . Мы получили, что число различных полиномов Жегалкина совпадает с числом функций алгебры логики. Поскольку каждой функции соответствует хотя бы один полином, а каждому полиному соответствует ровно одна функция, то соответствие между ними взаимно однозначно, так как множества полиномов Жегалкина над n переменными и функций алгебры логики от n переменных равномощны. Единственность доказана.
§5. Понятие замкнутого класса. Замкнутость классов
T0, T1 и L.
1°. Понятие замкнутого класса.
Определение 1. Пусть A P2. Тогда замыканием A называется множество всех функций алгебры логики, которые можно выразить формулами над A.
Обозначение: [A].