Восстановление булевой функции по изображающему числу ⇐ ПредыдущаяСтр 2 из 2
Рассмотрим методы, позволяющие переходить от задания булевой функции в виде изображающего числа к явному выражению ее через элементы. Дизъюнктивная нормальная форма (ДНФ). Пусть имеется множество, состоящее из n элементов А1 ..., Аn. Произведение вида Совершенная дизъюнктивная нормальная форма (СДНФ) булевой функции — сумма элементарных произведений. Чтобы по данному изображающему числу восстановить булеву функцию в СДНФ, нужно суммировать элементарные произведения, изображающие числа которых имеют единицы в тех же разрядах, что и изображающее число булевой функции. Например, 1001 0110 имеет единицы в разрядах 0, 3, 5, 6, поэтому Конъюнктивная нормальная форма (КНФ). Элементарными суммами для лnэлементов А1 ..., Аn называются суммы вида
Конъюнктивная нормальная форма булевой функции представляет собой произведение элементарных сумм. Для того чтобы написать булеву функцию, соответствующую данному изображающему числу в КНФ, необходимо перемножить элементарные суммы, изображающие числа которых имеют те же 0, что и изображающее число булевой функции. Например, число 1001 0110 имеет 0 в разрядах 1, 2, 4 и 7, поэтому 1001 0110 = Булевы уравнения
Решение многих задач, связанных с распознаванием образов, может быть сведено к решению булевых алгебраических уравнений с одним (или более) неизвестными. Примером булева уравнения с одним неизвестным может служить соотношение X&(A+B)≡A&B&C, где X — некоторая булева функция, зависящая от А, В,С, такая, чтобы в результате подстановки Х(А, В, С) в уравнение оно обращалось в тавтологию.
Перейдем от элементов X, А, В, С к их изображающим числам. Относительно базиса b [А, В, С] найдем #А=00000001; #(A+B)=01110111 и, следовательно, #Х должно быть таким, чтобы выполнялось равенство
#X&(0111 0111) ≡00000001.
Представим #X=(x0x1x2x3x4x5x6x7x8). Для каждой компоненты этого вектора получим отдельное уравнение, беря исходные данные построчно:
Отсюда находим:
x0&0=0. Поскольку любое из чисел в конъюнкции с нулём даст 0, то x0 может быть любым, и мы будем обозначать это, как x0=*. Далее, x1&1=0. Только x1=0 может дать такой результат. Аналогичное решение получается для x2, x3, x5 и x6. Решение для x4 получается так же, как и для x0, а в случае x7 мы будем иметь x7&1=1, откуда x7=1. Общее решение уравнения запишем в виде изображающего числа X:
#X=[*000*001].
Таким образом, рассматриваемое уравнение имеет четыре решения, соответствующие изображающим числам 0000 0001, 00001001, 10000001 и 10001001, которым соответствуют 4 логических функции
(здесь мы вернулись к общепринятым обозначениям дизъюнкции и конъюнкции).
Уравнение в виде импликации всегда можно записать как соотношение эквивалентности, например, вместо приведённого выше уравнения можно было бы написать Существуют также уравнения, которые вообще не имеют решений, например
©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|