Релейно-контактные (переключательные) схемы.

Рассмотрим еще один способ реализации функций алгебры логики – — релейно-контактные схемы (РКС), широко используемые в электронно-вычислительной технике. Описание и конструирование таких схем в силу их громоздкости весьма затруднительно. Однако оказалось, что при конструировании РКС можно использовать аппарат булевых функций.

Исходное замечание состоит в том, что если логической переменной поставить в соответствие проводник, по которому ток идет или нет в зависимости от того или , то последовательному соединению проводников отвечает конъюнкция переменных, а параллельному – — дизъюнкция. Часто проводники на схемах заменяют обозначением специальных устройств – — переключателей, которые могут быть механическими и электронными. Многократно используя параллельно-последовательные соединения, можно строить сложные схемы. Мы ограничимся только схемами, в которых соединяются лишь контакты. Контакт или переключатель будем изображать отрезком или прямоугольником, концы контакта называть полюсами. Конструкция, изображенная на рис. 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. По данной матрице смежности вершин и инциденций нарисовать соответствующий граф.

, .

По первой матрице может быть построен ориентированный мульти- и псевдограф, изображёенный на рис. 1.24. Следует помнить, что рисунок графа может быть и иным по расположению вершин и форме дуг, важно лишь количество вершин и дуг и порядок их инцидентности. Так как матрица бинарна, то ей соответствующий граф будет неориентированным. Он изображёен на рис. 1.25.

[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.30

Вариант 2

1. ;

1. .

Вариант 3

1. ;

Рис. 1.31

Вариант 4

1. ;

1. .

Вариант 5

1. ;

Рис. 1.32

Вариант 6

1. ;

1. .

Вариант 7

1. ;

Рис. 1.33

Вариант 8

1. ;

1. .

Вариант 9

1. ;

Рис. 1.34

Вариант 10

1. ;

1. .

Вариант 11

1. ;

Рис. 1.35

Вариант 12

1. ;

1. .

Вариант 13

1. ;

Рис. 1.36

Вариант 14

1. ;

1. .

Вариант 15

1. ;

Рис. 1.37

Вариант 16

1. ;

1. .

Вариант 17

1. ;

Рис. 1.38

Вариант 18

1. ;

1. .

Вариант 19

1. ;

Рис. 1.39

Вариант 20

1. ;

1. .

Вариант 21

1. ;

Рис. 1.40

Вариант 22

1. ;

1. .

Вариант 23

1. ;

Рис. 1.41

Вариант 24

1. ;

1. .

Вариант 25

1. ;

Рис. 1.42

Вариант 26

1. ;

1. .

Вариант 27

1. ;

Рис. 1.43

Вариант 28

1. ;

1. .

Вариант 29

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