Геометрическое представление логических функций
Обозначим через Еn множество всех наборов (α1,..., αη), состоящих из чисел ноль и единица. Множество Еn называется n -мерным кубом, а набор (α1, ..., αη) - вершинами куба. Пусть σ1, ..., σr- фиксированный набор чисел из 0 и 1. Множество всех вершин (α1,..., αη) куба Еn таких, что αi1 = σ1, αi2 = σ2, ... , αir = σr, 1 < i1 < i2 < ...< ir, называется (n – r)- мерной гранью. Очевидно, что (n – r)-мерная грань является (n – r) - подкубом куба Еn. Например, в трехмерном кубе Е3 наборы (0,0,1) и (0,0,0) образуют одномерную ( n = 3, r = 2) грань (ребро), а наборы (1,0,0), (1,0,1), (1,1,0), (1,1,1) - двухмерную грань. Пусть f(X1,X2,…,Xn) - произвольная булева функция. Ей сопоставляется в соответствие подмножество Νf вершин куба Еn, таких что (α1, ..., αη) Nf тогда и только тогда, когда f(α1, ..., αη) = l Очевидно, что по подмножеству Nf исходная функция f(X1, X2., ... , Χn) восстанавливается однозначно. Таким образом геометрический способ задания булевой функции заключается в задании множества вершин n -мерного куба Еn, в которых данная функция истинна. Пример 8. Пусть функция f(X1, X2, Х3) задана табл. 4. Составить для нее множество Nf. Таблица 4
Решение. Очевидно, что Nf = {(0,0,0), (1,0,0), (1,0,1), (1,1,0), (1,1,1)}. Множество Nf изображено на рис. 3. Напомним [1], что для любой булевой функции существует ее представление в СДНФ. Причём в алгоритме построения СДНФ используется только те наборы значений, при которых функция равна единице [3]. Это позволяет проинтерпретировать геометрическое представление функции следующим образом. Рассмотрим трёхмерный куб и занумеруем вершины так, как показано на рис. 4.
Тогда его грани (двумерные подкубы) можно рассматривать как
Ребрами данного куба ( одномерными подкубами) будут, например, , и т.д. Пример 9. Построитьмодель куба, соответствующего функции: . Решение. Первому слагаемому соответствует вершина 2, второму – вершина 6, третьему – вершина 3, четвертому – вершина 8, пятому – вершина 4 (рис. 5). Пример 10. Дана модель куба с помеченными вершинами (рис. 6). Составить СДНФ для данной булевой функции Решение. Вершине 1 соответствует конъюнкция , вершинам 3 и 4 конъюнкция и соответственно; вершинам 5 и 6 - конъюнкции и . Следовательно, искомая СДНФ имеет вид . Заметим, что для функций, зависящих от четырёх и более переменных, геометрическое представление применяется очень редко, т.к. трудно построить наглядную модель n-мерного куба при n > 3. Поэтому в этом и следующих параграфах мы будем рассматривать только булевы функции трех аргументов, хотя все изложенное справедливо для других функций, зависящих от большого числа аргументов. Перейдем теперь к геометрической постановке задачи минимизации булевых функций.
Популярное: Почему стероиды повышают давление?: Основных причин три... Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (337)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |