Тема: Логические основы ЭВМ
Урок 1: Логические функции и таблицы истинности
Мы закончили тему «Арифметические основы ЭВМ». Познакомились с системами счисления.
- Какая система счисления применяется в компьютере? (двоичная)
- Почему? (существует 2 устойчивых состояния: ток течет – ток не течет, напряжение высокое – низкое, участок магнитного диска намагничен – не намагничен, на лазерном диске «выпуклость» и «впадина», от которых луч лазера отражается – не отражается)
- Как выполняются арифметические операции в двоичной с. с.? Сложить два числа (обращая внимание на «запоминание» переносов)
1 1 1
1001
+1011
10100
- А как же эти действия выполняются в компьютере?! Неужели компьютер таким же образом считает 1+1=10, 0 пишем, 1 в уме. Где же и как компьютер пишет, как именно запоминает «в уме»? Наша задача разобраться в этом.
- На какой элементной базе строились ЭВМ различных поколений? Сколько поколений ЭВМ существует? (4 поколения: I – на электронных лампах; II – на транзисторах; III – на микросхемах; IV – большие интегральные схемы, микропроцессоры). А еще раньше – были построены счетные машины на электромеханических реле (Марк-1). А еще ранее в 1823 году Ч. Бэббидж пытался построить ЭВМ на основе гидравлических систем.
Основоположником древнейшей науки ЛОГИКИ был великий древнегреческий ученый Аристотель.
Логика – это наука о формах и способах мышления.
Мышление всегда осуществляется в каких-либо формах. Основными формами мышления являются понятие, суждение и умозаключение.
Понятие – это форма мышления, фиксирующая основные, существенные признаки объекта. Т. е. понятие выделяет существенные признаки объекта, которые отличают его от других объектов.
Например, понятие «компьютер» объединяет множество электронных устройств, которые предназначены для обработки информации, в числе которых монитор и клавиатура. Даже по этому короткому описанию компьютер трудно спутать с другими объектами, например, с механизмами, служащими для перемещения по дорогам и хранящимися в гаражах, которые объединяются понятием «автомобиль»
Свое понимание окружающего мира человек формулирует в виде высказываний. Высказывание строится на основе понятий и по форме является повествовательным предложением.
Высказывание может быть либо истинным, либо ложным. Истинным будет высказывание, в котором связь понятий правильно отражает свойства и отношения реальных вещей. Например, «Процессор является устройством обработки информации» - истинное высказывание. «Процессор является устройством печати» - ложное высказывание. Иногда истинности того или иного высказывания является относительной.
Высказывание – это форма мышления, в которой что-либо утверждается или отрицается о процессах, предметах, их свойствах и отношениях между ними.
Высказывание может быть либо истинным, либо ложным.
Например:
– высказывание «В нашем классе сейчас горит свет» – истинно.
– высказывание «Кошки умеют летать» – ложно (для нормальных кошек).
Высказывание «X>Y» истинно при одних значениях Х и Y и ложно при других значениях. Поэтому «X>Y» – высказыванием не является. Не являются высказыванием и вопрос «Который час?», и восклицание «Какая прелесть!».
Простые высказывания можно объединять в сложные с помощью связок.
х |
|
0 | 1 |
1 | 0 |
Пусть есть высказывание х «В нашем классе сейчас горит свет». Оно истинно.
Построим отрицание этого высказывания с помощью связки НЕ: «В нашем классе сейчас не горит свет». Оно ложно.
Или высказывание «Кошки умеют летать». Оно ложно. Отрицание этого высказывания: «Кошки не умеют летать» - истинно.
Функция, которая строится с помощью частицы «НЕ» называется ОТРИЦАНИЕ или ИНВЕРСИЯ.
Обозначается y= или y= х
х | y | x&y |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Есть два высказывания:
х: «Ручка состоит из корпуса»
у: «Ручка состоит из стержня»
Объединим эти высказывания связкой «И»: «Ручка состоит из корпуса и стержня». Рассмотрим таблицу истинности для этого сложного высказывания:
Функция, которая строится с помощью частицы «И» называется КОНЪЮНКЦИЯ или Логическое умножение.
Обозначается z= x&y или z= xÙy или z= x×y
х | y | xVy |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
Рассмотрим другие два высказывания:
х: «На улице идет дождь»
у: «На улице идет снег»
Объединим эти высказывания связкой «ИЛИ»: «На улице идет дождь или снег». Рассмотрим таблицу истинности для этого сложного высказывания:
Функция, которая строится с помощью частицы «И» называется ДИЗЪЮНКЦИЯ или Логическое сложение.
Обозначается z= xÚy z= x+y
х | y | x®y |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 1 |
Рассмотрим еще два высказывания:
х: «На улице идет дождь»
у: «Улицы мокрые»
Объединим эти высказывания связкой «ЕСЛИ … ТО …»: «Если на улице идет дождь, то улицы мокрые». Рассмотрим таблицу истинности для этого сложного высказывания:
Функция, которая строится с помощью связки «ЕСЛИ … ТО …» называется ИМПЛИКАЦИЕЙ.
Обозначается z= x®y
х | y | x«y |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Рассмотрим следующие два высказывания:
х: «Вася выучит уроки»
у: «Рак на горе свиснет»
Объединим эти высказывания связкой «ТОГДА И ТОЛЬКО ТОГДА …»: «Вася выучит уроки тогда и только тогда, когда рак на горе свиснет». Рассмотрим таблицу истинности для этого сложного высказывания:
Функция, которая строится с помощью связки «ТОГДА И ТОЛЬКО ТОГДА …» называется ЭКВИВАЛЕНТНОСТЬЮ.
Обозначается z= x«y; x~y; x≡y;
х | y | x y xÅy |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Рассмотрим еще два высказывания:
х: «На футбольном матче я сижу на северной трибуне»
у: «На футбольном матче я сижу на южной трибуне»
Объединим эти высказывания связкой «ЛИБО … ЛИБО …»: «На футбольном матче я сижу либо на северной трибуне, либо на южной трибуне». Рассмотрим таблицу истинности для этого сложного высказывания:
Функция, которая строится с помощью связкой «ЛИБО … ЛИБО …» называется СТРОГОЙ ДИЗЪЮНКЦИЕЙ или СЛОЖЕНИЕМ ПО МОДУЛЮ ДВА.
Обозначается z= x
y или z= xÅy
Порядок выполнения логических операций (в порядке убывания приоритета их выполнения):
1. 
Действия в скобках
2. Инверсия (Ø)
3. Конъюнкция (Ù или &)
4. Дизъюнкция (Ú)
5. Строгая дизъюнкция (сложение по модулю два) ( или Å)
6. Импликация (®)
7. Эквивалентность («)
Задание 1: Построить таблицу истинности для функции:
х ® y Ú x Ù(Øy)
Решение:
1. Определяем количество переменных (2: x и y)
2. Определяем количество наборов (комбинаций 0 и 1 для такого количества переменных равно 2n, где n – количество переменных, в нашем случае n = 2: 22=4)
3. Определяем порядок выполнения действий:
1 4 3 2
(х ® y) Ú x Ù(Øy)
4. Составляем таблицу и заполняем ее:
х | y | 1 (х ® y) | 2 (Øy) | 3 x Ù(Øy) | 4 (1)Ú(3) |
0 | 0 | 1 | 1 | 1 | 1 |
0 | 1 | 1 | 0 | 1 | 1 |
1 | 0 | 0 | 1 | 1 | 1 |
1 | 1 | 1 | 0 | 0 | 1 |
Задание 2: Построить таблицу истинности для функции:
х Ù(Øy) Ù z Ú x
Решение:
1. Определяем количество переменных (3: x, y и z)
2. Определяем количество наборов (2n для n = 3: 23=8)
3. Определяем порядок выполнения действий:
2 1 3 4
х Ù(Øy) Ù z Ú x
4. Составляем таблицу и заполняем ее:
х | y | z | 1 Øy | 2 х Ù (Øy) | 3 x Ù(Øy) Ùz | 4 (3)Ú(x) | 2-й способ | х | y | z | 3 x Ù(Øy) Ùz | 4 (3)Ú(x) |
0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | |
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | |
1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | |
1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | |
1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | |
1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
Покажем, как можно упростить построение таблицы истинности для этой функции: функция конъюнкция («И», логическое умножение) будет иметь значение 1, когда равны 1 все переменные, т. е. х=1, 
=1 (т. е. у=0) и z=1. Т. о. можно сразу же записать столбец 3:
Кстати, обратите внимание, что в приведенном примере получено значение, полностью совпадающее с переменной х. Это должно навести нас на мысль, что должны быть способы упрощения логических выражений. Такие способы есть. Это материал следующего урока.
Итак, мы познакомились с основными логическими функциями, их обозначениями и таблицами истинности.
Дом. задание.
1. Выучить все функции, слова-связки, которые им соответствуют, их таблицы истинности.
2. Построить таблицы истинности для следующих функций:
(х Ú Øy Ú Øz) Ù x
(х ® y) Ù Ø(y « z)
Урок 2: Преобразование логических выражений. Законы алгебры логики.
Основные законы алгебры логики.
1. Переместительный (коммутативный) закон
X v Y = Y v X; X & Y = Y & X
2. Сочетательный (ассоциативный) закон
X v (Y v Z) = (X v Y) v Z; X & (Y & Z) = (X & Y) & Z
3. Распределительный (дистрибутивный) закон
X & (Y v Z) = X & Y v X & Z
В отличие от математики, в которой есть только один распределительный закон для умножения, в алгебре логики есть и второй распределительный закон для сложения:
X v (Y & Z) = (X v Y) & (X v Z) (! Докажите этот закон с помощью таблиц истинности!)
4. Операции с константами: 
X Ú 0 = X; X Ú 1 = 1
X & 1 = X; X & 0 = 0
5. Операции с переменной и ее инверсией (отрицанием)
X v 
= 1 - исключение третьего (Х Ú ØХ = 1)
X & = 0 - противоречие (Х Ù ØХ = 0)
6. Двойное отрицание 
= Х (Ø(ØХ) = Х)
7. Правила де Моргана (чтобы “разбить” “длинную” инверсию, нужно поставить инверсии над каждой переменной, входящей в операцию, а знак операции изменить на противоположный). _____ _ _ ______ _ _
X v Y = X & Y; X & Y = X v Y
[ Ø(X Ú Y) = ØX Ù ØY; Ø(X Ù Y) = ØX Ú ØY ]
(! Докажите эти законы с помощью таблиц истинности!)
8. Идемпотентность (убрать лишнее)
X v X = X; X & X = X
9. Поглощение X v (X & Y) = X; X & (X v Y) = X
10. Дополнительные формулы
· Преобразование импликации через И, ИЛИ, НЕ:
A → B = A Ú B или в других обозначениях A → B = 
· Преобразование эквивалентности через И, ИЛИ, НЕ:
A ~ B = ( A Ú B) Ù ( A Ú B) = ( A Ù B) Ú ( A Ù B) или в других обозначениях A ↔ B = 
· для упрощения выражений можно использовать формулы (следствия из распределительного закона)
(т. к. 
)
(т. к. 
)
Задача: упростить выражение: 
1. Применяем закон де Моргана: 
2. 2-й раз применяем закон де Моргана: 
3. Снова применяем закон де Моргана для каждой «длинной» инверсии: 
4. Применяем закон двойного отрицания для b и c: 
5. Применяя сочетательный закон для сложения, и учитывая, что умножение является более приоритетной операцией, чем сложение, убираем скобки и получаем ответ: 
2-й способ решения данной задачи:
1. Применяем закон де Моргана для конъюнкции (умножения): 
2. Применяем закон де Моргана для 1-й скобки и закон двойного отрицания для 2-й скобки:
3. Применяя сочетательный закон для сложения, и учитывая, что умножение является более приоритетной операцией, чем сложение, убираем скобки и получаем ответ:
Дом. задание.
1. Выучить все законы алгебры логики.
2. Доказать распределительный закон и 2 правила де Моргана с помощью таблиц истинности
3. Индивидуальные задания на упрощение логических выражений (выдает учитель)
Основные порталы (построено редакторами)