Дискретная математика. Часть 1

Лекция 2 по дискретной математики 16.02.2021 Этот файл следует смотреть в текстовом редакторе с моноширинным шрифтом, таким как Consolas. Это нужно для выравнивания колонок, чтобы схемы и таблицы отображались правильно. На лекции рассматривается разделы 8.2 и 8.3 в учебнике Алексеева (их следует прочитать), а также следующий материал. Теорема 8.1 о разложении функции по переменной в учебнике Алексеева. Для любой логической функции f(x1, ..., xn) справедливо тождество f(x1, x2, ..., xn) = x1 & f(1, x2, ..., xn) \/ (~x1) & f(0, x2, ..., xn) (1) Проверяется подстановкой x1 = 0 и x1 = 1 в обе части равенства. Функции f(1, x2, ..., xn) и f(0, x2, ..., xn) зависят от переменных x2, ..., xn. Их можно разложить по x2: f(1, ..., f(0, ..., x2, x3, ..., xn) = x2 & f(1, 1, x3, ..., xn) \/ (~x2) & f(1, 0, x3, xn) x2, x3, ..., xn) = x2 & f(0, 1, x3, ..., xn) \/ (~x2) & f(0, 0, x3, xn) Если подставить эти равенства в (1) и раскрыть скобки, получится f(x1, x2, ..., xn) = x1x2 & f(1, 1, x3, ..., xn) \/ x1(~x2) & f(1, 0, x3, ..., xn) \/ (~x1)x2 & f(0, 1, x3, ..., xn) \/ (~x1)(~x2) & f(0, 0, x3, ..., xn). Закономерность: вместо двух первых аргументов мы подставляем всевозможные значения 0 и 1. При этом если вместо какой-то переменной подставляется 1, то значение функции умножается на саму эту переменную, а если вместо этой переменной подставляется 0, то значение функции умножается на отрицание переменной. Если вспомнить обозначение x^0 = ~x x^1 = x то при подстановке a ∈ {0, 1} вместо xi, значение функции умножается на xi^a. Получившиеся функции от n-2 аргументов можно продолжать раскладывать по x3 и т.д. После раскладывания по переменным x1, ..., xk получается 2^k функций. Они называются компонентами, или подфункциями исходной функции. Пример. Разложим функцию f(x, y, z) = (~x)(y <-> z) + xy по всем переменным. f(x, y, z) = x & f(1, y, z) \/ (~x) & f(0, y, z) f(1, y, z) = (~1)(y <-> z) \/ 1y = y f(0, y, z) = (~0)(y <-> z) \/ 0y = y <-> z Таким образом, f(x, y, z) = xy \/ (~x)(y <-> z), что было очевидно сразу. Разложим получившиеся функции y и y <-> z по y. y = y1 \/ (~y)0 y <-> z = y(1 <-> z) \/ (~y)(0 <-> z) = yz \/ (~y)(~z) Таким образом, f(x, y, z) = xy1 \/ x(~y)0 \/ (~x)yz \/ (~x)(~y)(~z). Функции 1, 0, z и ~z можно разложить по z. Получится 1 = z1 \/ (~z)1 0 = z0 \/ (~z)0 z = z1 \/ (~z)0 ~z = z0 \/ (~z)1 Итого f(x, y, z) = xyz1 \/ xy(~z)1 \/ x(~y)z0 \/ x(~y)(~z)0 \/ (~x)yz1 \/ (~x)y(~z)0 \/ \/ (~x)(~y)z0 \/ (~x)(~y)(~z)1 = xyz \/ xy(~z) \/ (~x)yz \/ (~x)(~y)(~z) Получилась СДНФ функции f. Так будет и в общем случае: если разложить f(x1, ..., xn) по всем переменным, убрать конъюнкции с 0, а из оставшихся конъюнкций убрать 1, то получится СДНФ f. Это еще одно доказательства полноты системы функций {&, \/, ~}. Раздел 8.2.2 в учебнике Алексеева использует обратный процесс собирания функции для построения ее схемы из функциональных элементов. Сначала рассматриваются 2^(n-1) функций f(a1, ..., a(n-1), xn) для всевозможных a1, ..., a(n-1) ∈ {0, 1}. Каждая из этих функций зависит только от xn, поэтому она может быть одной из четырех: 1, 0, xn или ~xn. Каждую из этих функций можно реализовать схемой. Затем рассматриваются функции f(a1, ..., a(n-2), x(n-1), xn) = = x(n-1) & f(a1, ..., a(n-2), 1, xn) \/ (~x(n-1)) & f(a1, ..., a(n-2), 0, xn). Поскольку функции f(a1, ..., a(n-2), 1, xn) и f(a1, ..., a(n-2), 0, xn) уже реализованы схемами, можно также реализовать и f(a1, ..., a(n-2), x(n-1), xn). Этот процесс продолжается, пока не получится схема для f(x1, ..., xn). Рассмотрим один шаг этого процесса. Предположим, что схемы для функций f(a1, ..., a(k+1), x(k+2), ..., xn) для всевозможных констант a1, ..., a(k+1) ∈ {0, 1} уже построены. В частности, пусть S1 есть схема со входами x(k+2), ..., xn, которая реализует f(a1, ..., ak, 1, x(k+2), ..., xn), и пусть S0 есть схема с теми же входами, которая реализует f(a1, ..., ak, 0, x(k+2), ..., xn). Тогда функцию f(a1, ..., ak, x(k+1), ..., xn) со входами x(k+1), ..., xn можно построить следующим образом. +----+ | | +---+ | S1 |-----| & | | | +-| |-----------+ +----+ | +---+ | +----+ | +---+ +--| \/ | x(k+1) --+-| ~ |--+ +--| |--> +---+ | | +----+ +----+ | +---+ | | | +-| & | | | S0 |--------------| |--+ | | +---+ +----+ Здесь S1 и S0 имеют входы x(k+1), ..., xn, которые разветвляются и идут в каждую из этих двух схем. Таким образом, по сравнению с S1 и S0 добавляются 4 функциональных элемента. Обозначим эту надстройку следующим образом x(k+1) --+ | +----+ | +---+ | | +--| | | S0 |------| 4 |--> | | +--| | +----+ | +---+ | +----+ | | | | | S1 |---+ | | +----+ и будем считать, что входами этой схемы являются x(k+1), x(k+2), ..., xn в этом порядке. Заметим, что на данном шаге у нас имеется 2^k таких схем для каждого набора a1, ..., ak. Из них в последующих шагах собирается одна схема, реализующая f(x1, ..., xn). Рассмотрим пример построения схемы для функции f = (1, 4, 6, 7, 8, 10, 13, 14, 15). Она задается следующей таблицей истинности. x1 x2 x3 x4 f f(a1, a2, x3, x4) f(a1, x2, x3, x4) ------------+-------+-------------------------+-----------------------------0 0 0 0 | 0 | | 0 0 0 1 | 1 x4 | | ------------+-------+ (~x3)x4 \/ x3 & 0 = | 0 0 1 0 | 0 | = (~x3)x4 | 0 0 1 1 | 0 0 | | ------------+-------+-------------------------+ ~(x2)(~x3)x4 \/ x2(~x4 \/ x3) 0 1 0 0 | 1 | | 0 1 0 1 | 0 ~x4 | | ------------+-------+ (~x3)(~x4) \/ x3 & 1 = | 0 1 1 0 | 1 | = ~x4 \/ x3 | 0 1 1 1 | 1 1 | | ------------+-------+-------------------------+-----------------------------1 0 0 0 | 1 | | 1 0 0 1 | 0 ~x4 | | ------------+-------+ (~x3)(~x4) \/ x3(~x4) = | 1 0 1 0 | 1 | = ~x4 | 1 0 1 1 | 0 ~x4 | | ------------+-------+-------------------------+ (~x2)(~x4) \/ x2(x4 \/ x3) 1 1 0 0 | 0 | | 1 1 0 1 | 1 x4 | | ------------+-------+ (~x3)x4 \/ x3 & 1 = | 1 1 1 0 | 1 | = x4 \/ x3 | 1 1 1 1 | 1 1 | | ------------+-------+-------------------------+-----------------------------Если строить схему по СДНФ, то для каждого минтерма потребуется от 0 до 4 отрицаний и 3 конъюнкции. Поскольку в СДНФ 9 минтермов, для их соединения нужно 8 дизъюнкций. Общее количество элементов находится между 35 и 71. В таблице также показаны результаты склейки (противоположность разложения) по переменным x2, x3 и x4. Наконец, вся функция есть f(x1, x2, x3, x4) = (~x1)(~(x2)(~x3)x4 \/ x2(~x4 \/ x3)) \/ x1((~x2)(~x4) \/ x2(x4 \/ x3)). С помощью надстройки, которую мы обозначили через 4, для f можно построить следующую схему. +---+ x1 -------------------------| | +---+ | | x2 ------------------| | | | | | | | +---+ +---+ | | | | x3 ---| ~ |--| | | | | | +---+ | & |---| |--| | x4 ----------| | | 4 | | | +---+ | | | | | | | 4 | +----+ | | | | x3 ----------| | | | | | +---+ | \/ |--| | | | x4 ---| ~ |--| | +---+ | | +---+ +----+ | | x2 x4 x3 x4 | | +---+ | | ------------------| | | | +---+ | | | | ----------| ~ |---| | | | +---+ | 4 |--| | +----+ | | +---+ ----------| | | | | \/ |--| | ----------| | +---+ +----+ Здесь на первых шагах (при склейке по x3 и x4) мы использовали следующие упрощения. x0 = 0 x1 = x 0 \/ x = x ~xy \/ xy = y ~xy \/ x = y \/ x ~x \/ xy = ~x \/ y Также входы x2, x3, x4 показаны несколько раз, так как их разветвление усложнило бы схему. В этой схеме 6 + 3*4 = 18 элементов, что меньше количества при построении схемы непосредственно по СДНФ.