X-PDF

Кубическое задание функций алгебры логики

Поделиться статьей

Как следует из рассмотренного выше, функция алгебры логики (булева функция) может быть задана:

§ аналитически (системой булевых функций) .

§ словесным описанием .

§ таблицей истинности .

§ картами (диаграммами) Венна, Вейча, Карно .

§ логической схемой.

Более компактной формой записи функций алгебры логики является форма, когда вместо полного перечисления всех конъюнкций (дизъюнкций) используют номера наборов, на которых функция принимает единичное значение. Так, например, форма записи f(x1x2x3)=V F(0,2,3) означает, что функция от трех переменных принимает единичное значение на 0, 2 и 3 наборах таблицы истинности. Такая форма записи называется числовой.

Некоторые методы минимизации ориентируются на задание булевой функции в виде кубического покрытия. При этом логическая функция удобно интерпретируется с использованием ее геометрического представления. Так, функцию двух переменных можно интерпретировать как плоскость, заданную в системе координат х1х2. Получится квадрат, вершины которого соответствуют комбинациям переменных. Для геометрической интерпретации функции трех переменных используется куб, заданный в системе координат х1х2х3 .

Новое представление булевой функции получается путем отображения булевой функции n переменных на n-мерный куб (n-куб).

Для отображения булевой функции n переменных на n-кубе устанавливается соответствие между членами СДНФ и вершинами n-куба. На n-кубе определим координатную систему с координатами (e1,……,en), ei=0,1.

Установим соответствие между членом СДНФ x1e1 x2e2… xnenи некоторой вершиной e1,e2,….,en куба. При этом xiei= xi, если ei=1, и xiei= xi, если ei=0.

 
 

Рис.23. Геометрическое представление функции двух и трех переменных

Каждый набор при кубическом задании ФАЛ называется кубом.

Как следует из таблицы истинности (табл. 14), функция f определена на трех группах наборов переменных: L={3,4,5,6,7}, D={0,2} и N={1}.

Конъюнкции максимального ранга (конституенты единицы) принято называть 0-кубами. Множество 0-кубов образуют кубический комплекс

Таблица 14
  х1 х2 х3 f
         
       
         
         
         
         
         
         

011

К0 = 101.

Над 0-кубами, кодовое расстояние которых равно 1, выполняется операция склеивания, в результате которой образуются новые кубы, содержащие свободные координаты. Свободная (независимая) координата может принимать как нулевое, так и единичное значение, остальные компоненты называются связанными. Куб, содержащий свободные координаты, покрывает кубы, на которых он образован. Куб с одной независимой координатой х называется кубом первой размерности и в геометрическом представлении это ребро, покрывающее обе вершины. Кубы, образующиеся в результате последовательного выполнения операции склеивания, назовем r-кубами, где r – размерность полученного куба.

 
 

Геометрическая интерпретация сказанного приведена на рис. 24. В результате склеивания кубов 101 и 111 (0-кубы, вершины) образован 1-куб 1×1 (ребро), а 1-кубов 00x и 10х — 2-куб х0х (грань).

Рис. 24. Образование новых кубов

Кубическое представление ФАЛ позволяет обойтись тремя переменными 0,1,х вместо х1, х2,…,хn .

Количество свободных координат в кубе определяет его размерность r, чем i-го куба. больше r, тем больше свободных координат и тем меньше входов будет иметь реализующая его схема (логический элемент).

Цена схемы определяется количеством входов элементов, используемых для ее реализации:

,

Представленная информация была полезной?
ДА
58.69%
НЕТ
41.31%
Проголосовало: 1070

где k − количество полученных кубов . n-ri − количество единичных и нулевых значений

Два r-куба могут образовать r+1-куб, если в этих r-кубах все координаты, в том числе и свободные, совпадают, за исключением лишь какой-либо одной, которая в этих кубах имеет противоположное значение.

 
 

На рис. 25 приведено изображение куба, соответствующего булевой функции от четырёх переменных (гиперкуб).

Рис. 25. Геометрическое представление функции четырех переменных

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

Метод Квайна −Мак-Класки

Этот метод ориентирован на числовое задание ФАЛ в виде кубического комплекса, состоящего из 0-кубов. Метод представляет собой формализованный на этапе нахождения простых импликант метод Квайна. Основной недостаток метода Квайна – необходимость выполнения полного сравнения (склеивания) всех первичных импликант. В случае большого их количества сложность этого сравнения существенно возрастает. В рассматриваемом методе все исходные n-кубы разбиваются на непересекающиеся подгруппы по количеству единиц в кубе. Пусть, например, задана функция

f СДНФ(x1x2x3x4) = V (2, 3, 4, 6, 9, 10, 11, 12).

Сформируем кубический комплекс K, состоящий из 0-кубов:

K=(0010, 0011, 0100, 0110, 1001, 1010, 1011, 1100).

Выполнив разбиение комплекса K на группы, получим:

, , .

Попарное сравнение можно проводить только между соседними по номеру группами кубов, так как кубы, порождающие новые кубы, должны иметь кодовое расстояние, равное 1. В результате сравнения кубов получим:

, .

После выполнения первого шага алгоритма простых импликант не выявлено. Полученные 1-кубы разобьем на n групп кубов в зависимости от местоположения свободной координаты в кубе.

, , , .

Далее выполняется сравнение кубов внутри каждой из групп. В результате могут быть получены 2-кубы, которые, в свою очередь, аналогично 1-кубам будут объединены в группы по совпадению свободных координат и вновь будет выполнено сравнение. На каждом шаге сравнения выявляются кубы, не участвовавшие в образовании новых кубов, и исключаются из дальнейшего упрощения. Для рассматриваемого примера сравнение в группах привело к образованию двух новых кубов х01х и х01х и кубов, не образовавших новых {х100, 0х10, 10х1, 01х0}.

, .

Дальнейшее сравнение не приводит к формированию новых кубов . Таким образом, получено множество простых импликант:

fсокр.ДНФ={х100, 0х10, 10х1, 01х0, х01х}.

Далее аналогично методу Квайна строится импликантная таблица (табл.15). Формирование минимального покрытия сводится к выявлению обязательных простых импликант и построению на их основе тупиковых форм.

Таблица 15

  Простые импликанты Конституенты единицы  
                   
  Х100   *   *          
  0х10 *       *        
  10х1           *   *  
  01х0   *     *        
  Х01х *   *       * *  

Из таблицы следует, что простые импликанты x100, 10×1, x01x являются обязательными. Оставшиеся две простые импликанты не являются обязательными и образуют следующие две тупиковые формы.

f МДНФ = {х100, 10х1, х01х, 0х10} – 1-я тупиковая форма .

f МДНФ = {х100, 10х1, х01х, 01×0} – 2-я тупиковая форма.


Поделиться статьей
Автор статьи
Анастасия
Анастасия
Задать вопрос
Эксперт
Представленная информация была полезной?
ДА
58.69%
НЕТ
41.31%
Проголосовало: 1070

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram

ОБРАЗЦЫ ВОПРОСОВ ДЛЯ ТУРНИРА ЧГК

Поделиться статьей

Поделиться статьей(Выдержка из Чемпионата Днепропетровской области по «Что? Где? Когда?» среди юношей (09.11.2008) Редакторы: Оксана Балазанова, Александр Чижов) [Указания ведущим:


Поделиться статьей

ЛИТЕЙНЫЕ ДЕФЕКТЫ

Поделиться статьей

Поделиться статьейЛитейные дефекты — понятие относительное. Строго говоря, де­фект отливки следует рассматривать лишь как отступление от заданных требований. Например, одни


Поделиться статьей

Введение. Псковская Судная грамота – крупнейший памятник феодального права эпохи феодальной раздробленности на Руси

Поделиться статьей

Поделиться статьей1. Псковская Судная грамота – крупнейший памятник феодального права эпохи феодальной раздробленности на Руси. Специфика периода феодальной раздробленности –


Поделиться статьей

Нравственные проблемы современной биологии

Поделиться статьей

Поделиться статьейЭтические проблемы современной науки являются чрезвычайно актуальными и значимыми. В связи с экспоненциальным ростом той силы, которая попадает в


Поделиться статьей

Семейство Первоцветные — Primulaceae

Поделиться статьей

Поделиться статьейВключает 30 родов, около 1000 видов. Распространение: горные и умеренные области Северного полушария . многие виды произрастают в горах


Поделиться статьей

Вопрос 1. Понятие цены, функции и виды. Порядок ценообразования

Поделиться статьей

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


Поделиться статьей

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram
Заявка
на расчет