2 канонические формы. Две канонические формы алгебраической записи логической функции

• Название: Две канонические формы алгебраической записи логической функции
• Дата: 27.03.2019
• Размер: 115.45 Kb.
• Имя файла: 2 канонические формы.docx
• Тип: Документы; #71675
• страница: 2 из 3

Постановка задачи. Способы минимизации

При построении цифрового устройства, выполняющего логическую функцию, заданную некоторым аналитическим выражением (либо таблицей истинности), возникает необходимость ее преобразования с целыо приведения к виду, наиболее пригодному для реализации. Такое преобразование называется минимизацией. Требования, которым стремятся удовлетворить в процессе минимизации, могут быть различными. В подавляющем большинстве случаев они направлены на следующие цели:

1. 
   уменьшение количества используемых элементов;
   
2. 
   возможность построения схемы на однотипных элементах. Уменьшение числа используемых элементов достигается приведением
   

логической функции к виду, имеющему минимальное количество символов и логических действий. Наиболее универсальный способ упрощения логического выражения основан на применении теорем и формул алгебры логики. Он проиллюстрирован ниже в примере 18.2.

При количестве аргументов у логической функции не более пяти кратчайшим путем минимизации является использование карт Карно. Соответствующая методика рассмотрена в [7, 13].

2. 
   Минимизация по формулам алгебры логики
   

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

• 
  вынесение за скобки общих членов;
  
• 
  применение теоремы де Моргана;
  
• 
  повторение слагаемых в логической сумме и сомножителей в логическом произведении;
  
• 
  двойное отрицание и др.
  

Пример 18.2. Пользуясь формулами алгебры логики (см. табл. 18.3), минимизировать логическое выражение функции трех аргументов y(x_vx₂,x₃), полученное в примере 18.1 и имеющее совершенную дизъюнктивную нормальную форму

y(x_v х₂, х₃) = Xt‘X₂‘X₃ + Xt’X₂ -Х₃ + Х] -Х₂ ‘Х₃.

Решете

1. 
   Воспользуемся приемом вынесения за скобки общего сомножителя х_х\
   

у = х\(х2-х3 +х₂-Жз + х2-х3).

2. 
   В сумме, заключенной в круглые скобки, повторяем слагаемое х.рс₃ (см. правило повторения в табл. 18.3) и производим группировку слагаемых:
   

у = хх(рс2 -х3 + Х2’Х3 + х2-х3 + х2 -хл) = хх[х2(х3 + х3) + х3(х2 + х2)\.

3. 
   Из тождества х + х = 1 (табл. 18.3) следуют равенства х₃ + дг₃ = 1; х₂ + х₂ = 1. Учитывая их, приходим к достаточно простому логическому выражению
   

y(xv х2, Л‘з) = х\(х2 + х3) = хх •х2 + х\ -х3.

3. 
   Универсальные базисы «И-НЕ» и «ИЛИ-НЕ»
   

Логические функции «И-НЕ» (функция Пирса) и «ИЛИ-HE» (функция Шеффера) являются результатом инверсии операций логического сложения «ИЛИ» и логического умножения «И» соответственно. Они занимают особое положение в цифровой технике и называются универсальными базисами (так же как и элементы, их реализующие). Причина заключается



в следующем: цифровое устройство, выполняющее любую логическую функцию, можно построить, гш&я элементы только одного вида («ИЛИ-HE» либо «И-IIE»). При интегральной технологии с точки зрения надежности и стоимости использование однотипных элементов весьма предпочтительно.

1. 
   Операции «ИЛИ-HE», «И-НЕ»
   

Операция «ИЛИ-HE» математически обозначается стрелкой «|» (стрелка Пирса) и для функции двух переменных записывается так:


ИЛH-HE(xp х₂) = х\ +дг₂ = х, | х₂.

Операция «И-НЕ» изображается значком штрих «|» (штрих Шеффера), и согласно определению в случае двух аргументов для нее применяется запись


И-НЕ(г_рх2) = ХХ'Х₂ = х{ \х2.


На рис. 18.5, а, б даны таблицы истинности и условные изображения соответствующих элементов на структурных схемах.


^х\

х₂

У

0

0

1

0

1

0

1

0

0

1

1

0


*1

х₂

У

0

0

1

0

1

1

1

0

1

1

1

0


я б

Рис. 18.5. Условные изображения и таблицы истинности элементов, выполняющих логические операции: «ИЛИ-HE» (я); «И-НЕ» (б)

2. 
   Универсальность функций «ИЛИ-HE» и «И-НЕ»
   

Обоснованием универсального характера функций Пирса и Шеффера являются алгебраические выражения, связывающие простейшие логические действия (сложение, умножение и инверсию) с любой из этих функций. Их несложно получить при помощи законов алгебры логики (и прежде всего закона де Моргана). Эти соотношения (включая краткий вывод) помещены в табл. 18.6 и 18.7, там же изображены функциональные схемы, выполняющие логические действия «ИЛИ», «И», «НЕ», построенные на однотипных универсальных базисах.

Таблица 18.6


Реализация простейших логических операций «НЕ», «ИЛИ», «И» в универсальном базисе «ИЛИ-НЕ»











Окончание табл. 18.6


Таблица 18.7


Реализация простейших логических операций «НЕ», «ИЛИ», «И» в универсальном базисе «И-НЕ»

3. 
   Методика записи и структурной реализации логических функций в универсальных базисах «И-НЕ» и «ИЛИ-НЕ»
   

Если поставлена задача построения цифрового устройства на однотипных универсальных базисных элементах, то целесообразно заданную ему логическую функцию записать через операцию выбранного базиса («И-НЕ» либо «ИЛИ-HE»). Получаемое при этом выражение уже содержит наглядную информацию о структуре цифрового устройства.

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

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

2. 
   Проводится минимизация функции у (либо по формулам алгебры логики, либо по карте Карно).
   
3. 
   Минимизированное выражение функции у преобразуется с помощью теорем алгебры логики (и прежде всего закона де Моргана) к виду, удобному для реализации в выбранном базисе, а именно:
   

• 
  при реализации в базисе «И-НЕ» функция у приводится к выражению, не содержащему логических сумм, т.е. у = А В С-..._у причем каждый из сомножителей (Л, В, С,...) должен иметь аналогичный вид.
  
• 
  при реализации в базисе «ИЛИ-HE» функция у преобразуется к виду,
  

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

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

Рассмотрим изложенный порядок на конкретных примерах.

Пример 18.3. Логическая функция двух аргументов задана алгебраическим выражением у = х_хх₂ + х_хх₂. Требуется:

• 
  выразить функцию у через универсальные базисы обоих видов — «И-НЕ» и «ИЛИ-НЕ»;
  

• 
  построить структурные схсмы устройства, реализующего заданную фупк цию в элементах «И-НЕ» и «ИЛИ-НЕ».
  

Решение

1. 
   Запись и реализация в базисе «ИЛИ-НЕ».
   

Подвергаем функцию у воздействию двойного отрицания:

у = у = х\х2 + х{х2.

Инверсию заданной функции у = х_хх₂ + х_хх₂ преобразуем к виду, не содержащему логических произведений, пользуясь теоремой де Моргана ab = a + b. Согласно записанной формуле

х{ - х2 = хх+х2 = хх + х2 = хх I х2 — функция Пирса от аргументов хх и х2;

хх -х2 = х, + х2 = х{ +х2 = хх\ х2 — функция Пирса от аргументов хх и х2.

Тогда для функции у получаем выражение

у = (X, | X.) + (J, | х₂) = (.г, | х2) | (х, i х._г).

Оно имеет вид функции Пирса от аргументов x_t 1 х₂ и х\ | х₂. Следовательно, справедливо равенство

у = у=(хх |х2)1(х{ \х2). (18.1)

Оно удобно для реализации в базисе «ИЛИ-НЕ».

Пользуясь полученным выражением (18.1), строим структурную схему соответствующего цифрового устройства. Согласно (18.1) оно должно выполнять три операции Пирса (по числу стрелок Пирса) и одну операцию инверсии. Последняя операция также может быть осуществлена элементом «ИЛИ-НЕ» путем объединения двух его входов (см. табл. 18.6). Таким образом, искомая схема может быть построена на четырех элементах «ИЛИ-НЕ». Она показана на рис. 18.6,