Определенные конституанты отличаются друг от друга более чем В одном разряде. 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Определенные конституанты отличаются друг от друга более чем В одном разряде.



Учитывая, что в двоичных наборах 0 соответствует , а 1 соответствует , и прочерк (-) означает, что множество, соответствующие этому разряду, в пересечение отсутствует, объединяем полученные двоичные наборы (конституанты). Тем самым мы получим сокращенное множество:

2 этап. Построение минимального множества M min сводится к покрытию двумерной таблицы Квайна.

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

Строим таблицу Квайна. В ней столбцами являются заданные конституанты, а строками – конституанты, полученные после объединения заданных конституант:

Новые конституанты Конституанты
         
-00          
1-0          
11-          
-11          

Каждая конституанта строки после подстановки вместо прочерка нуля сравнивалась с конституантами столбцов. Если существует столбец с такой же конституантой, то на пересечении рассматриваемых строки и столбца ставилась единица. После этого в той же конституанте строки вместо прочерка ставилась единица и проводилась аналогичная процедура сравнения.

Если в таблице покрытий Квайна удалить вторую строку сверху, то покрытие столбцов строками будет осуществляться, т.к. в каждом столбце будет по крайней мере одна единица.

Если дополнительно удалить еще одну строку, например, третью сверху, то покрытия не будет, т.к. третий столбец не будет иметь ни одной единицы.

Если удалить в таблице одну третью строку сверху, то покрытие столбцов строками будет осуществляться.

Удаляя строки, не влияющие на покрытие столбцов строками, и объединяя оставшиеся новые конституанты, получим минимальное множество M min.

В нашей задачи таких множеств будет два. Удаляем вторую строку сверху, тогда

Удаляем третью строку сверху, тогда

Для определения сложности заданного множества M запишем его аналитическое выражение

Тогда L(M) = 15,

Дальнейшее уменьшение сложности выражения, определяющее заданное множество, возможно с использованием скобок. Используя закон дистрибутивности пересечения относительно объединения, получим

В этом случае

Пример 4. В трехмерном пространстве J = {M1,M2,M3} задано множество

Минимизировать данное множество методом Квайна.

Определить сложность заданного множества и минимизированного множества.

Построим гиперкуб, соответствующий заданному множеству M. Он изображен на рис.3.3.

Рис.3.3

1. Найдем M сокр. Для этого определим объединение конституант, соответствующих соединенным ребрам заштрихованным вершинам гиперкуба:



Поделиться:


Последнее изменение этой страницы: 2017-01-19; просмотров: 131; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 44.200.101.170 (0.012 с.)