Удобным способом представления логических выражений являются логические схемы. Вот как изображаются на таких схемах три основные логические операции:

Рис 6.1 - Схематическое изображение логических операций

Пример. Для вычисления логического выражения: 1 или 0 и 1 нарисовать схему, от­ра­жающую последовательность выполнения логических операций. По схеме вычислить зна­чение логического выражения.

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

В результате получилась1 , т.е. «ИСТИНА».

Пример. Дано выражение:не (1 и (0 или 1) и 1).

Вычислить значение выражения с помощью логической схемы.

Решение. Логическая схема с результатами вычислений выглядит так:

Импликация и эквивалентность

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

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

Выражение, стоящее после словто, тогда, называется следствием. В логических формулах операция импликации обозначается знаком «→». Импликация - двухместная операция; записывается так: А→В .

Эквивалентность. Языковой аналог - союзы если и только если; тогда и только тогда, когда... Эквивалентность обозначаетсязнаком «≡» или «↔».

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

Преобразование логических выражений

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

Основные формулы преобразования логических выражений:

2. (А & В) ≡ А В.

3. (А В) ≡ А & В.

4. (А → В) ≡А & В.

5. А→B ≡ A B.

6. А ↔ В ≡ (А & В) (А & В) ≡ (А В) & (А B).

7. А & (А B) ≡ А.

8. А А & В ≡ А.

9. А & (А В) ≡ А & В.

10. A А & В ≡ А В.

11. Законы коммутативности:

А & В ≡ В & А;

А В ≡ В А.

12. Законы ассоциативности:

(A B) С ≡ А (В С);

(А & В) & С ≡ А & (В & С).

13. Законы идемпотентности:

А А ≡ А;

14. Законы дистрибутивности:

А & (В С) ≡ (А & В) (А & С);

А (В & С) ≡ (А В) & (А С).

15. А 1 ≡ 1;

16. А & 1 ≡ А;

17. А А ≡ 1;

18. А & 0 ≡ 0;

19. А & А ≡ 0.

6.3. Задание на лабораторную работу

Задания распределяются в зависимости от выданного преподавателем mn -кода. Если m - число нечетное, то ваш вариант 1, если четное - вариант 2.

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

Вариант 1.

1) хотя бы одно из чисел X, Y, Z положительно;

2) только одно из чисел X, Y, Z не является положительным.

3) только одно из чисел X, Y, Z больше 10

4) ни одно из чисел X, Y, Z не равно 104

Вариант 2.

1) хотя бы одно из чисел X, Y, Z отрицательно;

2) только одно из чисел X, Y, Z является отрицательным.

3) только одно из чисел X, Y, Z не больше 10

4) каждое из чисел X, Y, Z равно 0

Задание 2. Определите значение логического выражения не (X>Z) ине (X=Y), если:

Вариант 1.

1) X=3, Y=5, Z=2;

2) X=5, Y=0, Z=–8.

Вариант 2.

1) X=9, Y=–9, Z=9;

2) X=0, Y=1, Z=19.

Задание 3. Пусть a, b, c - логические величины, которые имеют следующие значения: а = истина , b= ложь , c = истина . Нарисуйте логические схемы для следующих логических выражений и вычислите их значения:

Вариант 1.

1) а и b;

2) не а или b;

3) а или b и с;

4) (а или b) и (c или b).

Вариант 2.

1) а или b;

2) а и b или с;

3) не а или b и с;

4) не (а и b и с).

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

Вариант 1. x 1 и (не x 2 или x 3).

Вариант 2. x 1 и x 2 или не x 1 и x 3 .

Задание 5. Выполните вычисления по логическим схемам. Запишите соответствующие логические выражения:

Вариант 1. Вариант 2.

Задание 6. Дана логическая схема. Построить логическое выражение, соответствующее этой схеме.

Вычислить значение выражения для:

Вариант 1.

1) x 1 =0, x 2 =1;

2) x 1 =1, x 2 =1.

Вариант 2.

1) x 1 =1, x 2 =0;

2) x 1 =0, x 2 =0.

Задание 7. Дана логическая схема. Построить таблицу истинности для данной схемы.

Задание 8. Определить истинность формулы:

Вариант 1. ((a ) .

Вариант 2. .

Задание 9. Упростите выражение:

Вариант 1. .

Вариант 2. .

6.4. Требования к содержанию отчета

1. Цель лабораторной работы.

2. Задание на лабораторную работу. Mn – код.

3. Результаты решения заданий своего варианта.

4. Выводы по полученным результатам.

6.5. Контрольные вопросы

1. Что такое логическое высказывание, константа, переменная, формула?

2. Какие виды логических операций рассматриваются в лабораторной работе?

3. Таблицы истинности для импликации и эквивалентности?

4. Перечислите законы алгебры логики?


Лабораторная работа №7
"СИСТЕМЫ СЧИСЛЕНИЯ"

7.1. Цель работы

Изучение систем счисления. Приобретение навыков перевода из одной системы счи­с­ления в другую

7.2. Методические указания

Развернутой формой записи числа называется запись в виде:

A q =±(a n-1 q n-1 + a n-2 q n-2 +…+ a 0 q 0 + a –1 q -1 + a -2 q -2 + …+ а -m q -m).

Здесь А q - само число, q - основание системы счисления, а i - цифры данной системы счи­сления, n - число разрядов целой части числа, m - число разрядов дробной части чис­ла.

Пример. Получить развернутую форму десятичных чисел 32478; 26,387.

32478 10 = 3*10000 + 2*1000 + 4*100 + 7*10 + 8 = 3*10 4 + 2*10 3 + 4*10 2 + 7*10 1 + 8*10 0 .

26,387 10 = 2*10 1 + 6*10 0 + 3*10 -1 + 8*10 -2 + 7*10 -3 .

Пример. Получить развернутую форму чисел 112 3 , 101101 2 , 15FC 16 , 101,11 2

112 3 =1*10 2 + 1*10 1 + 2*10 0 .

1011012 = 1*10 101 + 0*10 100 + 1*10 11 + 1*10 10 + 0*10 1 + 1*10 0 .

15FC 16 = 1*10 3 + 5 *10 2 + F*10 1 + С.

101,11 2 = 1*10 10 + 0*10 1 + 1*10 0 + 1*10 -1 + 1*10 -10 .

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

Пример. Все числа из предыдущего примера перевести в десятичную систему.

112 3 =1*3 2 + 1*3 1 + 2*3 0 = 9+3+2 = 14 10 .

101101 2 = 1*2 5 + 0*2 4 + 1*2 3 + 1*2 2 + 0*2 1 + 1*2 0 =32+8+4+1 = 45 10 ,

15FC 16 = 1*16 3 + 5*16 2 + 15*16 1 + 12 = 4096 + 1280 + 240 + 12 = 5628 10 .

101,11 2 = 1*2 2 + 0*2 1 + 1*2 0 + 1*2 –1 + 12 -2 = 4 + 1 + 1/2 + 1/4 = 5 + 0,5 + 0,25 = 5,75 10 .

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

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

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

Этот элемент выполняет операцию логического умножения (конъюнкция): 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. Упростить логическую функцию (используя законы булевой алгебры) и выполнить проверку преобразования таблицей истинности.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача : Составить таблицу истинности для данной формулы: (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. «Построение логических схем по заданным булевым выражениям»

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

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

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

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

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

Конспект урока
«Построение логических схем с помощью базовых логических элементов»

10 класс

Тип урока: лекция, самостоятельная работа.

Оборудование: проектор, карточки с заданиями.

Формы работы: коллективная, индивидуальная.

Продолжительность урока: 45 мин.

Цели урока:

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

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

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

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

    привитие навыков самостоятельности в работе, воспитание аккуратности, дисциплинированности.

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

    развитие внимания, мышления, памяти учащихся.

Ход урока:

1. Организационный момент (1 мин).
2. Проверка пройденного материала (5 мин).

Фронтальный опрос.

    Перечислите основные логические операции.

    Что такое логическое умножение?

    Что такое логическое сложение?

    Что такое инверсия?

    Что такое таблица истинности?

    Что такое сумматор?

    Что такое полусумматор?

3. Изучение нового материала (20 мин).

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

Логический элемент «И»:

Логический элемент «ИЛИ»:

Логический элемент «НЕ»:

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

Пример 1. построить логическую схему.

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

Пример 2. Выписать из логической схемы соответствующую ей логическую формулу:

Решение:

4. Закрепление нового материала (15 мин).

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

Вариант 1.


Решение:

Решение:

Вариант 2.

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

2. Выписать из логической схемы соответствующую ей логическую формулу:

Решение:

5. Постановка домашнего задания. (3 мин).

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

6. Подведение итогов урока. (1 мин).

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

Литература, эор:

    Информатика и информационные технологии. Учебник для 10-11 классов, Н. Д. Угринович – 2007г.;

    Практикум по информатике и информационным технологиям. Учебное пособие для общеобразовательных учреждений, Н. Д. Угринович, Л. Л. Босова, Н. И. Михайлова – 2007г.