Логические основы ЭВМ Логика высказываний

Рассмотрим несколько утверждений Все рыбы умеют плавать Пять – число четное Некоторые медведи бурые Картины Пикассо слишком абстрактны Число х не превосходит единицы Сколько времени? Все рыбы умеют плавать Пять – число четное Некоторые медведи бурые Картины Пикассо слишком абстрактны Число х не превосходит единицы Сколько времени? Только про первые три можно однозначно сказать, правдивы они или нет.

В ы с к а з ы в а н и е – повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно. Высказывание Общее ЧастноеЕдиничное Буква А - гласная Некоторые высказывания ложны Все дороги ведут в Париж

В ы с к а з ы в а н и е – повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно. Простое Сегодня солнечно И идет дождь На улице НЕ идет дождь Сегодня идет дождь ИЛИ солнечно Сегодня солнечно Высказывание Простое Сложное Связки: И, ИЛИ, НЕ и т.д.

А л г е б р а л о г и к и – это раздел математики, изучающий высказывания с точки зрения их логических значений (истинности или ложности) и логических операций над ними. Логическое значение Символьное обозначение ИСТИНА1TRUE ЛОЖЬ0FALSE Простые высказывания – логические переменные Сложные высказывания – логические выражения (функции) Связки (И, ИЛИ, НЕ и др.) – логические операции Логические константы – ИСТИНА, ЛОЖЬ. Создателем алгебры логики является живший в ХIХ в. английский математик Джордж Буль, в честь которого она названа булевой алгеброй высказываний.

Логические операции И н в е р с и я (О т р и ц а н и е) Операция «НЕ» Обозначение: ^А, А ^A истинно, если А ложно, и наоборот Пример: А: Два – четное число; ^A: Два – НЕ четное число. Отрицание - это логическая операция, которая каждому простому высказыванию ставит в соответствие составное высказывание, заключающееся в том, что исходное высказывание отрицается

Логические операции К о н ъ ю н к ц и я (логическое умножение) Операция «И» Обозначение: А & В, А В A & B истинно, только если и А, и В истинны Пример: А: Два – четное число; В: Три – четное число А & B: Два – четное число И Три – четное число. лат. conjunctio соединение Конъюнкция - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны.

Логические операции Д и з ъ ю н к ц и я (логическое сложение) Операция «ИЛИ» Обозначение: А V В, А + В A V B ложно, только если и А, и В ложны Пример: А: Два – четное число; В: Три – четное число А & B: Два – четное число ИЛИ Три – четное число. лат. disjunctio разъединение Дизъюнкция - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны, и истинным, когда хотя бы одно из них истинно.

Таблица истинности основных логических операций Таблица истинности устанавливает соответствие между всеми возможными значениями набора переменных и значениями функций. АВ^AA & BA V B

Логические операции Импликация и Эквиваленция ( «ЕСЛИ А, то В» и «ЕСЛИ И ТОЛЬКО ЕСЛИ А, то В») Если и А, и В истинны, то обе функции будут истинны: из А следует В Если и А, и В ложны, обе функции также истинны - логика не нарушена Если А истинно, а В ложно, логика нарушена, функция ложна Если А ложно, а В истинно, функции ведут себя по-разному: первая будет истинна, а вторая ложна, т.к. в ней условие более строгое АВА –> ВА В Примеры Импликация (А –> В): «ЕСЛИ число делится на 4, ТО оно делится на 2» Эквиваленция (А В): «Число кратно 2 ЕСЛИ И ТОЛЬКО ЕСЛИ оно четное» ЕСЛИ А, ТО В: А В Импликация - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие (первое высказывание) истинно, а следствие (второе высказывание) ложно. ЕСЛИ И ТОЛЬКО ЕСЛИ А, ТО В: А В Эквиваленция - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны либо одновременно ложны.

Пример: Составим таблицу истинности сложной функции Выполнение логических операций: слева направо с учетом скобок Приоритет операций: Отрицание Конъюнкция Дизъюнкция прочие

любую логическую функцию можно представить c помощью набора основных логических операций: И, ИЛИ, НЕ. Импликация: А В = A V B Эквиваленция: АВ = A B V A B Набор основных логических операций: И, ИЛИ, НЕ является функционально полным АВАВAB А –> ВА В

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

Равносильное (тождественное) преобразование логических функций выполняется с целью их упрощения или приведения к определенному виду с помощью основных законов алгебры логики. Основные законы алгебры логики Закон Для ИДля ИЛИ Переместительный Сочетательный Распределительный Правило де Моргана Идемпотенция Поглощение Склеивание Операции с инверсией Операции с константой Двойное отрицание Пример:

Логические элементы ПК Логический элемент компьютера – это часть электронной схемы, которая реализует элементарную логическую функцию Инвертор Конъюнктор Дизъюнктор С помощью этих трех элементов можно реализовать любую логическую схему 1&1 AA A B A B A B A V B Основные логические элементы

Логическая схема для операции «импликация» А В = A V B А В 1 А 1 А V B

Логическая схема для операции «эквиваленция» АВ = A B V A B А В 1 А 1 В & А B & 1 АВ