close

Вход

Забыли?

вход по аккаунту

?

Mishyra(Osnovy algebry logiki)

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
ЦИФРОВЫЕ АВТОМАТЫ.
ОСНОВЫ АЛГЕБРЫ ЛОГИКИ.
МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ
ПРИ ПОМОЩИ ДИАГРАММ ВЕЙЧА
Учебно-методическое пособие
Санкт-Петербург
2013
Составитель О. В. Мишура, кандидат технических наук, доцент
Рецензент В. П. Попов, кандидат технических наук, доцент
Учебно-методическое пособие предназначено для студентов 2-го курса
заочной формы обучения по направлению 230200, квалификация – бакалавр.
Подготовлено кафедрой информационно-сетевых технологий и рекомендовано к изданию редакционно-издательским советом Санкт-Петербургского
государственного университета аэрокосмического приборостроения.
Методическое пособие может быть полезно для студентов дневной формы обучения при изучении дисциплины «Цифровые автоматы».
Редактор Г. Д. Бакастова
Компьютерная верстка Н. Н. Караваевой
Сдано в набор 09.04.13. Подписано к печати 01.07.13. Формат 6084 1/16.
Бумага офсетная. Усл. печ. л. 2,5. Тираж 100 экз. Заказ № 357.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
1. ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ ЛОГИКИ
1.1. Логическая переменная. Логическая функция
Логической переменной называется такая переменная х, которая может принимать только одно из двух значений: 0 или 1.
Высказывание – это такое предположение, о котором можно говорить, что оно истинно или ложно.
Любое высказывание можно обозначить величиной х и говорить, что
высказывание истинно, если соответствующая ему величина х = 1, и ложно, если х = 0.
Логическая функция – это функция
, которая принимает значения 0 или 1 на наборе логических переменных
.
1.2. Логическая функция от одной переменной f(x)
Функцию
можно представить в виде таблицы истинности. Таблица истинности содержит следующую информацию. Левый столбец задает все наборы переменных, на которых существует заданная функция, таким образом определяется количество строк в таблице. Это количество
определяется величиной , где n – количество переменных, от которых
зависит логическая функция. Для функции от одной переменной наборов,
на которых существует эта функция, т. е. количество строк в таблице истинности, равно
.
Полное количество логических функций, зависящих от n перемен.
ных, равно
Для функции, зависящей от одной переменной, это количество равно
=
.
Объединим в одной таблице истинности четыре таблицы (табл. 1)
и представим в ней все четыре функции, зависящие от одной переменной:
f1(x) – функция «константа 0»; абсолютно ложная функция; функция,
принимающая значения 0 при любых значениях переменной;
f2(x) – функция «константа 1»; абсолютно истинная функция; функция, принимающая значения 1 при любых значениях переменных;
f3(x) – тождественная функция; f3(x) ≡ х; функция, принимающая значения переменной;
f4(x) – функция логического отрицания; функция инверсии; функция НЕ;
.
Таблица 1
X
f1(x)
f2(x)
f3(x)
f4(x)
0
1
0
0
1
1
0
1
1
0
3
1.3. Логическая функция от двух переменных
Определим размеры таблицы истинности для представления любых
функций, зависящих от двух переменных.
Количество наборов, на которых определена данная функция, равно
n
2
2 = 2 = 4. Всего функций, зависящих от двух переменных:
=
.
Таблица 2
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
0
0
0
0
1
1
1
1
0
Представим в таблице истинности четыре основные функции, зависящие от двух переменных, которые наиболее часто используются на
практике (табл. 2):
– функция дизъюнкции, логического сложения,
функция ИЛИ;
– функция инверсии логического сложения,
функция Пирса, функция ИЛИ-НЕ;
– функция конъюнкции, функция логического умножения, функция И;
– функция инверсии конъюнкции, функция Шеффера, функция И-НЕ.
1.4. Свойства логических переменных и логических функций
Логическая переменная х обладает следующими свойствами:
1) ̿ = – двойное отрицание переменной равно исходной переменой;
2)
ческого выражения;
3)
;
4)
,
5)
} – правила, позволяющие сократить длину логи-
.
Справедливость представленных свойств можно проверить путем
простого подставления значений 0 или 1 для переменной х.
4
Дизъюнкция и конъюнкция обладают рядом свойств, аналогичных
свойствам арифметических операций сложения и умножения.
1. Свойство ассоциативности (сочетательный) закон:
(1)
(2)
2. Свойство коммутативности (переместительный) закон:
(3)
(4)
3. Свойство дистрибутивности (распределительный) закон:
(5)
(5а)
4. Свойства, позволяющие перейти от операции дизъюнкции к операции конъюнкции и наоборот (законы де Моргана):
5. Законы поглощения:
=
(9)
6. Законы склеивания:
5
2. АНАЛИТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ
ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ
Любую логическую функцию можно представить при помощи таблицы истинности. Но эта довольно громоздкий способ, так как чем больше
переменных, от которых зависит функция, тем больше наборов, на которых определена эта функция, т. е. больше строчек в таблице. Поэтому при
большом количестве переменных предпочтительнее аналитический способ
задания функций, который дает более компактную запись.
2.1. Представление логических функций
в дизъюнктивной нормальной (ДНФ)
и совершенной дизъюнктивной нормальной формах (СДНФ)
Конъюнкция нескольких переменных, каждая из которых входит
в нее не больше одного раза с инверсией или без нее, называется элементарной конъюнкцией, элементарным произведением, минтермом, конституэнтой единицы.
Дизъюнкция нескольких элементарных конъюнкций называется
дизъюнктивной нормальной формой представления логической функции.
Например:
(12)
Дизъюнктивная нормальная форма представления функции называется совершенной дизъюнктивной нормальной формой, т. е. ДНФ называемой СДНФ, если каждая переменная, от которых зависит функция, входит
в каждую элементарную конъюнкцию только один раз с инверсией или
без нее. Например:
т. е. в выражении (12) во вторую конъюнкцию должна войти переменная х2, а в третью конъюнкцию – переменная х1.
Любая логическая функция может быть представлена в СДНФ.
2.2. Представление логических функций
в конъюнктивной нормальной (КНФ) СДНФ
Дизъюнкция нескольких логических переменных, в которую каждая
переменная входит не более одного раза с инверсией или без нее, называется элементарной дизъюнкцией, макстермом, конституэнтой нуля.
Конъюнкция нескольких элементарных дизъюнкций называется конъюнктивной нормальной формой представления функции КНФ. Например:
6
Конъюнктивная нормальная форма представления логической функции называется совершенной конъюнктивной нормальной формой, т. е.
КНФ называется СКНФ, если каждая переменная, от которых зависит
функция, входит в каждую элементарную дизъюнкцию не более одного раза с инверсией или без нее. Например:
т. е. в выражении (14) в первую дизъюнкцию должна войти переменная х2,
а в третью дизъюнкцию – переменная х1.
2.3. Ранги термов и суммы рангов ДНФ, СДНФ, КНФ и СКНФ
представления функций
Элементарные дизъюнкция и конъюнкция называются термами. Количество переменных, составляющих терм, образует ранг терма. Наприранг терма r = 3, для дизъюнкции
̅̅̅
мер, для конъюнкции
ранг терма r = 2.
Для выражения (12) сумма рангов R = r1 + r2 + r3 = 3 + 2 + 2 = 7.
Для выражения (15) сумма рангов R = r1 + r2 + r3 = 3 + 3 + 3 = 9.
Совершенные формы представления функций отличаются от нормальных форм суммой рангов. В совершенных формах сумма рангов
больше, так как ранг каждого терма в представлении функции максимален.
Максимум ранга определяется количеством переменных, от которых зависит логическая функция.
2.4. Способ представления логической функции в СДНФ и СКНФ
Представим таблицу истинности, например, для так называемой
мажоритарной функции, которая зависит от трех переменных (табл. 3).
Для этой функции значения на каждом наборе переменных определяются
значением большинства логических переменных. Определим размеры таблицы истинности в этом случае. Так как функция зависит от трех переменных, то количество наборов, на которых определена функция, равно 2 3,
т. е. 8. Таким образом, в таблице истинности будет 8 строк.
Таблица 3
СДНФ
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
СКНФ
0
0
0
1
0
1
1
1
7
Получим представление функции в СДНФ. В этой форме элементарные конъюнкции объединяются знаками дизъюнкции. Поэтому в столбце
СДНФ в таблице истинности нужно представить конъюнкции. Поскольку
конъюнкция – это конституэнта единицы, то нужно для единичных значений функции представить конъюнкции, в которых единичные переменные
для соответствующего набора берутся без инверсии, а нулевые – с инверсией. Теперь нужно объединить полученные конъюнкции знаком дизъюнкции:
(16)
Получим представление функции в СКНФ. В этой форме элементарные дизъюнкции объединяются знаком конъюнкции. Поэтому в столбце
СКНФ в таблице истинности нужно представить дизъюнкции. Поскольку
дизъюнкция – это конституэнта 0, то нужно для нулевых значений функции записать дизъюнкции, причем единичные переменные соответствующего набора переменных берутся с инверсиями, а нулевые – прямыми. Теперь нужно объединить полученные дизъюнкции знаками конъюнкции:
(17)
8
3. РЕАЛИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ ПРИ ПОМОЩИ
ЛОГИЧЕСКИХ ЭЛЕМЕНТОВ
3.1. Логические элементы
Информация в ЦВМ представляется в двоичном коде. Физическими
аналогами 0 и 1 являются сигналы, принимающие два хорошо различимых
значения. Например, потенциалы высокого и низкого уровней – потенциальный код, отсутствие или наличие электрического импульса – импульсный код.
Преобразование информации в ЦВМ сводится к согласованному изменению значений сигналов и описывается в термах алгебры логики. Для
реализации операций над двоичными сигналами используются логические
элементы.
Логическим элементом называется электрическая схема, реализующая элементарную логическую функцию и имеющая количество входов,
равное числу аргументов функции, и только один выход. Входные сигналы, поступающие на входы логического элемента, определяют значения
входных переменных. Значение выходного сигнала является функцией
значений входных сигналов. Для выполнения операций отрицания, дизъюнкции и конъюнкции используются логические элементы НЕ, ИЛИ, И.
Система из элементов ИЛИ и НЕ, а также И и НЕ являются функционально полными, т. е. из подобных элементов можно построить схемы, реализующие любые заданные логические функции. На рис. 1 представлены
условные обозначения логических элементов: НЕ, ИЛИ, И, ИЛИ-НЕ, И-НЕ:
а – нвертор – инвертирует только потенциальные сигналы. Для инвертирования импульсных сигналов используются элементы И-НЕ, ИЛИ-НЕ;
НЕ
Х1
Х
И
ИЛИ
Х1
1
Х2
а
&
Х2
б
ИЛИ-НЕ
Х1
1
Х2
в
г
И-НЕ
Х1
&
Х2
д
Рис. 1. Условные обозначения логических элементов
9
б – элемент ИЛИ – реализует операцию дизъюнкции, называется
дизъюнктором;
в – элемент И – реализует операцию конъюнкции, называется конъюнктором;
г – элемент ИЛИ-НЕ – является комбинацией дизъюнктора и инвертора, называется элементом Пирса (Р). Может использоваться в качестве
инвертора для импульсных сигналов (рис. 2). В этом случае на оба входа
двухвходового элемента Пирса необходимо подать переменную, которую
нужно проинвертировать, или же подать на один вход переменную, а на
второй вход 0.
Х
1
Х
1
Х
1
1
Х
Рис. 2
д – элемент И-НЕ – является комбинацией конъюнктора и инвертора,
называется элементом Шеффера (S). Аналогично элементу Пирса может
использоваться в качестве инвертора для импульсных сигналов (рис. 3). В
этом случае на оба входа двухвходового элемента Шеффера необходимо
подать переменную, которую нужно проинвертировать или же подать на
один вход переменную, а на второй вход 1.
Х
&
1
Х
Х
1
&
a)
1
1
б)
Рис. 3
3.2. Логические и комбинационные схемы
Последовательное соединение логических элементов, при котором
выход одного элемента соединен с входом другого элемента, соответствует
подстановке в логические функции в качестве аргументов других логических функций.
Совокупность логических элементов, организованная для выполнения операций над двоичными переменными (сигналами), называется логической схемой.
В зависимости от класса реализуемых функций логические схемы
подразделяются на комбинационные и последовательностные.
Логическая схема, реализующая систему логических функций, называется комбинационной схемой.
10
Выходные сигналы комбинационных логических схем в отличие от
последовательностных схем, имеющих память, определяются только значениями входных сигналов в любой данный момент времени.
3.3. Примеры построения логических схем
для реализации логических функций
Для реализации мажоритарной функции из п. 2.4 повторим аналитическое выражение этой функции в СДНФ (16):
Поскольку это выражение состоит из четырех элементарных конъюнкций, то потребуется для построения логической схемы четыре конъюнктора, а поскольку ранг каждой конъюнкции равен 3, то конъюнкторы
должны иметь по 3 входа. Выходы конъюнкторов нужно подать на дизъюнктор, так как конъюнкции в СДНФ объединяются знаком дизъюнкции.
Дизъюнктор будет четырехвходовым.
При построении схемы нужно учесть, что значения переменных будут подаваться на входы конъюнкторов с генератора. Код подачи может
быть монофазным. В этом случае значения переменных будут только прямыми. Если нужны и инверсные значения, то потребуется парафазный код
подачи переменных. В выражении (16) имеются как прямые, так и инверсные значения переменных, поэтому будем использовать парафазный код
подачи переменных. На рис. 4 приведена логическая схема реализации
мажоритарной функции, представленной в СДНФ.
&
&
1
&
&
Рис. 4
11
1
1
&
1
1
Рис. 5
Представим логическую схему мажоритарной функции в СКНФ. Для
этого повторим выражение этой функции в СКНФ (17):
Для построения схемы нужны четыре дизъюнктора, так как в выражении имеются четыре дизъюнкции. Дизъюнкторы будут трехвходовыми, поскольку ранг дизъюнкции равен 3. Выходы дизъюнкторов подаются на конъюнктор, который должен иметь четыре входа. Для схемы будет использоваться парафазный код подачи переменных с генератора на входы дизъюнкторов.
На рис. 5 представлена схема, реализующая мажоритарную функцию в СКНФ.
3.4. Функционально полные системы логических функций
Операция, в результате которой в качестве аргументов одной логической функции используются значения других логических функций, называется суперпозицией.
Одни логические функции можно выражать через другие.
Система функций алгебры логики называется функционально полной,
или базисом, если она позволяет через суперпозицию достаточного количества
повторений этой системы выразить любую логическую функцию.
К базису относится система функций И-ИЛИ-НЕ. Базисами также
являются системы, содержащие функции Шеффера и Пирса.
Базисы могут быть избыточными и минимальными.
Базис является минимальным, если удаление хотя бы одной функции
превращает систему в неполную.
Базис И-ИЛИ-НЕ является избыточным, так как из него возможно
удаление некоторых функций по законам де Моргана.
12
4. ИСПОЛЬЗОВАНИЕ ЗАКОНОВ ДЕ МОРГАНА
ДЛЯ ПОСТРОЕНИЯ ЛОГИЧЕСКИХ СХЕМ,
РЕАЛИЗУЮЩИХ ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ
4.1. Перевод логической функции, представленной в СДНФ, в СКНФ
Для того чтобы поменять знак одной логической операции на другой, в данной задаче знак дизъюнкции на знак конъюнкции между термами, т. е. перейти от СДНФ к СКНФ, необходимо воспользоваться законами
де Моргана (см. выражения (6) и (7)).
Повторим логическую функцию в СДНФ (16):
По законам де Моргана (6), т. е. используя отрицание дизъюнкции,
перейдем к знаку конъюнкции, но переменные возьмем с отрицаниями.
Таким образом, в выражении (16) необходимо отрицание над знаками дизъюнкции. Одно отрицание проинвертирует значение функции, поэтому воспользуемся двойным отрицанием, т. е.
̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿
(18)
Верхняя инверсия остается без изменений, а нижняя по выражению (6)
разрывается и меняет знак дизъюнкции на знак конъюнкции, т. е.
(19)
=
В выражении (19) над элементарными конъюнкциями появились инверсии. По законам де Моргана (7) отрицание конъюнкции дает дизъюнк, поэтому
цию отрицаний:
=
(20)
Таким образом, логическая функция в СДНФ (16), после использования законов де Моргана записывается как выражение (20), а это – инверсия
СКНФ.
Поэтому можно сделать вывод, что
СДНФ =
(21)
4.2. Перевод логической функции,
представленной в СКНФ, в СДНФ
Повторим логическую функцию в СКНФ (17):
Для перевода этой функции в СДНФ проведем преобразования из п. 4.1.
=
13
.
(22)
Выражение (22) – это инверсия от СДНФ.
Таким образом, СДНФ =
(23)
4.3. Построение логических схем в базисе Шеффера
для логической функции, заданной в СДНФ
Повторим функцию в СДНФ (16):
.
Чтобы реализовать эту функцию в базисе Шеффера, нужно вспомнить, что базис Шеффера – это операции И-НЕ. Здесь отсутствует операция дизъюнкции, которая присутствует в СДНФ (16). Воспользуемся законами де Моргана, т. е. возьмем двойное отрицание от выражения (16), т. е.
̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿,=
(24)
Верхнее отрицание останется без изменения, а нижнее, разрываясь, поменяет знак дизъюнкции на знак конъюнкции по законам де Моргана (6), т. е.
Выражение (25) записано в базисе Шеффера, т. е. присутствуют
только операции И-НЕ. Поэтому можно записать:
(
(26)
)
В выражении (26) под символом S понимается логический элемент
Шеффера. В скобках представлены переменные, которые являются входными
сигналами соответствующих элементов Шеффера. Поскольку переменные
имеют инверсии, то выражение (26) записано для парафазного хода подачи
переменных. На рис. 6 приведена логическая схема для функции (16) в базисе
Шеффера для парафазного кода подачи переменных.
Чтобы представить схему на рис. 6 для монофазного кода подачи переменных, нужно в выражении (26) для каждой переменой с отрицанием
использовать элемент Шеффера (см. п. 3.1, рис. 3). Выражение (26) перепишем для монофазного кода подачи переменных:
(
(
)
)
(27)
На рис. 7 приведена схема для функции (16) в базисе Шеффера для монофазного кода подачи переменных.
14
&
&
&
&
&
Рис. 6
&
&
&
&
&
&
&
&
Рис. 7
15
4.4. Построение логических схем в базисе Пирса
для логической функции, заданной в СДНФ
Повторим функцию в СДНФ (16):
Чтобы реализовать эту функцию в базисе Пирса, нужно вспомнить,
что базис Пирса – это операции ИЛИ-НЕ. Здесь отсутствует операция
конъюнкции, которая присутствует в элементарных конъюнкциях в СДНФ
(16). Воспользуемся законами де Моргана, т. е. возьмем двойное отрицание для каждой элементарной конъюнкции в выражении (16), т. е.
̿̿̿̿̿̿̿̿̿ ̿̿̿̿̿̿̿̿̿ ̿̿̿̿̿̿̿̿̿ ̿̿̿̿̿̿̿̿̿ =
(28)
Все верхние отрицания останутся без изменения, а нижние, разрываясь,
поменяют знак конъюнкции в каждом терме в (16) на знак дизъюнкции по
законам де Моргана (7), т. е.
=
=
(29)
Чтобы выражение (29) можно было представить в базисе Пирса,
нужно взять двойное отрицание от всего выражения, т. е.
̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿
(30)
Выражение (30) записано в базисе Пирса, так как присутствуют
только операции ИЛИ-НЕ. Его можно представить в символах Р, где под
каждым символом Р понимается логический элемент Пирса, т. е.

 
 

= РР ( Р х1, х2 , х3 , Р х1, х2 , х3 , Р х1, х2 , х3 , Р ( х1, х2 , х3 )).
(31)
В скобках представлены переменные, которые являются входными
сигналами для соответствующих элементов Пирса. Поскольку переменные
имеют инверсии, то выражение (31) записано для парафазного кода подачи
переменных.
На рис. 8 приведена логическая схема для функции (16) в базисе
Пирса для парафазного кода подачи переменных.
Чтобы представить схему на рис. 8 для монофазного кода подачи переменных, нужно в выражении (31) для каждой переменной с отрицанием
использовать элемент Пирса (см. п. 3.1, рис. 2). Выражение (31) перепишем для монофазного кода подачи переменных,т. е.

 

= РР Р  х1), Р( х2 ), Р( х3  , Р Р  х1  , х2 , Р  х3  , Р  Р  х1  , Р  х2  , х3  ,


Р Р  х1  , Р  х2  , Р  х3  .
(32)
На рис. 9 показана логическая схема для функции (16) в базисе Пирса для монофазного кода подачи переменных.
16
1
1
1
1
1
1
Рис. 8
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Рис. 9
17
4.5. Построение логических схем в базисе Шеффера
для логической функции, заданной в СКНФ
Повторим функцию в СКНФ (17):
Чтобы реализовать эту функцию в базисе Шеффера, нужно вспомнить, что базис Шеффера – это операции И-НЕ. Здесь отсутствует операция
дизъюнкции, которая присутствует в элементарных дизъюнкциях в СКНФ
(17). Воспользуемся законами де Моргана, т. е. возьмем двойное отрицание от каждой элементарной дизъюнкции в выражении (17), т. е.
̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿ ̿̿̿̿̿̿̿̿̿̿̿̿̿̿, =
(33)
Все верхние отрицания останутся без изменения, а нижние, разрываясь, поменяют знак дизъюнкции в каждом терме в (17) на знак конъюнкции по законам де Моргана, т. е.
=(
)(
)(
)(
)
Чтобы выражение (34) можно было записать в базисе Шеффера,
нужно взять двойное отрицание от всего выражения, т. е.
̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿
=(
)(
)(
)(
)
Выражение (35) записано в базисе Шеффера, так как присутствуют
только операции И-НЕ. Его можно представить в символах S, где под каждым символом S понимается логический элемент Шеффера, т. е.
(
(
))
В скобках представлены переменные, которые являются входными
сигналами для соответствующих элементов Шеффера. Поскольку переменные имеют инверсии, то выражение (36) записано для парафазного кода подачи переменных.
На рис. 10 приведена логическая схема для функции (17) в базисе
Шеффера для парафазного кода подачи переменных.
Чтобы представить схему на рис. 10 для монофазного кода подачи
переменных, нужно в выражении (36) для каждой переменной с отрицанием использовать элемент Шеффера (см. п. 3,1, рис. 3). Выражение (36) перепишем для монофазного кода подачи переменных, т. е.
(
(
)
(
)
)
37)
На рис. 11 показана логическая схема для функции (17) в базисе
Шеффера для монофазного кода подачи переменных.
18
х1 х1 х2 х2 х3 х3
&
&
&
&
&
&
Рис. 10
&
&
&
&
&
&
&
&
&
&
&
&
&
&
&
Рис. 11
19
4.6. Построение логических схем в базисе Пирса
для логической функции, заданной в СКНФ
Запишем функцию в СКНФ (17):
Чтобы реализовать эту функцию в базисе Пирса, нужно вспомнить,
что базис Пирса – это операции ИЛИ-НЕ. Здесь отсутствует операция
конъюнкции, которая присутствует в СКНФ (17). Воспользуемся законами
де Моргана, т. е. возьмем двойное отрицание от выражения (17):
̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿
(38)
Верхнее отрицание останется без изменения, а нижнее, разрываясь,
поменяет знак конъюнкции на знак дизъюнкции по законам де Моргана (7):
Выражение (36) записано в базисе Пирса, т. е. присутствуют только
операции ИЛИ-НЕ. Его можно представить в символах Р, где под каждым
символом Р понимается логический элемент Пирса, т. е.
=P(P(
),P(
),P(
),P(
)).
(40)
В скобках представлены переменные, которые являются входными
сигналами для соответствующих элементов Пирса. Поскольку переменные
имеют инверсии, то выражение (40) записано для парафазного кода подачи
переменных.
На рис. 12 приведена логическая схема для функции (17) в базисе
Пирса для парафазного кода подачи переменных.
х1 х1 х2 х2 х3 х3
1
1
1
1
1
Рис. 12
20
Чтобы представить схему на рис. 12 для монофазного кода подачи
переменных, нужно в выражении (40) для каждой переменной с отрицанием использовать элемент Пирса (см. п. 3.1, рис. 2). Выражение (40) перепишем для монофазного кода подачи переменных:
= P(P(
P(
),P(
,
),P(P( )
)).
(41)
На рис. 13 представим логическую схему для функции (17) в базисе
Пирса для монофазного кода подачи переменных.
1
1
1
1
1
1
1
1
Рис. 13
21
5. МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ
5.1. Понятие диаграммы Вейча
Минимизация – это процесс преобразования логических функций
к такому виду, который допускает наиболее простую, с наименьшим числом логических элементов, имеющих наименьшее число входов, физическую реализацию функции. Частная задача минимизации логических
функций сводится к такому представлению заданной функции, которое содержит наименьшее возможное число переменных и наименьшее возможное число операций над ними.
ДНФ и КНФ представления логических функций имеют меньшую
сумму рангов, чем СДНФ и СКНФ для этих же функций. Поэтому возникает задача нахождения для логических функций представления их в ДНФ
и КНФ с минимальной суммой рангов.
Для небольшого количества переменных (n = 2, 3, 4) приемлемым
способом минимизации являются диаграммы Вейча, которые представляют собой разновидность карт Карно.
Известно, что любую логическую функцию можно задать при помощи таблицы истинности. Диаграмма Вейча – это та же таблица истинности, только другим образом организованная, так как содержит ту же самую
информацию, что и таблица истинности.
Диаграмма Вейча представляет собой квадрат или прямоугольник,
разделенные на 2n клеток, где n – количество переменных, от которых зависит функция.
Если n – четное, то диаграмма Вейча – квадрат, сторона которого
разделена на ⁄ клеток.
Ели n – нечетное, то диаграмма Вейча – это прямоугольник, у котоклеток, а вторая – на
клеток.
рого одна сторона разделена на
Но в любом случае общее количество клеток в диаграмме Вейча 2n.
Такое же количество строк в таблице истинности, так как 2n – это количество наборов переменных, на которых существует заданная логическая
функция.
В таблице истинности каждому набору переменных ставится в соответствие значение функции, которое она принимает на этом наборе.
В диаграмме Вейча каждая клетка соответствует определенному
набору переменных, поэтому в эту клетку проставляется соответствующее
значение функции.
Чтобы каждая клетка диаграммы Вейча соответствовала определенному набору переменных, проводят разметку диаграммы, причем таким
образом, чтобы для соседних клеток диаграммы был справедлив закон
склеивания.
Рассмотрим диаграмму Вейча для двух переменных. В качестве
примера приведем функцию дизъюнкции (см. п. 1.3, табл. 2).
22
Таблица истинности функции дизъюнкции, зависящей от двух переменных, имеет следующий вид (табл. 4).
Таблица 4
х1 х2
f
0 0
0
0 1
1
1 0
1
1 1
1
На рис. 14 представлена диаграмма Вейча для этой функции. Она является квадратом и содержит 4 клетки. Проведена правосторонняя разметка. Под чертой разметки значения переменной – единичные, при отсутствии в нулевых клетках согласно разметке проставлен набор переменных,
который соответствует данной клетке. В самой клетке проставлено значение функции, которое она принимает на этом наборе.
X1
X2
00
10
0
1
01
11
1
1
Рис. 14
Рассмотрим применение закона склеивания (10) для соседских
клеток.
На наборе х1 = 1, х2 = 0 значение функции равно 1. На наборе х1 = 1,
х2 = 1 значение функции также равно 1.
Запишем дизъюнкцию элементарных конъюнкций наборов этих
клеток
Выражение (42) показывает применение закона склеивания для соседних клеток диаграммы Вейча, что позволяет уменьшить сумму рангов
выражения. В этом и заключается процесс минимизации при помощи диаграмм Вейча.
Таким образом, разметка диаграммы Вейча должна производиться
так, чтобы для соседних клеток был применим закон склеивания, который
позволяет уменьшать сумму рангов выражения.
23
Рассмотрим диаграмму Вейча для трех переменных и ее разметку.
В данном случае она представляет собой прямоугольник, содержащий 8 клеток, так как функция в этом случае существует на 8 наборах
переменных: 23 = 8. На рис. 15 представлена диаграмма Вейча для мажоритарной функции (см. табл. 3).
x2
x1
000
100
110
100
0
0
1
0
001
011
111
101
0
1
1
1
x3
Рис. 15
В углу каждой клетки проставлен набор переменных в соответствии
с приведенной разметкой, а внутри клетки проставлено значение функции,
которое она приобретает на этом наборе.
5.2. Соседние клетки и соседние области в диаграмме Вейча
Диаграмма Вейча заполняется так же, как и таблица истинности.
В клетку, которая соответствует набору, где функция принимает единичное значение, проставляется 1. В клетку, которая соответствует набору, где
функция принимает значение «0», может проставляться нуль, но чаще эту
клетку оставляют пустой, чтобы не загромождать диаграмму. Если функция не определена на каком-то наборе, то в этой клетке ставится прочерк.
Две клетки диаграммы Вейча называются соседними, если они имеют общее ребро и к конъюнкциям, соответствующим их набором переменных, применим закон склеивания.
В любой диаграмме соседними клетками являются не только смежные, но и клетки, находящиеся на противоположных концах любой строки
или столбца. Эти клетки становятся смежными (имеющими общее ребро),
если диаграмму свернуть по горизонтали или вертикали в цилиндр, а затем
концы полученного цилиндра замкнуть в кольцо.
Соседние клетки объединяются в соседние области. Областями соседних клеток являются прямоугольники с количеством клеток, кратным 2m.
Чем больше клеток входит в соседнюю область, тем по большему количеству переменных происходит склеивание, тем меньше будет сумма рангов
конечного выражения.
24
5.3. Пример минимизации мажоритарной функции по единицам
При записи аналитического выражения для функции по таблице истинности для использования единичных значений функции каждому значению ставится в соответствие конъюнкция из переменных данного набора
как конституэнта «1». Эти конъюнкции соединяют знаками дизъюнкции
и получается выражение функции в СДНФ (16).
При минимизации функции по диаграмме Вейча по единицам выражение функции будет в ДНФ, причем сумма рангов выражения должна
быть минимальной.
В процессе минимизации нужно покрыть клетки с единичными значениями прямоугольниками – соседними областями максимально возможных размеров (количество клеток в области кратно 2m). Каждой соседней
области ставится в соответствие конъюнкция, в которой будут отсутствовать те же переменные, которые изменяют в этой области свои значения – по ним происходит склеивание. Эти конъюнкции объединяют знаками дизъюнкции и получается выражение для логической функции
в ДНФ.
Следует иметь в виду, что одна и та же клетка может входить в несколько соседних областей, но в каждой соседней области должна быть
хотя бы одна клетка, принадлежащая только этой соседней области.
Если клетка с прочерком увеличивает соседнюю область, то ее нужно использовать, считая прочерк единичным значением функции, если же
такая клетка не входит в соседние области, то ее не учитывают при минимизации.
На рис. 16 в качестве примера приведена диаграмма Вейча для мажоритарной функции (см. рис. 15) по единицам.
x2
x1
1
1
x3
1
3
1
1
2
Рис. 16
В диаграмме на рис. 16 пустые клетки соответствуют нулевым значениям функции.
В диаграмме найдены три соседние области, каждая из которых содержит по две клетки. Одна «1» входит во все соседние области, но в каждой области есть одна клетка, принадлежащая только этой области.
25
Запишем выражение для данной диаграммы:
– первой соседней области соответствует конъюнкция: х1х3 (единичные переменные в конъюнкцию входят без инверсии);
– второй соседней области соответствует конъюнкция: х2х3;
– третьей соседней области соответствует конъюнкция: х1х2.
Представим выражение в ДНФ:
.
Сумма рангов этого выражения равна: 2 + 2 + 2 = 6.
Если сравнить полученную сумму рангов с суммой рангов для выражения этой функции в СДНФ (16), которая равна 12, то выигрыш очевиден.
5.4. Пример минимизации мажоритарной функции по нулям
При записи аналитического выражения для функции по таблице истинности при использовании нулевых значений функции каждому значению ставится в соответствие дизъюнкция из переменных данного набора
как конституэнта «0». Эти дизъюнкции соединяют знаками конъюнкции
и получается выражение функции в СКНФ (17).
При минимизации функции по диаграмме Вейча по нулям выражение функции будет в КНФ, причем сумма рангов выражения должна быть
минимальной.
В процессе минимизации нужно покрыть клетки с нулевыми значениями прямоугольниками – соседними областями максимально возможных размеров (количество клеток в области кратно 2m). Каждой соседней
области ставится в соответствие дизъюнкция, в которой будут отсутствовать те переменные, которые изменяют в этой области свои значения (по
ним происходит склеивание). Эти дизъюнкции объединяют знаками конъюнкции и получается выражение для логической функции в КНФ.
Следует иметь в виду, что одна и та же клетка может входить в несколько соседних областей, но в каждой области должна быть хотя бы одна клетка, принадлежащая только этой соседней области.
Если клетка с прочерком увеличивает размеры соседней области, то
ее нужно использовать, считая прочерк нулевым значением функции, если
же такая клетка не входит в соседнюю область, то ее не учитывают при
минимизации.
На рис. 17 в качестве примера приведена диаграмма Вейча для мажоритарной функции (см. рис. 15) по нулям.
В диаграмме на рис. 17 пустые клетки соответствуют нулевым значениям функции.
В диаграмме найдены три соседние области, каждая из которых содержит по две клетки. Область три получается при сворачивании диаграммы Вейча в цилиндр по вертикальной оси. Один «0» входит во все соседние области,
но в каждой области есть одна клетка, принадлежащая только этой области.
26
x2
3
x1
3
1
1
x3
1
1
2
1
Рис. 17
Запишем выражение для данной диаграммы:
– первой соседней области соответствует дизъюнкция: х1 v х3 (нулевые переменные в дизъюнкцию входят без инверсии);
– второй соседней области соответствует дизъюнкция: х1 v х2;
– третьей соседней области соответствует дизъюнкция: х2 v х3.
Представим выражение в КНФ
Сумма рангов этого выражения равно: 2 + 2 = 2 = 6.
Если сравнить полученную сумму рангов с суммой рангов для выражения этой функции в СКНФ (17), которая равна 12, то выигрыш очевиден.
5.5. Построение логической схемы в базисе Шеффера
для логической функции, представленной в ДНФ (43)
Для реализации схемы в базисе Шеффера нужно вспомнить, что базис Шеффера, это операции И-НЕ (см. п. 4.5). Воспользуемся законами де
Моргана и выполним некоторые преобразования:
̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿
=S(S(
),S(
),S(
)).
=
(44)
Выражение (44) представлено для построения логической схемы
в базисе Шеффера. Поскольку в (44) отсутствуют переменные с инверсиями будем использовать монофазный код подачи переменных. На рис. 18
приведена логическая схема в базисе Шеффера для логической функции
в ДНФ (42).
27
&
&
&
&
Рис. 18
5.6. Построение логической схемы в базисе Пирса
для логической функции, представленной в КНФ (43)
Для реализации схемы в базисе Пирса необходимо вспомнить, что
базис Пирса – это операции ИЛИ-НЕ (см. п. 4.6). Воспользуемся законами
де Моргана и выполним некоторые преобразования:
̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿
(
)
1
1
&
1
1
Рис. 19
Выражение (45) является основой для построения логической схемы
в базисе Пирса. Поскольку в (45) отсутствуют переменные с инверсиями,
будем использовать монофазный код подачи переменных. На рис. 19 приведена логическая схема в базисе Пирса для логической функции в КНФ (43).
28
6. МАЖОРИТАРНАЯ ЛОГИЧЕСКАЯ ФУНКЦИЯ,
ЗАВИСЯЩАЯ ОТ ЧЕТЫРЕХ ПЕРЕМЕННЫХ
6.1.Таблица истинности для мажоритарной функции,
зависящей от четырех переменных.
Представление функции в СДНФ, СКНФ
Поскольку функция зависит от четырех переменных, то количество строк
в таблице, т. е. количество наборов, на которых функция определена, равняется 2n = 24 = 16. Значения функции определяются значениями большинства переменных набора. Если в наборе две переменных равны 1 и две другие переменные равны 0, то значение функции неопределенно и проставляется прочерк (табл. 5).
Таблица 5
х1 х2 х3 х4
f
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
0
0
0
0
1
0
1
1
1
1
СДНФ
СКНФ
х1  х2  х3  х4
х1  х2  х3  х4
х1  х2  х3  х4
х1  х2  х3  х4
х1х2 х3 х4
х1  х2  х3  х4
х1 х2 х3 х4
х1х2 х3 х4
х1х2 х3 х4
х1х2 х3 х4
Представим функцию в СДНФ. Для этого нужно объединить элементарные конъюнкции, соответствующие наборам переменных, где
функция принимает единичные значения, знаками дизъюнкции.
f  x1, x2 , x3 , х4   х1х2 х3 х4  х1 х2 х3х4  х1х2 х3х4  х1х2 х3 х4  х1х2 х3х4 . (46)
Сумма рангов функции равна R = 20.
Представим функцию в СКНФ. Для этого нужно объединить элементарные дизъюнкции, соответствующие набором переменных, где функция
принимает нулевые значения, знаками конъюнкции.
f  x1, x2 , x3 , х4   ( х1  х2  х3  х4 )( х1  х2  х3  х4 )
(47)
( х1  х2  х3  х4 )( х1  х2  х3  х4 )( х1  х2  х3  х4 ).
Сумма рангов функции равна R = 20.
29
6.2. Минимизация мажоритарной функции
при помощи диаграммы Вейча
Диаграмма Вейча в данном случае будет квадратом, разделенным на
16 клеток, каждая из которых соответствует своему набору переменных
(рис. 20).
В диаграмме на рис. 20 в клетках проставлены значения наборов переменных и соответствующие им значения функций. Пустые клетки соответствуют нулевым значениям функции.
Рис. 20
Для диаграммы на рис. 20 найдены две соседние области для единичных значений функции: области 1 и 2. Области содержат по четыре
клетки, клетки с прочерками в данном случае увеличивают размеры областей, поэтому используются.
Запишем выражение функции в ДНФ:
Сумма рангов выражения (48) R = 4.
Для нулевых значений функции найдены две соседние области по
четыре клетки: 3 и 4. Эти соседние области также имеют в своем составе
клетки с прочерками.
30
Запишем выражение в КНФ:
Сумма рангов выражения (49) R = 4.
Таким образом, можно сделать вывод, что использование диаграммы
Вейча для минимизации логических функций является достаточно простыми эффективным способом уменьшения суммы рангов выражений, т. е.
упрощения функций для реализации этих функций при помощи логических схем. Необходимо помнить, что выражение в ДНФ или КНФ должно
быть минимальным ДНФ или КНФ, т. е. не подлежащие дальнейшему
упрощению и должны иметь минимальные суммы рангов.
31
7. КОНТРОЛЬНЫЕ ВОПРОСЫ
7.1. Найти сумму рангов выражения функции, которая задана диаграммой Вейча на рис. 21. Проминимизировать по единицам и нулям.
5
X2
7
X1
6
7
1
X4
4
-
-
1
1
6
1
3
1
X3
7
7
5
5
2
1
Рис. 21
Для единичных значений найдены три соседних области (1, 2 и 3).
Запишем выражение в ДНФ:
Сумма рангов R = 7.
Для нулевых значений найдены четыре соседние области, содержащие по четыре клетки: 4, 5, 6, 7. Запишем выражение в КНФ:
Сумма рангов полученного выражения (51) равна R = 8.
7.2. Сколько клеток в диаграмме Вейча нужно отметить единицами,
если функция в ДНФ имеет вид:
Необходимо представить диаграмму Вейча для четырех переменных.
Далее для каждой конъюнкции из ДНФ нужно поставить в соответствие
соседнюю область (рис. 22).
На рис. 21 показаны соседние области для конъюнкций в (52): 1, 2, 3.
Количество клеток, отмеченных 1, равно 9.
32
X2
X1
1
3
3
1
1
1
X4
1
1
1
1
1
1
2
X3
3
3
Рис. 21
7.3. Какое выражение соответствует приведенной на рис. 22 схеме?
1
1
)
1
1
f
&
&
&
)(
Рис. 22
)
Для ответа на данный вопрос нужно после каждого логического элемента, учитывая переменные на входах, записать результат операции на
выходе и последовательно записать полученное выражение. А далее,
используя законы де Моргана, привести выражение к ДНФ, т. е. к элементарным конъюнкциям объединенным знаками дизъюнкции (53):
[(
) (
)] [(
)(
)]
33
] [ ̿̿̿̿̿̿
[
̿̿̿̿̿̿ ]
Выражение (54) представлено в ДНФ.
7.4. Сколько нужно элементов типа И-НЕ – элементов Шеффера,
с числом входов не более двух для построения логической схемы по выражению в ДНФ:
Вначале это выражение нужно привести к базису Шеффера. Воспользуемся законами де Моргана^
̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿
),S(
S(S(
),S(
)).
(56)
Выражение (56) представлено в базисе Шеффера, но первый и третий
элементы Шеффера, а также выходной элемент Шеффера в схеме имеют
по три входа. Воспользуемся следующим преобразованием:
̿̿̿̿̿̿ ,
S(
Т. е.
) = S(SS(
(57)
),S( )).
(58)
Проведем следующие преобразования:
̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿̿
̿̿̿̿̿̿
̿̿̿̿̿̿
=
(
(
)
)
(60)
В выражении (59) пронумерованы все инверсии, эти номера совпадают с номерами логических элементов Шеффера, имеющих не более двух
входов в выражении (60), для которого построим логическую схему, используя парафазный код подачи переменных (рис. 23).
Рис. 23
34
Библиографический список
1. Мишура О. В. Цифровые автоматы. Основы алгебры логики. Минимизация логических функций при помощи диаграмм Вейча: метод. указ.
для студентов 2-го курса заочной формы обучения. СПб.: ГУАП, 2012.
2. Пятибратов А. П., Кирпиченко А. А., Гудьно Л. П. Вычислительные системы, сети и телекоммуникации. М.: Финансы и статистика, 2002.
3. Фрикс К. Вводный курс цифровой электроники. М.: Техносфера,
2004.
СОДЕРЖАНИЕ
1. Основные понятия алгебры логики ........................................................................................... 3
2. Аналитическое представление функций алгебры логики ................................................... 6
3. Реализация логических функций при помощи логических элементов ............................. 9
4. Использование законов де Моргана для построения логических схем,
реализующих функции алгебры логики ................................................................................ 13
5. Минимизация логических функций ........................................................................................ 22
6. Мажоритарная логическая функция, зависящая от четырех переменных .................... 29
7. Контрольные вопросы................................................................................................................. 32
Библиографический список ........................................................................................................... 35
35
Документ
Категория
Без категории
Просмотров
0
Размер файла
2 013 Кб
Теги
osnovy, logika, mishyra, algebra
1/--страниц
Пожаловаться на содержимое документа