Релейно-контактные (переключательные) схемы.
Рассмотрим еще один способ реализации функций алгебры логики – — релейно-контактные схемы (РКС), широко используемые в электронно-вычислительной технике. Описание и конструирование таких схем в силу их громоздкости весьма затруднительно. Однако оказалось, что при конструировании РКС можно использовать аппарат булевых функций.
Исходное замечание состоит в том, что если логической переменной поставить в соответствие проводник, по которому ток идет или нет в зависимости от того
или
, то последовательному соединению проводников отвечает конъюнкция переменных, а параллельному – — дизъюнкция. Часто проводники на схемах заменяют обозначением специальных устройств – — переключателей, которые могут быть механическими и электронными. Многократно используя параллельно-последовательные соединения, можно строить сложные схемы. Мы ограничимся только схемами, в которых соединяются лишь контакты. Контакт или переключатель будем изображать отрезком или прямоугольником, концы контакта называть полюсами. Конструкция, изображенная на рис. 1.16, называется двухполюсником. Двухполюсник будем снабжать символом переменной
, если контакт замыкающий, и
, если размыкающий. Двухполюсники соединяются полюсами. В результате схема будет представлять из соебойя граф.
Рис. 1.16.Двухполюсник
Граф с
полюсами, в котором каждое ребро помечено буквой из алфавита
, называется
-полюсной контактной схемой, реализующей булевы функции переменных
, или
-схемой. Контактная схема называется связной (сильно связной, паралллельно-последовательной), если таковым является ее граф. Параллельно-последовательная схема называется
-схемой. В графе выделяются две вершины: вход и выход. Часто вход изображает полюс в виде светлого кружка, остальные полюса изображаются темными кружками.
Какую же функцию алгебры логики реализует контактная схема? Эта функция равна единице при тех значениях аргументов, при которых в схеме есть проводимость, и нулю, если проводимости нет. Пусть и
- — два полюса контактной схемы
,
— - некоторая цепь, соединяющая
и
, и
— - конъюнкция букв, приписанных ребрам цепи
. Функция
, определяемая формулой
, (1.13.9)
в которой дизъюнкция берется по всем простым цепям схемы, соединяющим полюса и
, называется функцией проводимости между полюсами
и
схемы
. На самом деле для получения функции проводимости достаточно брать дизъюнкцию не по всем цепям, а лишь по некоторым.
![]() |
Цепь

Рис. 1.17.Схема элементарной конъюнкции
Рис. 1.18.Схема элементарной дизъюнкции
Посмотрим теперь как обстоит дело с обратной задачей: построением по функции реализующей ее схемы. Представим функцию в виде ДНФ. Каждой входящей в ДНФ элементарной конъюнкции поставим в соответствие схему (рис. 1.17), состоящую из последовательно соединенных контактов
. Это схема элементарной конъюнкции. На рис. 1.17 и 1.18 величины
обозначены через
.[K1] После отождествления между собой, с одной стороны, входов всех этих схем, с другой стороны – — выходов, получим функцию, соответствующую заданной схеме. Естественно, можно реализовать функцию по схемам также исходя из КНФ. Каждой элементарной дизъюнкции
поставим в соответствие схему, изображенную на рис. 1.18. Затем последовательно соединим все эти схемы для всех элементарных дизъюнкций, входящих в КНФ, так, чтобы вход последующей схемы совпадал с выходом предыдущей.
Схему, состоящую из одного контакта, называют элементарной. Ясно, что любая -схема может быть получена из элементарных за некоторое число шагов при помощи параллельных и последовательных соединений. Каждому способу построения
-схемы из элементарных схем отвечает представление функции проводимости в виде формулы, содержащей только дизъюнкции, конъюнкции и отрицания.
Если контактная схема является -схемой, то ее можно разбить на несколько схем, соединенных либо последовательно, либо параллельно. Обратное тоже верно. Если схема не допускает разбиения на две схемы, соединенные либо последовательно, либо параллельно, она не является
-схемой. Для примера рассмотрим схему "“мостик”" (рис. 1.19), которая не является элементарной. Если две схемы соединены последовательно, то у полученной общей схемы все полюсы, кроме соединяющего, либо не имеют общих контактов ни с входом, ни с выходом всей схемы, либо имеют общий контакт или только с входом, или только с выходом. Очевидно, что какой бы из внутренних полюсов на рис. 1.19 мы не приняли за соединяющий подсхемы, оставшийся полюс будет иметь общий контакт как с входом, так и с выходом схемы. Поэтому схему “"мостик”" нельзя получить последовательным соединением двух схем.
Рис. 1.19.Схема "мостик"
Если общая схема – — результат параллельного соединения двух схем, то ее контакты и полюсы можно разбить на две части так, чтобы либо в одной части содержались контакты, непосредственно соединяющие вход и выход, либо полюсы, входящие в рассматриваемые различные две части схемы и отличные от входа и выхода, не будут иметь общих контактов. Ни первая, ни вторая возможность на схеме рис. 1.19 не может реализоваться. Следовательно, эта схема не является -схемой.
Две контактные схемы называются эквивалентными, если они реализуют одну и ту же булеву функцию или одну и ту же систему функций. Схема называется минимальной, если она содержит наименьшее возможное число контактов среди всех схем, имеющих ту же функцию проводимости.
![]() |
[K2] Рис. 1.20.Примеры релейно-контактных схем
Пример 3. Найти функции, реализуемые схемами на рис. 1.20.
Первые две функции представлены -схемами, поэтому их восстановление довольно просто: а)
; б)
.
Для последнего пункта (в) составим по формуле (1.12.9) функцию проводимости. Для этого необходимо перечислить все цепи, соединяющие начальный и конечный
полюсы схемы:
.
.
1.14. Практическое занятие № 2.[K3] Математические основы информатики. Алгебра высказываний. Операции над множествами. Графы и способы задания графов. Релейно-контактные схемы
Основное понятие алгебры логики – — высказывание. Основные понятия любой отрасли науки не могут быть определены строго формально, а лишь поясняются. Логическое значение высказывания "“истина”" ("“ложь”") чаще всего обозначаются цифрой 1 (0). Все высказывания можно разделить на простые и составные или сложные. Логическое значение любого высказывания легко может быть установлено с помощью таблиц истинности основных логических операций.
Пример 1. Определить являются ли высказываниями следующие предложения, и установить истинность или ложность имеющихся высказываний:
1. чЧисло 15 не делится на 3;
2. Ллетайте самолёетами Аэрофлота!
3. Еесть ли жизнь на Марсе?
4. Вв Петербурге более 4-х миллионов жителей;
5. Ввсе действительные числа удовлетворяют коммутативному закону.
Из приведёенных пяти предложений второе и третье не являются высказываниями, т. к. высказыванием может быть лишь повествовательное предложение. Первое высказывание ложно, четвертое и пятое – — истинны.
Пример 2. Составить таблицу истинности для формулы .
Применение таблицы истинности – — самый простой способ исследования булевой функции. Каждая таблица для функции переменных содержит
строк, поэтому таблицы истинности удобно применять, если функция содержит не более 3-—4-х переменных. В нашем случае имеет место табл. 1.19.
Таблица 1.19
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() ![]() | ![]() | ![]() | ![]() |
По табл. 1.19 видно, что формула - выполнима, т. к. принимает значения 0 и 1 при разных наборах переменных
.
Пример 3. Доказать, что если формулы и
тождественно истинны, то формула
также тождественно истинна.
Предположим обратное, пусть . Тогда из таблицы . 1.16
,
, т. е.
. Следовательно,
и
, т. е.
и
одновременно, что невозможно. Таким образом, наше предположение неверно и
.
Пример 4. Булевы функции, представленные по формулам (1.13.4) и (1.13.5), находятся в виде совершенных дизъюнктивной и конъюнктивной нормальных форм. К такому виду любую булеву функцию можно привести путёем эквивалентных преобразований с использованием формул (1.13.1)—-(1.13.3). Однако самый простой, но не самый удобный способ – — использование таблицы истинности.
По структуре формулы (1.13.4) ясно, что в еёе правой части стоят логические слагаемые, каждое из которых состоит из логического произведения всех переменных исходной формулы или их отрицаний, причёем только из тех строк таблицы истинности, в которых сама функция равна единице.
Поэтому, чтобы получить совершенную дизъюнктивную нормальную форму булевой функции , необходимо записать в виде дизъюнкции все выражения вида
только в тех строках таблицы истинности, где
.
Рассмотрим в качестве примера функцию и еёе таблицу истинности (табл. 1.20).
Тогда . Форму (1.13.5) удобнее получать не напрямую, а по формуле
. В нашем случае
и
.
Таблица 1.20
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
Алгебра логики и теория множеств являются двумя интерпретациями (моделями) одной общей теории, называемой алгеброй Буля[1]*. Поэтому все понятия алгебры логики и теории множеств очень похожи.
Пример 5. Доказать равенство . Проще всего это сделать с помощью диаграмм Эйлера – — Венна (см. рис. 1.21). Видно, что множества
и
непересекающиеся, т. е. не имеют общих элементов. То же самое можно полу-чить чисто формально:
(см. рис. 1.21),
.
![]() |
[K4] Рис. 1.21.Диаграмма Эйлера – Венна равенства

Пример 6. Пусть ,
. Найти
,
,
,
,
,
.
,
,
,
,
,
,
очевидно .
Пример 7. Дано бинарное отношение , изображёенное на рис. 1. 22. Определить является ли оно рефлексивным, иррефлексивным, симметричным, антисимметричным, транзитивным?
[K5] Рис. 1.22.Бинарное отношение
Матрица этого отношения имеет вид . Отношение
не рефлексивно, т. к. на главной диагонали его матрицы имеется два нуля; это отношение не иррефлексивно, т. к.
. Матрица
не симметрична, тогда не симметрично и отношение
; для симметричных отношений справедливо
, что, очевидно, не выполняется в данном случае.
. Отношение
антисимметрично, т. к. все элементы, стоящие вне главной диагонали матрицы
, равны нулю.
Транзитивность проще проверить по определению, используя элементы этого отношения: . По определению отношение
транзитивно, если из
и
следует, что
. В нашем случае
,
, но и
;
,
, но и
, т. е.
транзитивно.
Пример 8. Для графов, изображёенных на рис. 1.23, составить матрицу смежности вершин и инциденций.
[K6] Рис. 1.23. Примеры графов
![]() |
а) Дан ориентированный граф. Тогда
и .
б) Этот граф неориентированный, поэтому матрица смежности вершин будет симметрической, а матрица инциденций – — бинарной.
,
.
Пример 9. По данной матрице смежности вершин и инциденций
нарисовать соответствующий граф.
,
.
![]() |
По первой матрице


[K7] Рис. 1.24.Ориентированный мульти- и псевдограф
Пример 10. Найти эксцентриситет вершин, радиус и диаметр графа, изображёенного на рис. 1.25.
,
. Все вершины центральные и периферийные. Диаметральные цепи:
,
,
,
,
и т. п.
![]() |
Рис. 1.25.Неориентированный граф
Пример 11. Реализовать релейно-контактными схемами функции:
а) ;
б) .
Поскольку релейно-контактные схемы реализуются на основе элементарных конъюнкции и дизъюнкции, то при необходимости следует упростить формулу по правилам (1.13.1)—-(1.13.3).
а)
. Тогда релейно-контактная схема имеет вид, изображёенныйизображенный на рис. 1.26, а).
![]() |
Рис. 1.26.Релейно-контактные схемы функций примера 11
![]() |
Рис. 1.27.Релейно-контактные схемы функций примера 12
б) В этом случае формулу упрощать не требуется. Релейно-контактная схема этой данной формулы изображена на рис. 1.26, б).
Пример 12. Найти функции, реализуемые релейно-контактными схемами, изображёенными на рис. 1.27.
а) ;
б)
.
1.14.1.[K8] Обозначить элементарные высказывания буквами и записать следующие высказывания с помощью символов алгебры логики:
а) или
;
б) если число 512 делится на 2 и 8, то оно делится на 16;
в) тает лёед и .
1.14.2. ППустьСуществуетусть дано высказывание мишень поражена
-м выстрелом
,
. Что означают следующие высказывания:
а) ;
б) ;
в) ?
1.14.3. Составить таблицы истинности для формул:
а) ;
б) ;
в) .
1.14.4. По таблице истинности получить СДНФ и СКНФ для формул:
а) ;
б) ;
в) .
1.14.5. Доказать следующие тождества:
а) ;
б) ;
в) .
1.14.6. Определить в каком отношении ( ) находятся множества
и
, если:
а) ;
б) ;
в) .
1.14.7. По данной матрице смежности вершин или инциденций
построить соответствующий граф:
а) ;
б) ;
в) ; г)
.
1.14.8. Для графов, изображёенныхизображенных на рис. 1.28, составить матрицы смежности вершин и инциденций:
![]() |
Рис. 1.28.Графы для задания 1.14.8
1.14.9. Построить -схемы для формул:
а) ;
б) ;
в) .
1.14.10. Найти функции, реализуемые контактными схемами, изображёенными на рис. 1.29.
Рис. 1.29.Релейно-контактные схемы для задания 1.14.10
1.14.11. Выполните арианты расчёетно-графическуюой работу по вариантамы.
Задание к расчётно-графической работе.
1.По таблице истинности найти СДНФ формулы алгебры логики.
1.Доказать равенство.
1.По данной матрице смежности вершин или инциденций
построить граф и найти его метрические характеристики (эксцентриситеты вершин, радиус и диаметр графа).
1.Восстановить булеву функцию по данной релейно-контактной схеме ( см. рис. 1.30-—1.44) или построить релейно-контактную схему по данной функции.
Вариант 1
1. ;
1. ;
1. ;
1.
![]() |
Рис. 1.30
Вариант 2
1. ;
1. ;
1. ;
1. .
Вариант 3
1. ;
1. ;
1. ;
1.
![]() |
Рис. 1.31
Вариант 4
1. ;
1. ;
1. ;
1. .
Вариант 5
1. ;
1. ;
1. ;
1.
![]() |
Рис. 1.32
Вариант 6
1. ;
1. ;
1. ;
1. .
Вариант 7
1. ;
1. ;
1. ;
1.
![]() |
Рис. 1.33
Вариант 8
1. ;
1. ;
1. ;
1. .
Вариант 9
1. ;
1. ;
1. ;
1.
![]() |
Рис. 1.34
Вариант 10
1. ;
1. ;
1. ;
1. .
Вариант 11
1. ;
1. ;
1. ;
1.
![]() |
Рис. 1.35
Вариант 12
1. ;
1. ;
1. ;
1. .
Вариант 13
1. ;
1. ;
1. ;
1.
![]() |
Рис. 1.36
Вариант 14
1. ;
1. ;
1. ;
1. .
Вариант 15
1. ;
1. ;
1. ;
1.
![]() |
Рис. 1.37
Вариант 16
1. ;
1. ;
1. ;
1. .
Вариант 17
1. ;
1. ;
1. ;
1.
![]() |
Рис. 1.38
Вариант 18
1. ;
1. ;
1. ;
1. .
Вариант 19
1. ;
1. ;
1. ;
1.
![]() |
Рис. 1.39
Вариант 20
1. ;
1. ;
1. ;
1. .
Вариант 21
1. ;
1. ;
1. ;
1.
![]() |
Рис. 1.40
Вариант 22
1. ;
1. ;
1. ;
1. .
Вариант 23
1. ;
1. ;
1. ;
1.
![]() |
Рис. 1.41
Вариант 24
1. ;
1. ;
1. ;
1. .
Вариант 25
1. ;
1. ;
1. ;
1.
![]() |
Рис. 1.42
Вариант 26
1. ;
1. ;
1. ;
1. .
Вариант 27
1. ;
1. ;
1. ;
1.
![]() |
Рис. 1.43
Вариант 28
1. ;
1. ;
1. ;
1. .
Вариант 29
1. ;
1.если , то
;
1. ;
1.
![]() |
Рис. 1.44
Вариант 30
1. ;
1.если и
, то
;
1. ;
1. .
[1] Джордж Буль (1815—1864 гг.) — английский математик и логик.
* Джордж Буль (1815-1864) – английский математик и логик.
[K1]Для чего? Лучше одинаково.
На рисунке в CorelDRAW конструкцию создать весьма затруднительно. Мне это пока не удалось. Я попробую ещё раз, если получится, то выделенной Вами предложение можно будет убрать.
[K2]Название? Или в примерах и заданиях не будем делать?
Название в тексте, по-моему мнению, лучше давать. Можно не давать названия рисункам в вариантах типовых расчётов. Этот рисунок можно назвать, например, Примеры релейно-контактных схем.
[K3]Будем перемещать в конец главы?
Не будем.
[K4]Подпись?
Например, Диаграмма Эйлера – Венна равенства
[K5]Название?
Например, Рассматриваемое бинарное отношение или Бинарное отношение ,
[K6]Подпись?
Примеры графов
[K7]Подпись?
Рис. 1.24. Ориентированный мульти- и псевдограф
Рис. 1.25. Неориентированный граф
Рис. 1.26. Релейно-контактные схемы функций примера 11
Рис.1.27. Релейно-контактные схемы функций примера 12
И далее желтым.
[K8]Если вынесем в конец главы практику, то нумерацию лучше сделать 2.1, 2.2, 2.3 (т.к. это практич. занятие 2).
Всё оставим как есть.
Дата добавления: 2016-06-05; просмотров: 9109;