Лабораторный практикум № 1. дискретка. Отображения. Обратные отображения эта тема является очень важной, терминами из этой темы мы будем пользоваться во многих других вопросах
 Скачать 86.29 Kb.
|
|
13. ФОРМУЛА ВКЛЮЧЕНИЙ-ИСКЛЮЧЕНИЙ Пусть у нас есть несколько множеств A1, A2, ..., Ak, которые попарно пересекаются (попарно пересекаются - это значит, что, любые два множества, которые вы возьмёте, будут пересекаться). В нашем случае k = 3. Тогда у этих множеств образуется множество элементов, которое принадлежит общему пересечению всех множеств (здесь это множество обозначено как g). Формула включений-исключений позволяет найти мощность множества элементов, находящихся в объединении всех множеств, если известны мощности множеств A1, A2, ..., An и мощности попарных пересечений этих множеств, пересечений по три множества и тд. То есть, если опираться на этот пример, то формула включений-исключений позволяет найти количество элементов в a+b+c+d+e+f+g, если известно количество элементов в остальных всевозможных областях. Мы будем использовать очень много пересечений в этой формуле. Мы можем брать наши множества А1, А2, ..., Аn по одиночке (на рисунке это Х = a+b+g+f, Y = b + c+ d + g, Z = d + e + f + g), затем брать все области, где какие-то два множества пересекаются (на рисунке это b+g, d+g, f+g), затем брать все области, где какие-то 3 множества пересекаются и тд. (на рисунке это просто g). Обозначим за m1 сумму мощностей множеств, взятых по одному; m2 - сумму мощностей попарных пересечений множеств; m3 - сумму мощностей пересечений множеств по 3 и тд. Математически это записывается так: m1 = ∑ |𝐴 𝑛 𝑖=1 i | m2 = ∑ | 𝑖<𝑗 14. Ф.А.Л. СУЩЕСТВЕННОСТЬ ПЕРЕМЕННЫХ Теперь переходим к следующему разделу – алгебра логики. Чтобы дальше изучать темы в этом разделе, понадобятся на данном этапе следующие объекты и понятия: 1) Множество 𝐸2 = {0, 1} 2) Множество 𝐸2 𝑛 – множество всех двоичных наборов длины n (запись похожа на количество сочетаний или размещений, но к комбинаторике это никакого отношения не имеет) 3) Множество 𝑃2 – множество всех функций алгебры логики 4) Функцией алгебры логики называется всякое отображение вида 𝑓: 𝐸2 𝑛 → 𝐸2 То есть, если мы построим, например, для n = 2 какое-нибудь отображение 𝐸2 𝑛 → 𝐸2: x1 x2 f(x1, x2) 0 0 0 0 1 0 1 0 0 1 1 1 то мы получим отображение всех двоичных наборов длины 2 в определённую последовательность нулей и единиц. Это и будет называться функцией, и в данном случае здесь представлена конъюнкция. Сразу в этой теме хочется дать определение формулы. Пусть есть некоторое множество функций алгебры логики B ⊆ P2. Тогда 1. Если 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ) B, то запись 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ) является формулой над B. 2. Пусть 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ) B и A1 , . . . , An это либо формулы над B, либо обозначения переменных. Тогда запись 𝑓(𝐴1,𝐴2, … , 𝐴𝑛 ) формула над B. 3. Никакие другие записи не являются формулами над B. Примером формулы над множеством элементарных функций является следующая запись: U = ((x1&x2) ((x3) x2)). Здесь, к примеру, f - , A1 = (x1&x2), A2 = x3 x2. Отсюда U = 𝑓(𝐴1, 𝐴2 ). То есть, можно сказать, что формула – это то, что мы видим перед собой. Функцией же, представляющей эту формулу, будет являться множество значений, получаемых при подстановке определённых двоичных наборов в выражение. Формула, можно сказать, это как сложная функция. То есть если есть например функции y = sin(x), y = x^3, y = log2x, то сложная функция (формула) будет, например, 𝑦 = 𝑙𝑜𝑔2(𝑠𝑖𝑛3 (𝑥)). Это и есть некоторая ассоциация функции и формулы. Только здесь пример с одной переменной, а переменных может быть много. Формулой над множеством элементарных функций будет являться именно запись. Функцией будет являться отображение 𝑓: 𝐸2 𝑛 → 𝐸2, то есть те значения, которые получаются при подстановке двоичных наборов. Рассмотрим теперь такое понятие, как существенность переменных. Если у нас есть набор из n переменных x1, x2, …, xn, то будем обозначать фиксированные наборы этих переменных как 𝜎1, 𝜎2, …, 𝜎n. В примере ниже у нас есть 8 наборов переменных x1, x2, x3, каждый из них можно обозначить за 𝜎1, 𝜎2, …, 𝜎n (n = 3). Рассмотрим пример. Пусть у нас есть ФАЛ, к примеру, от трёх переменных, с табличным заданием x1x2x3 f(x1, x2, x3) 000 1 001 1 010 0 011 0 100 0 101 0 110 0 111 0 Рассмотрим в ней, например, переменную x1. Возьмём какие-то наборы, которые отличаются лишь значением x1 (у нас это 101 и 001). Мы видим, что значения функции на этих наборах разные. Переформулируем чуть по-другому: мы видим, что существует хотя бы один набор переменных x2 и x3 𝜎2 , 𝜎3 (в данном случае это набор 01), который меняет своё значение, если меняет своё значение переменная x1. В этом случае говорят, что x1 - существенная переменная. Также можно заметить, что при одинаковых наборах переменных x1 и x2 и соответствующих произвольных значениях переменной x3 функция не меняет своё значение. Другими словами, для всех наборов 𝜎1, 𝜎2 при произвольных значениях переменной x3 функция не будет менять своё значение. В этом случае говорят, что x3 - несущественная переменная. Теперь поговорим не про 3 переменные, а про n переменных. Определения существенной и несущественной переменной довольно громоздкие, но идея несложная. Переменная xi функции 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛) называется существенной переменной этой функции, если ∃𝛿1, 𝛿2, …, 𝛿i-1, 𝛿i+1,…, 𝛿n (f(𝜎1, 𝜎2, …, 𝜎i-1, 0, 𝜎i+1,…, 𝜎n) ≠ f(𝜎1, 𝜎2, …, 𝜎i-1, 1, 𝜎i+1,…, 𝜎n)). То есть, если хотим проверить переменную xi на существенность, то мы должны посмотреть на наборы, которые отличаются только значениями переменной xi и проверить, меняется ли значение функции на этих наборах. Если хотя бы на одном наборе меняется, то переменная xi - существенная. Если на всех наборах (это очень важно), отличающихся между собой только значением переменной xi функция не меняет своё значение, то переменная xi – несущественная. Определение несущественной переменной: Переменная xi функции 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛) называется несущественной переменной этой функции, если ∀𝜎1, 𝜎2, …, 𝜎i-1, 𝜎i+1,…, 𝜎n (f(𝜎1, 𝜎2, …, 𝜎i-1, 0, 𝜎i+1,…, 𝜎n) = f(𝜎1, 𝜎2, …, 𝜎i-1, 1, 𝜎i+1,…, 𝜎n)). Теперь о количестве функций алгебры логики. Всего в табличном задании функции алгебры логики от n переменных существует 2n строк (каждая строка – определённый двоичный набор длины n). Но, подставляя любой произвольный набор в функцию, может получиться 2 значения: 0 или 1. И так для каждого набора. Но всего наборов столько же, сколько и строк (2n ). А функция представляет собой некое множество нулей и единиц. Например, если рассмотрим функцию от трёх переменных: x1x2x3 f(x1, x2, x3) 000 0 (1) 001 0 (1) 010 0 (1) 011 0 (1) 100 0 (1) 101 0 (1) 110 0 (1) 111 0 (1) то в каждой из 8 = 2^3 строк может быть два варианта значений: 0 или 1. А количество функций от трёх переменных равно количеству множеств значений в столбце значений функции. Поэтому всего функций от трёх переменных 2*2*…*2 (8 раз) = 2 8 = 2 2 3 = 64. С количеством функций от n переменных та же ситуация, только их не 2 2 3 , а 2 2 𝑛 (просто стоит провести те же рассуждения, только не с цифрой 3, а с буквой n). Поэтому мы можем сказать, что мощность множества всех функций алгебры логики от n переменных (мощность 𝑃2 𝑛 ) равна 2 2 𝑛 . Теперь про глубину формулы. Пусть U – формула над B ⊆ P2. Глубиной формулы U называется число, значение которого определяется по правилам: 1) Если x – символ переменной, то d(x) = 0 2) Если U = f(A1,…,An), то d(U) = max(d(Ai)) + 1, i = 1, 𝑛 Здесь можно привести аналогию, например, с обычными функциями. Например, есть функция g(f(x), h(r(t))). Здесь х, t – независимые переменные, поэтому их глубину принято считать за 0. Функция f же зависит от х, а функция r – от t, поэтому их глубина равна глубине аргумента + 1, то есть 0 + 1 = 1. Глубина h аналогично равна 1 + 1 = 2. Глубина g будет равна максимальной из глубин входящих в неё аргументов (то есть f и h) + 1. В данном случае максимальная глубина у h, поэтому глубина g равна 2 + 1 = 3. Глубина формулы понадобится в дальнейших темах. 17. РАЗЛОЖЕНИЕ Ф.А.Л. ПО ПЕРЕМЕННЫМ Нам понадобятся умения представлять функции в самых различных видах. Формула разложения ф.а.л. по переменным нам это поможет сделать. Перед тем, как перейти к формуле разложения ф.а.л. по переменным, нужно ввести несколько понятий. 1) Нам понадобится функция 𝑥 𝜎 . Если представлять её через привычные нам конъюнкцию, дизъюнкцию и отрицание, то это равно 𝑥&𝜎 𝑉 𝑥&𝜎, или же x ≡ 𝜎. То есть она принимает значение 1, если 𝑥 = 𝜎, и значение 0, если 𝑥 ≠ 𝜎. Также, если 𝜎 = 1, то 𝑥 𝜎 = x; если 𝜎 = 0, то 𝑥 𝜎 = 𝑥. 2) Элементарная конъюнкция. Это просто конъюнкция нескольких слагаемых вида 𝑥𝑖 𝜎𝑖 . Это просто новый объект, который понадобится в записи формулы разложения ф.а.л по переменным. У этой конъюнкции количество слагаемых называется рангом. То есть K = xi1^ 𝜎1& xi2^ 𝜎2&…& xir^ 𝜎r – элементарная конъюнкция ранга r (напомню: i означает просто какую-то произвольно выбранную переменную). Элементарных конъюнкций ранга r существует Cn r × 2 r штук, поскольку каждая переменная в конъюнкции (их r штук) принимает 2 значения (0 и 1), а количество способов выбрать r переменных из n равно Cn r . Теперь сама формула. Эту формулу не нужно выводить, но нужно уметь её доказывать. Она выглядит следующим образом: 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ) = ⋁ (𝑥1 𝜎1& 𝑥2 𝜎2& … &𝑥𝑚 𝜎𝑚 (𝜎 &𝑓(𝜎1, 𝜎2, … , 𝜎𝑚, 𝑥𝑚+1, … , 𝑥𝑛)) 1,𝜎2,…,𝜎𝑚) Это формула разложения ф.а.л. по m переменным. Суть в том, что функция представляется в виде дизъюнкции конъюнкций, а слагаемых будет ровно столько, сколько существует различных двоичных наборов длины m, то есть 2^m. Например, если m = 2, то слагаемых и наборов будет 2^2 = 4: 00, 01, 10, 11. Сами конъюнкции представляют собой произведение элементарной конъюнкции ранга m и значения функции f(x1, x2, …, xn), но только с параметрами 𝜎1, 𝜎2, … , 𝜎𝑚 и следующими за ними переменными xm+1,…, xn (то есть первые m параметров – двоичный набор длины m, остальные слагаемые – просто переменные). Разберём пример. Пусть есть функция f(x1, x2, x3). Разложим её по двум переменным x1 и x2. f(x1, x2, x3) = ⋁ (𝑥1 𝜎1& 𝑥2 𝜎2 (𝜎 &𝑓(𝜎1, 𝜎2, 𝑥3)) 1,𝜎2 ) . Поскольку мы раскладываем по двум переменным, то у нас будет 4 набора для x1 и x2: 00, 01, 10, 11. Поэтому будет 4 конъюнкции. Имеем: 𝑓(𝑥1, 𝑥2, 𝑥3 ) = 𝑥1 0&𝑥2 0&𝑓(0, 0, 𝑥3 )𝑉 𝑥1 0&𝑥2 1&𝑓(0, 1, 𝑥3 )𝑉 𝑥1 1&𝑥2 0&𝑓(1, 0, 𝑥3 )𝑉 𝑥1 1&𝑥2 1&𝑓(1, 1, 𝑥3 ) = = 𝑥1 & 𝑥2 & 𝑓(0, 0, 𝑥3 ) 𝑉 𝑥1&𝑥2&𝑓(0, 1, 𝑥3 )𝑉 𝑥1&𝑥2&𝑓(1, 0, 𝑥3 )𝑉 𝑥1&𝑥2&𝑓(1, 1, 𝑥3 ) В общем случае просто разложение не по 2 переменным, а по произвольному количеству переменных (это количество обозначили за m). Доказывается эта формула просто подстановкой произвольного двоичного набора 𝛾1, 𝛾2, … , 𝛾𝑛. Слева получается 𝑓(𝛾1, 𝛾2, … , 𝛾𝑛 ). Осталось доказать, что справа тоже будет 𝑓(𝛾1, 𝛾2, … , 𝛾𝑛 ). Справа при подстановке получается следующее: ⋁ (𝛾1 𝜎1& 𝛾2 𝜎2& … &𝛾𝑚 𝜎𝑚 (𝜎 &𝑓(𝜎1, 𝜎2, … , 𝜎𝑚, 𝛾𝑚+1, … , 𝛾𝑛)) 1,𝜎2,…,𝜎𝑚) . Теперь вспомним, что мы имеем дизъюнкцию конъюнкций. Конъюнкция из m слагаемых принимает значение 1 тогда и только тогда, когда все m слагаемых принимают значение 1. Но у нас слагаемые вида 𝛾𝑖 𝜎𝑖 . А теперь вспомним, когда такая функция принимает значение 1. Для этого просто вспомним начало этой темы: 𝛾𝑖 = 𝜎𝑖 . Остальные конъюнкции будут принимать значение 0. Поэтому получаем 𝑓(𝛾1, 𝛾2, … , 𝛾𝑛 ) = ⋁ (𝛾1 𝛾1& 𝛾2 𝛾2& … &𝛾𝑚 𝛾𝑚 (𝛾 &𝑓(𝛾1, 𝛾2, … , 𝛾𝑚, 𝛾𝑚+1, … , 𝛾𝑛)) 1,𝛾2,…,𝛾𝑚) = 𝑓(𝛾1, 𝛾2, … , 𝛾𝑚, 𝛾𝑚+1, … , 𝛾𝑛 ) = 𝑓(𝛾1, 𝛾2, … , 𝛾𝑛 ), так как данная конъюнкция ранга m принимает значение 1, что и требовалось доказать. Из этой формулы вытекает важное следствие: если подставлять все наборы 𝜎1, 𝜎2, … , 𝜎𝑛 такие, что 𝑓(𝜎1, 𝜎2, … , 𝜎𝑛 ) = 1, то слагаемое в правой части 𝑓(𝜎1, 𝜎2, … , 𝜎𝑛 ) в конъюнкции будет равно 1, поэтому можно переписать наше равенство в следующем виде: 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ) = ⋁ (𝑥1 𝜎1& 𝑥2 𝜎2& … &𝑥𝑛 𝜎𝑛 ) 𝑓(𝜎1,𝜎2,…,𝜎𝑛)=1 Только здесь уже дизъюнкция по наборам 𝜎1, 𝜎2, … , 𝜎𝑛, а не 𝜎1, 𝜎2, … , 𝜎𝑚. Такое представление функции называется совершенной дизъюнктивной нормальной формой (СДНФ). Эта формула позволяет нам сделать вывод, что любую функцию алгебры логики можно представить с помощью трёх операций: конъюнкция, дизъюнкция и отрицание. Но эта формула верна, если функция не принимает значение 0 на всех двоичных наборах. Если функция является тождественным нулём, то эта функция не будет иметь никакой ДНФ. Но оказывается, что и функцию, тождественно равную нулю, можно представить в виде формулы из этих трёх операций (только здесь не будет дизъюнкции): 𝑓(𝑥) = 𝑥&𝑥 (здесь только одна переменная в этой функции, так как тождественный ноль – функция от одной переменной). 18. МИНИМИЗАЦИЯ ДНФ Познакомимся теперь с ещё одним способом представления функции – с помощью дизъюнктивной нормальной формы (ДНФ). Дизъюнктивной нормальной формой (ДНФ) называется всякая D = K1 V K2 V…V KS, где K1, K2, …, KS – разные элементарные конъюнкции произвольных рангов. ДНФ – это просто представление функции с помощью операций конъюнкции, дизъюнкции, отрицания. Сложностью ДНФ D называется число L(D), равное количеству вхождений &, 𝑉. Если ДНФ D и функция 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ) на одинаковых двоичных наборах принимают значение 1, то ДНФ D представляет функцию 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ). Одна и та же функция алгебры логики может представляться различными ДНФ. Например, две ДНФ: U = x2𝑥1&x3 и W = x1&x2&x3 x1&x2&x3 x1&x2&x3 x1&x2&x3 x1&x2&x3 представляют одну и ту же функцию алгебры логики. ДНФ D – минимальная ДНФ для ФАЛ 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ), если: 1) Эта ДНФ представляет функцию 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ): 𝑓𝐷 = 𝑓 2) Сложность этой ДНФ – минимальная из всех ДНФ данной функции: L(D) = min (L(D1)), где 𝑓𝐷1 = 𝑓 (D1 – произвольная ДНФ, представляющая функцию 𝑓). Первое условие важное, и про него не стоит забывать. ТЕОРЕМА. Если 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 )≢ 0, то для этой функции существует минимальная ДНФ. ДОКАЗАТЕЛЬСТВО. 1) Для каждой функции, отличной от тождественного нуля, существует хотя бы одна ДНФ (например, СДНФ, которую мы рассматривали в предыдущей теме). 2) Теперь нам потребуется рассматривать элементы в конъюнкции в виде троичных наборов 𝜎1, 𝜎2, … , 𝜎𝑛 (элемент x может входить в конъюнкцию как x, как x с отрицанием ( 𝑥 ), а может не входить в конъюнкцию). То есть 𝜎𝑖 = { 0, если 𝑥𝑖 входит в 𝐾 1, если 𝑥𝑖 входит в 𝐾 2, если 𝑥𝑖 не входит в 𝐾 Посчитаем количество всевозможных элементарных конъюнкций из n переменных, которые вообще могут быть. На каждое из n мест существует 3 варианта поставить элемент (просто элемент, элемент с отрицанием или вовсе не поставить). Но, если в конъюнкции троичный набор будет выглядеть как 22…2 (двоек n штук), то тогда никакие элементы в эту конъюнкцию не входят и поэтому такой вариант нужно отбросить. Таким образом, элементарных троичных наборов 3 n – 1. Теперь посчитаем количество ДНФ, каждую из которых можно составить 3 n – 1 элементарными конъюнкциями. Каждая ДНФ может состоять из одной конъюнкции, двух конъюнкций, и так далее…, из 3 n – 1 конъюнкций (то есть если мы рассматриваем какое-то множество из 3 n – 1 элементов (конъюнкций), то ДНФ представляет собой некоторое подмножество этих конъюнкций). Иными словами, количество ДНФ равно 𝐶3 n− 1 1 + 𝐶3 n− 1 2 +… + 𝐶3 n− 1 3 𝑛− 1 - 1= (1+1)^(3n – 1) – 1 = 2 3 𝑛− 1 − 1 (вычитаем единицу, так как одно из подмножеств – пустое множество). Здесь мы в очередной раз воспользовались формулой бинома Ньютона. 3) Следовательно, множество ДНФ – конечное и непустое. Последовательно просматривая все ДНФ, составленные из переменных функции f, можно найти такую из них, которая представляет f и имеет минимальную сложность среди всех ДНФ, представляющих f, что и требовалось доказать. Формулы, которые помогают преобразовывать ДНФ и доводить её до минимальной: 1) Правила поглощения: 𝑥&𝑲𝑲 ≡ 𝑲 𝑥 & 𝑲𝑲 ≡ 𝑲 Пример: x1&x2&x3 x2&x3 Здесь x = x1, 𝑲 = x2&x3. В итоге получается просто x2&x3 2) Правило склеивания: 𝑥 & K 𝑥 & K K Пример: 𝑥1&x2&x3𝑥1&x2&x3. Здесь x = x1, 𝑲 = x2&x3. В итоге получается тоже x2&x3 3) Правило обобщённого склеивания: 𝑥 & K1 𝑥 & K2 = 𝑥 & K1 v 𝑥 & K2 v K1 & K2 Пример: 𝑥1&x2&x3𝑥1&x4&x5. Здесь x = x1, K1 = x2&x3, K2 = x4&x5. В итоге получается 𝑥1&x2&x3𝑥1&x4&x5 x2&x3&x4&x5 Первые две формулы доказываются с помощью формулы (A v B) & (A v C) A&(B v C) Третью формулу можно доказать, если подставить х = 1 и х = 0 в это соотношение. Если х = 1, то слева будет К1, а справа К1 v K1&K2, что по правилу поглощения равно К1. Аналогично с х = 0. 19. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ МИНИМАЛЬНОЙ ДНФ Множество двоичных наборов, составляющих 𝐸2 𝑛 , удобно представлять с помощью вершин единичного n-мерного куба. Пусть мы рассматриваем функцию 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ), отличная от тождественного нуля (так как нам нужно её представление в виде ДНФ). Пусть её ДНФ D равна 𝐷 = 𝐾1 𝐾2 … KS (S – количество конъюнкций). Рассмотрим n-мерный куб, в вершинах которого будут все возможные двоичные наборы длины n. В геометрической интерпретации вводятся свои обозначения 𝑁𝑓, 𝑁𝐾𝑖 , 𝑁𝐷. 𝑁𝑓 - множество всех вершин, которые соответствуют двоичным наборам, где функция 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ) принимает значение 1. Аналогично с 𝑁𝐾𝑖 и 𝑁𝐷. То есть 𝑁𝐾𝑖 - множество всех вершин, которые соответствуют двоичным наборам, где конъюнкция 𝐾𝑖 принимает значение 1, 𝑁𝐷 - множество всех вершин, которые соответствуют двоичным наборам, где ДНФ D принимает значение 1. Заметим следующее: так как ДНФ является неким представлением функции 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ), то если взять набор, где ДНФ принимает значение 1, то на этом же наборе и функция будет принимать значение 1 (аналогично с набором, где ДНФ принимает значение 0). Поэтому 𝑁𝑓 = 𝑁𝐷. Это нам понадобится в дальнейшем. Теперь, вспомним, что 𝐷 = 𝐾1 𝐾2 … KS . Рассмотрим произвольную конъюнкцию 𝐾𝑖 из этой ДНФ. Очевидно, что если эта конъюнкция принимает значение 1 на каком-то двоичном наборе, то ДНФ на этом же наборе принимать значение 0 не может, так как дизъюнкция истинна, если хотя бы одно слагаемое истинно, и значит, ДНФ тогда тоже истинна. Поэтому множество 𝑁𝐷 состоит из всех вершин, на которых определённое число конъюнкций принимают значение 1 (то есть, множество вершин двоичных наборов, на которых определённое количество конъюнкций принимает значение 1 совпадает со множеством вершин двоичных наборов, на которых ДНФ принимает значение 1) и математически это записывается так: 𝑁𝑓 = 𝑁𝐷 = ⋃𝑁𝐾𝑖 𝑆 𝑖=1 По-другому можно сказать так: всякая ДНФ, представляющая ФАЛ f, соответствует покрытию множества 𝑁𝑓 множествами 𝑁𝐾𝑖 (i = 1, 2, …, s). Теперь снова рассмотрим произвольную элементарную конъюнкцию из ДНФ ранга r. То есть K = xi1^ 𝜎1& xi2^ 𝜎2&…& xir^ 𝜎r. Конъюнкция составлена из переменных функции 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ). Мы хотим попробовать понять, какие вершины в геометрической интерпретации соответствуют двоичным наборам, на которых эта конъюнкция принимает значение 1. Конъюнкция истинна тогда и только тогда, когда все слагаемые, входящие в неё, истинны. Мы взяли из общего числа переменных (n) несколько ( r ) переменных. Значит, эти r переменных должны принимать значение 1 (слагаемые элементарной конъюнкции, напомню, имеют вид xi^ 𝜎I, а не xi). Было n переменных, взяли r, а значит, осталось n-r. Так как мы имеем n-мерный куб, то мы должны найти в нём такие наборы, чтобы первые r переменных имели фиксированное значение, на котором конъюнкция истинна (иначе она будет ложна), а остальные n-r переменных принимали произвольные значения (так как эта конъюнкция от значений этих n-r переменных не зависит). Каждая переменная может принимать ровно 2 значения, поэтому количество таких наборов, на которых конъюнкция истинна, равно 2*2*…*2 (n-r раз) = 2 n-r . Так как существует всего 2 n-r наборов, на которых эта конъюнкция истинна, то такой конъюнкции будет соответствовать (n-r)-мерная грань n-мерного куба, где все точки этой грани и будут являться точками с двоичными наборами, на которых эта конъюнкция истинна (в (n-r)-мерной грани 2 n-r вершин). Пример. Пусть у нас есть функция 𝑓(𝑥1, 𝑥2, 𝑥3 ) = 𝑥1 → (𝑥2&𝑥3) x3 = x1 𝑥2&𝑥3 x3. Рассмотрим элементарную конъюнкцию ранга 2 (обозначим её как 𝐾𝑖 ): 𝐾𝑖 = 𝑥2&𝑥3. Она принимает значение 1 при x2 = x3 = 1, а переменная x1 может принимать и 0, и 1, так как эта конъюнкция не зависит от этой переменной. Поэтому в трёхмерном кубе нам будут удовлетворять вершины (для этой конъюнкции) 011 и 111. Для этой конъюнкции это и есть элементы множества 𝑁𝐾𝑖 . А самой конъюнкции будет соответствовать (n-r) = (3-2) = 1-мерная грань (то есть ребро куба, отрезок с началом и концом в этих вершинах). Поэтому между гранями n-мерного куба разной размерности и элементарными конъюнкциями разных рангов существует биективное соответствие. А именно элементарной конъюнкции ранга r K = xi1^ 𝜎1& xi2^ 𝜎2&…& xir^ 𝜎r соответствует (nr)-мерная грань n-мерного куба с вершинами (наборами), где эта конъюнкция принимает значение 1. Заметим теперь следующее. K = xi1^ 𝜎1& xi2^ 𝜎2&…& xir^ 𝜎r. Чем меньше слагаемых мы берём в конъюнкцию (r), тем больше у нас остаётся (n-r увеличивается), а значит, тем больше размерность грани, которой соответствует эта конъюнкция. А значит, запись конъюнкции будет тем меньше, чем больше размерность грани, соответствующей ей. То есть если взять конъюнкции К1 и К2 и причём запись К1 короче записи К2, то 𝑁𝐾1 > 𝑁𝐾2. |