A) элементтері болса 14 страница

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

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

Идея ещё одного приема получения более минимальной функции из тупиковой минимальной ДНФ сводится к выявлению одинаковых фрагментов в функции и исключению их повторения. Такой процедурой осуществляется оптимизация структуры функции с целью уменьшения общего числа операций логической функции. Данный подход назовём структурной оптимизацией логической функции.

Структурная оптимизация может осуществляться с помощью двух видов действий.

1. Вынесение за скобки одинаковых фрагментов логической формулы.

2. Создание системы логических функций эквивалентной исходной функции.

Покажем исполнение этих действий на примерах.

 

Пример 2.5.23.

Пусть задана тупиковая форма в виде следующей логической функции

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

Заметим, что исходную функцию составляют 17 операций, в полученном результате остаётся только 8.

Пример 2.5.24.

Пусть задана тупиковая форма в виде следующей логической функции

Выражения в скобках связаны между собой. Для выявления этой связи осуществим следующее преобразование. Здесь были использованы первая аксиома булевой алгебры, закон де Моргана и раскрытие скобок.

Теперь построим систему, эквивалентную заданной функции.

Исходная функция содержит 20 операций, система – только 10.

Пример 2.5.24 демонстрирует часто встречающийся случай связи между отдельными частями логического выражения, которая позволяет аналитически сконструировать одинаковые фрагменты функции.

 

 

Возможность выявления при минимизации одинаковых фрагментов логических функций, показанная в (п. 2.5.6.), применима и для минимизации систем логических функций.

Пример 2.5.25.

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

Введём дополнительные операции.

, подставим их в систему и вынесем одинаковые множители за скобки.

где

Каждое из исходных уравнений являлось тупиковой формой. Система в целом содержала 40 операций. Преобразованная система вместе с расшифровкой введённых дополнительных переменных содержит только 22 операции.

Существует также возможность в системе логических функций минимизировать только одну функцию, а все остальные функции выражать через минимизированную. Вот классический пример такого подхода.

Пример 2.5.28. Задана система функций { y1, y2} в табличной и аналитической формах.

x1 x2 x3 y1 y2  
y1 = y2 = 0
y1 = y2 = 1

 

Функция y1 не минимизируется. Минимизация функции y2 даёт следующий результат.

Функцию y2 принимаем в качестве опорной. Выразим y1 в функции от y2. Из таблицы истинности следует, что имеют место три варианта зависимости

y1 = y2 = 0, , y1 = y2 = 1.

Поэтому, можно записать

 


3. Представление логических функций на

физических носителях.

Таблица 3.1.1
Операция Ранг Условное обозначение
НЕ Ø , ‾.
И Ù,&, · , без знака.
ИЛИ Ú, + .

Основа, на которой строится формальная запись логической функции, может быть различной. Напомним, что в алгебре логики конструкция записи функций определяется условными обозначениями логических операций и их рангами (Таблица 3.1.1). Такое описание функций называется аналитическим. Это достаточно подробно описано в п.п 1.4 и 1.5.

В прикладном плане, на стадиях конструирования логических схем, оказывается более удобным блочное представление функций. Удобство состоит в том, что каждому блоку соответствует реальный физический элемент. Основа, на которой он создаётся, может быть различной. В принципе, существуют механические, пневматические, релейно-контактные и электронные логические элементы. Предпоследний и особенно последний тип элементов получили наибольшее распространение. Далее следует краткое описание общих правил построения логических схем на электронных (п. 3.1) и релейно-контактных (п. 3.2) элементах.

 

3.1 Построение логических схем на микроэлектронных

элементах.

На рисунке 3.1.1 приведено сопоставление блочного и аналитиче­ского представления логических функций для базиса булевой алгебры. Эти функции положены в основу построения более сложных функций как в ана­литическом так и в блочном исполнениях. Логические элементы блочного типа являются электронными схемами, построенными на микроэлементах. Эти схемы называются микросхемами. Пример упрощённых микросхем,