Презентация по информатике на тему Алгебра логики

Логика – это наука о формах и законах человеческого мышления. Ее основоположник – древнегреческий мыслитель Аристотель (384-322 года до н. э.). Логика Джордж Буль (1815-1864). Создал новую область науки - Алгебру логики (Булеву алгебру или Алгебру высказываний). Вильгельм Лейбниц (1646-1716). Основоположник математической логики (пытался построить первые логические исчисления: арифметические и буквенно-алгебраические). Алгебра логики (булева алгебра) - это раздел математики, изучающий высказывания, и логические операции над ними. Цель алгебры логики - описание поведения и структуры логических схем.Объекты алгебры логики – высказывания. Логическое высказывание – это повествовательное предложение, относительно которого можно однозначно сказать, истинно оно или ложно.Высказывание или нет?Сейчас идет дождь.Жирафы летят на север.История – интересный предмет.У квадрата – 10 сторон и все разные.Красиво!В городе N живут 2 миллиона человек.Который час? Виды высказываний Высказывания Простые Составные Высказывание называется простым, если никакая его часть сама не является высказыванием. Сложные (составные) высказывания строятся из простых с помощью логических связок (и; или; не; если, то; и др). Так, например, из элементарных высказываний "Петров — врач", "Петров — шахматист" при помощи связки "и" можно получить составное высказывание "Петров — врач и шахматист", понимаемое как "Петров — врач, хорошо играющий в шахматы". При помощи связки "или" из этих же высказываний можно получить составное высказывание "Петров — врач или шахматист", понимаемое в алгебре логики как "Петров или врач, или шахматист, или и врач и шахматист одновременно". В алгебре логики высказывания обозначают ЗАГЛАВНЫМИ буквами латинского алфавита и называют логическими переменными. Если высказывание истинно, то значение соответствующей ему логической переменной обозначают единицей (А = 1), а если ложно - нулём (В = 0). 0 и 1 называются логическими значениями. Так, например, предложение " Трава зеленая" следует считать высказыванием, так как оно истинное. Записывается: А=1 Предложение " Лев - птица" тоже высказывание, так как оно ложное. Записывается: В=0 Пусть через А обозначено высказывание "Тимур поедет летом на море", а через В — высказывание "Тимур летом отправится в горы". Тогда составное высказывание   "Тимур летом побывает и на море,  и в горах"   можно кратко записать как     А и ВЗдесь   "и"  — логическая связка, А,   В   — логические переменные, которые могут принимать только два значения - "истина"  или "ложь", обозначаемые, соответственно, "1" и  "0". A – Сейчас идет дождь.B – Форточка открыта. A и B A или не Bесли A, то B не A и BA тогда и только тогда, когда B Сейчас идет дождь и открыта форточка.Сейчас идет дождь или форточка закрыта.Если сейчас идет дождь, то форточка открыта.Сейчас нет дождя и форточка открыта.Дождь идет тогда и только тогда, когда открыта форточка. Составьте из простых высказываний составные при помощи связок: Операция НЕ   Операция, выражаемая словом "не", называется инверсией или отрицанием и обозначается чертой над высказыванием.    Если высказывание A истинно, то "не А" ложно, и наоборот. Высказывание А истинно, когда A ложно, и ложно, когда A истинно. Пример. "Луна — спутник Земли" (А); "Луна — не спутник Земли" (А). А не А 1 0 0 1 таблица истинности операции НЕ Таблица истинности логического выражения F – это таблица, где в левой части записываются все возможные комбинации значений исходных данных, а в правой – значение выражения F для каждой комбинации. Операция И    Операция, выражаемая связкой "и", называется конъюнкцией (лат. conjunctio — соединение) или логическим умножением и обозначается точкой " . " (может также обозначаться знаками ^ или &). Высказывание А · В истинно тогда и только тогда, когда оба высказывания А и В истинны. Например, высказывание   "10 делится на 2 и 5 больше 3"   истинно, а высказывания:  "10 делится на 2 и 5 не больше 3",     "10 не делится на 2 и 5 больше 3",    "10 не делится на 2 и 5 не больше 3"     —   ложны. A B А и B 1 0 также: A·B, A  B, A & B 0 0 0 1 1 0 1 1 0 0 A  B Таблица истинности конъюнкции Операция ИЛИ    Операция, выражаемая связкой "или" называется дизъюнкцией (лат. disjunctio — разделение) или логическим сложением и обозначается знаком v (или + «плюсом»). Высказывание А v В ложно тогда и только тогда, когда оба высказывания А и В ложны. Например, высказывание   "10 не делится на 2 или 5 не больше 3"   ложно,     а высказывания "10 делится на 2 или 5 больше 3",   "10 делится на 2 или 5 не больше 3",   "10 не делится на 2 или 5 больше 3"—   истинны. A B А или B 1 0 также: A+B, A  B 0 0 0 1 1 0 1 1 1 1 Таблица истинности дизъюнкции Базовый набор операций С помощью операций И, ИЛИ и НЕ можно реализовать любую логическую операцию. ИЛИ И НЕ базовый набор операций Сколько всего существует логических операции с двумя переменными? ? Операция ЕСЛИ-ТО   Операция, выражаемая связками   "если ..., то",  "из ... следует",  "... влечет ...",  называется импликацией (лат. implico — тесно связаны) и обозначается знаком . Высказывание   А В ложно тогда и только тогда, когда  А  истинно,  а  В  ложно. A – "Работник хорошо работает". B – "У работника хорошая зарплата". A B А  B 0 0 0 1 1 0 1 1 1 1 1 0 Таблица истинности импликации Операция РАВНОСИЛЬНО   Операция, выражаемая связками "тогда и только тогда", "необходимо и достаточно", "... равносильно ...", называется эквиваленцией и обозначается знаком    или  ~.   Высказывание А В истинно тогда и только тогда, когда значения А и В совпадают.       A B А  B 0 0 1 0 1 0 1 0 0 1 1 1 Таблица истинности эквиваленции С помощью логических переменных и символов логических операций любое высказывание можно формализовать, то есть заменить логической формулой. Определение логической формулы: 1. Всякая логическая переменная и символы "истина" ("1") и "ложь" ("0") - формулы. 2. Если  А и В - формулы,   то  А , А · В , А v В ,   А B ,   А В   - формулы. 3. Никаких других формул в алгебре логики нет. Порядок выполнения логических операций в сложном логическом выражении1.Инверсия;2. Конъюнкция;3. Дизъюнкция;4. Импликация;5. Эквивалентность. Определите истинность составного высказывания: (А&В) & (C\/D), состоящего из простых высказываний: А = {Принтер – устройство вывода информации}, В = {Процессор – устройство хранения информации}, С = {Монитор – устройство вывода информации}, D = {Клавиатура – устройство обработки информации}.   Сначала на основании знания устройства компьютера устанавливаем истинность простых высказываний: А = 1, В = 0, С = 1, D = 0. Определим теперь истинность составного высказывания, используя таблицы истинности логических операций: ( 1 & 0 ) &(1 \/ 0) = (0 & 1) & (1 \/ 0) = 0 Составное высказывание ложно. Даны простые высказывания:А = {Принтер – устройство ввода информации}, В = {Процессор – устройство обработки информации}, С = {Монитор – устройство хранения информации}, D = {Клавиатура – устройство ввода информации}.   Определите истинность составных высказываний: а) (А & В) & (C v D); б) (А & В) => (C v D); в) (А v В)   (C & D); г) А  B . Логические выражения и их таблицы истинности  Составные высказывания в алгебре логики записываются с помощью логических выражений. Для любого логического выражения достаточно просто построить таблицу истинности. логическая формула Таблица истинности - это табличное представление логической схемы (операции), в котором перечислены все возможные сочетания значений истинности входных сигналов (операндов) вместе со значением истинности выходного сигнала (результата операции) для каждого из этих сочетаний. Построение таблиц истинности для логических выражений подсчитать n - число переменных в выражении подсчитать общее число логических операций в выражении установить последовательность выполнения логических операций определить число столбцов в таблице заполнить шапку таблицы, включив в неё переменные и операции определить число строк в таблице без шапки: m =2n выписать наборы входных переменных провести заполнение таблицы по столбцам, выполняя логическиеоперации в соответствии с установленной последовательностью A B A&B AVA&B 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 А V A & Bn (число переменных) = 2, m (количество строк без шапки)= 22 = 4.Операций – 2, значит количество столбцов будет: n+2=4 Приоритет операций: &, V Пример построения таблицы истинности Составление таблиц истинности A B F 0 0 0 1 1 0 1 1 0 1 2 3 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 1 Составление таблиц истинности A B C A∙B A∙C B∙C F 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 1 2 3 4 5 6 7 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 1 Закон тождества A = A Закон тождества означает, что в процессе рассуждения нельзя подменять одну мысль другой, одно понятие другим. При нарушении этого закона возможны логические ошибки.Например, рассуждение Правильно говорят, что язык до Киева доведет, а я купил вчера копченый язык, значит, теперь смело могу идти в Киев неверно, так как первое и второе слова «язык» обозначают разные понятия. Всякое понятие и суждение тождественно самому себе. Закон непротиворечия A & notA = 0 Не могут быть одновременно истинны утверждение и его отрицание. То есть если высказывание А— истинно, то его отрицание не А должно быть ложным (и наоборот). Тогда их произведение будет всегда ложным.Это равенство часто используется при упрощении сложных логических выражений.Примеры невыполнения закона непротиворечия:1. На Марсе есть жизнь и на Марсе жизни нет.2. Оля окончила среднюю  школу и учится в X классе. Закон исключения третьего A and not A = 1 В один и тот же момент времени высказывание может быть либо истинным, либо ложным, третьего не дано. Истинно либо А, либо не А. Примеры выполнения закона исключенного третьего:1. Число 12345 либо четное, либо нечетное, третьего не дано.2. Предприятие работает убыточно или безубыточно.3. Эта жидкость является или не является кислотой. Закон двойного отрицания Not (notA)=1 Если отрицать дважды некоторое высказывание, то в результате получается исходное высказывание. Например, высказывание А = Матроскин — кот   эквивалентно высказыванию А = Неверно, что Матроскин не кот. Логический элемент компьютера — это часть электронной логической схемы, которая реализует элементарную логическую функцию. Логическими элементами компьютеров являются электронные схемы И, ИЛИ, НЕ, И—НЕ, ИЛИ—НЕ и другие. Каждый логический элемент имеет свое условное обозначение, которое выражает его логическую функцию, но не указывает на то, какая именно электронная схема в нем реализована. Это упрощает запись и понимание сложных логических схем. Логические элементы компьютера & 1 1 & НЕ И ИЛИ ИЛИ-НЕ И-НЕ значок инверсии Логические элементы компьютера Любое логическое выражение можно реализовать на элементах И-НЕ или ИЛИ-НЕ. & И: НЕ: & & ИЛИ: & & & Составление схем последняя операция - ИЛИ & 1 & & И Триггер (англ. trigger – защёлка) – это логическая схема, способная хранить 1 бит информации (1 или 0). Строится на 2-х элементах ИЛИ-НЕ или на 2-х элементах И-НЕ. 1 1 основной выход вспомогательный выход reset, сброс set, установка обратные связи S R Q режим 0 0 0 1 1 0 1 1 хранение запрещен 1 1 0 0 сброс установка 1 0 0 Полусумматор – это логическая схема, способная складывать два одноразрядных двоичных числа. Σ сумма перенос A B P S 0 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0 & 1 & & Сумматор - это логическая схема, способная складывать два одноразрядных двоичных числа с переносом из предыдущего разряда. Σ сумма перенос перенос A B C P S 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1