Оптимальное логическое устройство: его функциональная схема и структурная формула
Перед нами задача: создать логическое устройство, которое имеет несколько входов и один выход. На входы подаются сигналы 0 или 1. Такие сигналы могут обозначать, к примеру, значения поданного голоса при голосовании. 0 обозначает «я против», 1 обозначает «я — за». Сигнал на выходе должен показать итоговый результат голосования — да / нет, в зависимости от поданных голосов. Интересно было бы рассмотреть полный процесс создания такого логического устройства. Но прямо сейчас, на этом уроке, мы можем изучить теоретические расчёты, которые предваряют техническое изготовление логического устройства.
Цель урока: познакомить учащихся с задачами инженерного характера: как построить оптимальное логическое устройство по словесному описанию его работы.
Задачи
Обучающие:
- научить формализовать условия содержательной текстовой задачи и представлять их в виде таблицы истинности;
- получить СДНФ и СКНФ по полученной таблице истинности (совершенная дизъюнктивная нормальная форма — СДНФ и совершенная конъюнктивная нормальная форма — СКНФ);
- упростить СДНФ (или СКНФ) с целью обеспечения оптимальности функциональных схем, их реализующих;
- построить функциональную схему в соответствии с реализуемой структурной формулой;
- проверить соответствие логической схемы реализуемой структурной формуле.
Развивающая
- Учить видеть структуру там, где она есть, и быть готовым работать со структурой адекватными методами.
Воспитательная
- Поднять ценность теории алгебры логики ибо она применима на практике.
Тип урока: урок получения новых знаний, приближенных к инженерной теории.
Вид урока: урок закрепления изучаемого материала.
Планируемые результаты
- Мы узнаем: алгоритм построения функциональной схемы по таблице истинности.
- Мы научимся: формализовать текстовое содержание задачи ради построения таблицы истинности.
- Мы сможем: построить оптимальную функциональную схему на основе упрощенной структурной формулы.
Оборудование и средства обучения: доска, мел, конспекты лекций, у каждого ученика и учителя есть методическое пособие Лыскова В.Ю. Логика в информатике / В.Ю.Лыскова, Е.А.Ракитина. — 2-е изд. — М.: Лаборатория Базовых Знаний, 2006, распечатки бланков централизованного тестирования по информатике 2006 года для каждого ученика и учителя.
План урока
1 этап. Организационный этап.
2 этап. Объявление темы и актуализация знаний.
3 этап. Формирование новых знаний: образцы решения задач и обсуждение.
4 этап. Домашнее задание.
Ход урока
1 этап. Организационный этап
Здравствуйте. Присаживайтесь. Отметим отсутствующих и приступим к уроку.
2 этап. Объявление темы и актуализация знаний
Сегодняшнее число. Тема урока «Оптимальное логическое устройство: его функциональная схема и структурная формула».
Что такое функциональная схема и что такое структурная формула — эти понятия не вызывают затруднений, надеюсь. Давайте их проговорим. Кто желает?
(Ответ должен быть проговорен вслух.
Схема соединения логических элементов называется функциональной схемой.
Структурная формула — это форма описания функции, реализуемой логическим устройством.
Логическое устройство — цепочка из логических элементов, в которой выходы одних элементов являются входами других.)
Теперь, что такое оптимальность? Давайте подумаем. Ваш вариант ответа?
«Оптимальность — это достижение наилучшего результата в данных условиях при минимальных затратах времени и усилий участников», — гласит Словарь терминов по общей и социальной педагогике.)
Сегодня нам понадобятся знания логических элементов, алгоритм составления СДНФ и СКНФ, а также ваши хорошие навыки упрощения логических выражений.
Проведем короткую проверочную работу в качестве «разминки».
(Учитель раздает карточки проверочной работы — учащиеся письменно отвечают на вопросы. Двоих вызывает к доске — выполнять проверочную работу. Остальные пишут на местах.)
Вопросы проверочной работы:
- Нарисуйте логические элементы и подпишите их названия.
- Дана таблица истинности для двух переменных.
По этой таблице составить СДНФ и СКНФ.
Результаты на доске учитель проверяет сразу. И сообщает оценки сразу.
1. Логические значения 0 и 1 — это цифровые сигналы. Они поступают, преобразовываются и выходят из так называемых логических элементов. Логические элементы выполняют дизъюнкцию, конъюнкцию, инверсию; логические устройства выполняют: сложение по модулю 2, эквивалентность, импликацию, коимпликацию, элемент Вебба (или-не), элемент Шеффера (и-не). Смотри Рисунок 1.
2. Обратимся к Методическому пособию Лысковой В.Ю., где описаны алгоритмы получения СДНФ и СКНФ. Привожу фрагмент пособия, чтобы материал урока был целостным. «Существует алгоритм, позволяющий по известной таблице истинности построить схему устройства. В основе алгоритма лежит теорема алгебры логики: любую функцию, кроме констант 0 и 1, можно представить в виде СДНФ, так и СКНФ. Совершенная дизъюнктивная нормальная форма — СДНФ и совершенная конъюнктивная нормальная форма — СКНФ.
Алгоритм получения СДНФ по таблице истинности.
1. Отметить те строки таблицы истинности, в последнем столбце которых стоят 1:
2. Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно 0, о ее отрицание:
3. Все полученные конъюнкции связать в дизъюнкцию:
3 этап. Формирование новых знаний: образцы решения задач и обсуждение результатов
Задача 1 «Устройство для голосования». (Из Методического пособия Лысковой В.Ю., стр. 97. Задачу перепечатываю.)
«Пусть в некотором конкурсе решается вопрос о допуске того или иного участника к следующему туру тремя членами жюри: P, Q, R. Решение положительно тогда и только тогда, когда хотя бы двое членов жюри высказываются за допуск, причем среди них обязательно должен быть председатель жюри Q. Необходимо разработать устройство для голосования, в котором каждый член жюри нажимает на одну из кнопок — «За» или «Против», а результат голосования всех трех членов жюри определяется по тому, загорится (решение принято) или нет (решение не принято) сигнальная лампочка.
Формально это можно выразить так: требуется составить функциональную схему устройства, которое на выходе выдавало бы 1, если участник допускается к следующему туру, и 0, если не допускается.»
1. Нужно рассмотреть всевозможные комбинации голосов жюри. Если голос «против», то будем обозначать его нулем. Если голос «за», то обозначим его единицей. Жюри состоит из трех человек. Значит, надо составить все трехбитные двоичные коды. Их будет 8.
Затем напротив каждого кода записать вывод — допускается или нет участник к следующему туру. Работу жюри представим в виде таблицы истинности:
Какая из структурных формул соответствует логической схеме
Сигнал, выработанный одним логическим элементом можно подавать на вход другого логического элемента. Это дает возможность образовывать цепочки из отдельных логических элементов. На рисунке 15 показаны примеры таких цепочек.
Рисунок 15. Цепочка из нескольких логических элементов
На рисунке 15 а) элемент ИЛИ (дизъюнктор) соединен с элементом НЕ (инвертор), а на рисунке 15 б) — элемент И (конъюнктор) с элементом НЕ (инвертор). Каждую такую цепочку будем называть логическим устройством: поскольку она состоит из нескольких элементов.
| Цепочку из логических элементов будем называть логическим устройством. Схемы, соответствующие таким устройствам, называют функциональными . |
На рисунке 16 приведен пример более сложной функциональной схемы.
Рисунок 16. Сложная функциональная схема
Составить логическую схему по функциональной формуле достаточно просто. Например, функциональная схема, изображенная на рисунке 16, имеет два входа A и B. До поступления на конъюнктор B отрицается, а затем отрицается результат логического умножения. Все это приводит нас к формуле
которая представляет собой структурную формулу логического устройства. Важно научиться решать и обратную задачу: по структурной формуле вычерчивать соответствующую ей функциональную схему. Усложним задачу. Пусть имеется произвольная логическая функция, требуется построить функциональную схему.
Алгоритм решения такой задачи начинается с построения таблицы истинности. Затем в таблице следует определить одну или несколько строк, с результатом равным 1. На следующем шаге необходимо выписать комбинацию входных переменных, соединенных логическим умножением. Если входная переменная в нужной нам строке имеет значение 0, то она должна войти в логическое выражение с отрицанием. Полученные таким образом конъюнкции требуется логически сложить. Далее полученную формулу нужно сократить с использованием логических законов. Рассмотрим этот алгоритм на следующем примере.
Задача 7. Начертить функциональную схему, соответствующую таблице истинности.
| A | B | F(A,B) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Рассмотрим строки, которые в столбце F(A,B) дают истину (эти строки в таблице выделены). Составим по первой строке выражение (A следует отрицать, потому что в таблице стоит 0), аналогичное выражение по третьей строке дает . Соединяем два последних выражения союзом ИЛИ, получим . Вычерчиваем по логическому выражению функциональную схему.
Рисунок 17. Функциональная схема логической функции .
| Логическую функцию F(A,B)=Ā Λ B V A Λ называют операцией XOR (исключающее или) и обозначают . |
Еще один пример построения функциональной схемы.
Начертить функциональную схему, соответствующую таблице истинности.
| A | B | C | результат |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Выделяем в таблице строки, когда результатом функции является истина.
| A | B | C | результат |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Для первой строки последней таблицы имеем.
для второй строки —
для третьей строки —
(24) для четвертой строки —
(25) и для пятой строки —
Соединяем выражения (22)-(26) логическим сложением. Будем иметь
Теперь требуется упростить (27) на основе логических законов. .
| Таким образом, получили: . | (28) |
Построим функциональную схему. Для этого потребуется отрицание A с последующим умножением на B, затем на C и, наконец, сложение с A. Полученная функциональная схема представлена на рисунке 18.
Логические схемы и таблицы истинности
Логические схемы создаются для реализации в цифровых устройствах булевых функций (функций алгебры логики).
В цифровой схемотехнике цифровой сигнал — это сигнал, который может принимать два значения, рассматриваемые как логическая «1» и логический «0».
Логические схемы могут содержать до 100 миллионов входов и такие гигантские схемы существуют. Представьте себе, что булева функция (уравнение) такой схемы была потеряна. Как восстановить её с наименьшими потерями времени и без ошибок? Наиболее продуктивный способ — разбить схему на ярусы. При таком способе записывается выходная функция каждого элемента в предыдущем ярусе и подставляется на соответствующий вход на следующем ярусе. Этот способ анализа логических схем со всеми нюансами мы сегодня и рассмотрим.
Логические схемы реализуются на логических элементах: «НЕ», «И», «ИЛИ», «И-НЕ», «ИЛИ-НЕ», «Исключающее ИЛИ» и «Эквивалентность». Первые три логических элемента позволяют реализовать любую, сколь угодно сложную логическую функцию в булевом базисе. Мы будем решать задачи на логические схемы, реализованные именно в булевом базисе.
Для обозначения логических элементов используется несколько стандартов. Наиболее распространёнными являются американский (ANSI), европейский (DIN), международный (IEC) и российский (ГОСТ). На рисунке ниже приведены обозначения логических элементов в этих стандартах (для увеличения можно нажать на рисунок левой кнопкой мыши).
На этом уроке будем решать задачи на логические схемы, на которых логические элементы обозначены в стандарте ГОСТ.
Задачи на логические схемы бывают двух видов: задача синтеза логических схемы и задачи анализа логических схем. Мы начнём с задачи второго типа, так как в таком порядке удаётся быстрее научиться читать логические схемы.
Чаще всего в связи с построением логических схем рассматриваются функции алгебры логики:
- трёх переменных (будут рассмотрены в задачах анализа и в одной задаче синтеза);
- четырёх переменных (в задачах синтеза, то есть в двух последних параграфах).
Рассмотрим построение (синтез) логических схем
- в булевом базисе «И», «ИЛИ», «НЕ» (в предпоследнем параграфе);
- в также распространённых базисах «И-НЕ» и «ИЛИ-НЕ» (в последнем параграфе).
Логические схемы строятся на основе логических выражений и функций. Бывает, что изначально составленная функция является излишне сложной, из-за чего её схемная или программная реализация оказывается избыточной. Способам и приёмам минимизации логических функций посвящены отдельные материалы сайта — минимизация логических функций: общие сведения, минимизация логических функций: метод непосредственных преобразований и минимизация логических функций: метод Квайна.
Задача анализа логических схем
Задача анализа заключается в определении функции f , реализуемой заданной логической схемой. При решении такой задачи удобно придерживаться следующей последовательности действий.
- Логическая схема разбивается на ярусы. Ярусам присваиваются последовательные номера.
- Выводы каждого логического элемента обозначаются названием искомой функции, снабжённым цифровым индексом, где первая цифра — номер яруса, а остальные цифры — порядковый номер элемента в ярусе.
- Для каждого элемента записывается аналитическое выражение, связывающее его выходную функцию с входными переменными. Выражение определяется логической функцией, реализуемой данным логическим элементом.
- Производится подстановка одних выходных функций через другие, пока не получится булева функция, выраженная через входные переменные.
Пример 1. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.
Решение. Разбиваем логическую схему на ярусы, что уже показано на рисунке. Запишем все функции, начиная с 1-го яруса:
Теперь запишем все функции, подставляя входные переменные x, y, z :
В итоге получим функцию, которую реализует на выходе логическая схема:
Таблица истинности для данной логической схемы:
| x | y | z | f | ||||
| 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
- Пригодится: минимизация логических функций — общие сведения
- Пригодится: минимизация логических функций методом непосредственных преобразований
- Пригодится: минимизация логических функций методом Квайна
Найти булеву функцию логической схемы самостоятельно, а затем посмотреть решение
Пример 2. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.
Пример 3. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.
Продолжаем искать булеву функцию логической схемы вместе
Пример 4. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.
Решение. Разбиваем логическую схему на ярусы. Запишем все функции, начиная с 1-го яруса:
Теперь запишем все функции, подставляя входные переменные x, y, z :
В итоге получим функцию, которую реализует на выходе логическая схема:
Таблица истинности для данной логической схемы:
| x | y | z | f | ||
| 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 | 1 | 1 |
- Пригодится: минимизация логических функций — общие сведения
- Пригодится: минимизация логических функций методом непосредственных преобразований
- Пригодится: минимизация логических функций методом Квайна
Пример 5. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.
Решение. Разбиваем логическую схему на ярусы. Структура данной логической схемы, в отличие от предыдущих примеров, имеет 5 ярусов, а не 4. Но одна входная переменная — самая нижняя — пробегает все ярусы и напрямую входит в логический элемент в первом ярусе. Запишем все функции, начиная с 1-го яруса:
Теперь запишем все функции, подставляя входные переменные x, y, z :
В итоге получим функцию, которую реализует на выходе логическая схема:
Таблица истинности для данной логической схемы:
| x | y | z | f | ||
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 | 1 |
- Пригодится: минимизация логических функций — общие сведения
- Пригодится: минимизация логических функций методом непосредственных преобразований
Задача синтеза логических схем в булевом базисе
Разработка логической схемы по её аналитическому описанию имеет название задачи синтеза логической схемы.
Каждой дизъюнкции (логической сумме) соответствует элемент «ИЛИ», число входов которого определяется количеством переменных в дизъюнкции. Каждой конъюнкции (логическому произведению) соответствует элемент «И», число входов которого определяется количеством переменных в конъюнкции. Каждому отрицанию (инверсии) соответствует элемент «НЕ».
Часто разработка логической схемы начинается с определения логической функции, которую должна реализовать логическая схемы. В этом случае дана только таблица истинности логической схемы. Мы разберём именно такой пример, то есть, решим задачу, полностью обратную рассмотренной выше задаче анализа логических схем.
Пример 6. Построить логическую схему, реализующую функцию с данной таблицей истинности:
| x | y | f |
| 1 | 1 | 0 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
Решение. Разбираем таблицу истинности для логической схемы. Определяем функцию, которая получится на выходе схемы и промежуточные функции, которые на входе принимают аргументы x и y . В первой строке результатом реализации выходной функции при том, что значения входных переменных равны единицам, должен быть логический «0», во второй строке — при разных значениях входных переменных на выходе тоже должен быть логический «0». Поэтому нужно, чтобы выходная функция была конъюнкцией (логическим произведением).
Теперь подбираем промежуточные функции. Получаем следующую таблицу для промежуточных функций и выходной функции — конъюнкции промежуточных функций:
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
| 0 | 1 | 0 |
Для построения логической схемы необходимо элементы, реализующие логические операции, указанные в выходной функции, располагать в порядке, заданной этой функцией. Из выражения видно, что понадобятся 3 схемы «НЕ», две двухвходовых схемы «И» и одна двухвходовая схема «ИЛИ». В соответствии с выходной функцией получаем следующую логическую схему:
А теперь очередь дошла до функций алгебры логики четырёх переменных. Сначала выполним синтез логической схемы в булевом базисе.
Пример 7. Построить в булевом базисе логическую схему, реализующую функцию алгебры логики
Решение. Для построения логической схемы потребуются 4 схемы «НЕ», одна трёхвходовая схема «И», 2 двухвходовые схемы «И» и одна трёхвходовая схема «ИЛИ». В соответствии с этим получаем следующую логическую схему:
- Пригодится: минимизация логических функций — общие сведения
- Пригодится: минимизация логических функций методом непосредственных преобразований
Задача синтеза логических схем в базисах «И-НЕ» и «ИЛИ-НЕ»
Часто для сокращения числа микросхем используют элементы «И-НЕ» или/и «ИЛИ-НЕ». Рассмтрим примеры, как построить схему, реализующую ту же функцию, что в предыдущем примере, но, сначала в базисе «И-НЕ», а затем в базисе «ИЛИ-НЕ».
Пример 8. Построить в базисе «И-НЕ» логическую схему, реализующую функцию алгебры логики .
Решение. Логическая функция должна быть приведена к виду, содержащему только операции логического умножения (конъюнкции) и инвертирования (отрицания). Это делается при помощи двойного инвертирования исходного выражения функции и применения закона де Моргана:
Для построения логической схемы потребуются 8 схем «И-НЕ». Получаем следующую логическую схему:
Пример 9. Построить в базисе «ИЛИ-НЕ» логическую схему, реализующую функцию алгебры логики .
- Пригодится: минимизация логических функций — общие сведения
- Пригодится: минимизация логических функций методом непосредственных преобразований
- Пригодится: минимизация логических функций методом Квайна
4. Функциональные схемы и структурные формулы логических устройств
Устройства компьютера строятся на основе базовых логических элементов соответствующих базовым логическим операциям.
Х & Y
Х Y
Цепочку из логических элементов, в которой выходы одних элементов являются входами других, называют логическим устройством. Схема соединения логических элементов, реализующая логическую функцию, называется, функциональной схемой. Формой описания функции, реализуемой логическим устройством, является структурная формула.
Пример 4. По заданной структурной формуле (логической функции) F(A,B) = B & A B & A построить функциональную (логическую) схему.
Решение. Построение надо начинать с операции, которая должна выполняться последней. В данном случае это логическое сложение, значит, на выходе логической схемы должен быть дизъюнктор. На него сигналы подаются от двух конъюнкторов, на которые, в свою очередь подаются один входной сигнал нормальный и один инвертированный (инверторов).
B & A
B & A
F(A,B) ) = B & A B & A
