ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 16671
Скачиваний: 202
141
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1. Нанесите на карту Вейча функцию
).
(
)
(
AD
BC
CD
AB
f
+
⊕
+
=
Сколько всего единиц на карте и сколько на ней клеток, где
записано по две единицы?
2. Найдите производную по аргументу E и нанесите её на
карту Вейча:
.
E
C
B
E
D
A
BCE
ABE
f
+
+
+
=
Сколько в производной минтермов и сколько букв в
минимальной ДНФ производной?
3. Укажите десятичные номера минтермов функции
,
f
E
∂
∂
если
.
D
C
B
E
C
A
BD
BC
AE
f
+
+
+
+
=
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
6.8 Симметрические булевы функции
Булева функция называется симметрической, если она инвариантна отно-
сительно всякой перестановки ее аргументов [4, с. 54; 14, с. 238; 23, с. 277].
Простейшими примерами симметрических функций являются выражения:
(
)
(
)
,
,
,
,
f A B
AB
f A B
A
B
=
= +
так как
,
.
f
AB
BA
f
A
B
B
A
=
=
= + = +
Если в записи функции содержатся инверсные аргументы, то в некоторых
случаях она также может быть симметрической. Например, выражение
B
A
f =
не относится к классу симметрических функций, поскольку
.
A
B
B
A
≠
Если же переставить местами буквы в выражении
,
)
,
(
B
A
B
A
B
A
f
+
=
то функция не изменится. Следовательно, она является симметрической.
Всего возможно n! перестановок n переменных. Заметим, что при пере-
становках меняются местами только буквы, а знаки конъюнкции, дизъюнкции и
инверсии остаются на своих местах. Рассмотрим, например, функцию
142
.
)
,
,
(
BC
A
C
AB
C
B
A
f
+
=
За счёт перестановок переменных получаем следующий список функций:
;
)
,
,
(
1
BC
A
C
AB
C
B
A
f
+
=
;
)
,
,
(
2
CB
A
B
AC
B
C
A
f
+
=
;
)
,
,
(
3
AC
B
C
BA
C
A
B
f
+
=
;
)
,
,
(
4
AB
C
B
CA
B
A
C
f
+
=
;
)
,
,
(
5
CA
B
A
BC
A
C
B
f
+
=
.
)
,
,
(
6
BA
C
A
CB
A
B
C
f
+
=
В этом списке первое выражение является исходным. Все остальные по-
лучены путём перестановки переменных в записях функций. В результате пере-
становок получилось:
1
6
( , , )
( , , );
f A B C
f C B A
=
2
5
( , , )
( , , );
f A C B
f B C A
=
3
4
( , , )
( , , ).
f B A C
f C A B
=
Остальные пары функций образуют неравенства, например:
1
2
( , , )
( , , );
f A B C
f A C B
≠
3
6
( , , )
( , , ).
f B A C
f C B A
≠
Так как функция остаётся неизменной не при всех перестановках пере-
менных, то в класс симметрических она не входит.
В общем случае симметрическую функцию можно выразить через набор
а-чисел [48], или рабочих чисел [57], где а-число (а также рабочее число) пока-
зывает, сколько аргументов должны принять единичное значение, чтобы функ-
ция также была равной единице. Например, рассмотрим следующую симметри-
ческую функцию:
4
( , , , , )
,
S A B C D E
ABCDE
ABCDE
ABCDE
ABCDE
ABCDE
=
+
+
+
+
где S
4
– условное обозначение симметрической функции с а-числом, равным 4.
Эта функция зависит от пяти аргументов и принимает единичное значение
только в том случае, когда единичное значение принимают точно четыре аргу-
мента из пяти.
Симметрические функции с одиночными а-числами не поддаются мини-
мизации в смысле Квайна, так как все минтермы таких функций являются про-
стыми импликантами. Минимизация возможна лишь при нескольких а-числах
и при условии, что среди них имеется хотя бы два а-числа, разность которых
143
равна единице. Примером может служить симметрическая функция вида
2,3,4
( , , , ),
S
A B C D содержащая три а-числа. Две пары из этих трёх а-чисел со-
держат признак возможности минимизации. Это а-числа 2 и 3, а также 3 и 4.
СДНФ функции имеет вид:
2,3,4
( , , , ) (3, 5, 6, 7, 9,10,11,12,13,14,15).
S
A B C D =
Минимизируем ее, например, при помощи карты Вейча:
2,3,4
( , , , )
.
S
A B C D
AB
AC
AD
BC
BD
CD
=
+
+
+
+
+
Среди симметрических функций n переменных особое значение имеют
две функции, получившие названия «чёт» и «нечёт»: f
чёт
и f
нечёт
. Первая из них
состоит из всех чётных а-чисел, вторая – из всех нечётных. Например, при n = 6
функции f
чёт
и f
нечёт
имеют вид:
чёт
0,2,4,6
( , , , , , );
f
S
A B C D E F
=
нечёт
1,3,5
( , , , , , ).
f
S
A B C D E F
=
В СДНФ этих функций нет ни одной пары склеивающихся минтермов,
следовательно, обе функции не поддаются минимизации (по Квайну), т. е. все
входящие в них минтермы являются простыми импликантами, а сокращённые,
тупиковые и минимальные ДНФ совпадают с СДНФ. На карте Вейча единицы
функций f
чёт
и f
нечёт
располагаются в шахматном порядке.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1. Сколько конъюнкций содержит ДНФ симметрической
функции семи переменных, если её а-число равно 3?
2. Укажите номера функций, в которых имеются склеиваю-
щиеся минтермы (все функции зависят от переменных A, B, C, D, E,
F):
1) S
0,2,4,6
; 2) S
0,3,4
; 3) S
0,1,4,6
; 4) S
0,2,5,6
; 5) S
0,4,6
; 6) S
0,2,5
; 7) S
0,3,4,5
.
3. Укажите номера симметрических функций:
1)
0;
f =
2)
1;
f =
3)
( , )
;
f A B
AB
=
4) ( , )
;
f A B
A
=
5)
( , )
.
f A B
A
=
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
144
7 Булева алгебра и контактные структуры
7.1 Вводные сведения
Контактный элемент – это устройство, замыкающее и размыкающее элек-
трическую цепь. К контактным элементам относятся кнопки, тумблеры, элек-
тромагнитные реле. Принцип их работы носит четко выраженный двоичный
характер: «включено – выключено», без каких-либо промежуточных состояний.
Такие элементы называют бистабильными.
Контактные схемы, построенные из бистабильных элементов, распадают-
ся на два непересекающихся класса:
1) параллельно-последовательные схемы;
2) мостиковые структуры.
В первом случае для упрощения переключательных схем широко приме-
няется булева алгебра, особенно такие её разделы, как минимизация нормаль-
ных (дизъюнктивных и конъюнктивных) форм булевых функций и повышение
их порядка, в пределе сводящееся к поиску абсолютно минимальных форм.
В классе мостиковых контактных структур булева алгебра также находит
применение, но в этой сфере её значение по сравнению с параллельно-
последовательными схемами существенно ниже. Здесь всё зависит от изобрета-
тельности и инженерной смекалки разработчика, занятого поиском экономич-
ных решений, так как для структур мостикового типа до сих пор не найдены
практические методы, при помощи которых обеспечивалась бы возможность
нахождения предельно экономичных контактных структур.
Контактные схемы разрабатываются в два этапа. На первом этапе выпол-
няется только логический расчёт. Его результатом является контактная схема,
где указаны все электрические соединения переключающих элементов, харак-
теризующихся только одним свойством – соединять или разъединять какие-
либо точки электротехнического устройства. На втором этапе выбираются кон-
тактные элементы с необходимыми техническими характеристиками, такими
как величина коммутируемого тока, рабочее напряжение, скорость переключе-
ния и т. д. Первый этап является важнейшим. Ошибка в логической схеме, как
правило, полностью обесценивает работу не только первого этапа, но и второго.
В связи с этим в данном пособии всё внимание уделено только первому этапу,
т. е. вопросам логического проектирования контактных структур.
145
7.2 Тумблеры
Одним из наиболее простых контактных элементов является тумблер. На
рисунке 7.1, а показано условное обозначение простейшего двухпозиционного
тумблера, имеющего два вывода: m и n. Тумблеры обычно имеют два равно-
правных устойчивых состояния. Одно из них условно называют «включено»,
другое – «выключено». Из одного состояния в другое тумблер переводится при
помощи специальной ручки, переключающего рычажка. Какое состояние счи-
тается включенным, а какое – выключенным, обычно определяется по положе-
нию переключающей ручки тумблера, установленного на каком-либо щитке.
Нижнее положение ручки, как правило, обозначает «выключено», верхнее –
«включено».
Рис. 7.1
На рисунке 7.1, б показан переключательный тумблер с тремя выводами.
В одном положении тумблера замкнуты контакты m и k (точки m и n разомкну-
ты), а в другом – контакты m и k размыкаются, а контакты m и n замыкаются.
На рисунке 7.1, в представлен сдвоенный переключательный тумблер. На
нём изображены две параллельные линии, соединяющие подвижные контакты
обеих групп. Но эти линии не являются токопроводящими. Их назначение: по-
казать, что переключение осуществляется одновременно всеми контактами, че-
рез которые проходят эти параллельные линии.
7.3 Кнопки
Для обыкновенных кнопок, в отличие от тумблеров, характерно лишь од-
но устойчивое состояние – исходное. Если кнопку нажать, то она переходит в
другое состояние, но только на время, пока она нажата. После отпускания
кнопка под действием специальной пружины переходит в исходное положение.
На рисунке 7.2, а изображена кнопка с нормально разомкнутым контак-
том. Слово «нормально» говорит о том, что контакт изображен в состоянии,
когда кнопка не нажата.
На рисунке 7.2, б приведено условное изображение кнопки с нормально
замкнутым контактом. В исходном состоянии, когда кнопка не нажата, выводы
а)
б)
в)
m
n
m
n
k