Логические схемы
Выбери формат для чтения
Загружаем конспект в формате docx
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
ема 2. Логические схемы
Логическая схема – это схематическое изображение некоторого устройства, состоящего из переключателей и соединяющих их проводников, а также из входов и выходов, на которые подаётся и с которых снимается электрический сигнал.
Каждый переключатель имеет только два состояния: замкнутое и разомкнутое. Переключателю Х поставим в соответствие логическую переменную х, которая принимает значение 1 в том и только в том случае, когда переключатель Х замкнут и схема проводит ток; если же переключатель разомкнут, то х равен нулю.
Две схемы называются равносильными, если через одну из них проходит ток тогда и только тогда, когда он проходит через другую (при одном и том же входном сигнале).
Из двух равносильных схем более простой считается та схема, функция проводимости которой содержит меньшее число логических операций или переключателей.
Электрическая схема, предназначенная для выполнения какой-либо логической операции с входными данными, называется логическим элементом. Входные данные представляются здесь в виде напряжений различных уровней, и результат логической операции на выходе — также получается в виде напряжения определенного уровня.
Операнды в данном случае подаются в двоичной системе счисления — на вход логического элемента поступают сигналы в форме напряжения высокого или низкого уровня, которые и служат, по сути, входными данными. Так, напряжение высокого уровня — это логическая единица 1 — обозначает истинное значение операнда, а напряжение низкого уровня 0 — значение ложное. 1 — ИСТИНА, 0 — ЛОЖЬ.
Логический элемент — элемент, осуществляющий определенную логическую зависимость между входными и выходными сигналами. Логические элементы обычно используются для построения логических схем вычислительных машин, дискретных схем автоматического контроля и управления. Для всех видов логических элементов, независимо от их физической природы, характерны дискретные значения входных и выходных сигналов.
В зависимости от устройства схемы элемента, от ее электрических параметров, логические уровни (высокие и низкие уровни напряжения) входа и выхода имеют одинаковые значения для высокого и низкого (истинного и ложного) состояний.
Традиционно логические элементы выпускаются в виде специальных радиодеталей — интегральных микросхем. Логические операции, такие как конъюнкция, дизъюнкция, отрицание и сложение по модулю (И, ИЛИ, НЕ, исключающее ИЛИ) — являются основными операциями, выполняемыми на логических элементах основных типов.
Далее рассмотрим каждый из этих типов логических элементов более внимательно.
1. Логический элемент «И» - конъюнкция, логическое умножение.
2. Логический элемент «ИЛИ» - дизъюнкция, логическое сложение.
3. Логический элемент «НЕ» - отрицание, инвертор.
4. Логический элемент «И-НЕ» - конъюнкция (логическое умножение) с отрицанием.
5. Логический элемент «ИЛИ-НЕ» - дизъюнкция (логическое сложение) с отрицанием.
6. Логический элемент «исключающее ИЛИ» - сложение по модулю 2.
7. Логический элемент «исключающее ИЛИ-НЕ» сложение по модулю 2 с отрицанием.
8. Логический элемент «НЕ-ИЛИ» - импликация.
ПРИМЕРЫ
Триггер - это логическая схема, способная хранить 1 бит информации (1 или 0). Строиться на 2-х элементах ИЛИ-НЕ или на 2-х элементах И-НЕ.
Полусумматор - это логическая схема, способная складывать два одно разрядных двоичных числа.
Сумматор – это логическая схема, способная складывать два одноразрядных двоичных числа с переносом из предыдущего разряда.
Вернуться к разделу Меню
Тема 3. Важнейшие замкнутые классы
Любую булеву функцию можно выразить в виде формулы через элементарные функции: отрицание, конъюнкцию, дизъюнкцию, двоичное сложение и константу 0 или 1.
Эти функции можно рассматривать как систему элементарных функций, через которые выражается любая булева функция.
Система булевых функций {f1, f2, …, fm} называется полной, если любая булева функция может быть выражена через функции этой системы с помощью составления из них сложных функций.
1. Класс функций, сохраняющих ноль.
Функция f(х1, ..., хn) называется сохраняющей ноль, если она на нулевом наборе принимает значение 0, то есть f(0, ..., 0) = 0.
2. Класс функций, сохраняющих единицу.
Функция f(х1, ..., хn) называется сохраняющей единицу, если она на единичном наборе принимает значение 1, то есть f (1, ..., 1) = 1.
3. Класс самодвойственных функций.
Функция f (х1,..., хn) называется самодвойственной, если f(х1, ..., хn) =f(х1, ..., хn).
4. Класс монотонных функций.
Набор a = (a1, ..., an) предшествует набору b = (b1, ..., bn), если ai ≤ bi (i = l, 2, ...,n). Это обозначаем как a ≤ b. Наборы, которые находятся в отношении ≤ называются сравнимыми.
Функция f(х1, ..., хn) называется монотонной, если для любой пары наборов a и b таких, что при a ≤ b: f(a) ≤ f(b).
5. Класс линейных функций.
Функция f(х1, ..., хn) называется линейной, если полином Жегалкина этой функции имеет линейный вид: f(х1, ..., хn) = а0 + а1 x1 + … + аn xn, где аi Î{0,1} (i = 0, l, ..., n).
Теорема Поста: Для того, чтобы система булевых функций была полной, необходимо и достаточно, чтобы для каждого из классов Т0, Т1, S, L, M нашлась функция fi из этой системы не принадлежащая этому классу.
Пример. Требуется проверить на полноту систему функций Ƿ = {0, 1, xy, x y z }. Рассмотрим принадлежность функции Ƿ классам T0, T1, S, M, L и заполним таблицу.
T0
T1
S
M
L
+
-
-
+
+
1
-
+
-
+
+
xy
+
+
-
+
-
+
+
+
-
+
Рассмотрим, например, проверку функции :
Теперь, заполнив и проанализировав таблицу, можно убедиться, что система функции Ƿ является полной, так как в каждой столбце, соответствующем одному из классов присутствует хотя-бы один минус. В то же время ни одно подмножество Ƿ полной системой не является, поскольку, если вычеркнуть в таблице хотя-бы одну строку появится столбец не имеющий минуса.
Вернуться к разделу Меню
Тема 4. Множества
Один из величайших математиков петербургский академик Леонард Эйлер за свою долгую жизнь (1707 – 1783 гг.) написал более 850 научных работ. В одной из них и появились эти круги. А впервые он их использовал в письмах к немецкой принцессе. Эйлер писал тогда, что «круги очень подходят для того, чтобы облегчить наши размышления». Позднее аналогичный прием использовал ученый Венн и его назвали «диаграммы Венна». Эйлер писал тогда, что «они очень подходят для того, чтобы облегчить наши размышления». При решении целого ряда задач Леонард Эйлер использовал идею изображения множеств с помощью кругов и они получили название «круги Эйлера».
Этот метод даёт ещё более наглядное представление о возможном способе изображения условий, зависимости, отношений в логических задачах.
Множество всех действительных чисел Эйлер изобразил с помощью этих кругов: N-множество натуральных чисел, Z – множество целых чисел, Q – множество рациональных чисел, R – множество вех действительных чисел.
Ну а как же круги Эйлера помогают при решении задач? Для ответа возьмем несколько задач:
Решение задач с помощью кругов Эйлера
1. Часть жителей нашего города умеет говорить только по-русски, часть – только по-башкирски и часть умеет говорить на обоих языках. По-башкирски говорят 85%, по-русски 75%. Сколько процентов жителей говорят на обоих языках?
Решение. Составим схему –
В кружке под буквой «Б» обозначим жителей, говорящих по-башкирски, под буквой «Р» - по-русски. В общей части кружков обозначим жителей, говорящих на обоих языках. Теперь от всех жителей (100%) отнимем кружок «Б» (85%), получим жителей, говорящих только по-русски (15%). А теперь от всех, говорящих по-русски (75%), отнимем эти 15%. Получим говорящих на обоих языках (60%).
2. Все мои подруги выращивают в своих квартирах какие-нибудь растения. Шестеро из них разводят кактусы, а пятеро — фиалки. И только у двоих есть и кактусы и фиалки. Угадайте, сколько у меня подруг?
Решение. Обратимся к кругам Эйлера:
Изобразим два круга, так как у нас два вида цветов. В одном будем фиксировать владелиц кактусов, в другом — фиалок. Поскольку у некоторых подруг есть и те, и другие цветы, то круги нарисуем так, чтобы у них была общая часть. В этой общей части ставим цифру 2 так как кактусы и фиалки у двоих. В оставшейся части «кактусового» круга ставим цифру 4 (6 − 2 = 4). В свободной части «фиалкового» круга ставим цифру 3 (5 − 2 = 3). А теперь рисунок сам подсказывает, что всего у меня 4 + 2 + 3 = 9 подруг.
3. В футбольной команде «Спартак» 30 игроков, среди них 18 нападающих. 11 полузащитников, 17 защитников и вратари. Известно, что трое могут быть нападающими и защитниками, 10 защитниками и полузащитниками, 6 нападающими и защитниками, а 1 и нападающим, и защитником, и полузащитником. Вратари не заменимы. Сколько в команде «Спартак» вратарей?
Решение.
18+11+17-3-10-6+1=28 (игроков) на этой диаграмме. Но в команде всего 30 футболистов. Значит вратарей будет 30-28=2. Ответ: 2 вратаря.
4. В классе 30 человек. 20 из них каждый день пользуются метро, 15 — автобусом, 23 — троллейбусом, 10 — и метро, и троллейбусом, 12 — и метро, и автобусом, 9 — и троллейбусом, и автобусом. Сколько человек ежедневно пользуются всеми тремя видами транспорта?
Решение.
1 способ. Для решения опять воспользуемся кругами Эйлера:
Пусть х человек пользуется всеми тремя видами транспорта. Тогда пользуются только метро и троллейбусом — (10 − х) человек, только автобусом и троллейбусом — (9 − х) человек, только метро и автобусом — (12 − х) человек. Найдем, сколько человек пользуется одним только метро:
20 − (12 − х) − (10 − х) − х = х − 2
Аналогично получаем: х − 6 — только автобусом и х + 4 — только троллейбусом, так как всего 30 человек, составляем уравнение:
x + (12 − х) + (9 − х) + (10 − х) + (х + 4) + (х − 2) + (х − 6) = 30. отсюда х = 3.
2 способ. А можно эту задачу решить задачу другим способом:
20+15+23-10-12-9+х=30, 27+х=30, х=3.
5. В восьмом классе учится 40 человек. Каждый из них изучает не менее одного иностранного языка: английский, немецкий, французский. 34 человека изучают хотя бы один из двух языков: английский, немецкий. 25 человек — хотя бы один из языков: немецкий, французский. 6 человек только немецкий. Одновременно два языка — английский и немецкий — изучают на 3 человека больше, чем французский и немецкий языки. Сколько человек изучает каждый из языков и сколько изучает одновременно каждую пару языков?
Решение
Н = 6
А + Н = на 3 человека >, чем Ф + Н = х
одновр. одновр.
34 – х – 3 – 6 – х + х + 3 + 6 + х +25 – х – 6 – х – 3 = 40
– 2х = 40 – 34 + 3 – 25
– 2х = –10
х = 5
Ф + Н = 5 человек.
А + Н = 8 человек.
А = 34 – 8 – 6 – 5 =15 человек.
Н = 6 человек.
Ф =25 – 5 – 6 –8 = 6 человек.
Всего 40 человек.
4. В магазине побывало 65 человек. Известно, что они купили 35 холодильников, 36 микроволновок, 37 телевизоров. 20 из них купили и холодильник и микроволновку, 19 - и микроволновку, и телевизор, 15-холодильник и телевизор, а все три покупки совершили три человека. Был ли среди них посетитель, не купивший ничего?
Решение:
Купили только холодильники: 35-(20-3)-(15-3)-3=4.
Купили только микроволновки: 36-(20-3)-(19-3)-3=0.
Купили только телевизоры: 37-(15-3)-(19-3)-3=6.
Тогда всего покупателей было: 4+17+3+16+12+6=58.
65-58=7 посетителей магазина не купили ничего.
Решите задачи:
1. В классе 38 человек. Из них 16 играют в баскетбол, 17 - в хоккей, 18 - в футбол. Увлекаются двумя видами спорта - баскетболом и хоккеем - четверо, баскетболом и футболом - трое, футболом и хоккеем - пятеро. Трое не увлекаются ни баскетболом, ни хоккеем, ни футболом. Сколько ребят увлекаются одновременно тремя видами спорта? Сколько ребят увлекается лишь одним из этих видов спорта?
2. Среди школьников шестого класса проводилось анкетирование по любимым мультфильмам. Самыми популярными оказались три мультфильма: «Белоснежка и семь гномов», «Губка Боб Квадратные Штаны», «Волк и теленок». Всего в классе 38 человек. «Белоснежку и семь гномов» выбрали 21 ученик, среди которых трое назвали еще «Волк и теленок», шестеро – «Губка Боб Квадратные Штаны», а один написал все три мультфильма. Мультфильм «Волк и теленок» назвали 13 ребят, среди которых пятеро выбрали сразу два мультфильма. Сколько человек выбрали мультфильм «Губка Боб Квадратные Штаны»?
3. На полке стояло 26 волшебных книг по заклинаниям. Из них 4 прочитал и Гарри Поттер, и Рон. Гермиона прочитала 7 книг, которых не читали ни Гарри Поттер, ни Рон, и две книги, которые читал Гарри Поттер. Всего Гарри Поттер прочитал 11 книг. Сколько книг прочитал Рон?
4. 9 моих друзей любят бананы, 8 – апельсины, а 7 – сливы, 5 – бананы и апельсины, 3 – бананы и сливы, 4 – апельсины и сливы, 2 – бананы, апельсины и сливы. Сколько у меня друзей?
Вернуться к разделу Меню
Тема 5. Бинарные отношения
Чтобы пояснить понятие бинарного отношения, рассмотрим известную детскую игру «камень-ножницы-бумага». Предполагается, что: камень побеждает ножницы (тупит), ножницы побеждают бумагу (режут), бумага побеждает камень (оборачивает), в остальных случаях (например, камень — камень) — боевая ничья. Будем говорить, что x находится в отношении R к y и писать x R y, в случае, если x побеждает y, где x и y принадлежат множеству {камень, ножницы, бумага}. Естественно отождествить отношение R с множеством, элементами которого являются упорядоченные пары (камень, ножницы), (ножницы, бумага), (бумага, камень) и только они. Отметим, что так определенное отношение (множество) R, очевидно, является подмножеством множества, состоящего из всевозможных упорядоченных пар, где каждый элемент пробегает множество {камень, ножницы, бумага}.
Этот простой пример приводит нас к следующему определению бинарного отношения.
Бинарным отношением R называется подмножество пар (a,b) ∈ R декартова произведения A×B, т. е. R⊆A×B. При этом множество A называют областью определения отношения R, множество B – областью значений.
Обозначение: aRb (т. е. a и b находятся в отношении R).
Способы задания бинарных отношений
1. Списком (перечислением пар), для которых это отношение выполняется.
2. Матрицей. Бинарному отношению R ∈ A × A , где A = (a1, a2,..., an), соответствует квадратная матрица порядка n , в которой элемент cij, стоящий на пересечении i-й строки и j-го столбца, равен 1, если между ai и aj имеет место отношение R, или 0, если оно отсутствует:
Операции над бинарными отношениями
Пусть R1, R1 есть отношения, заданные на множестве A .
1. объединение R1∪ R2 = {(a,b) : (a,b) ∈ R1 или (a,b) ∈ R2};
2. пересечение R1∩ R2 = {(a,b) : (a,b) ∈ R1 и (a,b) ∈ R2};
3. разность R1 \ R2 = {(a,b) : (a,b) ∈ R1 и (a,b) Ï R2};
4. дополнение R – в матрице исходного отношения R заменить единицы нулями, а нули – единицами.
5. обратное отношение R–1 – проставить в ней единицы, симметричные (относительно главной диагонали) соответствующим единицам исходной матрицы.
6. составное отношение R(2) – для каждой единицы исходной матрицы отношения R, принадлежащей i-й строке, например единицы в j-м столбце, т.е. для cij=1, в i-й строке вычисляемой матрицы проставить единицы в тех k-х столбцах, в которых имеются единицы в j-й строке исходной матрицы.
7. транзитивное замыкание R0 – выполнить серию (одну или более) итераций, заключающихся в следующем:
а) для каждой единицы исходной матрицы отношения R, принадлежащей i-й строке, например единицы в j-м столбце, т.е. для cij =1, в i-й строке вычисляемой матрицы проставляются единицы в тех k-х столбцах, в которых имеются единицы в i-й строке, а также в j-й строке исходной матрицы;
б) полученную матрицу отношений R принимают за исходную и повторяют процедуру а), выполняя таким образом следующий цикл вычислений (построения матрицы), и т.д. до тех пор, пока матрица не перестанет изменяться, т.е. пока в некотором цикле вычислений исходная и вычисленная матрицы не совпадут.
8. рефлексивное замыкание R* – построить матрицу транзитивного замыкания (см. выше), а затем в полученной матрице заменить нули на главной диагонали, если таковые имеются, на единицы.
Пример 1. Пусть M={1,2,3,4,5,6}. Задать в явном виде (списком) и матрицей отношение R⊆M×M, если R означает - «быть строго меньше».
• Отношение R как множество содержит все пары элементов a,b из M такие, что a
