Главная > Документ

1

Смотреть полностью

Министерство ОБРАЗОВАНИя РОССИЙСКОЙ ФЕДЕРАЦИИ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНЖЕНЕРНО-ФИЗИЧЕС­КИЙ ИНСТИТУТ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

Гуров В.В.

Синтез комбинационных схем

в примерах и решениях

Москва 2001

УДК 004.312(075)

ББК 32.973-02я7

Г95

Гуров В.В. Синтез комбинационных схем в примерах. Уч. пособие. М.: МИФИ, 2001. – с.

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

Рекомендовано редсоветом МИФИ

в качестве учебного пособия

© Московский государственный инженерно-физический институт

(технический университет), 2001

ВВЕДЕНИЕ

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

Логическая (булева) переменная – такая величина х, которая может принимать только два значения: х = 0,1.

Логическая функция (функция алгебры логики - ФАЛ) - функция f(х1,х2,...,хn), аргументами которой являются только логические переменные и принимающая только два значения: ”истинно” или “ложно”.

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

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

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

Каждый логический элемент описывается своей логической функцией. Описание функционирования сложных логических схем, полученных соединением выходов одних логических элементов с входами других, сводится к указанию логической функции, явля­ю­щейся суперпозицией функций, реализуемых составляющими ее логическими эле­мен­тами.

Специалисты, разрабатывающие и использующие вычислительную тех­ни­ку, должны уметь

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

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

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

1. Основные понятия и соотношения

алгебры логики

Напомним некоторые определения и соотношения, используемые в алгебре логики.

Все возможные логические функции от одной переменной пред­­ставлены в таблице 1.1.

Таблица 1.1

Функция

x

Наименование

функции

Обозначение

функции

x=0

x=1

f0

0

0

Константа ";ноль";

f(x)=0

f1

0

1

Тождественная функция

f(x)=x

f2

1

0

Отрицание

f(x)=^x

f(x)=x

f3

1

1

Константа ";единица";

f(x)=1

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

Таблица 1.2

функции

Значение функции на наборах логичес­ких переменных

Наименование

функции

Обозначение

функции

x=0

y=0

x=1

y=0

x=0

y=1

x=1

y=1

f0

0

0

0

0

Константа ";ноль";

f(x,y)=0

f1

0

0

0

1

Конъюнкция

f(x,y)=x&y

f(x,y)=xy

f(x,y)= xy

f(x,y)=xy

f2

0

0

1

0

Запрет по y

xy

f3

0

0

1

1

x

f(x,y)=x

f4

0

1

0

0

Запрет по x

yx

f5

0

1

0

1

y

f(x,y)=y

f6

0

1

1

0

Сумма по mod2

(неравнозначность)

f(x,y)=xy

Продолжение табл.1.2

Значение функции на наборах логичес­ких переменных

Наименование

функции

Обозначение

функции

f7

0

1

1

1

Дизъюнкция

f(x,y)=xvy

f(x,y)=x+y

f8

1

0

0

0

Стрелка Пирса (Вебба)

f(x,y)=xy

f(x,y)=x О y

f9

1

0

0

1

Равнозначность

f(x,y)=xy

f(x,y)=xy

f10

1

0

1

0

Инверсия y

f(x,y)=^y

f(x,y)=y

f11

1

0

1

1

Импликация от y к x

f(x,y)=yx

f12

1

1

0

0

Инверсия x

f(x,y)=^x

f(x,y)=x

f13

1

1

0

1

Импликация от х к y

f(x,y)=xy

f14

1

1

1

0

Штрих Шеффера

f(x,y)=x/y

f15

1

1

1

1

Константа ";единица";

f(x,y)=1

Для простоты описания набора аргументов логических функций используем понятие номера набора, который определим как двоичное число, образованное последовательностью цифр этого набора. При введении нумерации наборов необходимо условиться о порядке записи аргументов. В дальнейшем аргументы x1,x2,…,xn будем располагать в порядке возрастания их индексов, а при использовании латинских букв – в алфавитном порядке. Например, набор аргументов x1 = 1, x2 = 0, x3 = 1, x4 = 1 имеет номер 11, а набор x = 1, y = 1, z = 0 – номер 6.

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

Отрицание

= 1 (1.1)

= 0 (1.2)

= x (1.3)

Конъюнкция

0 & 0 = 0 (1.4)

0 & 1 = 0 (1.5)

1 & 1 = 1 (1.6)

0 & x = 0 (1.7)

1 & x = x (1.8)

x & ¯x = 0 (1.9)

x & x = x (1.10)

x & x &...& x = x (1.11)

x & y = y & x (1.12)

x & y & z = (x & y) & z = x & (y & z) (1.13)

Дизъюнкция

00 = 0 (1.14)

01 = 1 (1.15)

11 = 1 (1.16)

0x = x (1.17)

1x = 1 (1.18)

x¯x = 1 (1.19)

xx = x (1.20)

xx...x = x (1.21)

xy = yx (1.22)

xyz = (xy) z = x (yz) (1.23)

Штрих Шеффера

0/0 = 1 (1.24)

0/1 = 1 (1.25)

1/1 = 0 (1.26)

0/x = 1 (1.27)

1/x = ¯x (1.28)

x/x = ¯x (1.29)

xx = 1 (1.30)

x/y = y/x (1.31)

x/(y/z)  (x/y)/z (1.32)

Стрелка Пирса

00=1 (1.33)

01=0 (1.34)

11=0 (1.35)

0xx (1.36)

1x=0 (1.37)

xxx (1.38)

x  ¯x = 0 (1.39)

xy=yx (1.40)

x(yz)(xy)z (1.41)

Правила де Моргана

= (1.42)

= & &…& (1.43)

Конъюнктивный терм (или минтерм, или конституэнта единицы) – терм, связывающий все переменные, представленные в прямой или инверсной формах, знаком конъ­юнкции. Любой конъюнктивный терм равен единице только на одном наборе переменных:


Например, F2(a,b,c) = ¯a & b & ¯c .

Совершенная дизъюнктивная нормальная форма (СДНФ) – ФАЛ, заданная в виде:

f(x1,x2,…,xn) = x1α11x2α12xnα1nVx1α21x2α22xnα2nV…Vx1αm1x2αm2xnαmn=

= Vix1α1x2α2xnαn,

где Vi – символ обобщенной дизъюнкции по всем минтермам данной функции:

Иногда для обозначения обобщенной дизъюнкции используется символ ∑i.

Иными словами, совершенной дизъюнктивной нормальной формой некоторой логической функции называется дизъюнкция всех конституэнт единицы этой ФАЛ. Любую ФАЛ, кроме константы ";ноль";, можно представить в виде СДНФ. Любая ФАЛ имеет единственную СДНФ с точностью до перестановки ее членов.

Дизъюнктивный терм (или макстерм, или конституэнта нуля) – терм, связывающий все переменные, представленные в прямой или инверсной форме, знаком дизъюнкции. Любой дизъюнктивный терм равен нулю только на одном наборе переменных:


Например, Ф5(a,b,c) = ¯a v b v ¯c ..

Рангом терма называется количество переменных, составляющих данный терм.

Совершенная конъюнктивная нормальная форма (СКНФ) – ФАЛ, заданная в виде:

f(x1,x2,…,xn) = (x1α11 v x2α12 v … xnα1n) Λ (x1α21 v x2α22 v … v xnα2n) Λ …

…Λ (x1αm1 v x2αm2 v … v xnαmn) = Λi (x1α1 Λ x2α2 Λ … Λ xnαn),

где Λi – символ обобщенной конъюнкции по всем макстермам данной функции. Иногда для обозначения обобщенной конъюнкции используется символ ∏i или &i.

Иными словами, совершенной конъюнктивной нормальной формой некоторой логической функ­ции называется конъюнкция всех конституэнт нуля этой ФАЛ. Любую ФАЛ, кроме константы ";единица";, можно представить в виде СКНФ. Любая ФАЛ имеет един­ст­венную СКНФ с точностью до перестановки ее членов.

Конъюнкция нескольких различных переменных, взятых с отрицаниями или без них, называется элементарной конъюнкцией.

Дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ). Например, функция ab v ¯ac v v c не является ДНФ, так как член не яв­ляет­ся элементарной конъюнкцией, а функция ab v ¯ac v abc является дизъюнктивной нормальной формой некоторой ФАЛ.

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

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

Собственной частью элементарной конъюнкции называют терм, полученный путем исключения из элементарной конъюнкции одного или не­скольких сомножителей. Например, элементарная конъюнкция ac имеет следующие собственные части a, ac, c, a, , c.

Первичная импликанта функции – импликанта типа элементарной конъюнкции некоторых переменных, никакая собственная часть которой уже не является импликантой.

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

Дизъюнктивная нормальная форма ФАЛ называется минимальной (МДНФ), если количество букв, которое она содержит, будет не больше, чем в любой другой дизъюнктивной нормальной фор­ме той же ФАЛ. Некоторые ФАЛ имееют несколько МДНФ.

Тупиковой дизъюнктивной нормальной формой называется дизъюнкция первичных импликант, ни одна из которых не является лишней. ФАЛ может иметь несколько тупиковых форм. Минимальные формы также являются тупиковыми. Поэтому процесс отыскания минимальных форм сводится к получению всех тупиковых форм и выбору из них форм с минимальным количеством букв.

Дизъюнкция нескольких различных переменных, взятых с отрицаниями или без них, называется элементарной дизъюнкцией.

Конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ). Пример конъюнктивной нормальной формы: (a v ) & ( ¯a v c) & (a v b v c)

Таким образом, функция алгебры логики может быть ана­ли­ти­чески задана своей единственной совершенной дизъ­юн­к­тивной нор­­мальной формой, или единственной совершенной конъ­юнк­тивной нормальной формой, или несколькими различными дизъ­юн­к­­тивными или конъ­юн­к­тивными нормальными формами. Все эти представления могут быть получены одно из другого экви­ва­лентными преобразованиями функции.

Определение понятий, относящихся к конъюнктивным нор­мальным формам, аналогичны определениям, относящимся к дизъ­­юнктивным формам, в предположении, что термин ";импликанта"; заменяется на термин ";имплицента";.

Базис – набор функций алгебры логики, с помощью которых любая ФАЛ может быть представлена суперпозицией функций, составляющих базис.

2. Представление функций алгебры логики

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

Таблицами истинности для функций одной и двух переменных являются таблицы 1.1 и 1.2 соответственно.

Помимо таблицы истинности, возможны и другие виды представления ФАЛ, наиболее распрост­раненными из которых являются совершенная дизъюнктивная нормальная форма, описывающая все наборы переменных, на которых функция принимает значение, равное 1, и совершенная конъюнктивная нормальная форма, описывающая все наборы переменных, на которых функция принимает значение, равное 0.

Рассмотрим способы перехода от одного вида представления ФАЛ к другому.

Пример 2.1

Пусть ФАЛ задана в виде таблицы истинности (2.1).

Таблица 2.1

Номер набора

x

y

z

f(x,y,z)

0

0

0

0

1

1

0

0

1

0

2

0

1

0

0

3

0

1

1

1

4

1

0

0

1

5

1

0

1

1

6

1

1

0

0

7

1

1

1

1

Получить СДНФ и СКНФ этой функции.
Решение

Получение СДНФ.

Для представления сокращенной записи СДНФ этой функции необходимо под знаком обобщенной дизъюнкции  или V перечислить через запятую номера всех наборов, на которых функция принимает значение, равное 1.:

f(x,y,z)СДНФ = (0,3,4,5,7)

Примечания:

данный вид представления функции является сокращенной записьюСДНФ, а не записью со­кращенной дизъюнктивной нормальной формы.

Получение развернутой записи СДНФ включает следующие этапы.

Этап 1.

Записать дизъюнкцию k конъюнктивных термов, содержащих все переменные, от которых зависит функция, где k - количество наборов, на которых функция принимает значение, равное 1, то есть количество наборов, перечисленное в сокращенной записи СДНФ:

f(x,y,z) =xyz V xyz V xyz V xyz V xyz

Этап 2.

Записать под каждым термом двоичный эквивалент одного из наборов, на которых функция принимает значение, равное 1:

f(x,y,z) =xyz V xyz V xyz V xyz V xyz

000 011 100 101 111

Этап 3.

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

f(x,y,z)СДНФ =xyz V xyz V xyz V xyz V xyz

0 0 0 0 1 1 1 0 0 1 0 1 1 1 1

Полученная запись представляет собой совершенную дизъюнктивную нормальную форму для функции, заданной таблицей истинности 2.1.

Получение СКНФ.

Для представления сокращенной записи СКНФ этой функции необходимо под знаком обобщенной конъюнкции  или Λ перечислить через запятую номера всех наборов, на которых функция принимает значение, равное 0:

f(x,y,z)СКНФ= (1,2,6)

Примечания:

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

Получение развернутой записи СДНФ включает следующие этапы.

Этап 1.

Записать конъюнкцию m дизъюнктивных термов, содержащих все переменные, от которых зависит функция, где m - количество наборов, на которых функция принимает значение, равное 0, то есть количество наборов, перечисленное в сокращенной записи СКНФ:

f(x,y,z) = (xVyVz) & (xVyVz) & (xVyVz)

Этап 2.

Записать под каждым термом двоичный эквивалент одного из наборов, на которых функция принимает значение, равное 0:

f(x,y,z) = (xVyVz) & (xVyVz) & (xVyVz)

0 0 1 0 1 0 1 1 0

Этап 3.

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

f(x,y,z)СКНФ = (x V y Vz) & (x Vy V z) & (x Vy V z)

0 0 1 0 1 0 1 1 0

Полученная запись представляет собой совершенную конъюнктивную нормальную форму для функции, заданной таблицей истинности 2.1.

Пример 2.2

Пусть ФАЛ задана сокращенной записью СДНФ:

f(x,y,z)СДНФ=(0,1,2,5,7)

Представить таблицу истинности, а также полную и сокращенную записи СКНФ этой функции.

Решение
Получение таблицы истинности

Этап 1.

Подготовить ТИ для логической функции трех переменных

Номер набора

x

y

z

f(x,y,z)

0

0

0

0

1

0

0

1

2

0

1

0

3

0

1

1

4

1

0

0

5

1

0

1

6

1

1

0

7

1

1

1

Этап 2.

Записать 1 в качестве значения функции в строки, соответствующие наборам, перечисленным в сокращенной записи СДНФ.

Номер набора

x

y

z

f(x,y,z)

0

0

0

0

1

1

0

0

1

1

2

0

1

0

1

3

0

1

1

4

1

0

0

5

1

0

1

1

6

1

1

0

7

1

1

1

1

Этап 3.

Записать 0 в качестве значения функции в остальные строки таблицы.

Номер набора

x

y

z

f(x,y,z)

0

0

0

0

1

1

0

0

1

1

Продолжение

Номер набора

x

y

z

f(x,y,z)

2

0

1

0

1

3

0

1

1

0

4

1

0

0

0

5

1

0

1

1

6

1

1

0

0

7

1

1

1

1

Таблица истинности получена.

Получение СКНФ.

Получение СКНФ по ТИ описано в примере 2.1.

Результатом будет:

f(x,y,z)СКНФ = ∏(3,4,6) = (x V ¯y Vz ) & (x V y V z ) & (x Vy Vz)

Пример 2.3

Пусть ФАЛ задана сокращенной записью СКНФ:

f(x,y,z)СКНФ = (2,3,4,5,7)

Получить полную и сокращенную записи СДНФ этой функции.

Решение

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

Этап 1.

Получить сокращенную запись СДНФ этой функции. Для этого под знаком обобщенной дизъюнкции  перечислить все наборы, не входящие в сокращенную запись СКНФ:

f(x,y,z)СДНФ = (0,1,6)

Этап 2.

Получить полную запись СДНФ согласно указаниям примера 2.1. Результатом будет:

f(x,y,z)СДНФ =xyz Vxyz V xyz

Пример 2.4

Пусть ФАЛ задана в виде СДНФ:

f(x,y,z)СКНФ = xyz Vxyz Vxyz V xyz

Получить полную и сокращенную записи СКНФ этой функции.

Решение

Получим сокращенную запись СДНФ функции, для чего сна­ча­ла определим двоичные эквиваленты наборов, соответствующих каждому конъюнктивному члену в полной записи СДНФ этой функ­­ции, поставив 1 под переменными, входящими в запись в пря­мом виде, и 0 под переменными, представленными в инверсном виде:

f(x,y,z)СКНФ=xyz Vxyz VxyzV xyz

1 0 0 0 0 1 0 1 0 1 1 1

Затем представим эти наборы в десятичном коде и перечислим их под знаком обобщенной дизъюнкции :

f(x,y,z)СДНФ=(4,1,2,7)

По полученной сокращенной записи СДНФ функции получим сокращенную запись СКНФ, перечислив под знаком обобщенной конъюнкции  номера наборов, не вошедших в сокращенную запись СДНФ:

f(x,y,z)СКНФ=(0,3,5,6)

По сокращенной записи СКНФ получим ее полную запись согласно методике, изложенной в примере 2.1.

f(x,y,z)СКНФ =(x V y V z) & (xVy Vz) & (x V y Vz) & (x Vy V z)

Пример 2.5

Пусть ФАЛ задана в виде СКНФ:

f(x,y,z)СКНФ =(x Vy V z) & (x Vy Vz) & (x V y Vz)

Получить полную и сокращенную записи СДНФ этой функции.

Решение

Получим сокращенную запись СКНФ этой функции. Для этого сначала определим двоичные эквиваленты наборов, соответствующих каждому дизъюнктивному члену в полной записи СДНФ этой функции, поставив 0 под переменными, входящими в запись в прямом виде, и 1 под переменными, представленными в инверсном виде:

f(x,y,z)СКНФ =(x Vy V z) & (x Vy Vz) & (x V y Vz)

0 1 0 0 1 1 1 0 1

Затем представим эти наборы в десятичном коде и перечислим их под знаком обобщенной конъюнкции :

f(x,y,z)СКНФ=(2,3,5)

По полученной сокращенной записи СКНФ функции получим сокращенную запись СДНФ, перечислив под знаком обобщенной дизъюнкции  номера наборов, не вошедших в сокращенную запись СКНФ:

f(x,y,z)СДНФ=(0,1,4,6,7)

По сокращенной записи СДНФ получим ее полную запись согласно методике, изложенной в примере 2.1:

f(x,y,z)СКНФ=xyzVxyz Vxyz Vxyz Vxyz

Пример 2.6

Пусть ФАЛ задана в виде дизъюнктивной нормальной формы, не являющейся совершенной. Например:

f(x,y,z)=xVxyVxyz

Получить полную и сокращенную записи СКНФ этой функции.

Решение

Для решения этой задачи можно сначала получить СДНФ функции.

Для получения СДНФ необходимо обеспечить зависимость каждого конъюнктивного терма от всех переменных, от которых зависит функция. Необходимые преобразования базируются на следующей эквивалентности:

a =ab V ab

Тогда, последовательно повышая ранг для термов, зависящих не от всех переменных, получим:

x =xy Vxy =xyz Vxyz Vxyz Vxyz

xy = xyz V xyz

f(x,y,z) =x V xy V xyz =

=xyz Vxyz Vxyz Vxyz V xyz V xyz V xyz

После выполнения преобразования на основе эквивалентности

aVa = a

получим полную, а затем и сокращенную записи СДНФ:

f(x,y,z)СДНФ =xyz Vxyz Vxyz Vxyz V xyz V xyz

f(x,y,z)СДНФ = (3,2,1,0,7,6)

Последующие шаги по решению поставленной задачи рассмотрены ранее.

В результате получим:

f(x,y,z)СКНФ = (4,5)

f(x,y,z)СКНФ = (x V y V z) & (x V y Vz)

Пример 2.7

Пусть ФАЛ задана в виде конъюнктивной нормальной формы, не являющейся совершенной. Например:

f(x,y,z)= (x V y) & (x Vz )

Получить полную и сокращенную записи СДНФ этой функции.

Решение

Решение этой задачи аналогично предыдущей.

Для получения СКНФ необходимо использовать следующие эквивалентности:

a = (aVb) & (a Vb)

a & a = a

Тогда получим:

xVy = (x V y V z) & (x V y Vz)

x Vz = (x V y Vz) & (x Vy Vz)

f(x,y,z) = (x V y V z) & (x V y Vz) & (x V y Vz) & (x Vy Vz)

f(x,y,z)СКНФ= (xVyVz) & (xVyVz) & (xVyVz)

f(x,y,z)СКНФ = (4,5,7)

Исходя из полученной СКНФ функции, определим ее СДНФ:

f(x,y,z)СДНФ = (0,1,2,3,6)

f(x,y,z)СДНФ =xyz V xyz V xyz V xyz V xyz

Пример 2.8

Пусть ФАЛ задана в виде совершенной дизъюнктивной нормальной формы:

f(x,y,z)СДНФ =xyz V xyz V xyz

Представить запись этой функции в базисе “Штрих Шеффера”.

Решение

Для перехода от представления ФАЛ в виде СДНФ к базису “Штрих Шеффера” необходимо выполнить следующее.

Этап 1.

Заменить все знаки дизъюнкции и конъюнкции на знак функции “Штрих Шеффера”. При этом вследствие невыполнения для данной функции ассоциативного закона (см. (1.32)) каждый конъюнктивный член должен быть заключен в скобки:

f(x,y,z) = (x /y / z ) / (x /y / z) / (x / y /z)

Этап 2.

Выразить функцию отрицания через функцию “Штрих Шеффера” согласно (1.29), также заключая эту операцию в скобки:

f(x,y,z) = ((x / x) / (y / y) / z) / (x / (y / y) / z) / (x / y / (z / z))

Пример 2.9

Пусть ФАЛ задана в виде:

f(x,y,z)СДНФ = x V xy V xyz

Представить запись этой функции в базисе “Штрих Шеффера”.

Решение

Особенность выполнения первого этапа обусловлена наличием в записи функции члена x, не являющегося конъюнкцией каких-либо переменных. Для приведения этой функции к дизъюнктивной нормальной форме воспользуемся выражением (1.10):

f(x,y,z)СДНФ = xx V xy V xyz

Дальнейшие действия в этом примере полностью совпадают с примером 2.8.

Результатом выполнения этапа 1 будет

f(x,y,z) = (x / x) / (x /y) / (x / y /z),

а окончательный результат:

f(x,y,z) = (x / x) / (x / (y / y)) / ((x / x) / y / (z / z))

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

3.1. метод Квайна – Мак-Класки

Минимальная форма представления ФАЛ – форма представления ФАЛ, которая содержит минимальное количество термов и переменных в термах.

С точки зрения использования функций алгебры логики для функционального описания проектируемой аппаратуры, процесс минимизации ФАЛ заключается в ее эквивалентных преобразованиях с целью получения такого ее представления, которое потребует в дальнейшем минимального количества оборудования для своей реализации.

Все рассматриваемые ниже методы минимизации предполагают, что ФАЛ задана в виде совершенных нормальных форм или таблицы истинности. Если исходная форма задания ФАЛ не является совершенной, ее следует привести к таковой, используя методику, описанную в примерах 2.6 и 2.7.

Минимизация функций алгебры логики, представленных в виде совершенной дизъюнктивной нормальной формы, базируется на следующих эквивалентных преобразованиях ФАЛ:

xy V xy = x – операция склеивания (3.1.1)

xy V xy = x V xy V xy – операция неполного склеивания (3.1.2)

x V xy = x – операция поглощения (3.1.3)

Здесь x и y могут представлять собой как отдельные переменные, так и ФАЛ, зависящие от нескольких переменных.

Минимизация функций алгебры логики, представленных в виде совершенной конъюнктивной нормальной формы, базируется на следующих эквивалентных преобразованиях ФАЛ:

(x V y) & ( x V y) = x – операция склеивания (3.1.4)

(x V y) & (x Vy) = x & (x V y) & (x V y) – операция неполного

склеивания (3.1.5)

x &(x V y) = x – операция поглощения (3.1.6)

Здесь x и y также могут представлять собой как отдельные переменные, так и ФАЛ, зависящие от нескольких переменных.

Пример 3.1

Минимизировать ФАЛ, заданую в виде совершенной дизъюнктивной нормальной формы, методом Квайна – Мак-Класки:

f(a,b,c,d)СДНФ = (3,7,8,10,11,12,15)

Решение

Этап 1.

Выписать двоичное представление наборов, образующих СДНФ данной функции:

(0011, 0111, 1000, 1010, 1011, 1100, 1111)

Этап 2.

Разбить полученные двоичные коды на группы, содержащие одинаковое количество единиц в коде. Для ФАЛ, зависящих от n переменных, таких групп может быть n+1 (ни одной единицы в коде, одна единица, две единицы, ... , n единиц в коде). Расположить группы по возрастанию количества единиц. Если количество получившихся групп меньше n+1, то отсутствующие группы пометить как пустые:

- - - -

1000

0011

1010

1100

0111

1011

1111

Этап 3.

Сравнить каждый код из одной группы с каждым кодом из соседних групп. Если найдены два кода, отличающиеся только в одном разряде (то есть они могут “склеиваться” между собой согласно 3.1.1), то пометить эти коды каким-либо особым символом, например "; * ";, и в новую группу поместить код, сохраняющий значение в совпадающих разрядах и имеющий какой-либо особый символ, например ";-";, на месте не­сов­па­да­ю­ще­го разряда. При этом образуется n-1 новая группа кодов. Если код попадает в несколько “склеек”, то он символом * может по­ме­чать­ся только один раз.

Эта процедура повторяется для вновь образованных групп до тех пор, пока возможна процедура “склеивания“ элементов соседних групп. Максимальное возможное число шагов на этом этапе равно n. На всех шагах, начиная со второго, необходимо следить за тем, чтобы два “склеиваемых” кода представляли собой термы, зависящие от одних и тех же логических переменных, то есть знаки ";-"; у них должны находиться в одних и тех же позициях. При появлении в одной группе нескольких одинаковых импликант для дальнейшего анализа следует оставить лишь одну из них, исходя из соотношения (1.21):

- - - -

- - - -

- - - -

1000*

10-0

1-00

- - - -

0011*

1010*

1100*

0-11*

-011*

101-

--11

--11

0111*

1011*

-111*

1-11*

1111*

шаг 1

шаг 2

Результат выполнения данного этапа – получение всех первичных импликант исходной ФАЛ., то есть сокращенной дизъюнктив­ной нормальной формы. Первичными импликантами будут все им­пликанты, полученные на последнем шаге этого этапа, а также все импликанты, полученные на всех предшествующих шагах и не во­шедшие ни в одну из ";склеек";, то есть, не помеченные симво­лом *.

Этап 4.

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

В ячейку таблицы ставится какой-либо отличительный символ, например "; + ";, если первичная импликанта, стоящая в заголовке строки, является собственной частью конституэнты единицы, стоящей в заголовке столбца. В противном случае ячейка остается пустой:

Первичные импликанты

Конституэты единицы

0011

0111

1000

1010

1011

1100

1111

--11

+

+

+

+

10-0

+

+

1-00

+

+

101-

+

+

-111

+

+

Простейший, но, конечно, не полный, контроль правильности заполнения таблицы может быть проведен следующим образом. Если первичная импликанта, стоящая в заголовке строки, не содержит символов ";-";, то в этой строке должна быть ровно одна помеченная ячейка. Строка, имеющая в заголовке импликанту с k символами ";-";, должна содержать ровно 2k помеченных ячеек. Кроме того, не должно быть ни одного столбца, не имеющего хотя бы одной помеченной ячейки.

Этап 5.

Найти существенные импликанты функции.

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

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

Для рассматриваемой функции существенными импликантами будут --11 и 1-00, так как только первичная импликанта --11 позволяет покрыть импликанту 0011 исходного набора, а первичная импликанта 1-00 необходима для покрытия импликанты 1100.

Таблица после вычеркивания из нее соответствующих строк и столбцов примет вид:

Первичные импликанты

Конституэты единицы

0011

0111

1000

1010

1011

1100

1111

--11

+

+

+

+

10-0

+

+

1-00

+

+

101-

+

+

-111

+

+

Этап 6.

Найти тупиковые дизъюнктивные нормальные формы и выбрать из них минимальные ДНФ.

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

Для анализа после этапа 5 остался только один столбец. Его покрытие может быть обеспечено включением в тупиковую форму либо импликанты 10-0, либо 101-, что приводит к двум тупиковым ДНФ. При наличии выбора в минимальную форму включается импликанта, зависящая от меньшего числа переменных. Обе полученные импликанты зависят от трех переменных, поэтому каждая из них может быть включена в минимальную форму. При равенстве рангов дополнительным фактором для включения той или иной импликанты в минимальную форму иногда служит меньшее число переменных, входящих в импликанту в инверсном виде, так как это в ряде случаев позволяет сократить объем оборудования для аппаратной реализации полученной функции. Мы в своем рассмотрении данный параметр в критерий минимальности включать не будем.

Таким образом, рассматриваемая функция имеет две различные минимальные дизъюнктивные формы:

f1МДНФ= cd v acd v abd

- -1 1 1-0 0 1 0 -0

f2МДНФ= cd v acd v ab с

- -1 1 1- 0 0 1 0 1 -

Пример 3.2

Минимизировать ФАЛ, заданую в виде совершенной конъюнктивной нормальной формы, методом Квайна – Мак-Класки:

f(a,b,c,d)СДНФ = (0,7,10,11,13,14,15)

Решение

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

Этап 1.

Записать двоичное представление наборов, образующих СКНФ данной функции:

(0000, 0111, 1010, 1011, 1101, 1110, 1111)

Этап 2.

Разбить полученные коды на группы, содержащие одинаковое количество нулей в коде. Для ФАЛ, зависящих от n переменных, таких групп может быть n+1 (ни одного нуля в коде, один нуль, два нуля, ... , n нулей в коде). Расположить группы по возрастанию количества нулей. Если количество получившихся групп меньше n+1, то отсутствующие группы помечаются как пустые:

1111

0111

1011

1101

1110

1010

-------

0000

Этап 3.

Сравнить каждый код из одной группы с каждым кодом из соседних групп. Если найдены два кода, отличающихся только в одном разряде (то есть они могут “склеиваться” между собой согласно (3.1.4)), то пометить их каким-либо особым символом, например, "; * ";, и в новую группу поместить код, сохраняющий значение в совпада­ющих разрядах и имеющий какой-либо особый символ, например ";-";, на месте несовпадающего разряда. При этом образуется n-1 новая группа кодов.

Эта процедура повторяется для вновь образованных групп до тех пор, пока возможна процедура “склеивания “ элементов соседних групп. Максимально возможное число шагов на этом этапе равно n. На всех шагах, начиная со второго, необходимо следить за тем, чтобы два “склеиваемых” кода представляли собой термы, зависящие от одних и тех же логических переменных, то есть знаки ";-"; у них должны находиться в одних и тех же позициях. При появлении в одной группе нескольких одинаковых термов для дальнейшего анализа следует оставить лишь один из них, исходя из соотношения (1.11).

1111*

-111

1-11*

11-1

111-*

1-1-

1-1-

0111*

1011**

1101*

1110**

101-*

1-10*

1010*

-------

-------

-------

0000

шаг 1

шаг 2

Результатом этого этапа является получение всех первичных имплицент функции и ее сокращенной конъюнктивной нормальной формы.

Этап 4.

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

В ячейку таблицы ставится какой-либо отличительный символ, например ";+";, если первичная имплицента, стоящая в заголовке строки, является собственной частью конституэнты нуля, стоящей в заголовке столбца. В противном случае ячейка остается пустой:

Первичные

имплиценты

Конституэты нуля

0000

0111

1010

1011

1101

1110

1111

1-1-

+

+

+

+

-111

+

+

11-1

+

+

0000

+

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

Этап 5.

Найти существенные имплиценты.

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

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

Для рассматриваемой функции все содержащиеся в заголовках строк минтермы будут существенными, так как первичная имплицента 1-1- необходима для покрытия макстермов 1010, 1011, 1110 и 111 исходного набора, имплиценнта -111 – для покрытия макстерма 0111, имплиценнта 11-1 – для по­крытия макстерма 1101, а имплицента 0000 необходима для покрытия такого же макстерма в ис­ходном наборе.

Таким образом, получим единственный набор, покрывающий все макстермы, составляющие совершенную конъюнктивную нормальную форму заданной функции. В связи с этим отсутствует этап, аналогичный этапу 6 в примере 3.1.

Полученная единственная минимальная конъюнктивная нормальная форма имеет следующий вид:

f(x,y,z)СКНФ = (a Vc) & (b Vc Vd) & (a Vb Vd) & (aVbVcVd)

1 - 1 - - 1 1 1 1 1 - 1 0 0 0 0

Пример 3.3

Получить методом Квайна – Мак-Класки минимальные ДНФ и КНФ для ФАЛ, заданной в виде совершенной конъюнктивной нормальной формы:

f(x,y,z)СДНФ = (0,2,5,6,7)

Решение

Вначале получим минимальную конъюнктивную нормальную форму по схеме, изложенной в примере 3.2.

Этап 1.

Записать двоичные коды наборов, образующих СКНФ данной функции:

(000, 010, 101, 110, 111)

Этап 2.

Разбить полученные коды на группы, содержащие одинаковое количество нулей в коде. Расположить группы по возрастанию количества нулей:

111

110

101

010

000

Этап 3.

Выполнить склейку кодов, попарно сравнивая элементы соседних групп:

111*

11-

1-1

110*

101*

-10

010*

0-0

000*

Этап 4.

Составить имплицентную матрицу:

Этап 5.

Определить существенные имплиценты.

Для рассматриваемой функции существенными имплицентами будут 0-0 и 1-1.

Этап 6.

Найти тупиковые конъюнктивные нормальные формы и выбрать из них минимальные КНФ.

Из анализа имплицентной матрицы получим, что функция имеет две тупиковые конъюнктивные нор­мальные формы, каждая из которых является минимальной:

f(x,y,z)1МКНФ = (x Vz ) & (x V z) & (xV ¯y )

1 1 0 – 0 1 1

f(x,y,z)2МКНФ = (x Vz ) & (x Vz) & (¯y V z)

1 – 1 0 – 0 – 1 0

Теперь получим минимальную дизюнктивную нормальную форму.

Этап 1.

Записать двоичные коды наборов, образующих СДНФ данной функции:

(001, 011, 100)

Этап 2.

Разбить полученные коды на группы, содержащие одинаковое количество единиц в коде. Расположить группы по возрастанию количества единиц:

001

100

011

Этап 3.

Выполнить склейку кодов, попарно сравнивая элементы соседних групп:

001

100

0-1

011*

Этап 4.

Составить импликантную матрицу:

Первичные импликанты

Конституэты единицы

001

011

100

0-1

+

+

100

+

Этапы 5 и 6.

Анализ импликантной матрицы показывает, что все полученные первичные импликанты являются сущест­вен­ными и, сле­до­ва­тель­но, рассматриваемая ФАЛ имеет единственную минимальную дизъюнктивную нормальную форму:

f(x,y,z)МДНФ =xz V x ¯y ¯z

0-1 1 0 0

3.2. метод диаграмм Вейча

Один из способов графического представления функций алгебры логики от небольшого числа переменных – карты Карно и их разновидности – диаграммы Вейча.

Диаграмма Вейча представляет собой организованную особым образом таблицу истинности ФАЛ. Расположение клеток этой таблицы позволяет легко определить склеивающиеся между собой члены. Ввиду особенностей геометрического представления диаграммы Вейча и интерпретации получаемых с ее помощью результатов, наиболее распространенными являются диаграммы Вейча для функций трех или четырех логических переменных.

На рис.3.1,а приведена диаграмма Вейча для функции трех переменных. Каждой клетке диаграммы соответствует определенный на­бор значений переменных. В скобках указаны номера наборов таблицы истинности, соответствующих данной ячейке диаграммы Вейча.

Если данную таблицу рассматривать как цилиндр, образованный соединением первой и последней колонок, то тогда склеивающиеся между собой конституэнты едини­цы (рис.3.1,б) или нуля (рис.3.1,в) в диаграммах Вейча будут расположены в соседних клетках. При этом прямоугольники, покрывающие 2kсоседних клеток, описывают имликанту (имплиценту), имеющую ранг (n-k), где n – число переменных, от которых зависит функция.

Положение переменных, задающих координаты ячеек диаграммы Вейча, может быть иным. Однако при этом должна обеспечиваться возможность задания на диаграмме всех наборов переменных. Естественно, при таких изменениях поменяются номера ячеек, но на процесс и результат минимизации ФАЛ данное обстоятельство влияния не окажет.

Клетки, содержащие в диаграмме Вейча единицы, будем называть 1-клетками, а клетки, содержащие нули – 0-клетками. Основное свойство диаграмм Вейча заключается в том, что любая первичная импликанта ранга n-m образует на ней прямоугольник и только прямоугольник 1-клеток площадью 2m, где n – количество переменных, от которых зависит функция. Такие прямоугольники называют m-кубами (m=0,1,…,n.; 0-кубу соответствует минтерм, а n-кубу – константа ";единица";). Так любая пара единиц в соседних клетках диаграммы Вейча для логической функции трех переменных представляется импликантой второго ранга. Четыре единицы, образующие прямоугольник, выражаются одной переменной (с отрицанием или без него).

Чтобы записать первичную импликанту, представляющую собой некий m-куб на диаграмме Вейча, необходимо просто составить конъюнкцию тех переменных, которые в пределах данного m-куба сохраняют постоянные значения (только прямые или только инверсные).

Таким образом, получение минимальной ДНФ с помощью диаграмм Вейча сводится к отысканию минимального числа m-кубов максимального размера, состоящих из 1-клеток, и составлению дизъюнкции импликант, соответствующих этим m-кубам (каждая 1-клетка должна войти хотя бы в один m-куб, любавя 1-клетка может входить одновременно в несколько различных m-кубов).

При получении МДНФ с помощью диаграммы Вейча необходимо обратить внимание на следующее:

m-кубу, покрывающему 2m 1-клеток, соответствует первичная импликанта, не зависящая от m переменных, причем исключаются те m переменных, которые в прямоугольной области на диаграмме Вейча, состоящей из 1-клеток, имеют различное значение (прямое и инверсное);

прямоугольные области на диаграмме Вейча, используемые при минимизации, могут состоять только из 2m соседних клеток, где m = 0,1,…,n;

каждая клетка на диаграмме Вейча, вне зависимости от способа разметки этой диаграммы, имеет ровно n соседних клеток; в связи с этим диаграмма Вейча представляется нанесенной на по­верхность соответствующего тела (цилиндра – для случая трех переменных, тора – для случая четырех переменных);

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

Получение минимальной КНФ проводится аналогичным образом по отношению к 0-клеткам.

Пример 3.4

Получить методом диаграмм Вейча минимальную ДНФ следующей логической функции:

f(x,y,z)СДНФ = (0,1,2,5,7)

Решение

Этап 1.

Занести значение функции на диаграмму Вейча. В связи с тем что ФАЛ задана в виде сокращенной записи совершенной дизъюнктивной нор­мальной формы, для ее представления в виде диаграммы Вейча целесообразно использовать вид этой диаграммы, представленный на рис. 3.1,а. При этом, так как по заданию предполагается получение лишь минимальной дизъюнктивной нормальной формы, для улучшения восприятия диаграммы можно отметить лишь те ячейки, которые соответствуют конституэнтам единицы, предполагая, что ячейки, оставшиеся незаполненными, соответствуют нулевым значениям ФАЛ:

y

¯y

x

1

1

¯x

1

1

1

¯z

z

¯z

Этап 2.

Отметить на диаграмме 1-клетки, входящие в единственный mкуб. Выбрать для них покрытие в виде m-куба максимального размера. При этом одна 1-клетка может входить в не­сколько mкубов одновременно. Разорван­ный овал, накрывающий клетки 2 и 0, соответствует покрытию со­сед­них клеток при представлении таблицы в виде цилиндра с соединенными левой и правой колонками:

y

¯y

x

1

1

¯x

1

1

1

¯z

z

¯z

Этап 3.

Не вошедшую ни в один из m-кубов 1-клетку можно включить в один из 2-кубов либо с 1-клеткой, стоящей справа от нее, либо с 1‑клеткой, стоящей выше нее. Так как оба альтернативных m-куба имеют одинаковый размер, то в результате получим две ми­ни­маль­ные дизъюнктивные нормальные формы:

y

¯y

x

1

1

¯x

1

1

1

¯z

z

¯z

и

y

¯y

x

1

1

¯x

1

1

1

¯z

z

¯z

Этап 4.

Представить полученные m-кубы в виде минимальных дизъюнктивных нор­маль­ных форм:

f(x,y,z)1МДНФ = xz v ¯x ¯z v ¯x ¯y

f(x,y,z)2МДНФ = xz v ¯x ¯z v z ¯y

Пример 3.5

Получить методом диаграмм Вейча минимальную ДНФ следующей логической функции:

f(x,y,z)СДНФ = xyz v x¯y ¯z v ¯xy¯z v ¯x ¯y¯z

Решение

Этап 1.

Занести значение функции на диаграмму Вейча согласно ее представлению на рис. 3.1,б:

y

¯y

x

1

1

¯x

1

1

¯z

z

¯z

Этап 2.

Отметить на диаграмме 1-клетки, входящие в единственный mкуб:

y

¯y

x

1

1

¯x

1

1

¯z

z

¯z

Этап 3.

Так как на диаграмме не осталось непокрытых 1-клеток, то ми­нимальная ДНФ будет иметь вид:

f(x,y,z)МДНФ = xyz v ¯x ¯z v ¯¯y ¯z

Пример 3.6

Получить методом диаграмм Вейча минимальную КНФ следующей логической функции:

f(x,y,z)СДНФ = ∏(0,2,5,6,7)

Решение

Этап 1.

Занести значение функции на диаграмму Вейча согласно ее представлению на рис. 3.1,а. При этом в ячейки, имеющие номера, перечисленные в сокращенной записи СКНФ функции, заносятся нули, а остальные ячейки можно оставить незаполненными:

y

¯y

x

0

0

0

¯x

0

0

¯z

z

¯z

Этап 2.

Отметить на диаграмме 0-клетки, входящие в единственный mкуб:

y

¯y

x

0

0

0

¯x

0

0

¯z

z

¯z

Этап 3.

Не вошедшую ни в один из m-кубов 0-клетку можно включить в один из 1-кубов либо с 0-клеткой, стоящей справа от нее, либо с 0‑клеткой, стоящей ниже ее. В результате получим две мини­мальные конъюнктивные нормальные формы:

y

¯y

x

0

0

0

¯x

0

0

¯z

z

¯z

f(x,y,z)1МКНФ = (¯x v ¯z) & (x v z) & (¯x v ¯y)

y

¯y

x

0

0

0

¯x

0

0

¯z

z

¯z

f(x,y,z)2МКНФ = (¯x v ¯z) & (x v z) & (¯¯y v z)

Следует обратить внимание на то, что при описании m-кубов, представленных на диаграмме Вейча, в виде конъюнктивной нормальной формы, переменные в записи элементарных дизъюнкций берутся инверсными по отношению к представлению их координат на диаграмме Вейча.

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

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


Пример 3.7

Получить методом диаграмм Вейча минимальную ДНФ для следующей ФАЛ:

f(a,b,c,d)СДНФ = (0,2,3,4,7,11,15)

Решение

Этап 1.

Занести значение функции на диаграмму Вейча, представленную на рис. 3.2,а:

¯d

d

¯d

a

¯c

1

1

c

¯a

1

1

1

1

1

¯c

b

¯b


Этап 2. Отметить на диаграмме 1-клетки, входящие в единственный m-куб:

¯d

d

¯d

a

¯c

1

1

c

¯a

1

1

1

1

1

¯c

b

¯b

Этап 3.

Оставшийся непокрытым набор 2 включить в m-куб мак­си­маль­ного размера. Ввиду того, что оба альтернативных по­кры­тия представляют собой 1-кубы, функция будет иметь две минимальные ДНФ:

¯d

d

¯d

a

¯c

1

1

c

¯a

1

1

1

1

1

¯c

b

¯b

f(a,b,c,d)1МДНФ = cd v ¯a ¯c v ad

¯d

d

¯d

a

¯c

1

1

c

¯a

1

1

1

1

1

¯c

b

¯b

f(a,b,c,d)2МДНФ = cd v ¯a ¯cv aс

Пример 3.8

Получить методом диаграмм Вейча минимальную ДНФ для ФАЛ, заданную сокращенной записью СДНФ:

f(a,b,c,d)СДНФ = (0,2,3,7,9,10,11,14)

Решение

Этап 1.

Занести значение функции на диаграмму Вейча, представленную на рис. 3.2,а:

¯d

d

¯d

a

1

¯c

1

1

1

c

¯a

1

1

1

1

¯c

b

¯b


Этап 2.

Отметить на диаграмме 1-клетки, входящие в единственный m-куб:

¯d

d

¯d

a

1

¯c

1

1

1

c

¯a

1

1

1

1

¯c

b

¯b

Этап 3.

Так как все 1-клетки вошли в какой-либо из m-кубов, то осталось только записать ми­ни­мальную ДНФ:

f(a,b,c,d)МДНФ = a d v a c v сd v

Необходимо обратить внимание на то, что, как указывалось выше, не следует начинать поиск покрытий с отыскания m-кубов максимально возможной площади. Так, в данном случае 1-клетки (2,3,10,11) можно было бы включить в 2-куб (c). Однако при этом все равно сохранилась бы необходимость покрытия остальных 1‑клеток 1-кубами. Поэтому данный 2-куб в окончательный вариант покрытия входить не должен.


¯d

d

¯d

a

1

¯c

1

1

1

c

¯a

1

1

1

1

¯c

b

¯b

Пример 3.9

Получить методом диаграмм Вейча минимальные КНФ и ДНФ логической функции, заданной в виде сокращенной записи СКНФ:

f(a,b,c,d)СКНФ = ∏(2,3,5,6,7,10,11,13,14)

Решение

Получение минимальной КНФ

Этап 1.

Занести значение функции на диаграмму Вейча, представленную на рис 3.2,а, помещая в клетки, соответствующие указанным при задании функции наборам, нули:

¯d

d

¯d

a

0

¯c

0

0

0

c

¯a

0

0

0

0

0

¯c

b

¯b


Этап 2.

Отметить на диаграмме 0-клетки, входящие в единственный m‑куб:

¯d

d

¯d

a

0

¯c

0

0

0

c

¯a

0

0

0

0

0

¯c

b

¯b

Этап 3.

Так как все 0-клетки вошли в какой-либо из m-кубов, то записать единственную ми­ни­мальную КНФ:

f(a,b,c,d)МКНФ = (a v ¯c ) (b v ¯c ) ( ¯c v d) ( v c v )

Получение минимальной ДНФ

Этап 1.

Заполнить 1-клетки для заданной ФАЛ, помещая в клетки, оставшиеся незаполненными в про­цессе получения МКНФ, единицы:

¯d

d

¯d

a

1

1

1

¯c

1

c

¯a

1

1

1

¯c

b

¯b


Этап 2.

Отметить на диаграмме 1-клетки, входящие в единственный mкуб:

¯d

d

¯d

a

1

1

1

¯c

1

c

¯a

1

1

1

¯c

b

¯b

Отметим, что 1-клетки (0,4,8,12) в совокупности на поверхности тора, образуемого диаграммой Вей­ча, со­став­ля­ют 2‑куб.

Этап 3.

Так как все 1-клетки вошли в какой-либо из m-кубов, то запишем единственную ми­ни­мальную ДНФ:

f(a,b,c,d)МДНФ = ¯c v ¯c v abcd

4. Минимизация неполностью определенных функций

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

При представлении такой ФАЛ в виде таблицы истинности наборы, на которых значение функции не определено, отмечаются особым символом, отличным от ";0"; и ";1";, например, Х. В табл. 4.1 приведен пример такой функции трех переменных. Эта функция принимает значение ";1"; на наборах 0, 5 и 7, значение ";0"; - на наборах 2 и 6.. На наборах 1,3 и 4 значение функции не определено.

Таблица. 4.1

Номер набора

a

b

c

f(a,b,c)

0

0

0

0

1

1

0

0

1

Х

2

0

1

0

0

3

0

1

1

Х

4

1

0

0

Х

5

1

0

1

1

6

1

1

0

0

7

1

1

1

1

Сокращенная запись этой функции имеет вид:

f(a,b,c) = ∑(0,5,7), Х(1,3,4) или

f(a,b,c) = ∏(2,6), Х(1,3,4).

При преобразованиях неполностью определенных логических функций, в частности, при их минимизации, можно произвольно задать значения выходных сигналов на тех наборах входных переменных, на которых значение ФАЛ не определено. Основная задача минимизации неполностью определенных функций заключается в отыскании оптимального варианта ее доопределения, позволяющего получить минимальную нормальную форму. Если значения ФАЛ не определены на k наборах, то ее можно доопределить 2k способами. Поэтому минимизация неполностью определенной логической функции состоит в выборе одной из 2k полностью определенных функций, которая позволяет получить форму с минимальным количеством букв.

Это накладывает особенности на использование тех или иных методов минимизации.

4.1. Минимизация неполностью определенных функций Методом Квайна – Мак-Класки

Начальные этапы минимизации методом Квайна – Мак-Класки для полностью и не­­полностью определенных логических функций совпадают до момента получения со­к­ра­щенной нормальной формы. При этом в качестве исходной функции рассматривается ФАЛ, которая принимает на неопределеных наборах значение 1 при получении минимальной дизъюнктивной нормальной формы, и значение 0 при получении минимальной конъюнктивной нормальной формы. При построении импликантной или имплицентной матрицы, заголовки строк включают полученные первичные импликанты (имплиценты), а заголовки столбцов – конституэнты единицы (нуля) исходной функции без учета наборов, на которых значение функции не определено. Дальнейшая работа с полученой матрицей аналогична действиям, описанным выше в разделе 3.1.

Пример 4.1

Минимизировать методом Квайна – Мак-Класки неполностью определенную ФАЛ, заданую в следующем виде:

f(a,b,c,d) = (0,5,8,12,15), Х(1,2,3,10.13,14)

Решение

Этап 1. Найти рассмотренным выше способом сокращенную ДНФ для функции

f(a,b,c,d)СДНФ = (0,1,2,3,5,8,10,12,13,14,15)

0000*

000-*

00--

0001*

00-0*

-0-0

0010*

-000*

1--0

1000*

00-1*

11--

0011*

0-01

0101*

001-*

1010*

-010*

1100*

10-0*

1101*

1-00*

1110*

-101

1111*

1-10*

110-*

11-0*

11-1*

111-*

Сокращенная дизъюнктивная нормальная форма этой ФАЛ имеет вид:

f(a,b,c,d)СкДНФ = ¯a v v a¯ v a b v ¯a ¯c d v b ¯c ¯ d

Этап 2.

Составить импликантную матрицу для этой функции:

0000

0101

1000

1100

1111

00--

+

-0-0

+

+

1—0

+

+

11--

+

+

0-01

+

-101

+

Обратим внимание на то, что в этой таблице строка, имеющая в заголовке импликанту с k символами ";-";, не обязательно содержит 2k помеченных ячеек. Также в таблице могут присутствовать строки, не имеющие ни одной помеченной ячейки. В то же время, не должно быть ни одного столбца, не имеющего хотя бы одной помеченной ячейки.

Из анализа импликантной матрицы получим две возможные минимальные дизъюн­к­­тивные формы:

f1(a,b,c,d)МДНФ = v ab v ¯a ¯c ¯ d

f2(a,b,c,d)МДНФ = v ab v b ¯c ¯ d

Пример 4.2

Минимизировать методом Квайна - Мак-Класки неполностью определенную ФАЛ, заданую в виде:

f(a,b,c) = ∏(0,5,7), Х(1,6)

Решение

Этап 1.

Найти сокращенную КНФ для функции

f(a,b,c)СКНФ = ∏(0,1,5,6,7).

Сокращенная конъюнктивная нормальная форма этой ФАЛ имеет вид:

f(a,b,c,d)СкКНФ = (a v b) (b v ¯c) ( ¯a v ¯ c ) ( ¯a v )

Этап 2.

Составить имплицентную матрицу для исходной функции:

000

101

111

00-

+

-01

+

1-1

+

+

11-

+

Этап 3.

По имплицентной матрице получить минимальную конъюнктивную нормальную форма. Для этой функции она единственная:

f(a,b,c)МКНФ = (a v b) (¯a v ¯c)

4.2. Минимизация неполностью определенных функций Методом диаграмм Вейча

Пример 4.3

Получить методом диаграмм Вейча минимимальную дизъюнктивную нормальную форму неполностью определенной ФАЛ, заданой в следующем виде:

f(a,b,c,d) = (0,5,8,12,15), Х(1,2,3,10.13,14)

Решение

Этап 1.

Занести значение функции на диаграмму Вейча. Заполнить 1‑клетки и клетки, соответствующие неопределенным значениям функции (будем называть их X-клетками):

¯d

d

¯d

a

1

x

1

¯c

x

1

x

c

¯a

x

x

1

x

1

¯c

b

¯b


Этап 2.

Выбрать такие значения ФАЛ в x-клетках, которые обеспечивают покрытие всех 1-кле­ток минимальным количеством m-кубов максимальной площади. Для рассматриваемой функции су­щест­вует два варианта таких доопределений, обеспечивающих полу­че­ние двух минимальных дизъюнктивных нормальных форм:

¯d

d

¯d

a

1

x

1

¯c

x

1

x

c

¯a

x

x

1

x

1

¯c

b

¯b

f1(a,b,c,d)1МДНФ = ab v v ¯a ¯ccd

¯d

d

¯d

a

1

x

1

¯c

x

1

x

c

¯a

x

x

1

x

1

¯c

b

¯b

f(a,b,c,d)2МДНФ = ab v v b ¯cd

Пример 4.4

Получить методом диаграмм Вейча минимимальную конъюнктивную нормальную форму неполностью определенной ФАЛ, заданую в следующем виде:

f(a,b,c,d) = ∏(2,3,5,6,7,8,13,15), Х(0,1,9)

Решение

Этап 1.

Занести значение функции на диаграмму Вейча. Заполнить 0-клетки и клетки, соответствующие неопределенным значениям функции:

¯d

d

¯d

a

0

x

0

¯c

0

c

¯a

0

0

0

0

0

x

x

¯c

b

¯b


Этап 2.

Выбрать такие значения ФАЛ в X-клетках, которые обеспечивают покрытие всех 0-кле­ток минимальным количеством m-кубов максимальной площади:

¯d

d

¯d

a

0

x

0

¯c

0

c

¯a

0

0

0

0

0

x

x

¯c

b

¯b

Этап 3.

Записать минимальную КНФ, соответствующую по­лу­ченным m‑кубам.

f(a,b,c,d)МКНФ = (b vc) (a v ¯c) (v )

Пример 4.5

Получить методом диаграмм Вейча минимальные КНФ и ДНФ следующей неполностью определенной логической функции

f(a,b,c,d)СКНФ = ∏(0,2,3,4,7,11,15), X(1,8,9)

Решение

Получение минимальной КНФ.

Этап 1.

Заполнить на диаграмме Вейча 0-клетки и X-клетки:

¯d

d

¯d

a

x

x

¯c

0

0

c

¯a

0

0

0

0

x

0

¯c

b

¯b


Этап 2.

Выбрать такие значения ФАЛ в X-клетках, которые обеспечивают покрытие всех 0-кле­ток минимальным количеством m-кубов максимальной площади:

¯d

d

¯d

a

x

x

¯c

0

0

c

¯a

0

0

0

0

x

0

¯c

b

¯b

Этап 3.

Записать минимальную КНФ, соответствующую полученным m‑кубам:

f(a,b,c,d)МКНФ = (a v b ) ( ¯c v ) (a v c v d )

Получение минимальной ДНФ.

Этап 1.

Заполнить на диаграмме Вейча 1-клетки и X-клетки. На диаграмму заносятся все X-клетки вне зависимости от того, как доопределялась ФАЛ при получении МКНФ:

¯d

d

¯d

a

1

1

x

x

¯c

1

1

c

¯a

1

1

x

¯c

b

¯b

Этап 2.

Выбрать такие значения ФАЛ в X-клетках, которые обеспечивают покрытие всех 1-кле­ток минимальным количеством m-кубов максимальной площади:

¯d

d

¯d

a

1

1

x

x

¯c

1

1

c

¯a

1

1

x

¯c

b

¯b

Обратим внимание на то, что на наборе 1 при получении МКНФ функция доопределялась нулевым значением, а при получении МДНФ – единичным.

Этап 3.

Записать минимальную ДНФ, соответствующую полученным m‑кубам:

f(a,b,c,d)МДНФ = ¯c v a ¯c v bc

Список ЛИТЕРАТУРы

1. Вавилов Е.Н., Егоров Б.М., Ланцев В.С., Тоценко В.Г. Синтез схем на пороговых элементах. – Под ред. Е.Н.Вавилова. – М.: Сов. радио, 1970. 368 с.

2. Каган Б.М. Электронные вычислительные машины и системы. - М.: Энергоатом­издат, 1991.

3. Поспелов Д.А.. Логические методы анализа и синтеза схем. – М.: Энергия, 1974.

4.Савельев А.Я. Прикладная теория цифровых автоматов. - М.: Высшая школа, 1987.

СОДЕРЖАНИЕ

Введение …………………………………………………….3

1. Основные понятия и соотношения алгебры логики …5

2. Представление функций алгебры логики ……………..

3. Минимизация функций алгебры логики ……………...

3.1. Метод Квайна – Мак-Класки………………….

3.2. Метод диаграмм Вейча………………………...

4. Минимизация неполностью определенных функций...

4.1. Минимизация неполностью определенных

функций методом Квайна – Мак-Класки.…………

4.2. Минимизация неполностью определенных

функций методом диаграмм Вейча…….…………..

Список литературы ………………………………………….

В.В.Гуров

Синтез комбинационных схем

в примерах и решениях

Москва 2001

Валерий Валентинович Гуров

Синтез комбинационных схем

в примерах и решениях

Редактор Антонова Н.Н.

Лицензия ЛР 020676 от 09.12.97г.

Подписано в печать Формат 60х84 1/16

Уч.-изд. л. 5,0. Печ. л. 5,25 Тираж 150 экз.

Изд. №029-1 Заказ

Московский государственный инженерно-физический институт

(технический университет)

Типография МИФИ

115409 Москва, Каширское шоссе, 31

Примечания и дополнения

Ранг терма r определяется количеством переменных, входящих в данный терм. Например, для минтерма F = ¯a & b & c ранг r=3, а для макстерма Ф = ¯a v ¯b v c v d ранг r=4.

Дизъюнктивная нормальная форма (ДНФ) – объединение термов, включающее минтермы переменного ранга.

Конъюнктивная нормальная форма (КНФ) – объединение термов, включающее макстермы разного ранга.

Основное понятие алгебры логики - высказывание. Высказывание - некоторое предложение, в отношении которого можно утверждать, что оно истинно или ложно. Любое высказавание можно обозначить каким-либо симвлолом, например х, и считать, что х=1, есливысказывание истинно, и х=0, если высказывание ложно.

Конъюнкция всех переменных, от которых зависит ФАЛ, взятых с отрицаниями или без них, называется конституэнтой единицы. Любая конституэнта единицы равна единице только на одном наборе переменных.

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

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

Дизъюнкция всех переменных, от которых зависит ФАЛ, взятых с отрицаниями или без них, называется конституэнтой нуля. Любая конституэнта нуля равна нулю только на одном наборе переменных.

Отыскание минимальных дизъюнктивных нормальных форм сводится к определению вариантов, при которых все единицы диаграммы Вейча накрываются наименьшим числом наиболее коротких произведений, то есть прямоугольников наибольшей площади. Как правило, метод диаграмм Вейча используется в чисто прикладныз целях и предполагает отыскание какой-либо одной минимальной формы из нескольких возможных вариантов.

Здесь 1-кубу будет соответствовать импликанта, содержащая 4 переменные, 2-кубу – ранга 3, 3-кубу – ранга 2.

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

В диаграммаах Вейча для функции двух переменных любая пара единиц, рас­по­ложенных в соседних клетках, при получении МДНФ выражается одной буквой, пред­ставляющую собой общую координату этой пары клеток.

48

1

Смотреть полностью


Скачать документ

Похожие документы:

  1. Библиографический указатель из фонда научной библиотеки

    Библиографический указатель
    ... -технических работ. МИФИ - городу Москве:Каталог.-М.,2001.-Б.п. 195. Московский государственный инженерно-физический ... .-26с. 4553. Гуров В.В. Синтезкомбинационныхсхем в примерах и решениях: Учеб.пособие/Гуров В.В.-М.:МИФИ,2001.-56с. 4554. Гусев ...
  2. Москва 2011 1 Цели и задачи дисциплины (3)

    Рабочая программа
    ... коммуникационные технологии Москва 2011 1. ... схемотехнических решений и ... и синтезасхем ЭВМ. Анализ комбинационныхсхем. Синтезкомбинационныхсхем: мультиплексор ... СПб.: БХВ-Петербург, 2001. 2. Пухальский Г.И., Новосельцева ... также примеры оценочных ...
  3. Программа обучения студентов ( syllabus ) (3)

    Программа обучения студентов
    ... домашних заданий, самостоятельное решение задач), итоги индивидуальных ... А.В. и др. «Информатика». – Москва.: ACADEMA, 1999 г. Информатика/ Под ... ДИАЛОГ-МИФИ,1993 Гуров В.В. Синтезкомбинационныхсхем в примерах М.: МИФИ, 2001 Гуров В.В., Ленский О.Д., ...
  4. РУССКАЯ ВЕРОЯТНОСТНАЯ ЛОГИКА

    Документ
    ... -ЭЛЕКТРОНЩИКА Москва 2008 ... Русская механика» А.Ф.Черняева (М.:2001 – 592с.) и « ... 1.4. СинтезкомбинационныхсхемСинтезкомбинационныхсхем можно проиллюстрировать решением простой ... Пример 1. «Энциклопедия - Россия-Он-Лайн» излагает примеррешения ...
  5. РУССКАЯ ВЕРОЯТНОСТНАЯ ЛОГИКА (2)

    Документ
    ... -ЭЛЕКТРОНЩИКА Москва 2008 ... Русская механика» А.Ф.Черняева (М.:2001 – 592с.) и « ... 1.4. СинтезкомбинационныхсхемСинтезкомбинационныхсхем можно проиллюстрировать решением простой ... Пример 1. «Энциклопедия - Россия-Он-Лайн» излагает примеррешения ...

Другие похожие документы..