Тема 9. Логические основы компьютеров Информатика Институт информатики, инноваций и бизнес-систем Кафедра информатики, инженерной и компьютерной графики Черкасова Евгения Анатольевна

1.Логические выражения и операции 2.Преобразование логических выражений 3.Логические элементы компьютера Логические основы компьютеров

1 Логические выражения и операции

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

Логические высказывания Логическое высказывание – это повествовательное предложение, относительно которого можно однозначно сказать, истинно оно или ложно. Высказывание или нет? Сейчас идет дождь. Жирафы летят на север. История – интересный предмет. У квадрата – 10 сторон и все разные. Красиво! В городе N живут 2 миллиона человек. Который час?

Обозначение высказываний A – Сейчас идет дождь. B – Форточка открыта. простые высказывания (элементарные) Составные высказывания строятся из простых с помощью логических связок (операций) "и", "или", "не", "если … то", "тогда и только тогда" и др. Любое высказывание может быть ложно (0) или истинно (1). ! A и B A или не B если A, то B не A и B A тогда и только тогда, когда B Сейчас идет дождь и открыта форточка. Сейчас идет дождь или форточка закрыта. Если сейчас идет дождь, то форточка открыта. Сейчас нет дождя и форточка открыта. Дождь идет тогда и только тогда, когда открыта форточка.

Операция НЕ (инверсия) Если высказывание A истинно, то "не А" ложно, и наоборот. Ане А таблица истинности операции НЕ также:, not A (Паскаль), ! A (Си) Таблица истинности логического выражения Х – это таблица, где в левой части записываются все возможные комбинации значений исходных данных, а в правой – значение выражения Х для каждой комбинации.

Операция И (логическое умножение, конъюнкция) ABА и B 1 0 также: A·B, A B, A and B (Паскаль), A && B (Си) конъюнкция – от лат. conjunctio соединение A B Высказывание "A и B" истинно тогда и только тогда, когда А и B истинны одновременно.

Операция ИЛИ (логическое сложение, дизъюнкция) ABА или B 1 0 также: A+B, A B, A or B (Паскаль), A || B (Си) дизъюнкция – от лат. disjunctio разъединение Высказывание "A или B" истинно тогда, когда истинно А или B, или оба вместе.

Операция "исключающее ИЛИ" Высказывание "A B" истинно тогда, когда истинно А или B, но не оба одновременно. AB А B 0 0 также: A xor B (Паскаль), A ^ B (Си)

A A = (A B) B = Свойства операции "исключающее ИЛИ" A 0 = A 1 = A 0 ? AB А B A

Импликация ("если …, то …") Высказывание "A B" истинно, если не исключено, что из А следует B. A – "Работник хорошо работает". B – "У работника хорошая зарплата". ABА B

Эквиваленция ("тогда и только тогда, …") Высказывание "A B" истинно тогда и только тогда, когда А и B равны. ABА B

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

Логические формулы Система имеет три датчика и может работать, если два из них исправны. A – "Датчик 1 неисправен". B – "Датчик 2 неисправен". C – "Датчик 3 неисправен". Аварийный сигнал: X – "Неисправны два датчика". X – "Неисправны датчики 1 и 2" или "Неисправны датчики 1 и 3" или "Неисправны датчики 2 и 3". логическая формула

Составление таблиц истинности ABA·BA·BX Логические выражения могут быть: тождественно истинными (всегда 1, тавтология) тождественно ложными (всегда 0, противоречие) вычислимыми (зависят от исходных данных)

Составление таблиц истинности ABCABACBCX

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

Законы алгебры логики названиедля Идля ИЛИ двойного отрицания исключения третьего операции с константами повторения поглощения переместительный сочетательный распределительный правила де Моргана

Упрощение логических выражений Шаг 1. Заменить операции на их выражения через И, ИЛИ и НЕ: Шаг 2. Раскрыть инверсию сложных выражений по формулам де Моргана: Шаг 3. Используя законы логики, упрощать выражение, стараясь применять закон исключения третьего.

Упрощение логических выражений раскрыли формула де Моргана распределительный исключения третьего повторения поглощения

3 Логические элементы компьютера

Логические элементы компьютера & 11 & НЕ ИИЛИ ИЛИ-НЕ И-НЕ значок инверсии

Логические элементы компьютера Любое логическое выражение можно реализовать на элементах И-НЕ или ИЛИ-НЕ. & И:И: НЕ: & & ИЛИ: & & &

Составление схем последняя операция - ИЛИ & 1 & & И И

Триггер (англ. trigger – защёлка) Триггер – это логическая схема, способная хранить 1 бит информации (1 или 0). Строится на 2-х элементах ИЛИ-НЕ или на 2-х элементах И-НЕ. 1 1 основной выход вспомогательный выход reset, сброс set, установка обратные связи SRQ режим хранение запрещен сброс установка 1 0 0

Полусумматор Полусумматор – это логическая схема, способная складывать два одноразрядных двоичных числа. Σ сумма перенос ABPS &1&&

Сумматор Сумматор – это логическая схема, способная складывать два одноразрядных двоичных числа с переносом из предыдущего разряда. Σ сумма перенос ABCPS

Многоразрядный сумматор это логическая схема, способная складывать два n-разрядных двоичных числа. перенос Σ Σ Σ

Вопросы Вопрос 1 Как записывается десятичное число 11 в двоичной системе счисления? А) 1111 Б) 1101 В) 1011 Г) 1001 Вопрос 2 Операционная система – это... А) программа, обеспечивающая управление базами данных Б) антивирусная программа В) программа, управляющая работой компьютера Г) система программирования Вопрос 3 Какие пары объектов находятся в отношении "объект - модель"? А) компьютер - данные Б) компьютер - его функциональная схема В) компьютер - программа г) компьютер - алгоритм Вопрос 4 Задан полный путь к файлу C:\DOC\PROBA.TXT Каково расширение файла, определяющее его тип? А) C:\DOC\PROBA.TXT Б) DOC\PROBA.TXT В) PROBA.TXT Г) TXT

31 Использование материалов презентации Использование данной презентации, может осуществляться только при условии соблюдения требований законов РФ об авторском праве и интеллектуальной собственности, а также с учетом требований настоящего Заявления. Презентация является собственностью авторов. Разрешается распечатывать копию любой части презентации для личного некоммерческого использования, однако не допускается распечатывать какую-либо часть презентации с любой иной целью или по каким-либо причинам вносить изменения в любую часть презентации. Использование любой части презентации в другом произведении, как в печатной, электронной, так и иной форме, а также использование любой части презентации в другой презентации посредством ссылки или иным образом допускается только после получения письменного согласия авторов.