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

Пример решение логических задач средствами алгебры логики

Логические схемы

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

Каждый переключатель имеет только два состояния: замкнутое и разомкнутое . Переключателю Х поставим в соответствие логическую переменную х, которая принимает значение 1 в том и только в том случае, когда переключатель Х замкнут и схема проводит ток; если же переключатель разомкнут, то х равен нулю.

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

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

При рассмотрении переключательных схем возникают две основные задачи: синтез и анализ схемы.

СИНТЕЗ СХЕМЫ по заданным условиям ее работы сводится к следующим трём этапам:

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

АНАЛИЗ СХЕМЫ сводится к:

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

Задача : Составить таблицу истинности для данной формулы: (x ~ z) | ((x y) ~ (y z)).

Решение : В таблицу истинности данной формулы полезно включить таблицы истинности промежуточных функций:

xyz	x ~ z	x y	y z	(x y) ~ (y z)	(x~ z)\|((x y) ~ (yz)

Методические указания для выполнения практического задания №2. «Алгебра логики». Построение таблиц истинности.

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

Задание:

1. В приложении 2 выбрать вариант задания и составить таблицу истинности .

2. Выполнить задание, используя пример решение логических задач средствами алгебры логики.

Задача :

Построить логическую схему по заданному булевому выражению:

F =`BA + B`A + C`B.

Решение:

Как правило, построение и расчет любой схемы осуществляется начиная с ее выхода.

Первый этап : выполняется логическое сложение, логическую операцию ИЛИ, считая входными переменными функции`B A, B`A и C`B:

Второй этап : к входам элемента ИЛИ подключаются логические элементы И, входными переменными которых являются уже A, B, C и их инверсии:

Третий этап : для получения инверсий`A и`B на соответствующих входах ставят инверторы:

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

Методические указания для выполнения практического задания №3. «Алгебра логики». Построение логических схем

Задание:

1. В приложении 2 выбрать вариант задания и построить логическую схему .

2. Выполнить задание, используя пример построения логических схем.

3. Оформить работу в тетради для практических работ.

4. Результат работы предъявить преподавателю.

5. Защитить выполненную работу у преподавателя.

Приложение 2. Таблица вариантов заданий

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

4. Индивидуальное задание. Модуль 1. «Построение логических схем по заданным булевым выражениям»

Задания к ИДЗ:

В приложении 3 выбрать вариант индивидуального задания.
Выполнить задание, пользуясь теоретическими сведениями
Проверить логическую схему у тьютора.
Оформить ИДЗ в формате А4, титульный лист по образцу Приложение 4.
Результат работы предъявить преподавателю.
Защитить выполненную работу у преподавателя.

Приложение 3. Таблица вариантов индивидуального задания

Варианты	Составить таблицу истинности и логическую схему по формулам

Приложение 4. Титульный лист ИДЗ

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

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

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

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

Элемент НЕ

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

Элемент ИЛИ

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

Элемент И

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

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

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

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

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

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

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

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

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

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

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

Логические операции конъюнкции, дизъюнкции, инверсии реализуются в ЭВМ с помощью следующих элементарных схем.

Конъюнкция – логический элемент «и»:

Этот элемент выполняет операцию логического умножения (конъюнкция): f = x 1 Ù x 2 Ùx 3 Ù…Ùx n ; и имеет n входов и один выход.

Дизъюнкция – логический элемент «или»:

Этот элемент выполняет операцию логического сложения (дизъюнкция): f = x 1 Ú x 2 Úx 3 Ú…Úx n ; и имеет n входов и один выход.

Инверсия – логический элемент «не»:

Этот элемент выполняет операцию логического отрицания (инверсии): f = ; и имеет один вход и один выход.

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

Пример выполнения контрольного задания

Задание:

Дана функция,

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

2. Упростить логическую функцию (используя законы булевой алгебры) и выполнить проверку преобразования таблицей истинности.

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

Выполнение:

1. Составим таблицу истинности для заданной функции:

x	y

2. Составим функциональную логическую схему по заданной функции:

3. Упростим заданную функцию, используя законы булевой алгебры:

а) по закону де Моргана – 9

б) по закону идемпотентности - 13

в) закон отрицание отрицания – 1

г) закон дистрибутивности – 6

д) свойства 1 и 0 – 19

е) свойства 1 и 0 – 16

Таким образом, упрощенная функция имеет вид:

4. Составим таблицу истинности для упрощенной функции:

x	y

Таким образом, сравнивая таблицы истинности для исходной и упрощенной функций (их последние столбцы) делаем вывод о правильности проведенных преобразований.

5. Составим функциональную логическую схему по упрощенной функции:

Задание для выполнения контрольной работы

Дана функция f(x,y), номер функции в таблице соответствует порядковому номеру студента по списку.

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

5. Упростить логическую функцию (используя законы булевой алгебры) и выполнить проверку преобразования таблицей истинности.

Лабораторная работа № 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. На входы логического элемента поступают сигналы-значения аргументов, на выходе появляется сигнал-значение функции.

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

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

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

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

Решение.

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

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

Цели урока:

Образовательные:

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

Развивающие:

формировать развитие алгоритмического мышления;
развить конструкторские умения;
продолжать способствовать развитию ИКТ - компетентности;

Воспитательные:

продолжить формирование познавательного интереса к предмету информатика;
воспитывать личностные качества:
активность,
самостоятельность,
аккуратность в работе;

Требования к знаниям и умениям:

Учащиеся должны знать:

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

Учащиеся должны уметь:

составлять логические схемы.

Тип урока: урок закрепления изученного материала

Вид урока: комбинированный

Методы организации учебной деятельности:

фронтальная;
индивидуальная;

Программно-дидактическое обеспечение:

ПК, SMART Board, карточки с индивидуальным домашним заданием.

Урок разработан с помощью программы Macromedia Flash .

Ход урока

I. Постановка целей урока.

Добрый день!

Сегодня мы продолжаем изучение темы "Построение логических схем".

Приготовьте раздаточный материал "Логические основы ЭВМ. Построение логических схем" Приложение 1

Вопрос учителя. Назовите основные логические элементы. Какой логический элемент соответствует логической операции И, ИЛИ, НЕ?

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

Вопрос учителя. По каким правилам логические элементы преобразуют входные сигналы. Рассмотрим элемент И. В каком случае на выходе будет ток (сигнал равный 1).

Ответ учащихся. На первом входе есть ток (1, истина), на втором есть (1, истина), на выходе ток идет (1, истина).

Вопрос учителя. На первом входе есть ток, на втором нет, однако на выходе ток идет. На входах тока нет и на выходе нет. Какую логическую операцию реализует данный элемент?

Ответ учащихся. Элемент ИЛИ - дизъюнктор.

Вопрос учителя. Рассмотрим логический элемент НЕ. В каком случае на выходе не будет тока (сигнал равный 0)?

Ответ учащихся. На входе есть ток, сигнал равен 1.

Вопрос учителя. В чем отличие логической схемы от логического элемента?

Ответ учащихся. Логические схемы состоят из логических элементов, осуществляющих логические операции.

Проанализируем схему и определим сигнал на выходе.

II. Закрепление изученного материала.

Почему необходимо уметь строить логические схемы?

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

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

Вопрос учителя. Каков алгоритм построение логических схем?

Ответ учащихся. Алгоритм построение логических схем:

Определить число логических переменных.

Определить количество базовых логических операций и их порядок.

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

Соединить вентили в порядке выполнения логических операций.

Проверка домашнего задания Приложение 1 . Домашнее задание. Часть 1

Построить логическую схему для логического выражения:

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

Таким образом, цель нашего следующего урока - изучить законы алгебры логики.

IV. Домашнее задание. Часть 2

V. Практическая работа.

Программа - тренажер "Построение логических схем"