Мегаобучалка Главная | О нас | Обратная связь


Геометрическое представление логических функций



2019-12-29 325 Обсуждений (0)
Геометрическое представление логических функций 0.00 из 5.00 0 оценок




 

Обозначим через Е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

X1 X2 X3 f(X1, X2, Х3)
0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 1
0 1 1 0
1 0 1 1
1 1 0 1
1 1 1 1

Решение. Очевидно, что Nf = {(0,0,0), (1,0,0), (1,0,1), (1,1,0), (1,1,1)}. Множество Nf  изображено на рис. 3.

Напомним [1], что для любой булевой функции существует ее представление в СДНФ. Причём в алгоритме построения СДНФ используется только те наборы значений, при которых функция равна единице [3]. Это позволяет проинтерпретировать геометрическое представление функции следующим образом. Рассмотрим трёхмерный куб и занумеруем вершины так, как показано на рис. 4.

Рис. 4

 

Тогда его грани (двумерные подкубы) можно рассматривать как

 

Ребрами данного куба ( одномерными подкубами) будут, например, , и т.д.

Пример 9. Построитьмодель куба, соответствующего функции:

.

Решение. Первому слагаемому соответствует вершина 2, второму – вершина 6, третьему – вершина 3, четвертому – вершина 8, пятому – вершина 4 (рис. 5).

Пример 10. Дана модель куба с помеченными вершинами (рис. 6). Составить СДНФ для данной булевой функции

Решение. Вершине 1 соответствует конъюнкция , вершинам 3 и 4 конъюнкция  и  соответственно; вершинам 5 и 6 - конъюнкции  и . Следовательно, искомая СДНФ имеет вид

    .

Заметим, что для функций, зависящих от четырёх и более переменных, геометрическое представление применяется очень редко, т.к. трудно построить наглядную модель n-мерного куба при n > 3. Поэтому в этом и следующих параграфах мы будем рассматривать только булевы функции трех аргументов, хотя все изложенное справедливо для других функций, зависящих от большого числа аргументов.

Перейдем теперь к геометрической постановке задачи минимизации булевых функций.




2019-12-29 325 Обсуждений (0)
Геометрическое представление логических функций 0.00 из 5.00 0 оценок









Обсуждение в статье: Геометрическое представление логических функций

Обсуждений еще не было, будьте первым... ↓↓↓

Отправить сообщение

Популярное:
Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы...
Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние...



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (325)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.006 сек.)