Пояснительная записка к презентации

«Основы логики и основы компьютера»

Фамилия, имя, отчество: Смирнова Елена Александровна

Место работы: МБОУ «Средняя общеобразовательная школа №25», г. Череповц

Должность: учитель информатики

4. Предмет конкурса: разработка уроков на данную тему

Данная презентация создана в программе Microsoft PowerPoint для учащихся 10-11 классов. Презентация может быть использована в качестве изучения данной темы или для закрепления изученного учебного материала по теме «Основы логики и логические основы компьютера». Содержание презентации включает в себя все основные подтемы этого раздела. Данная работа знакомит с понятием алгебры логики, рассказывает об операциях над логическими высказываниями. Демонстрация слайдов развивает алгоритмичность мышления, логику, а также развивает мыслительную активность учащихся. Полученные знания помогут в усвоении курса информатики, расширят кругозор и будут способствовать общему развитию школьников. Воспринимается презентация хорошо благодаря присутствию иллюстраций к работе. Вниманию зрителей предложены портреты основоположников учения, списки и таблицы и картинки.

6. Список литературы.

1. Информатика и ИКТ, 10 класс, Профильный уровень, Угринович Н.Д., 2008

http :// kpolyakov . narod . ru / school / ege . htm

http://book.kbsu.ru/theory/chapter5/1_5_0.html

О.Б. Богомолова Логические задачи. - М. БИНОМ. Лаборатория знаний, 2005

В.Ю. Лыскова, Е.А. Ракитина Логика в информатике. - М. “Информатика и образование”. 1999 г.

А.П. Бойко Практикум по логике. - М. “Издательский центр АЗ”, 1997 г.

Слайд 2

2 Логические операции «И», «ИЛИ», «НЕ» лежат в основе работы преобразователей информации любого компьютера американский математик, доказал применимость булевой алгебры в теории контактных и релейно-контактных схем (в 1938 году) Клод Шеннон (1916 г.)

Слайд 3

3 Коньюнктор Логический элемент «И», преобразует входные сигналы и выдает результат логического умножения & 1 0 0

Слайд 4

4 Дизъюнктор Логический элемент «ИЛИ», преобразует входные сигналы и выдает результат логического сложения. V 1 1 0

Слайд 5

5 Инвертор Логический элемент «НЕ». Преобразует входной сигнал и выдает результат логического отрицания. 1 1 0

Слайд 6

6 A & B v B Функциональная схема логического устройства Структурная формулаЛУ & А В V 1 F1 F2 F3 Зная функциональную схему, можно составить структурную формулу данного ЛУ. Анализируя структурную формулу, можно создать функциональную схему и понять, как работает данное ЛУ. 0 1 0 1 0 1

Слайд 7

7 Какие логические операции лежат в основе преобразователей информации в ПК? Как называются логические элементы ПК? Что такое структурная формула? Что можно увидеть на функциональной схеме? Какие устройства ПК построены на логических элементах? Какие основные операции выполняет центральный процессор? Как «работает» память ПК? Контрольные вопросы Не знаете? тогда идем дальше!

Слайд 8

8 Так как все многообразие операций в ПК сводится к сложению двоичных чисел, то главной частью процессора (АЛУ) являетсясумматор. Рассмотрим сложение одноразрядных двоичных чисел: Логические устройства ПК

Слайд 9

9 S=(А v B) & (A & B) P = A & B Докажем это, построив таблицу истинности для данного ЛВ 1 2 3 4

Слайд 10

10 S=(А v B) & (A & B) P = A & B Теперь, на основе полученных логических выражений, можно построить схемуданного устройства & V 1 & P S Данная схема называется полусумматором, так как суммирует одноразрядные двоичные числа без учета переноса из младшего разряда. A B

Слайд 11

11 Многоразрядный сумматор процессора состоит из полных одноразрядных сумматоров, причем выход (перенос) сумматора младшего разряда подключен ко входу сумматора старшего разряда. P = (A & B) V (A & P0) V (B & PO) S = (A V B V P0) & (-P0) V (A & B & P0)

Слайд 12

12 Для хранения информации в ОП и регистрах ЦП применяется устройство ТРИГГЕР. Ячейка памяти состоит из 8, 16 или 32 триггеров, что иопределяет разрядность ЦП. Триггер строится из двух элементов «ИЛИ» и двух элементов «НЕ». V V 1 1 0 1 S(1) R 1 0 В обычном состоянии на входы подан «0». Для записи на вход S подается «1». Он его будет хранить и даже после того, как сигнал на входе «S» исчезнет. Чтобы сбросить информацию, подается «1» на вход R (Reset), после чего триггер возвращается к исходному «нулевому» состоянию.

Слайд 13

13 Несколько триггеров можно объединить в группы - регистры И использовать в качестве запоминающих устройств (ЗУ). Если в регистр входит N триггеров, то при таком ЗУ можно запоминать N-разрядные двоичные слова. ОЗУ ЭВМ часто конструируется в виде набора регистров. Один регистр образует одну ячейку памяти, каждая из которых имеет свой номер т т т т 0 1 0 1 1 1 1 1 Таким образом, ЭВМ состоит из огромного числа Отдельных логических элементов, образующих все ее узлы и память.

Слайд 14

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

Используя панель Рисования редактора MS Word, создайте: 1. Схемы логических элементов Схему логического устройства Схему полусумматора по формулам: 4*. Схемы переноса Р и суммы S многоразрядного сумматора S=(А v B) & (A & B) P = A & B P = (A & B) V (A & P0) V (B & PO) S = (A V B V P0) & (-P0) V (A & B & P0) A & B v B

Посмотреть все слайды

Название документа

‹‹ ‹

1 из 62

› ››

Описание презентации по отдельным слайдам:

№ слайда 1

Описание слайда:

№ слайда 2

Описание слайда:

ФОРМЫ МЫШЛЕНИЯ ЛОГИКА - это наука о формах и законах человеческого мышления и, в частности, о законах доказательных рассуждений. Логика изучает мышление как средство познания объективного мира. Законы логики отражают в сознании человека свойства, связи и отношения объектов окружающего мира. Формальная логика связана с анализом наших обычных содержательных умозаключений, выражаемых разговорным языком. Математическая логика изучает только умозаключения со строго определенными объектами и суждениями, для которых можно однозначно решить, истинны они или ложны. Идеи и аппарат логики используется в кибернетике, вычислительной технике и электротехнике (построение компьютеров основано на законах математической логики). В основе логических схем и устройств ПК лежит специальный математический аппарат, использующий законы логики. Математическая логика изучает вопросы применения математических методов для решения логических задач и построения логических схем. Знание логики необходимо при разработке алгоритмов и программ, так как в большинстве языков программирования есть логические операции.

№ слайда 3

Описание слайда:

Основные формы мышления Основными формами мышления являются: ПОНЯТИЯ, СУЖДЕНИЯ, УМОЗАКЛЮЧЕНИЯ. ПОНЯТИЕ - форма мышления, в которой отражаются существенные признаки отдельного объекта или класса однородных объектов. Примеры: портфель, трапеция, ураганный ветер. Понятие имеет две стороны: содержание и объем. Содержание понятия составляет совокупность существенных признаков объекта. Чтобы раскрыть содержание понятия, следует найти признаки, необходимые и достаточные для выделения данного объекта из множества других объектов. Например, содержание понятия «персональный компьютер» можно раскрыть следующим образом: «Персональный компьютер - это универсальное электронное устройство для автоматической обработки информации, предназначенное для одного пользователя». Объем понятия определяется совокупностью предметов, на которую оно распространяется. Объем понятия «персональный компьютер» выражает всю совокупность (сотни миллионов) существующих в настоящее время в мире персональных компьютеров.

№ слайда 4

Описание слайда:

Основные формы мышления СУЖДЕНИЕ – это форма мышления, в которой что-либо утверждается или отрицается об объектах, их свойствах и отношениях. Суждениями обычно являются повествовательными предложениями, которые могут быть или истинными или ложными. «Берн - столица Франции», «Река Кубань впадает в Азовское море», «2>9», «3×5=10» УМОЗАКЛЮЧЕНИЕ – это форма мышления, посредством которой из одного или нескольких истинных суждений, называемых посылками, мы по определенным правилам вывода получаем новое суждение (заключение). Все металлы - простые вещества. Литий - металл.→ Литий - простое вещество. Один из углов треугольника равен 90º. → Этот треугольник прямоугольный.

№ слайда 5

Описание слайда:

АЛГЕБРА ВЫСКАЗЫВАНИЙ В основе работы логических схем и устройств персонального компьютера лежит специальный математический аппарат - математическая логика. Математическая логика изучает вопросы применения математических методов для решения логических задач и построения логических схем. Знание логики необходимо при разработке алгоритмов и программ, так как в большинстве языков программирования есть логические операции. Английский математик Джордж Буль (1815 - 1864 г.) создал логическую алгебру, в которой высказывания обозначены буквами. Сочинение Джорджа Буля, в котором подробно исследовалась эта алгебра, было опубликовано в 1854 г. Оно называлось «Исследование законов мысли» («Investigation of the Laws of Thought»). Отсюда ясно, что Буль рассматривал свою алгебру как инструмент изучения законов человеческого мышления, то есть законов логики. Алгебру логики иначе называют алгеброй высказываний. В математической логике суждения называются высказываниями.

№ слайда 6

Описание слайда:

ВЫСКАЗЫВАНИЕ - это повествовательное предложение, о котором можно сказать, что оно истинно или ложно. Например: Земля - планета Солнечной системы. (Истинно) 2+8<5 (Ложно) 5 · 5=25 (Истинно) Всякий квадрат есть параллелограмм (Истинно) Каждый параллелограмм есть квадрат (Ложно) 2 · 2 =5 (Ложно) Не всякое предложение является высказыванием: 1) Восклицательные и вопросительные предложения высказываниями не являются. - “Какого цвета этот дом?” - “Пейте томатный сок!” - “Стоп!” 2) Не являются высказываниями и определения. “Назовем медианой отрезок, соединяющий вершину треугольника с серединой противоположной стороны”. Определения не бывают истинными или ложными, они лишь фиксируют принятое использование терминов.

№ слайда 7

Описание слайда:

3) Не являются высказываниями и предложения типа “Он сероглаз” или “х- 4х + 3=0” - в них не указано о каком человеке идет речь или для какого числа х верно равенство. Такие предложения называются высказывательными формами. Высказывательная форма - это повествовательное предложение, которое прямо или косвенно содержит хотя бы одну переменную и становится высказыванием, когда все переменные замещаются своими значениями. Высказывания могут быть простыми и сложными. Высказывание считается простым, если никакую его часть нельзя рассматривать как отдельное высказывание Некоторые высказывания можно разложить на отдельные части, при этом каждая такая часть будет самостоятельным высказыванием. Например, высказывание “Сегодня в 4 часа дня я был в школе, а к 6 часам вечера пошел на каток” состоит из 2 частей. Высказывание может состоять и из большего количества частей. Высказывание, которое можно разложить на части, будем называть сложным, а неразложимое далее высказывание - простым.

№ слайда 8

Описание слайда:

Сложное высказывание получается путем объединения простых высказываний логическими связками - НЕ, И, ИЛИ. Значение истинности сложных высказываний зависит от истинности входящих в них простых высказываний и объединяющих их связок. Например, даны простые высказывания: На улице идет дождь. На улице светит солнце. На улице пасмурная погода. Составим из них сложные высказывания: На улице идет дождь и на улице светит солнце. На улице светит солнце или на улице пасмурная погода. Неверно что на улице идет дождь.

№ слайда 9

Описание слайда:

В математической логике не рассматривается конкретное содержание высказывания, важно только, истинно оно или ложно. Поэтому высказывание можно представить некоторой переменной величиной, значением которой может быть только 0 или 1. Если высказывание истинно, то его значение равно 1, если ложно - 0. Простые высказывания назвали логическими переменными и для простоты записи их обозначают латинскими буквами: А, В, С… Луна является спутником Земли. А = 1 Москва – столица Германии. В = 0 Сложные высказывания называются логическими функциями. Значения логической функции также может принимать значения только 0 или 1.

№ слайда 10

Описание слайда:

БАЗОВЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ В алгебре высказываний, как и в обычной алгебре, вводится ряд операций. Логические связки И, ИЛИ и НЕ заменяются логическими операциями: конъюнкцией, дизъюнкцией и инверсией. Это основные логические операции, при помощи которых можно записать любую логическую функцию.

№ слайда 11

Описание слайда:

1. Логическая операция ИНВЕРСИЯ (ОТРИЦАНИЕ) соответствует частице НЕ обозначается черточкой над именем переменной или знаком ¬ перед переменной Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна. Таблица истинности инверсии имеет вид: A 0 1 1 0

№ слайда 12

Описание слайда:

2. Логическая операция ДИЗЪЮНКЦИЯ (ЛОГИЧЕСКОЕ СЛОЖЕНИЕ) соответствует союзу ИЛИ обозначается знаком v или + или │ Дизъюнкция двух логических переменных ложна тогда и только тогда, когда оба высказывания ложны. Это определение можно обобщить для любого количества логических переменных, объединенных дизъюнкцией. А v В v С =0, только если А=0, В=0, С=0. Таблица истинности дизъюнкции имеет следующий вид: A B А V В 0 0 0 0 1 1 1 0 1 1 1 1

№ слайда 13

Описание слайда:

3. Логическая операция КОНЪЮНКЦИЯ (ЛОГИЧЕСКОЕ УМНОЖЕНИЕ) соответствует союзу И обозначается знаком & или Λ, или · Конъюнкция двух логических переменных истинна тогда и только тогда, когда оба высказывания истинны. Это определение можно обобщить для любого количества логических переменных, объединенных конъюнкцией. А & В & С=1, только если А=1, В=1, С=1. Таблица истинности конъюнкции имеет следующий вид: A B А & В 0 0 0 0 1 0 1 0 0 1 1 1

№ слайда 14

Описание слайда:

ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ И ТАБЛИЦЫ ИСТИННОСТИ Сложные высказывания можно записывать в виде формул. Для этого простые логические высказывания нужно обозначить как логические переменные буквами и связать их с помощью знаков логических операций. Такие формулы называются логическими выражениями. Например: Чтобы определить значение логического выражения необходимо подставить значения логических переменных в выражение и выполнить логические операции. Операции в логическом выражении выполняются слева направо с учетом скобок в следующем порядке: 1. инверсия; 2. конъюнкция; 3. дизъюнкция; 4. импликация и эквивалентность. Для изменения указанного порядка выполнения логических операций используются круглые скобки.

№ слайда 15

Описание слайда:

Таблицы истинности Для каждого составного высказывания (логического выражения) можно построить таблицу истинности, которая определяет истинность или ложность логического выражения при всех возможных комбинациях исходных значений простых высказываний (логических переменных). При построении таблиц истинности целесообразно руководствоваться определенной последовательностью действий: 1) записать выражение и определить порядок выполнения операций 2) определить количество строк в таблице истинности. Оно равно количеству возможных комбинаций значений логических переменных, входящих в логическое выражение (определяется по формуле Q =2n, где n - количество входных переменных) 3) определить количество столбцов в таблице истинности (= количество логических переменных + количество логических операций) 4) построить таблицу истинности, обозначить столбцы (имена переменных и обозначения логических операций в порядке их выполнения) и внести в таблицу возможные наборы значений исходных логических переменных. 5) заполнить таблицу истинности, выполняя базовые логические операции в необходимой последовательности и в соответствии с их таблицами истинности Теперь мы можем определить значение логической функции для любого набора значений логических переменных.

№ слайда 16

Описание слайда:

Например, построим таблицу истинности для логической функции: 1. Количество входных переменных в заданном выражении равно трем (A,B,C). Значит, количество входных наборов, а значит и строк Q=23=8. 2. Количество столбцов равно 6 (3 переменные + 3 операции). Столбцы таблицы истинности соответствуют значениям исходных выражений A,B,C, промежуточных результатов и (B V C), а также искомого окончательного значения сложного арифметического выражения

№ слайда 17

Описание слайда:

№ слайда 18

Описание слайда:

A B C B V C 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

№ слайда 19

Описание слайда:

Задание. Постройте таблицу истинности для данного логического выражения: A B C B V C 0 0 0 1 0 0 0 0 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 0 1 0

№ слайда 20

Описание слайда:

Равносильные логические выражения. Логические выражения, у которых последние столбцы таблиц истинности совпадают, называются равносильными. Для обозначения равносильных логических выражений используется знак =. Например: А В 0 0 0 1 1 0 0 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 1 1

№ слайда 21

Описание слайда:

ЗАПИСЬ ЛОГИЧЕСКОГО ВЫРАЖЕНИЯ ПО ТАБЛИЦЕ ИСТИННОСТИ Правила построения логического выражения: 1. Для каждой строки таблицы истинности с единичным значением функции построить минтерм. Минтермом называется произведение, в котором каждая переменная встречается только один раз - либо с отрицанием, либо без него. Переменные, имеющие нулевые значения в строке, входят в минтерм с отрицанием, а переменные со значением 1 - без отрицания. 2. Объединить все минтермы операцией дизъюнкция (логическое сложение), что даст стандартную сумму произведений для заданной таблицы истинности.

№ слайда 22

Описание слайда:

Пример. Дана таблица истинности: Для второй строки A=0, B=0, C=1. Эту строку описывает минтерм Для третьей строки A=0, B=1, C=0. Эту строку описывает минтерм Для шестой строки A=1, B=0, C=1. Эту строку описывает минтерм Объединяя термы, получим булево выражение В это выражение вошли термы-произведения для строк с единичным значением функции F, а вся сумма соответствует совокупности из трех строк. Для остальных пяти наборов значений входных переменных это выражение равно нулю. Найдем строки, в которых F=1. Это вторая, третья и шестая. Построим логическое выражение для F. A B C F 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 0

№ слайда 23

Описание слайда:

Логические функции Любое логическое выражение (составное высказывание) можно рассматривать как логическую функцию F(X1,X2, ..., Xn) аргументами которой являются логические переменные X1, X2, ..., Хn (простые высказывания). Сама функция как и аргументы могут принимать только два различных значения: «истина» (1) и «ложь» (0). Выше были рассмотрены функции двух аргументов: логическое умножение F(A,B) = A&B, логическое сложение F(A,B) = AVB, а также логическое отрицание F(A) = ¬А, в котором значение второго аргумента можно считать равным нулю. Каждая логическая функция двух аргументов имеет четыре возможных набора значений аргументов. Может существовать N = 24 = 16 различных логических функций двух аргументов. Таким образом, существует 16 различных логических функций двух аргументов, каждая из которых задается своей таблицей истинности:

№ слайда 24

Описание слайда:

Легко заметить, что здесь логическая функция F2 является функцией логического умножения, F8 - функцией логического сложения, F13 - функцией логического отрицания для аргумента А и F11 - функцией логического отрицания для аргумента В. В обыденной и научной речи кроме базовых логических связок «и», «или», «не» используются и некоторые другие: «если... то...», «... тогда и только тогда, когда...» и др. Некоторые из них имеют свое название и свой символ, и им соответствуют определенные логические функции. Аргументы Логические функции А В F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

№ слайда 25

Описание слайда:

ИМПЛИКАЦИЯ (ЛОГИЧЕСКОЕ СЛЕДОВАНИЕ). Импликация двух высказываний А и В соответствует союзу «ЕСЛИ…ТО». Она обозначается символом → Запись А → В читается как «из А следует В» Импликация двух высказываний истинна всегда, кроме случая, если первое высказывание истинно, а второе ложно. Таблица истинности импликации двух суждений А и В такова: В программировании эту операцию обозначают «IMP». А В А → В 0 0 1 0 1 1 1 0 0 1 1 1

№ слайда 26

Описание слайда:

ЭКВИВАЛЕНТНОСТЬ (ЛОГИЧЕСКОЕ РАВЕНСТВО, ФУНКЦИЯ ТОЖДЕСТВА) Она обозначается символами ≡ или <=>. («тогда и только тогда»). Запись А ≡ В читается как «А эквивалентно В». Эквивалентность двух высказываний истинна только в тех случаях, когда оба высказывания ложны или оба истинны. Таблица истинности эквивалентности двух суждений А и В такова: В программировании эту операцию обозначают «EQV». В алгебре высказываний все логические функции могут быть сведены путём логических преобразований к трём базовым логическим операциям: инверсии, дизъюнкции и конъюнкции А В А ≡ В 0 0 1 0 1 0 1 0 0 1 1 1

№ слайда 27

Описание слайда:

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

№ слайда 28

Описание слайда:

1. Закон тождества. Всякое высказывание тождественно самому себе: Этот закон сформулирован древнегреческим философом Аристотелем. Закон тождества утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует. 2. Закон непротиворечия. Высказывание не может быть одновременно истинным и ложным. Если высказывание А - истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно: Закон непротиворечия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием. “Это яблоко спелое” и “Это яблоко не спелое”

№ слайда 29

Описание слайда:

3. Закон исключенного третьего. Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означает, что результат логического сложения высказывания и его отрицания всегда принимает значение истина: Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно, либо ложно. Третьего не дано. “Сегодня я получу 5 либо не получу”. Истинно либо суждение, либо его отрицание. 4. Закон двойного отрицания. Если дважды отрицать неко­торое высказывание, то в результате мы получим исходное высказывание: Закон двойного отрицания. Отрицать отрицание какого-нибудь высказывания - то же, что утверждать это высказывание. “ Неверно, что 2× 2¹ 4”

№ слайда 30

Описание слайда:

5. Законы идемпотентности. В алгебре логики нет показателей степеней и коэффициентов. Конъюнкция одинаковых «сомножителей» равносильна одному из них: Дизъюнкция одинаковых «слагаемых» равносильна одному: 6. Законы де Моргана: Смысл законов де Моргана (Август де Морган (1806-1871) - шотландский математик и логик) можно выразить в кратких словесных формулировках: отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых; отрицание логического произведения эквивалентно логической сумме отрицаний множителей.

№ слайда 31

Описание слайда:

7. Правило коммутативности. В обычной алгебре слагаемые и множители можно менять местами. В алгебре высказываний можно менять местами логические переменные при операциях логического умножения и логического сложения: Логическое умножение: Логическое сложение: 8. Правило ассоциативности. Если в логическом выраже­нии используются только операция логического умножения или только операция логического сложения, то можно пре­небрегать скобками или произвольно их расставлять: Логическое умножение: Логическое сложение:

№ слайда 32

Описание слайда:

9. Правило дистрибутивности. В отличие от обычной алгеб­ры, где за скобки можно выносить только общие множители, в алгебре высказываний можно выносить за скобки, как общие множители, так и общие слагаемые: Дистрибутивность умножения относительно сложения: Дистрибутивность сложения относительно умножения: 10. 11. 12. Законы поглощения:

№ слайда 33

Описание слайда:

№ слайда 34

Описание слайда:

ЗАДАЧА 1. Разбирается дело Лёнчика, Пончика и Батончика. Кто-то из них нашел и утаил клад. На следствии каждый из них сделал по два заявления. Батончик: «Я не делал этого. Пончик сделал это» Лёнчик: «Пончик не виновен. Батончик сделал это» Пончик: «Я не делал этого. Лёнчик не делал этого» Суд установил, что один из них дважды солгал, другой - дважды сказал правду, третий - один раз солгал, один раз сказал правду. Кто утаил клад? В первом варианте один солгал дважды, а двое сказали правду дважды, что не соответствует условию задачи. В третьем варианте все один раз сказали правду и один раз солгали, что также не соответствует условию задачи. Во втором варианте один дважды солгал, другой дважды сказал правду, а третий один раз сказал правду, а один раз солгал, что соответствует условию задачи. Следовательно клад утаил Пончик. Решение: Введём обозначения: Б –клад утаил Батончик, П - клад утаил Пончик, Л - клад утаил Лёнчик. Рассмотрим три возможных варианта – виноват Батончик, виноват Пончик, виноват Лёнчик. При таких вариантах получаем следующие значения высказываний трёх обвиняемых. Возможные варианты Высказывания Батончика Высказывания Лёнчика Высказывания Пончика Соответствие условию задачи Б Л П ¬Б П ¬П Б ¬П ¬Л 1 0 0 0 0 1 1 1 1 - 0 0 1 1 1 0 0 0 1 + 0 1 0 1 0 1 0 1 0 -

№ слайда 35

Описание слайда:

Задача 2. В школьном первенстве по настольному теннису в четверку лучших вошли девушки: Наташа, Маша, Люда и Рита. Самые горячие болельщики высказали свои предположения о распределении мест в дальнейших состязаниях. Один считает, что первой будет Наташа, а Маша будет второй. Другой болельщик на второе место прочит Люду, а Рита, по его мнению, займет четвертое место. Третий любитель тенниса с ними не согласился. Он считает, что Рита займет третье место, а Наташа будет второй. Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Какое место на чемпионате заняли Наташа, Маша, Люда, Рита? Из анализа таблицы видно, что условию задачи соответствует только последняя строка, значит первое место заняла Наташа, второе – Люда, третье – Рита, а Маша –четвёртое. Решение: Введём обозначения: Н1 – Наташа на 1 месте, М2 – Маша на 2 месте, Л2 – Люда на 2 месте, Р4 – Рита на 4 месте, Р3 – Рита на 3 месте, Н2 – Наташа на 2 месте. Занесём возможные варианты высказываний трёх болельщиков в таблицу с учётом того, что каждый из болельщиков оказался прав только в одном из своих прогнозов: Высказывания 1-ого болельщика Высказывания 2-ого болельщика Высказывания 2-ого болельщика Соответствие условию задачи Н1 М2 Л2 Р4 Р3 Н2 0 1 0 1 0 1 - 0 1 0 1 1 0 - 0 1 1 0 1 0 - 0 1 1 0 0 1 - 1 0 0 1 0 1 - 1 0 0 1 1 0 - 1 0 1 0 0 1 - 1 0 1 0 1 0 +

№ слайда 36

Описание слайда:

Задача 3. Вадим, Сергей и Михаил изучают различные иностранные языки: китайский, японский и арабский. На вопрос, какой язык изучает каждый из них, один ответил: "Вадим изучает китайский, Сергей не изучает китайский, а Михаил не изучает арабский". Впоследствии выяснилось, что в этом ответе только одно утверждение верно, а два других ложны. Какой язык изучает каждый из молодых людей? Проанализируем строки в трёх последних столбцах. Условию задачи соответствует только вторая строка, значит Сергей изучает китайский язык, Михаил – японский (так как он не изучает арабский), тогда Вадим изучает арабский язык. Решение: Введём обозначения: ВК – Вадим изучает китайский язык, СК – Сергей изучает китайский язык, МА - Михаил изучает арабский язык. Занесём в таблицу возможные варианты значений высказываний с учётом условия задачи, что одно из утверждений верно, а два - ложны: Возможные варианты высказываний Соответствие условию задачи ВК ¬ СК ¬ МА ВК СК МА 1 0 0 1 1 1 - 0 0 1 0 1 0 + 0 1 0 0 0 1 -

№ слайда 37

Описание слайда:

Задача 4. Три одноклассника - Влад, Тимур и Юра, встретились спустя 10 лет после окончания школы. Выяснилось, что один из них стал врачом, другой физиком, а третий юристом. Один полюбил туризм, другой бег, страсть третьего - регби. Юра сказал, что на туризм ему не хватает времени, хотя его сестра - единственный врач в семье, заядлый турист. Врач сказал, что он разделяет увлечение коллеги. Забавно, но у двоих из друзей в названиях их профессий и увлечений не встречается ни одна буква их имен. Определите, кто чем любит заниматься в свободное время и у кого какая профессия. Решение: Здесь исходные данные разбиваются на тройки (имя - профессия - увлечение). Из слов Юры ясно, что он не увлекается туризмом и он не врач. Из слов врача следует, что он турист. Буква "а", присутствующая в слове "врач", указывает на то, что Влад тоже не врач, следовательно врач - Тимур. В его имени есть буквы "т" и "р", встречающиеся в слове "туризм", следовательно второй из друзей, в названиях профессии и увлечения которого не встречается ни одна буква его имени - Юра. Юра не юрист и не регбист, так как в его имени содержатся буквы "ю" и "р". Следовательно, окончательно имеем: Ответ. Влад - юрист и регбист, Тимур - врач и турист, Юра - физик и бегун. Имя Юра Профессия врач Увлечение туризм Имя Юра Тимур Влад Профессия физик врач юрист Увлечение бег туризм регби

№ слайда 38

Описание слайда:

Задачи для самостоятельного решения Задача 1. Трое друзей, болельщиков автогонок "Формула-1", спорили о результатах предстоящего этапа гонок. - Вот увидишь, Шумахер не придет первым, - сказал Джон. Первым будет Хилл. - Да нет же, победителем будет, как всегда, Шумахер, - воскликнул Ник. - А об Алези и говорить нечего, ему не быть первым. Питер, к которому обратился Ник, возмутился: - Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину. По завершении этапа гонок оказалось, что каждое из двух предположений двоих друзей подтвердилось, а оба предположения третьего из друзей оказались неверны. Кто выиграл этап гонки? Задача 2. В спортивных соревнованиях принимали участие пять команд: "Вымпел", "Метеор", "Нептун", "Старт" и "Чайка". Об их итогах соревнования имеется пять высказываний: 1) Второе место занял "Вымпел", a "Cтарт" оказался на третьем. 2) Хорошо выступала команда "Нептун", она стала победителем, а "Чайка" вышла на второе место. 3) Да нет же, "Чайка" заняла только третье место, а "Нептун"- был последним. 4) Первое место по праву завоевал "Cтарт", а "Метеор" был 4-м. 5) Да, "Метеор", действительно, был четвертым, а "Вымпел" был 2-м. Известно, что команды не делили места между собой и что в каждом высказывании одно утверждение правильное, а другое нет. Как распределились места между командами? Задача 3 Три дочери писательницы Дорис Кей - Джуди, Айрис и Линда, тоже очень талантливы. Они приобрели известность в разных видах искусств - пении, балете и кино. Все они живут в разных городах, поэтому Дорис часто звонит им в Париж, Рим и Чикаго. Известно, что: Джуди живет не в Париже, а Линда - не в Риме; парижанка не снимается в кино; та, кто живет в Риме, певица; Линда равнодушна к балету. Где живет Айрис, и какова ее профессия?

№ слайда 39

Описание слайда:

№ слайда 40

Описание слайда:

Логические элементы В основе обработки компьютером информации лежит алгебра логики, разработанная Дж. Булем. Знания из области математической логики можно использовать для конструирования различных электронных устройств. Нам известно, что 0 и 1 в логике не просто цифры, а обозначение состояний какого-то предмета нашего мира, условно называемых "ложь" и "истина". Таким предметом, имеющим два фиксированных состояния, может быть электрический ток. Были созданы устройства управления электричеством - электронные схемы, состоящие из набора полупроводниковых элементов. Такие электронные схемы, которые преобразовывают сигналы только двух фиксированных напряжений электрического тока стали называть логическими элементами. Логические элементы - это электронные устройства, которые преобразуют проходящие через них двоичные электрические сигналы по определенному закону. Логические элементы имеют один или несколько входов, на которые подаются электрические сигналы, обозначаемые условно 0, если отсутствует электрический сигнал, и 1, если имеется электрический сигнал. Также логические элементы имеют один выход, с которого снимается преобразованный электрический сигнал. Было доказано, что все электронные схемы компьютера могут быть реализованы с помощью трёх базовых логических элементов И, ИЛИ, НЕ.

№ слайда 41

Описание слайда:

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

№ слайда 42

Описание слайда:

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

№ слайда 43

Описание слайда:

Логический элемент И (конъюнктор) Логический элемент, выполняющий логическое умножение, называется конъюнктор. Он имеет, как минимум, два входа. На функциональных схемах он обозначается: На выходе этого элемента будет сигнал 1 только в том случае, когда на все входы поступает сигнал 1. Когда хотя бы на одном входе будет ноль, на выходе также будет ноль. Другие логические элементы построены из трех простейших базовых элементов и выполняют более сложные логические преобразования информации. вход 1 вход 2 выход 0 0 0 0 1 0 1 0 0 1 1 1

№ слайда 44

Описание слайда:

Рассмотрим еще два логических элемента, которые играют роль базовых при создании более сложных элементов и схем. Логический элемент И-НЕ выполняет логическую функцию штрих Шеффера (И-НЕ), он имеет, как минимум, два входа. На функциональных схемах он обозначается: Логический элемент ИЛИ-НЕ выполняет логическую функцию стрелка Пирса (И-НЕ), он имеет, как минимум, два входа. На функциональных схемах он обозначается: . Логический элемент И-НЕ Логический элемент ИЛИ-НЕ вход 1 вход 2 выход 0 0 1 0 1 0 1 0 0 1 1 0 вход 1 вход 2 выход 0 0 1 0 1 1 1 0 1 1 1 0

№ слайда 45

Описание слайда:

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

№ слайда 46

Описание слайда:

Таблица истинности функциональной схемы Для функциональной схемы можно составить таблицу истинности, то есть таблицу значений сигналов на входах и выходах схемы, по которой можно понять какую функцию выполняет данная схема. Таблица истинности - это табличное представление логической (функциональной) схемы в котором перечислены все возможные сочетания значений входных сигналов вместе со значением выходного сигнала для каждого из этих сочетаний. Составим таблицу истинности для данной логической схемы: Начертим таблицу: количество столбцов = количество входов + количество выходов, количество строк = 2 количество входов. В данной таблице 3 столбца и 4 строки. Заполним первые столбцы всеми возможными вариантами входных сигналов А (вход 1) В (вход 2) С (выход) 0 0 0 1 1 0 1 1

Описание слайда:

Рассмотрим четвёртый вариант входных сигналов: А=1, В=1. Проследим по схеме, как проходят и преобразуются входные сигналы. Результат, полученный на выходе (С=1), запишем в таблицу. В результате получаем таблицу истинности данной логической схемы: Задание. Построить таблицу истинности для данной логической схемы и записать формулу для данной схемы: А (вход 1) В (вход 2) С (выход) 0 0 1 0 1 0 1 0 1 1 1 1

№ слайда 49

Описание слайда:

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

№ слайда 50

Описание слайда:

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

№ слайда 51

Описание слайда:

Задание. Построить логическую схему для заданной таблицы истинности: Запишем логическую функцию по данной таблице истинности: Упростим полученное логическое выражение: Построим логическую схему для данного выражения: А В С F 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1

№ слайда 52

Описание слайда:

Попробуем, действуя по этому плану, сконструировать устройство для сложения двух двоичных чисел (одноразрядный полусумматор). Пусть нам необходимо сложить двоичные числа А и В. Через P и S обозначим первую и вторую цифру суммы: A + B = PS. Вспомните таблицу сложения двоичных чисел. 1. Таблица истинности, определяющая результат сложения, имеет вид: 2. Сконструируем функции P(A,B) и S(A,B) по этой таблице: Преобразуем вторую формулу, пользуясь законами логики: Слагаемые Перенос Сумма А В Р S 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0

Описание слайда:

Одноразрядный двоичный сумматор на три входа и два выхода называется полным одноразрядным сумматором. Логика работы одноразрядного сумматора на три входа или полного сумматора приведена в таблице, где А, В - суммируемые двоичные цифры, Pо - перенос из младшего разряда, S - образующаяся сумма данного разряда и осуществляет перенос P в следующий старший разряд. Полный одноразрядный сумматор. Формула переноса: . Формула для вычисления суммы: Слагаемые Перенос из младшего разряда Сумма Перенос А B P0 S P 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1

№ слайда 55

Описание слайда:

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

№ слайда 56

Описание слайда:

Сумматор - это электронная логическая схема, выполняющая суммирование двоичных чисел поразрядным сложением. Сумматор является центральным узлом арифметико-логического устройства процессора. Находит он применение и в других устройствах компьютера. В реальных электронных схемах сумматор изображается так: Сумматор выполняет сложение многозначных двоичных чисел. Он представляет собой последовательное соединение одноразрядных двоичных сумматоров, каждый из которых осуществляет сложение в одном разряде. Если при этом возникает переполнение разряда, то перенос суммируется с содержимым старшего соседнего разряда. На рисунке показано, как из N сумматоров можно составить устройство для сложения двух N-разрядных двоичных кодов, это схема многоразрядного сумматора.

№ слайда 57

Описание слайда:

ТРИГГЕР Триггер - электронная схема, применяемая для хранения значения одноразрядного двоичного кода. Воздействуя на входы триггера, его переводят в одно из двух возможных состояний (0 или 1). С поступлением сигналов на входы триггера в зависимости от его состояния либо происходит переключение, либо исходное состояние сохраняется. При отсутствии входных сигналов триггер сохраняет свое состояние сколь угодно долго. Термин триггер происходит от английского слова trigger - защёлка, спусковой крючок. Для обозначения этой схемы в английском языке чаще употребляется термин flip-flop, что в переводе означает "хлопанье". Это звукоподражательное название электронной схемы указывает на её способность почти мгновенно переходить ("перебрасываться") из одного электрического состояния в другое. Существуют разные варианты исполнения триггеров в зависимости от элементной базы (И-НЕ, ИЛИ-НЕ) и функциональных связей между сигналами на входах и выходах (RS, JK, T, D и другие). Самый распространённый тип триггера - это RS-триггер (S и R соответственно от английских set - установка, и reset - сброс). Условное обозначение RS-триггера:

№ слайда 58

Описание слайда:

RS-триггер RS-триггер построен на 2-х логических элементах: ИЛИ - НЕ либо И – НЕ. Как, правило, триггер имеет 2 выхода: прямой и инверсный Q и. Как он работает? Пусть на вход элемента №1 подан сигнал 1, а на вход элемента № 3 - 0. На выходе элемента №1 независимо от того, какой второй сигнал поступит на вход, будет 1, т.к. это элемент ИЛИ (по свойствам дизъюнкции). Пройдя через элемент № 2 сигнал примет значение 0 (Q=0). Следовательно, и на втором входе элемента № 3 установится сигнал 0. На выходе элемента №3 - 0. Пройдя через элемент № 4 сигнал изменится на 1. Следовательно, = 1. Убедимся, что данное устройство сохраняет информацию. Запомните, что S=0, R=1, Q=0, =1. В момент прекращения входных сигналов (S=0, R=0) на выходе =1. Это напряжение подается на вход элемента № 1. На выходе элемента №1 сохраняется 1, и на Q - сигнал 0. На входах элемента №3 - 0, следовательно =1. Таким образом, при отсутствии на внешних входах сигналов 1 триггер поддерживает постоянное напряжение на своих выходах. Чтобы изменить напряжение на выходах триггера, надо подать сигнал 1 на вход элемента № 3. Тогда Q=1, =0.

№ слайда 59

Описание слайда:

RS-триггер Вход Выход Режим работы S R Q 0 0 0 0 Хранение 1 0 1 0 Запись 1 0 1 0 1 Запись 0 1 1 Х Х Запрещение ()

№ слайда 60

Описание слайда:

РЕГИСТРЫ РЕГИСТРЫ. Функциональная схема компьютера, состоящая из триггеров, предназначенная для запоминания многоразрядных кодов и выполнения над ними некоторых логических преобразований называется регистром. Упрощенно регистр можно представить как совокупность ячеек, в каждой из которых может быть записано одно из двух значений: 0 или 1, то есть один разряд двоичного числа. С помощью регистров можно выполнять следующие операции: установку, сдвиг, преобразование. Основными типами регистров являются параллельные и последовательные (сдвигающие). Совокупность регистров, используемых ЭВМ для запоминания программы работы, исходных и промежуточных результатов называется оперативной памятью (ОП). Регистры содержатся в различных вычислительных узлах компьютера - процессоре, периферийных устройствах и т.д. Регистр - это устройство, предназначенное для хранения многоразрядного двоичного числового кода, которым можно представлять и адрес, и команду, и данные.

№ слайда 61

Описание слайда:

РЕГИСТРЫ Существует несколько типов регистров, отличающихся видом выполняемых операций. Некоторые важные регистры имеют свои названия, например: сдвиговый регистр - предназначен для выполнения операции сдвига; счетчики - схемы, способные считать поступающие на вход импульсы. К ним относятся Т-триггеры (название от англ. tumble - опрокидываться). Этот триггер имеет один счетный вход и два выхода. Под действием сигналов триггер меняет свое состояние с нулевого на единичное и наоборот. Число перебрасываний соответствует числу поступивших сигналов; счетчик команд - регистр устройства управления процессора (УУ), содержимое которого соответствует адресу очередной выполняемой команды; служит для автоматической выборки программы из последовательных ячеек памяти; регистр команд - регистр УУ для хранения кода команды на период времени, необходимый для ее выполнения. Часть его разрядов используется для хранения кода операции, остальные - для хранения кодов адресов операндов. В ЭВМ применяются регистры 8, 16, 32, 48 и 64 разрядов.

№ слайда 62

Описание слайда:

ШИФРАТОРЫ И ДЕШИФРАТОРЫ Шифратор и дешифратор являются типовыми узлами ЭВМ. Шифратор (кодер) - это логическое устройство, которое преобразует единичный сигнал на одном из входов в n-разрядный двоичный код. Наибольшее применение он находит в устройствах ввода информации (например в клавиатуре), для преобразования десятичных чисел в двоичную систему счисления. Дешифратор (декодер) - это логическое устройство, преобразующее двоичный код, поступающий на его входы, в сигнал только на одном из его выходов. Дешифраторы широко применяются в устройствах управления, в системах цифровой индикации с газоразрядными индикаторами, для построения распределителей импульсов по различным цепям и т.д. Схема используется для перевода двоичных цифр в десятичные. Дешифратор двоичного n-разрядного кода имеет 2n выходов, т.к. каждому из 2n значений входного кода должен соответствовать единичный сигнал на одном из выходов дешифратора.

Чтобы скачать материал, введите свой E-mail, укажите, кто Вы, и нажмите кнопку

ВВЕДЕНИЕ: Мы познакомились с устройством компьютера и узнали, что в процессе обработки двоичной информации процессор выполняет арифметические и логические операции. Поэтому для получения представлений об устройстве компьютера необходимо познакомиться и с основными логическими элементами, лежащими в основе построения компьютера и работающими аналогично переключательным схемам. Для понимания принципа работы таких элементов начнем это знакомство с основных начальных понятий формальной логики. Термин «логика» происходит от древнегреческого logos, означающего «слово, мысль, понятие, рассуждение, закон». ВВЕДЕНИЕ: Мы познакомились с устройством компьютера и узнали, что в процессе обработки двоичной информации процессор выполняет арифметические и логические операции. Поэтому для получения представлений об устройстве компьютера необходимо познакомиться и с основными логическими элементами, лежащими в основе построения компьютера и работающими аналогично переключательным схемам. Для понимания принципа работы таких элементов начнем это знакомство с основных начальных понятий формальной логики. Термин «логика» происходит от древнегреческого logos, означающего «слово, мысль, понятие, рассуждение, закон».переключательным схемам.переключательным схемам. 2

Логика - наука, изучающая законы и формы мышления. Этапы развития логики: I этап - формальная логика. Основатель Аристотель (гг. до н.э.), ввел основные формы абстрактного мышления. II этап - математическая логика. Основатель - немецкий ученый и философ Лейбниц (), предпринял попытку логических вычислений. III этап - математическая логика (булева алгебра). Основатель - английский математик Джордж Буль (), ввел алфавит, орфографию и грамматику для математической логики. 3

Алгебра логики - это математический аппарат с помощью которого записывают (кодируют), упрощают, вычисляют и преобразовывают логические высказывания. Высказывание (суждение) - повествовательное предложение, о котором можно сказать, истинно оно или ложно. Высказывание может принимать только одно из двух логических значений - истинно (1) или ложь (0). Примеры высказывании: Примеры высказывании: Земля - планета Солнечной системы (истинное высказывание). Земля - планета Солнечной системы (истинное высказывание) > 10 (ложное высказывание) > 10 (ложное высказывание). 4 10 (ложное высказывание). 3 + 6 > 10 (ложное высказывание). 4">

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

Объясните, почему следующие предложения не являются высказываниями: Объясните, почему следующие предложения не являются высказываниями: Уходя гасите свет. Уходя гасите свет. Какого цвета этот дом? Какого цвета этот дом? Посмотрите в окно. Посмотрите в окно. 6

Высказывания бывают простые и сложные. Простое высказывание (логическая переменная) Простое высказывание (логическая переменная) содержит только одну простую мысль. Логические переменные обычно обозначаются буквами латинского алфавита: A, В, С, D... содержит только одну простую мысль. Логические переменные обычно обозначаются буквами латинского алфавита: A, В, С, D... Например, А = {Квадрат - это ромб}. Например, А = {Квадрат - это ромб}. Сложное высказывание (логическая функция) Сложное высказывание (логическая функция) содержит несколько простых мыслей, соединенных между собой с помощью логических операций. содержит несколько простых мыслей, соединенных между собой с помощью логических операций. Например, Например, F(A,B) = {Лил дождь, (и) дул холодный ветер}. F(A,B) = {Лил дождь, (и) дул холодный ветер}. А В А В 7

Значение логической функции можно определить с помощью специальной таблицы (таблицы истинности). Таблица истинности - таблица, в которой перечислены все возможные значения входящих логических переменных и соответствующие им значения функции. Например: Значение логической функции можно определить с помощью специальной таблицы (таблицы истинности). Таблица истинности - таблица, в которой перечислены все возможные значения входящих логических переменных и соответствующие им значения функции. Например: А и В логические переменные, n = 2 А и В логические переменные, n = 2 F логическая функция F логическая функция Количество строк (q) в таблице истинности можно вычислить по формуле: Количество строк (q) в таблице истинности можно вычислить по формуле: q = 2 n q = 2 n 8 АВ F (A,B) F (A,B)

Логический элемент (вентиль) – часть электронной логической схемы, которая выполняет элементарную логическую операцию. Каждый логический элемент имеет свое условное обозначение, имеет один или несколько входов, на которые подаются сигналы «высокого» напряжения («1») и «низкого» напряжения («0»), и только один выход. 9

Основные логические операции 1. Отрицание (инверсия), от лат. inversio - переворачиваю: соответствует частице НЕ, словосочетанию НЕВЕРНО, ЧТО; соответствует частице НЕ, словосочетанию НЕВЕРНО, ЧТО; обозначение: не А, ¬А, А обозначение: не А, ¬А, А таблица истинности таблица истинности Инверсия логической переменной Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна, пример: А={На улице идет снег}. A={Неверно, что на улице идет снег} А={На улице не идет снег}; А={На улице не идет снег}; 10 А А01 10

11 2. Логическое сложение (дизъюнкция), от лат. disjunctio - различаю: соответствует союзу ИЛИ; обозначение: +, или, or, V; таблица истинности: Дизъюнкция ложна тогда и только тогда, когда оба высказывания ложны. пример: F={Ha улице светит солнце или дует сильный ветер}; ABF

3. Логическое умножение (конъюнкция), от лат. conjunctio - связываю: соответствует союзу И (в естественном языке: и А, и В как А, так и В А вместе с В А, несмотря на В А, в то время как В); обозначение: х, *, &, и, ^, and; таблица истинности: Конъюнкция истинна тогда и только тогда, когда оба высказывания истинны. пример: F={Ha улице светит солнце и дует сильный ветер}; 12ABF

Другие логические операции 4. Импликация (логическое следование), от лат. implicatio тесно связываю: соответствует речевому обороту ЕСЛИ...ТО соответствует речевому обороту ЕСЛИ...ТО (в естественном языке: если А, то В В, если А В необходимо для А (в естественном языке: если А, то В В, если А В необходимо для А А достаточно для В А достаточно для В А только тогда, когда В А только тогда, когда В В тогда, когда А В тогда, когда А Все А есть В; Все А есть В; обозначение:, => ; обозначение:, => ; 1414 ; обозначение:, => ; 1414">

Таблица истинности: таблица истинности: 1515ABF Импликация истинна всегда, за исключением случая, когда А истинно, а В ложно, пример: Если идет дождь, то земля мокрая. F = A B

5. ЭКВИВАЛЕНТНОСТЬ (равнозначность), от лат. Aequivalens – равноценное. 5. ЭКВИВАЛЕНТНОСТЬ (равнозначность), от лат. Aequivalens – равноценное. coответствует речевым оборотам ЭКВИВАЛЕНТНО: coответствует речевым оборотам ЭКВИВАЛЕНТНО: необходимо и достаточно для тогда и только тогда, когда; необходимо и достаточно для тогда и только тогда, когда; обозначение: =, ; обозначение: =, ; 1616

Таблица истинности: таблица истинности: 1717ABF Эквивалентность истинна тогда и только тогда, когда оба высказывания одновременно либо истинны, либо ложны. пример: Я пойду гулять тогда и только тогда, когда выучу все уроки.

Порядок выполнения логических операций: 1) операция в скобках; 1) операция в скобках; 2) отрицание; 2) отрицание; 3) логическое умножение; 3) логическое умножение; 4) логическое сложение; 4) логическое сложение; 5) импликация; 5) импликация; 6) эквивалентность. 6) эквивалентность. 1818

Задание 1: Даны два высказывания: А={Число 5 - простое} В={Число 4 - нечетное} Очевидно, А=1, В=0. В чем заключаются высказывания: а) А __________________________ б) В __________________________ в) А и В _______________________ г) А + В _______________________ Какие из этих высказываний истинны? Какие из этих высказываний истинны? 19

Задание 3: Запишите на языке алгебры логики следующие высказывания: Задание 3: Запишите на языке алгебры логики следующие высказывания: 1) Я поеду в Киев и если встречу друзей, то мы интересно проведем время. 2) Если я поеду в Киев и встречу там друзей, то мы интересно проведем время. 3) Неверно, что если погода пасмурная, то идет дождь тогда и только тогда, когда нет ветра. 21

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

Порядок построения таблиц истинности по булеву выражению: Порядок построения таблиц истинности по булеву выражению: 1) определить число переменных; 1) определить число переменных; 2) определить число строк в таблице истинности: 2) определить число строк в таблице истинности: q = 2 n q = 2 n 3) записать все возможные значения переменных; 3) записать все возможные значения переменных; 4) определить количество логических операций и их порядок; 4) определить количество логических операций и их порядок; 5) записать логические операции в таблицу 5) записать логические операции в таблицу истинности и определить для каждой значение; истинности и определить для каждой значение; 6) подчеркнуть значения переменных, для которых F = 1. 6) подчеркнуть значения переменных, для которых F = 1. 26

Построим таблицу истинности для заданного сложного логического выражения: Построим таблицу истинности для заданного сложного логического выражения: 27ABC ¬ A B C

28 Подчеркнём значения переменных, для которых F = 1: ABC

Упрощённо можно представить работу компьютера как некоторого устройства, производящего обработку двоичных сигналов, соответствующих 0 и 1. Такую обработку в любом компьютере выполняют так называемые логические элементы, из которых составляются логические схемы, выполняющие различные логические операции. Реализация любых логических операций над двоичными сигналами основана на использовании логических элементов трех типов: И, ИЛИ, НЕ. Повтор см. слайд 9 Упрощённо можно представить работу компьютера как некоторого устройства, производящего обработку двоичных сигналов, соответствующих 0 и 1. Такую обработку в любом компьютере выполняют так называемые логические элементы, из которых составляются логические схемы, выполняющие различные логические операции. Реализация любых логических операций над двоичными сигналами основана на использовании логических элементов трех типов: И, ИЛИ, НЕ. Повтор см. слайд 9Повтор см. слайд 9Повтор см. слайд 9 34

Названия и условные обозначения логических элементов являются стандартными и используются при составлении и описании логических схем компьютеров. Названия и условные обозначения логических элементов являются стандартными и используются при составлении и описании логических схем компьютеров. Логический элемент НЕ (инвертор), Логический элемент НЕ (инвертор), логическая схема: логическая схема: 35 А А

Построение логических схем по булеву выражению: 1) определить число переменных; 1) определить число переменных; 2) определить количество логических операций и их порядок; 2) определить количество логических операций и их порядок; 3) построить для каждой логической операции свою схему (если это возможно); 3) построить для каждой логической операции свою схему (если это возможно); 4) объединить логические схемы в порядке выполнения логических операций. 4) объединить логические схемы в порядке выполнения логических операций. 38

Получение булева выражения по таблице истинности: выбрать значения переменных, для которых значение функции равно 1; выбрать значения переменных, для которых значение функции равно 1; записать логическое умножение всех переменных для каждой строки, где F = 1 (если значение переменной равно 0, то берется ее отрицание); записать логическое умножение всех переменных для каждой строки, где F = 1 (если значение переменной равно 0, то берется ее отрицание); логически сложить полученные выражения; логически сложить полученные выражения; упростить полученное выражение c помощью тождеств и законов алгебры логики. упростить полученное выражение c помощью тождеств и законов алгебры логики. 48

ТОЖДЕСТВА АЛГЕБРЫ ЛОГИКИ. Логического сложения Логического сложения 1) A + 0 = A 2) A + 1 = 1 3) A + A = A 4) A + A = 1 (из двух противоречивых (из двух противоречивых высказываний хотя бы одно истинно) истинно) 5) А = А (двойное отрицание) (двойное отрицание) Логического умножения Логического умножения 1) A 0 = 0 2) A 1 = A 3) A A = A 4) A A = 0 (невозможно, чтобы одновременно два противоположных высказывания были истинны) (невозможно, чтобы одновременно два противоположных высказывания были истинны) 49 Распределительный закон: Распределительный закон: (A + B) C = A C + B C (A + B) C = A C + B C

Составить булевы выражения по таблицe истинности: Задание 1: Составить булевы выражения по таблицe истинности: Задание 1: 50ABCF

Составить булевы выражения по таблицe истинности: Задание 2: (самостоятельно) Составить булевы выражения по таблицe истинности: Задание 2: (самостоятельно) 51ABCF

Законы алгебры логики. Переместительный закон (коммутативности) Переместительный закон (коммутативности) 1) A + B = B + A 2) A B = B 1) A + B = B + A 2) A B = B A Сочетательный закон (ассоциативности) 3) (A + B) + C = A + (B + C) 4) (A B) C = A (B C) Распределительный закон (дистрибутивности) Распределительный закон (дистрибутивности) 5) (A + B) C = A C + B C 6) A B + C = (A + C) (B + C) Закон де Моргана (закон отрицания) Закон де Моргана (закон отрицания) 7) A + B = A B 8) A B = A + B 7) A + B = A B 8) A B = A + B 9) A B = B A = A + B 9) A B = B A = A + B 10) A B = A B + A B = (A + B) (A + B) 10) A B = A B + A B = (A + B) (A + B) 53

Домашнее задание: учебник Угринович (10-11 кл): учебник Угринович (10-11 кл): § 3.5. § 3.5. задания 3.5, 3.6. задания 3.5, 3.6. подготовиться к самостоятельной работе (упрощение логических функций, доказательство формул с помощью таблиц истинности). подготовиться к самостоятельной работе (упрощение логических функций, доказательство формул с помощью таблиц истинности). Дополнит_материалы: Интернет-версия издания: Шауцукова Л.З. Информатика

Физически каждый логический элемент представляет собой электронную схему, в которой на вход подаются некоторые сигналы, кодирующие 0 либо 1, а с выхода снимается также сигнал, соответствующий 0 или 1 в зависимости от типа логического элемента. В компьютерах и других автоматических устройствах широко применяются электрические схемы, содержащие сотни и тысячи переключательных элементов: реле, выключателей и т.п. Разработка таких схем весьма трудоёмкое дело. Оказалось, что здесь с успехом может быть использован аппарат алгебры логики. Физически каждый логический элемент представляет собой электронную схему, в которой на вход подаются некоторые сигналы, кодирующие 0 либо 1, а с выхода снимается также сигнал, соответствующий 0 или 1 в зависимости от типа логического элемента. В компьютерах и других автоматических устройствах широко применяются электрические схемы, содержащие сотни и тысячи переключательных элементов: реле, выключателей и т.п. Разработка таких схем весьма трудоёмкое дело. Оказалось, что здесь с успехом может быть использован аппарат алгебры логики. 61

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

Сумматор это электронная логическая схема, выполняющая суммирование двоичных чисел. При суммировании по правилам двоичной арифметики двух единиц результат равен 10 и происходит перенос 1 в старший двоичный разряд. Многоразрядный сумматор строится как логический схема на основе одноразрядных двоичных сумматоров. 63

Простейший одноразрядный двоичный сумматор (полусумматор). Такой сумматор принимает на входы младший разряд двоичных чисел А и В, складывает их, выдает значение (разряд) суммы S и переноса Р. Логика работы сумматора: 64 ABSP

Одноразрядный двоичный сумматор. При сложении чисел А и В в каждом разряде приходится иметь дело с тремя цифрами: цифрой аi первого слагаемого; цифрой bi второго слагаемого; переносом pi-1 из младшего разряда. В результате сложения получаем цифру суммы Si, и цифру «переноса» из данного разряда в следующий (старший) разряд pi+1. 67

Одноразрядный двоичный сумматор – устройство с тремя входами и двумя выходами, работа которого может быть описана следующей таблицей истинности: Одноразрядный двоичный сумматор – устройство с тремя входами и двумя выходами, работа которого может быть описана следующей таблицей истинности: 68 ВходыВыходы aiaiaiai bibibibi P i-1 sisisisi P i

ТРИГГЕР. Триггер (trigger защелка, спусковой крючок) устройство памяти компьютера для хранения одного бита информации. Триггер может находиться в одном из двух устойчивых состояний, которые соответствуют логической «1» и логическому «0». Триггер способен почти мгновенно переходить («перебрасываться») из одного электрического состояния в другое и наоборот. ТРИГГЕР. Триггер (trigger защелка, спусковой крючок) устройство памяти компьютера для хранения одного бита информации. Триггер может находиться в одном из двух устойчивых состояний, которые соответствуют логической «1» и логическому «0». Триггер способен почти мгновенно переходить («перебрасываться») из одного электрического состояния в другое и наоборот. 70

Самый распространенный триггер SR-триггер (S и R - от английских слов set установка, reset сброс). Условное обозначение SR-триггера: Он имеет два входа: S и R, два выхода: Q и Q. На каждый из двух входов подаются входные сигналы в виде кратковременных импульсов («1»), отсутствие импульса - «0». За единичное состояние триггера принято Q = Т Регистр - представляет собой электронный узел, предназначенный для хранения многоразрядного двоичного числового кода. Этот код может быть числовым кодом команды, выполняемой процессором, либо кодом некоторого числа (данного), которое используется при выполнении данной команды. Упрощенно можно представить регистр как совокупность ячеек, в каждой из которых может быть записано одно из двух значений: 0 или 1, то есть один разряд двоичного числа. Для хранения в регистре одного байта информации необходимо 8 ячеек - триггеров. Число триггеров в регистре называется разрядностью компьютера, которая может быть равна 8,16,32 и

Основные виды регистров: 75 Регистры памяти. Оперативная память компьютера конструируется в виде набора регистров памяти, которые служат только для хранения информации. Один регистр образует одну ячейку памяти, которая имеет свой адрес. Если в регистр входит N триггеров, то можно запомнить N бит информации. Современные микросхемы памяти содержат миллионы триггеров.

Счётчик команд – регистр устройства управления (УУ) процессора, хранит адрес выполняемой в данный момент команды, по которому она находится в оперативной памяти. После выполнения данной команды УУ увеличивает значение этого регистра на единицу, т.е. вычисляет адрес в оперативной памяти, по которому расположена следующая команда. Регистр команд - регистр УУ, служит для вычисления адреса ячейки, где хранятся данные, требуемые выполняемой в данный момент программе. Регистр флагов – регистр УУ, хранит информацию о последней команде, выполненной процессором. 76

Задание: Сколько триггеров необходимо для хранения информации объёмом: 92 1 байт _________________________ 1 байт _________________________ 1 Кбайт _________________________ 1 Кбайт _________________________ 1 Мбайт _________________________ 1 Мбайт _________________________ 64 Мбайт ________________________ 64 Мбайт ________________________ 77

Домашнее задание: Учебник Угринович: § 3.7 (стр). Учебник Угринович: § 3.7 (стр). Задание Задание Подготовка к ЕГЭ: Подготовка к ЕГЭ: 78 ТЕСТ - СБОРКА (ЛОГИКА) ТЕСТ - СБОРКА (ЛОГИКА) Трениров_задания 2010 Трениров_задания 2010Трениров_задания 2010Трениров_задания 2010

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

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

Полусумматор двоичных чисел Это устройство для сложения двух двоичных чисел. Оно должно давать на выходе следующие сигналы: = = = = 10 Обозначим слагаемые X и Y, результаты P и S, получим таблицу истинности: X(слаг)Y(слаг)P(перенос)S(сумма)

Сумматор двоичных чисел В целях максимального упрощения работы компьютера все многообразие математических операций в процессоре сводится к сложению двоичных чисел. Главной частью процессора является сумматор, который обеспечивает такое сложение. Полный одноразрядный сумматор должен иметь три входа: X, Y – слагаемые и P 0 – перенос из младшего разряда и два выхода: сумма S и перенос P.

Таблица сложения Слагаемые Перенос из младшего разряда Перенос Сумма XYP0P0 PS

Из таблицы видно, что перенос P принимает значение 1 только тогда, когда хотя бы две логические переменные одновременно принимают значения 1, т.е. перенос реализуется путем последовательного сложения результатов попарного логического умножения входных переменных (X, Y, P 0). Формула переноса имеет вид: P = (X&Y) (X&P 0) (Y&P 0) Логическое выражение для получения суммы в полном сумматоре имеет вид: S = (X Y P 0)& ¬P 0 (X&Y&P 0) Многоразрядный сумматор процессора состоит из полных одноразрядных сумматоров. На каждый разряд ставится одноразрядный сумматор, причем выход (перенос) младшего разряда подключен к выходу сумматора старшего разряда.

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

Схема триггера В обычном состоянии на входы триггера подан сигнал «0», и триггер хранит сигнал «0». Для записи «1» на вход S (установочный) подается сигнал «1». По схеме видно, что триггер переходит в это состояние и будет устойчиво находиться в нем и после того, как сигнал на входе S исчезнет. Триггер запомнил «1», т.е.с выхода триггера можно считать «1». Для того, чтобы сбросить информацию и подготовиться к приему новой, подается сигнал «1» на вход R (сброс), после чего триггер возвратится к исходному «нулевому» состоянию. ИЛИ НЕ S (1) RQ