1 из 20 1 Основы логики и логические основы компьютера

2 из 20 2 Логика Логика – это наука о формах и способах мышления Законы логики отражают в сознании человека свойства, связи и отношения объектов окружающего мира Логика позволяет строить формальные модели окружающего мира, отвлекаясь от содержательной стороны

3 из 20 3 Формы мышления Понятие Понятие – это форма мышления, фиксирующая основные, существенные признаки предмета Компьютер Множество электронных устройств

4 из 20 4 Формы мышления Понятие Содержание Содержание понятия составляет совокупность существенных признаков объекта Компьютер Универсальное устройство для автоматической обработки информации

5 из 20 5 Формы мышления Понятие Содержание Объем понятия определяется совокупностью предметов, на которое оно распространяется Компьютер Объем

6 из 20 6 Формы мышления Понятие Высказывание 2 х 2 =4 - математический язык Дважды два равно пять – естественный язык - Истинно - Ложно Высказывание – это форма мышления, в которой что-либо утверждается или отрицается о реальных предметах, их свойствах и отношениях между ними. Высказывание может быть либо истинным, либо ложным Алгебра высказываний определяет истинность или ложность составных высказываний

7 из 20 7 Формы мышления Понятие Высказывание Все углы треугольника равны Треугольник равносторонний Умозаключение – это форма мышления, с помощью которой из одного или нескольких суждений (посылок) может быть получено новое суждение (вывод) Умозаключение

8 из 20 8 Алгебра высказываний Алгебра высказываний служит для определения истинности или ложности составных высказываний, не вникая в их содержание Высказывания обозначаются именами логических переменных Логические переменные могут принимать значение: 1 – истина 0 – ложь

9 из 20 9 Логическое умножение (конъюнкция) Объединение двух или более высказываний в одно при помощи союза «И» называется операцией логического умножения или конъюнкцией Логическая конъюнкция выражается знаками &, ^, * Составное высказывание, образованное в результате операции конъюнкции истинно только тогда, когда истинны входящие в него простые высказывания

10 из Логическое умножение (конъюнкция) Пример A.На улице идет дождь B.На улице светит солнце C.Стоит теплая погода D.Стоит холодная погода E.На улице идет дождь и стоит холодная погода Е = A & D F.На улице светит солнце и стоит теплая погода F = B & C G.На улице идет дождь и стоит теплая погода G = A & C H.На улице светит солнце и стоит холодная погода H = B & D

11 из Логическое умножение (конъюнкция) Таблица истинности операции конъюнкция АВF=A&B Диаграмма Эйлера - Венна АВ (пересечение множеств)

12 из Логическое сложение (дизъюнкция) Объединение двух или более высказываний в одно при помощи союза «ИЛИ» называется операцией логического сложения или дизъюнкцией Логическая дизъюнкция выражается знаками, + Составное высказывание, образованное в результате операции дизъюнкции истинно тогда, когда истинно хотя бы одно из входящих в него простых высказываний

13 из Логическое сложение (дизъюнкция) Пример A.2 х 2 = 4 B.3 х 3 = 9 C.2 х 2 = 5 D.4 х 4 = 4 E.3 х 3 = 6 F.2 х 2 = 4 или 4 х 4 = 4 F = A D G.3 х 3 = 9 или 2 х 2 = 5 G = B C H.2 х 2 = 4 или 2 х 2 = 5 H = A C I.2 х 2 = 5 или 3 х 3 = 6 I = С Е

14 из Логическое сложение (дизъюнкция) Таблица истинности операции конъюнкция АВ F=A B Диаграмма Эйлера - Венна АВ (объединение множеств)

15 из Логическое отрицание (инверсия) Присоединение частицы «не» к высказыванию называется операцией логического отрицания или инверсией Логическая дизъюнкция выражается знаками, т. е. : Ā Логическое отрицание (инверсия) делает истинное высказывание ложным и, наоборот, ложное - истинным

16 из Логическое отрицание (инверсия) Пример A.2 х 2 = 5 - ложь Ā. 2 х 2 = 5 - истинно A.2 х 2 = 4 - истинно Ā. 2 х 2 = 4 - ложь A.2 х 2 = 4 - истинно

17 из Логическое отрицание (инверсия) Таблица истинности операции конъюнкция А F = Ā Диаграмма Эйлера - Венна А (дополнение до универсального множества) Ā

18 из Логические выражения и таблицы истинности Логическое выражение – это составное высказывание, которое можно выразить в виде формулы, в которую войдут логические переменные, обозначающие высказывания, и знаки логических операций, обозначающие логические функции. Пример А = «2 х 2=5» - ложно (0) В = «2 х 2=4» - истинно (1) F = A или В и не А или не В

19 из Логические выражения и таблицы истинности Для каждого составного высказывания можно построить таблицу истинности, которая определяет истинность или ложность при всех возможных комбинациях исходных значений простых высказываний (логических переменных) Количество строк в таблице истинности зависит от количества логических переменных (N): Количество строк = 2 N

20 из Логические выражения и таблицы истинности Логические выражения, у которых таблицы истинности совпадают, называются равносильными Задание 1 1. Составить таблицу истинности выражения ¯А& ¯В 2. Составить таблицу истинности выражения ¯(А В) Задание 2 1. Составить таблицу истинности выражения ¯А ¯В 2. Составить таблицу истинности выражения ¯(А & В)

21 из Логические функции Любое составное высказывание можно рассматривать как логическую функцию F(X 1, X 2, …, X N ), аргументами которой являются логические переменные X 1, X 2, …, X N простые высказывания. Функция и аргументы могут принимать только два различных значения «истинно» (1) и «ложь» (0).

22 из Логические функции Рассмотрим произвольную логическую функцию двух аргументов. Для построения таблицы истинности логической функции: 1. Определяем количество строк в таблице истинности: N 1 =2 2 N 1 = 4, т. е. в таблице истинности 4 строки. 2. Определяем количество столбцов в таблице истинности: N 2 =2 N 1, N 2 =2 4, N 2 = 16, т. е. в таблице истинности 16 столбцов. Вывод: существует 16 различных логических функций двух аргументов, каждая из которых задается своей таблицей истинности.

23 из Логические функции Таблица истинности логических функций двух аргументов Аргуме нты Логические функции АВF1F1 F2F2 F3F3 F4F4 F5F5 F6F6 F7F7 F8F8 F9F9 F 10 F 11 F 12 F 13 F 14 F 15 F F 2 – функция логического умножения 2. F 8 – функция логического сложения 3. F 11 – функция логического отрицания для В 4. F 13 – функция логического отрицания для А

24 из Логические функции Логическое следование Логическое следование (импликация) образуется соединением двух высказываний в одно с помощью оборота «если …, то …». 1. Составное высказывание, образованное с помощью операции логического следования (импликации) ложно тогда и только тогда, когда из истинной предпосылки (первого высказывания) следует ложный вывод (второе высказывание) 2. Логическая операция импликации («если А, то В») обозначается при помощи, т. е. А В

25 из Логические функции Логическое следование 3. Таблица истинности логической операции импликации («если А, то В») выражается при помощи функции F 14 А В АВ F 14 = А В Особенность: из ложной предпосылки может следовать что угодно. 5.Задание: Доказать равносильность высказываний А В и ¯А В

26 из Логические функции Логическое равенство Логическое равенство (эквивалентность) образуется соединением двух высказываний в одно с помощью оборота «…тогда и только тогда, когда …». 1. Составное высказывание, образованное с помощью логической операции эквивалентности истинно тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны. 2. Логическая операция эквивалентности обозначается при помощи, т. е. А В

27 из Логические функции Логическое равенство 3. Таблица истинности логической операции эквивалентности выражается при помощи функции F 10 А В АВ F 10 = А В Задание: Какое из данных высказываний равносильно высказыванию А В: 1) (¯А & ¯ В) ¯ (A & B) 2) (A ¯ В) & (¯А В)

28 из Логические законы и правила преобразования 1. Закон тождества Всякое высказывание тождественно самому себе А = А 2. Закон непротиворечия Высказывание не может быть одновременно истинным и ложным. Если высказывание А – истинно, то его отрицание ¯А - ложно. Значит, логическое произведение высказывания и его отрицания ложно: А & ¯А = 0

29 из Логические законы и правила преобразования 3. Закон исключенного третьего Высказывание не может быть одновременно истинным и ложным. Если высказывание А – истинно, то его отрицание ¯А - ложно. Значит, логическое сложение высказывания и его отрицания истинно: А ¯А = 1 4. Закон двойного отрицания Если дважды отрицать двойное высказывание, в результате получим само высказывание: ¯ ¯ А = А

30 из Логические законы и правила преобразования 5. Законы Моргана:¯(А В) = ¯А& ¯В ¯(А & В) = ¯А ¯В 6. Правило коммутативности:А В = В А А & В = В & А 7. Правило ассоциативности:(А В) С = А (В С) (А & В) & С = А & (В & С) 8. Правило дистрибутивности:a * b + a * c = a * ( b + c) (А & В) ( A & С) = А & (В С) (А В) & ( A С) = А (В & С)

31 из Логические законы и правила преобразования 9. Закон идемпотентности:А А = А А & А = А 10. Законы исключения констант: А 1 = 1 А 0 = А А & 0 = 0 А & 1 = А 11. Закон контрапозиции (правило перевертывания): А В = В А 12. Закон поглощения:А ( А & В) = А А & ( А В) = А 13. Закон исключения (склеивания):(А В) & (¯ А В) = В (А & В) (¯ А & В) = В

32 из Задания Упростить логические выражения: 1.(А & В) ( А & ¯ B) 2.(А ¯ A) & B 3. A & ( A B) & ( C ¯ B) 4. A & ¯ B B & C ¯ A & ¯ B 5. A ¯ A & B

33 из Решение логических задач Для решения логических задач их необходимо формализовать, т. е. записать на языке алгебры высказываний. Полученные логические выражения необходимо упростить и проанализировать, для чего – построить таблицу истинности высказывания. Пример В каждой из двух аудиторий может находиться либо кабинет информатики, либо кабинет физики. На аудиториях повесили таблички. На первой – «По крайней мере, в одной из этих аудиторий размещается кабинет информатики». На второй – «Кабинет физики находится в другой аудитории». Известно, что надписи на табличках либо обе истинны, либо обе ложны. Где находится кабинет информатики?

34 из Решение логических задач Пусть А – «В первой аудитории находится кабинет информатики» В – «Во второй аудитории находится кабинет информатики» Тогда ¯ А – «В первой аудитории находится кабинет физики» ¯ В – «Во второй аудитории находится кабинет физики» Высказывание, содержащееся на табличке на первой аудитории: Х = А В Высказывание, содержащееся на табличке на второй аудитории: Y = ¯ А

35 из Решение логических задач Утверждение, что надписи на табличках либо одновременно истинны, либо ложны, в соответствии с законом исключающего третьего: (X & Y) ( ¯ X & ¯ Y ) = 1 Подставим вместо X и Y соответствующие значения. Тогда, (X & Y) ( ¯ X & ¯ Y ) = (( А В) & ¯ А ) ¯ ( А В) & ¯ ¯ A = = ( А & ¯ А В & ¯ А ) ( ¯ А & ¯ В & А) = = ( 0 В & ¯ А ) ( 0 & ¯ В ) = ( 0 В & ¯ А ) 0 = В & ¯ А

36 из Решение логических задач Строим таблицу истинности высказывания В & ¯ А : АВ¯ А F=В & ¯ А Следовательно: Во второй аудитории – кабинет информатики, В первой аудитории – кабинет физики

37 из Решение логических задач Задача В процессе составления расписания уроков учителя высказали свои пожелания, Учитель математики хочет иметь первый или второй урок, учитель физики – второй или третий уроки. Сколько существует возможных вариантов расписания и какие они?

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

39 из Логические основы устройства компьютера И А (0, 0, 1, 1) В (0, 1, 0, 1) F 2 (0, 0, 0, 1) ИЛИ А (0, 0, 1, 1) В (0, 1, 0, 1) F 8 (0, 1, 1, 1) НЕ А (0, 1) F 13 (1, 0) Конъюнктор Дизъюнктор Инвертор

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

41 из Логические основы устройства компьютера Полусумматор При сложении двоичных чисел образуется сумма в данном разряде, при этом возможен перенос в старший разряд. Обозначим: А и В – слагаемые, Р – перенос, S – сумма Составим таблицу сложения одноразрядных двоичных чисел. Слагаемые Перенос Сумма АВРS

42 из Логические основы устройства компьютера Перенос Р можно реализовать с помощью операции логического умножения: Р = А & B Составим формулу для вычисления суммы. S = ( А В ) & ¯ ( А & B ) Задание Построить таблицу истинности для данного высказывания.

43 из Логические основы устройства компьютера Построим из базовых логических элементов схему полусумматора. Р = А & B Для реализации переноса используем логический элемент «И». И А (0, 0, 1, 1) В (0, 1, 0, 1) P (0, 0, 0, 1) Устройства компьютера (сумматоры в процессоры, ячейки памяти в оперативной памяти) строятся на основе базовых логических элементов.

44 из Логические основы устройства компьютера S = ( А В ) & ¯ ( А & B ) Проанализируем полученную формулу суммы. На выходе должен стоять логический элемент «И», который имеет два входа. Один вход – результат логического сложения А В, который реализуется элементом «ИЛИ», второй – результат инвертированного логического умножения исходных сигналов ¯ ( А & B ). И А В ИЛИ НЕ И А & B ¯ ( А & B ) ( А В ) ( А В ) & ¯ ( А & B ) Данная схема называется полусумматором, т. к. реализует суммирование двоихных чисел без учета переноса из младшего разряда

45 из Логические основы устройства компьютера Одноразрядный сумматор Полный одноразрядный сумматор должен иметь три входа: А, В – слагаемые, Р 0 – перенос из младшего разряда два выхода: сумма S и перенос P Задание Построить таблицу истинности для реализации сложения.

46 из Логические основы устройства компьютера Одноразрядный сумматор Таблица истинности для реализации сложения выглядит следующим образом: Слагаемые Перенос из младшего разряда Перенос Сумма АВP0P0 РS

47 из Логические основы устройства компьютера Одноразрядный сумматор P реализуется путем логического сложения результатов попарного логического умножения входных данных: Р = ( А & В ) ( А & Р 0 ) ( В & Р 0 ) S реализуется путем логического умножения инвертированного переноса ¯ Р на результат логического сложения входных данных: S = ( А В Р 0 ) & ¯ Р S дает правильное значение во всех случаях, кроме случая, когда все входные переменные принимают значение 1. Сложим S с результатом логического умножения входных переменных: S = ( А В Р 0 ) & ¯ Р 0 ( А & В & Р 0 )

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

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

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

51 из Логические основы устройства компьютера Вопросы 1. Какой сигнал будет на выходе логического элемента «И», если на вход будут поданы сигналы А=0, В=1? 2. Какой сигнал будет на выходе логического элемента «ИЛИ», если на вход будут поданы сигналы А=0, В=1? 3. Какой сигнал будет на выходе логического элемента «НЕ», если на вход будут поданы сигналы А=0; А=1? 4. Для чего необходим сумматор? 5. Чем отличается полный сумматор от полусумматора? 6. Как устроен полноразрядный сумматор? 7. Для чего необходим и где используется триггер?

52 из Логические основы устройства компьютера Задания 3 1. По заданной логической функции F(A,B) = (B & ¯ A) ( ¯ B & A) построить логическую схему. 2. Построить таблицу истинности, описывающую состояние входов и выходов RS - триггера 3. Какое количество базовых логических элементов необходимо для реализации 64-разрядного сумматора? 4. Какое количество базовых логических элементов образуют оперативную память современного ПК объемом 64 Мбайта?

53 из Логические основы устройства компьютера Задания 4 Упростить выражения: ¯ ( А & B ) ¯ ( А & C ) ¯ ( B & C ) (A & ¯ ( B C )) (A ¯ ( B & C )) ¯ ( ¯ B & ¯ C ) ¯ ( ¯ A & ¯ C ) ¯ ( ¯ A & ¯ B ) (А ( А & В)) & ( А & ( А В)) ( (А В) & (¯ А В) ) ( (А & В) (¯ А & В) ) ¯ ( (А В) & (¯ А В) ) & ¯ ( ¯ A & ¯ B )

54 из Логические основы устройства компьютера Задания 5 Решить логические задачи: 1. Джеку, Питеру и Майклу предъявлено обвинение в соучастии в ограблении банка. Похитители скрылись на поджидавшем их автомобиле. На следствии Джек показал, что преступники скрылись на синем Мерседесе, Питер сказал, что это был черный Джип, а Майкл утверждал, что это был Форд Мустанг и ни в коем случае не синий. Стало известно, что, желая запутать следствие, каждый из них указал правильно либо марку машины, либо только ее цвет. Какого цвета и какой марки была машина?

55 из Логические основы устройства компьютера Задания 5 Решить логические задачи: 2. По телевизору синоптик объявляет прогноз погоды на завтра и утверждает следующее: Если не будет ветра, то будет пасмурная погода без дождя Если будет дождь, то будет пасмурно и без ветра. Если будет пасмурная погода, то будет дождь и не будет ветра. Какая будет погода?

56 из Логические основы устройства компьютера Задания 5 Построить логическую схему по данному выражению и найти его значение при указанных параметрах: ¯ ( А & B ) ¯ ( B & ¯ C ), при А=0, В=1, С=0 ¯ ( ¯ B & ¯ C ) ¯ ( ¯ A & ¯ C ),при А=1, В=1, С=1 (А ( А & В)) & ( А & ( А В)), при А=1, В=1 ( (А В) & (¯ А В) ) ( (А & В) (¯ А & В) ), при А=1, В=0, С=1