Постройте булево выражение по логической схеме. Логические схемы. Переход от логического выражения к логической схеме и наоборот. Задание для выполнения контрольной работы

Лабораторная работа № 4 .

Схемотехническая реализация логических элементов. Построение логических схем.

Теоретическая часть.

В основе обработки компьютером информации лежит алгебра логики, разработанная Дж. Булем. Было доказано, что все электронные схемы ЭВМ могут быть реализованы с помощью логических элементов И, ИЛИ, НЕ.

Элемент НЕ

При подаче на вход схемы сигнала низкого уровня (0) транзистор будет заперт, т.е. ток через него проходить не будет, и на выходе будет сигнал высокого уровня (1). Если же на вход схемы подать сигнал высокого уровня (1), то транзистор “откроется”, начнет пропускать электрический ток. На выходе за счет падения напряжения установится напряжение низкого уровня. Таким образом, схема преобразует сигналы одного уровня в другой, выполняя логическую функцию.

Элемент ИЛИ

Функция “ИЛИ” - логическое сложение (дизъюнкция), ее результат равен 1, если хотя бы 1 из аргументов равен 1. Здесь транзисторы включены параллельно друг другу. Если оба закрыты, то их общее сопротивление велико и на выходе будет сигнал низкого уровня (логический “0”). Достаточно подать сигнал высокого уровня (“1”) на один из транзисторов, как схема начнет пропускать ток, и на сопротивлении нагрузки установится также сигнал высокого уровня (логическая “1”).

Элемент И

Если на входы Вх1 и Вх2 поданы сигналы низкого уровня (логические “0”), то оба транзистора закрыты, ток через них не проходит, выходное напряжение на R н близко к нулю. Пусть на один из входов подано высокое напряжение (“1”). Тогда соответствующий транзистор откроется, однако другой останется закрытым, и ток через транзисторы и сопротивление проходить не будет. Следовательно, при подаче напряжения высокого уровня лишь на один из транзисторов, схема не переключается и на выходе остается напряжение низкого уровня. И лишь при одновременной подаче на входы сигналов высокого уровня (“1”) на выходе мы также получим сигнал высокого уровня.

Таким образом, каждой базовой логической функции – «И», «ИЛИ», «НЕ» - соответствует особым образом сконструированная схема, называемая логическим элементом. Комбинируя сигналы, обозначающие логические переменные, и выходы, соответствующие логическим функциям, с помощью логических элементов, пользуясь таблицей истинности или представлением логической функции в виде КНФ и ДНФ, можно составить структурную или функциональную схему (см. примеры ниже), являющуюся основой для аппаратной реализации схемы.

Анализируя функциональную схему, можно понять, как работает логическое устройство, т.е. дать ответ на вопрос: какую функцию она выполняет. Не менее важной формой описания логических устройств является структурная формула. Покажем на примере как выписывают формулу по заданной функциональной схеме (1 схема). Ясно, что элемент “И” осуществляет логическое умножение значений и В. Над результатом в элементе “НЕ” осуществляется операция отрицания, т.е. вычисляется значение выражения: Формула и есть структурная формула логического устройства.

Итак, основные логические функции обозначаются

Инверсия
Конъюнкция
Дизъюнкция

Пример: дана логическая схема:

Она построена на основании булева выражения - Y = Ē /\ I \/ Ē /\ A \/ Ā /\ E

Практическая часть.

Задание 1. Для каждой из функциональных схем выписать соответствующую структурную формулу.

2) Для КНФ и ДНФ из лабораторной работы 5 построить функциональные схемы.

Логической функции в компьютере соответствует некоторая схема из вентилей. Этот принцип даёт такой подход к созданию компьютера :

Формируем логическую функцию, описывающую преобразование исходных двоичных кодов в нужный результат.

Полученную функцию упрощают, используя законы алгебры логики.

Окончательно полученную функцию записываем в виде схемы из вентилей.

Схема из вентилей реализуется на физическом уровне из электронных элементов.

Приведём пример реализации 3-го этапа . Дана функция

Получить логическую схему функции.

Формирование логической схемы следует начинать с учётом приоритета операций (смотри п. «Определение логической (булевой) функции»), а также круглых скобок, изменяющих порядок выполнения операций. Как известно, самый высокий приоритет имеют операции внутри скобок (если они есть), затем операция инверсии (отрицания). Следовательно, для заданной функции сначала нужно сформировать элементы
и, а затем элемент
. Далее можно выполнить сложение полученных элементов (
и
) и, в последнюю очередь, к полученной сумме добавить переменнуюa . В итоге мы получим следующую схему (рис. 5):

Рис. 5. Схема реализации функции (формула (28))

Возможно решение и обратной задачи, когда дана логическая схема, нужно получить логическую функцию. Например, на рис. 6 дана логическая схема. Требуется написать для неё логическую функцию.

Рис. 6. Схема реализации функции f ( x , y , z )

Двигаясь от входных переменных записываем последовательно для каждого вентиля его логическую операцию над его входными переменными по направлению стрелок. Тогда на выходе схемы получаем результат – функцию. При записи операций необходимо помнить, что операции выполняемые ранее имеют более высокий приоритет, который определяется или самой операцией или указывается скобками.

Так для схемы на рисунке 6 в первую очередь выполняться три операции: x∙y, и. Затем операция инвертирования суммы:
, далее ещё одна операция логического сложения результатов предыдущих операций:
. Последней будет выполняться операция инвертирования результата логического умножения:
. Таким образом, искомая функция имеет вид.

В цифровой схемотехнике цифровой сигнал - это сигнал, который может принимать два значения, рассматриваемые как логическая "1" и логический "0".

Логические схемы могут содержать до 100 миллионов входов и такие гигантские схемы существуют. Представьте себе, что булева функция (уравнение) такой схемы была потеряна. Как восстановить её с наименьшими потерями времени и без ошибок? Наиболее продуктивный способ - разбить схему на ярусы. При таком способе записывается выходная функция каждого элемента в предыдущем ярусе и подставляется на соответствующий вход на следующем ярусе. Этот способ анализа логических схем со всеми нюансами мы сегодня и рассмотрим.

Логические схемы реализуются на логических элементах: "НЕ", "И", "ИЛИ", "И-НЕ", "ИЛИ-НЕ", "Исключающее ИЛИ" и "Эквивалентность". Первые три логических элемента позволяют реализовать любую, сколь угодно сложную логическую функцию в булевом базисе . Мы будем решать задачи на логические схемы, реализованные именно в булевом базисе.

Для обозначения логических элементов используется несколько стандартов. Наиболее распространёнными являются американский (ANSI), европейский (DIN), международный (IEC) и российский (ГОСТ). На рисунке ниже приведены обозначения логических элементов в этих стандартах (для увеличения можно нажать на рисунок левой кнопкой мыши).

На этом уроке будем решать задачи на логические схемы, на которых логические элементы обозначены в стандарте ГОСТ.

Задачи на логические схемы бывают двух видов: задача синтеза логических схемы и задачи анализа логических схем. Мы начнём с задачи второго типа, так как в таком порядке удаётся быстрее научиться читать логические схемы.

Чаще всего в связи с построением логических схем рассматриваются функции алгебры логики:

• трёх переменных (будут рассмотрены в задачах анализа и в одной задаче синтеза);
• четырёх переменных (в задачах синтеза, то есть в двух последних параграфах).

Рассмотрим построение (синтез) логических схем

• в булевом базисе "И", "ИЛИ", "НЕ" (в предпоследнем параграфе);
• в также распространённых базисах "И-НЕ" и "ИЛИ-НЕ" (в последнем параграфе).

Задача анализа логических схем

Задача анализа заключается в определении функции f , реализуемой заданной логической схемой. При решении такой задачи удобно придерживаться следующей последовательности действий.

1. Логическая схема разбивается на ярусы. Ярусам присваиваются последовательные номера.
2. Выводы каждого логического элемента обозначаются названием искомой функции, снабжённым цифровым индексом, где первая цифра - номер яруса, а остальные цифры - порядковый номер элемента в ярусе.
3. Для каждого элемента записывается аналитическое выражение, связывающее его выходную функцию с входными переменными. Выражение определяется логической функцией, реализуемой данным логическим элементом.
4. Производится подстановка одних выходных функций через другие, пока не получится булева функция, выраженная через входные переменные.

Пример 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. Построить логическую схему, реализующую функцию с данной таблицей истинности.

Лабораторная работа № 2. Алгебра логики

Цель работы

Изучить основы алгебры логики.

Задачи лабораторной работы

В результате прохождения занятия студент должен:

• определения основных понятий (простое и сложное высказывания, логические операции, логические выражения, логическая функция);
• порядок выполнения логических операций;
• алгоритм построения таблиц истинности;
• схемы базовых логических элементов;
• законы логики и правила преобразования логических выражений;

• применять загоны логики для упрощения логических выражений;
• строить таблицы истинности;
• строить логические схемы сложных выражений.

Общие теоретические сведения

Основные понятия алгебры логики

Логической основой компьютера является алгебра логики, которая рассматривает логические операции над высказываниями.

Алгебра логики – это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними.

Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Пример. «3 – простое число» является высказыванием, поскольку оно истинно.

Не всякое предложение является логическим высказыванием.

Пример. предложение «Давайте пойдем в кино» не является высказыванием. Вопросительные и побудительные предложения высказываниями не являются.

Высказывательная форма – это повествовательное предложение, которое прямо или косвенно содержит хотя бы одну переменную и становится высказыванием, когда все переменные замещаются своими значениями.

Пример. «x+2>5» - высказывательная форма, которая при x>3 является истинной, иначе ложной.

Алгебра логики рассматривает любое высказывание только с одной точки зрения – является ли оно истинным или ложным. Слова и словосочетания «не», «и», «или», «если..., то», «тогда и только тогда» и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками .

Высказывания, образованные из других высказываний с помощью логических связок, называются составными (сложными). Высказывания, которые не являются составными, называются элементарными (простыми).

Пример. высказывание «Число 6 делится на 2» - простое высказывание. Высказывание «Число 6 делится на 2, и число 6 делится на 3» - составное высказывание, образованное из двух простых с помощью логической связки «и».

Истинность или ложность составных высказываний зависит от истинности или ложности элементарных высказываний, из которых они состоят.

Чтобы обращаться к логическим высказываниям, им назначают имена.

Пример. Обозначим через А простое высказывание «число 6 делится на 2», а через В простое высказывание «число 6 делится на 3». Тогда составное высказывание «Число 6 делится на 2, и число 6 делится на 3» можно записать как «А и В». Здесь «и» – логическая связка, А, В – логические переменные, которые могут принимать только два значения – «истина» или «ложь», обозначаемые, соответственно, «1» и «0».

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение (табл. 1).

Таблица 1. Основные логические операции

НЕ Операция, выражаемая словом «не», называется отрицанием и обозначается чертой над высказыванием (или знаком). Высказывание А истинно, когда A ложно, и ложно, когда A истинно.

Пример. Пусть А=«Сегодня пасмурно», тогда А=«Сегодня не пасмурно».

И Операция, выражаемая связкой «и», называется конъюнкцией (лат. conjunctio – соединение) или логическим умножением и обозначается точкой « » (может также обозначаться знаками или &). Высказывание А В истинно тогда и только тогда, когда оба высказывания А и В истинны.

Пример. Высказывание «Число 6 делится на 2, и число 6 делится на 3» - истинно, а высказывание «Число 6 делится на 2, и число 6 больше 10» - ложно.

ИЛИ Операция, выражаемая связкой «или» (в неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio – разделение) или логическим сложением и обозначается знаком

(или плюсом). Высказывание А В ложно тогда и только тогда, когда оба высказывания А и В ложны.

Пример: Высказывание «Число 6 делится на 2 или число 6 больше 10» - истинно, а высказывание «Число 6 делится на 5 или число 6 больше 10» - ложно.

ЕСЛИ … ТО Операция, выражаемая связками «если …, то», «из … следует», «... влечет …», называется импликацией (лат. implico – тесно связаны) и обозначается знаком → . Высказывание А→В ложно тогда и только тогда, когда А истинно, а В ложно.

Пример. Высказывание «если студент сдал все экзамены на «отлично», то он получит стипендию». Очевидно, эту импликацию следует признать ложной лишь в том случае, когда студент сдал на «отлично» все экзамены, но стипендии не получил. В остальных случаях, когда не все экзамены сданы на «отлично» и стипендия получена (например, в силу того, что студент проживает в малообеспеченной семье) либо когда экзамены вообще не сданы и о стипендии не может быть и речи, импликацию можно признать истинной.

РАВНОСИЛЬНО Операция, выражаемая связками «тогда и только тогда», «необходимо и достаточно», «... равносильно …», называется эквиваленцией или двойной импликацией и обозначается знаком ↔ или ~ . Высказывание А↔В истинно тогда и только тогда, когда значения А и В совпадают.

Пример: Высказывание «Число является четным тогда и только тогда, когда оно делится без остатка на 2» является истинным, а высказывание «Число является нечетным тогда и только тогда, когда оно делится без остатка на 2» - ложно.

ЛИБО … ЛИБО Операция, выражаемая связками «Либо … либо», называется исключающее ИЛИ или сложением по модулю 2 и обозначается XOR или . Высказывание А В истинно тогда и только тогда, когда значения А и В не совпадают.

Пример. Высказывание «Число 6 либо нечетно либо делится без остатка на 2» является истинным, а высказывание «Либо число 6 четно либо число 6 делится на 3» – ложно, так как истинны оба высказывания входящие в него.

Замечание. Импликацию можно выразить через дизъюнкцию и отрицание:

Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:

Исключающее ИЛИ можно выразить через отрицание, дизъюнкцию и конъюнкцию:

Вывод. Операций отрицания, дизъюнкции и конъюнкции достаточно, чтобы описывать и обрабатывать логические высказывания.

Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок договорились считать, что сначала выполняется операция отрицания («не»), затем конъюнкция («и»), после конъюнкции – дизъюнкция («или») и исключающего или и в последнюю очередь – импликация и эквиваленция.

С помощью логических переменных и символов логических операций любое высказывание можно формализовать, то есть заменить логической формулой (логическим выражением).

Логическая формула - это символическая запись высказывания, состоящая из логических величин (констант или переменных), объединенных логическими операциями (связками).

Логическая функция - это функция логических переменных, которая может принимать только два значения: 0 или 1. В свою очередь, сама логическая переменная (аргумент логической функции) тоже может принимать только два значения: 0 или 1.

Пример . – логическая функция двух переменных A и B.

Значения логической функции для разных сочетаний значений входных переменных – или, как это иначе называют, наборов входных переменных – обычно задаются специальной таблицей. Такая таблица называется таблицей истинности .

Приведем таблицу истинности основных логических операций (табл. 2)

Таблица 2

A	B

Опираясь на данные таблицы истинности основных логических операций можно составлять таблицы истинности для более сложных формул.

Алгоритм построения таблиц истинности для сложных выражений:

• количество строк = 2 n + строка для заголовка,
• n - количество простых высказываний.

• количество столбцов = количество переменных + количество логических операций;
• определить количество переменных (простых выражений);
• определить количество логических операций и последовательность их выполнения.

Пример 1. Составить таблицу истинности для формулы И–НЕ, которую можно записать так: .

1. Определить количество строк:

На входе два простых высказывания: А и В, поэтому n=2 и количество строк =2 2 +1=5.

2. Определить количество столбцов:

Выражение состоит из двух простых выражений (A и B) и двух логических операций (1 инверсия, 1 конъюнкция), т.е. количество столбцов таблицы истинности = 4.

3. Заполнить столбцы с учетом таблиц истинности логических операций (табл. 3).

Таблица 3. Таблица истинности для логической операции

Примечание: И–НЕ называют также «штрих Шеффера» (обозначают |) или «антиконъюнкция» ; ИЛИ–НЕ называют также «стрелка Пирса» (обозначают ↓) или «антидизъюнкция» .

Пример 2. Составить таблицу истинности логического выражения .

Решение:

1. Определить количество строк:

На входе два простых высказывания: А и В, поэтому n=2 и количество строк=2 2 +1= 5.

2. Определить количество столбцов:

Выражение состоит из двух простых выражений (A и B) и пяти логических операций (2 инверсии, 2 конъюнкции, 1 дизъюнкция), т.е. количество столбцов таблицы истинности = 7.

Сначала выполняются операции инверсии, затем конъюнкции, в последнюю очередь операция дизъюнкции.

3. Заполнить столбцы с учетом таблиц истинности логических операций (табл. 5).

Таблица 5. Таблица истинности для логической операции
Поскольку любая логическая операция может быть представлена в виде комбинации трех основных, любые устройства компьютера, производящие обработку или хранение информации, могут быть собраны из базовых логических элементов, как из “кирпичиков”.

Логические элементы компьютера оперируют с сигналами, представляющими собой электрические импульсы. Есть импульс – логический смысл сигнала – 1, нет импульса – 0. На входы логического элемента поступают сигналы-значения аргументов, на выходе появляется сигнал-значение функции.

Преобразование сигнала логическим элементом задается таблицей состояний, которая фактически является таблицей истинности, соответствующей логической функции, только представлена в форме логических схем. В такой форме удобно изображать цепочки логических операций и производить их вычисления.

Алгоритм построения логических схем.

1. Определить число логических переменных.
2. Определить количество логических операций и их порядок.
3. Изобразить для каждой логической операции соответствующий ей логический элемент.
4. Соединить логические элементы в порядке выполнения логических операций.

Пример. По заданной логической функции построить логическую схему.

Решение.

1. Число логических переменных = 2 (A и B).
2. Количество операций = 5 (2 инверсии, 2 конъюнкции, 1 дизъюнкция). Сначала выполняются операции инверсии, затем конъюнкции, в последнюю очередь операция дизъюнкции.
3. Схема будет содержать 2 инвертора, 2 конъюнктора и 1 дизъюнктор.
4. Построение надо начинать с логической операции, которая должна выполняться последней. В данном случае такой операцией является логическое сложение, следовательно, на выходе должен быть дизъюнктор. На него сигналы подаются с двух конъюнкторов, на которые, в свою очередь, подаются один входной сигнал нормальный и один инвертированный (с инверторов).

Похожая информация.

Познакомимся с ними поочередно.

Построение логической схемы по заданной логической функции.

Задача:

Дана логическая функция:

Составить логическую схему для неё.

Решение:

Расставим порядок выполнения логических операций, руководствуясь правилами:

1. отрицание
2. умножение
3. сложение

Не забываем про приоритет скобок.
Получаем:

Строим схему по указанному порядку.

Запись логической функции по заданной логической схеме.

Задача:

Дана логическая схема:

Составить логическую функцию по ней.

Решение:

Рассматриваем схему с конца и записываем соответствующие логические операции, учитывая, что в записываемой функции три операнда А, В, С

Можно сначала подписать на схеме промежуточные функции, получаемые на выходе каждого блока, а потом сцепить их логическими операциями.

Определение сигнала на выходе логической схемы по заданным значениям сигналов на всех входах этой схемы.

Задача:

Дана логическая схема и значения сигналов на всех входах:

Определить значение функции F на выходе схемы.

Решение:

Пользуясь таблицами истинности для соответствующих логических элементов схемы, расставляем значения сигналов на выходах и соответственно на входах каждого логического элемента пока не доберёмся до конца схемы. Получаем:

Ответ:

Значение функции F на выходе схемы = 1.

Построение таблицы истинности для заданной логической схемы.

Задача:

Дана логическая схема:

Построить для неё таблицу истинности.

Решение:

Проверяем количество входов на схеме. Количество комбинаций сигналов на 2 входах равно 4, для 3 входов равно 8, для 4 входов равно 16 и т. д. Составляем таблицу истинности, в которой первые столбцы - это входы схемы, обозначенные буквами, следущие столбцы - функции, полученные на выходах каждого элемента схемы, а строки - отражают разные комбинации сигналов на входах. Количество строк совпадает с количеством комбинаций сигналов. Пользуясь таблицами истинности для соответствующих логических элементов схемы, расставляем значения сигналов на выходах каждого логического элемента, т. е. по каждому столбцу пока не доберёмся до конца схемы. Получаем:

Ответ: