Презентация по информатике "Алгебра логики. Алгебра высказываний" (11 класс)

АЛГЕБРА ЛОГИКИ АЛГЕБРА ЛОГИКИ Алгебра  высказываний ЛОГИКА • (от греческого logos – слово, понятие,  рассуждение, разум) или: формальная  логика, ­ наука о законах и операциях  правильного мышления. • это раздел математической логики,  изучающий строение сложных логических  высказываний и способ установления их  истинности с помощью алгебраических  методов ЛОГИКА • Первые учения о формах и способах  рассуждений возникли в странах Древнего  Востока (Китай, Индия). Основы  формальной логики заложил Аристотель,  который впервые отделил логические  формы речи от ее содержания. • XIX век – алгебра высказываний.  Основатель алгебры логики – математик  Джордж Буль. • Логическое высказывание – это любое  повествовательное предложение, в отношении  которого можно однозначно сказать истинно  (1) оно или ложно (0).  • В алгебре высказываний суждениям (высказываниям)  ставятся в соответствие логические переменные  (заглавные буквы латинского алфавита) • А = 2 х 2 = 4;          А=1 (истинно) • В = 2 х 2 =10;         В = 0 (ложно) • Не всякое предложение является  высказыванием. Например, предложение  «Ученик 11 класса» ­ высказыванием не  является, так как ничего не утверждает об  ученике. Нужны какие­то дополнительные  сведения. • Вопросительные и восклицательные  предложения также не являются  высказываниями, так как говорить о их  истинности или ложности не смысла. ВЫСКАЗЫВАНИЯ Элементарные  (простые) А = «Аристотель  основоположник  логики» = 1 В = «На яблонях  растут бананы» = 0 Составные (сложные) ­образованные из других  высказываний с помощью  логических связок: И, ИЛИ, НЕ,  ЕСЛИ … ТО,  ТОГДА И ТОЛЬКО  ТОГДА Истинность и ложность  составных высказываний  зависит от истинности или  ложности элементарных  высказываний Так, А = 1, В = 0, то А и В = 0 Основные операции  алгебры высказываний Каждая логическая связка  рассматривается как операция  над логическими  высказываниями и имеет свое  название и обозначение. Логическое отрицание ­инверсия – это операция выраженная связкой «НЕ» с латинского – inversio – переворачиваю А (А, not) Высказывание А истинно, когда А –  ложно , и ложно, когда А ­ истинно Таблица истинности – таблица, которая  показывает какие значения принимает составное  высказывание при всех наборах значений, входящих в  него простых высказываний. Таблица истинности  логического отрицания А =  «Луна –  спутник  Земли» А А 0 1 1 0 Логическое умножение ­конъюнкция – это операция выраженная связкой «И» с латинского – conjunctio – связываю А^B (&, *, and) Высказывание А^B истинно, тогда  и только тогда, когда оба  высказывания истинны Таблица истинности  логического умножения А В А^B 0 0 0 0 0 1 1 1 0 1 0 1 10 не : 2 и 5 не > 3 10 не : 2 и 5 > 3 10 : 2 и 5 не > 3 10 : 2 и 5 > 3 Логическое сложение ­дизъюнкция – это операция выраженная связкой  «ИЛИ» с латинского – dizjunctio – различаю АVB (+, or) Высказывание АvB ложно, тогда и  только тогда, когда оба  высказывания ложны Таблица истинности  логического сложения 10 не : 2 или 5 не > 3 10 не : 2 или 5 > 3 10 : 2 или 5 не >3 10 : 2 или 5 > 3 А В АvB 0 0 0 1 1 1 1 1 0 1 0 1 Операция импликация – это операция выраженная связкой «ЕСЛИ … ТО» с латинского – implicatio – тесно связываю «Если выглянет солнце, то станет тепло» А     B (    , логическое следование) Высказывание А   B ложно, тогда и  только тогда, когда А ­ истинно, В –  ложно (А = 1, В = 0) Таблица истинности  1 1 0 1 импликации А В А   B 0 0 1 1 0 1 0 1 • Пример: Каким же образом импликация связывает два элементарных  высказывания? • Даны два элементарных высказывания:  А = «Данный четырехугольник – квадрат» В = «Около данного четырехугольника можно описать окружность» • Рассмотрим составное высказывание А­> В, понимаемое как «если данный  четырехугольник квадрат, то около него можно описать окружность».  • Есть три варианта, когда высказывание истинно: Есть три варианта, когда высказывание истинно: • 1. А=1, В=1­ «Данный четырехугольник квадрат и около него можно описать  окружность» • 2. А=0, В=1 ­ «Данный четырехугольник не является квадратом, но  около него  можно описать окружность» • 3. А=0, В=0 ­ «Данный четырехугольник не является квадратом, и  около него  нельзя описать окружность» • Ложен только один вариант: Ложен только один вариант: А=1, В=0 ­ «Данный четырехугольник является  квадратом, но около него нельзя описать окружность» Операция эквиваленция – это операция выраженная связкой  «ТОГДА И ТОЛЬКО ТОГДА» с латинского – aequivalens – равноценное «Людоед голоден тогда, и только тогда когда он давно не ел» А ~ B (    , равнозначность) Высказывание А ~ B истинно,  тогда и только тогда, когда  значения А и В совпадают Таблица истинности  эквиваленции 24 не : 6 ~ 24 : 5 24 не : 6 ~ 24 : 6 24 : 6 ~ 21 не : 3 24 : 6 ~ 21 : 3 А В А~B 0 0 1 1 1 0 0 1 0 1 0 1 Приоритет операций • Действия в скобках • Инверсия • Конъюнкция • Дизъюнкция • Импликация • Эквиваленция Импликацию можно выразить  через отрицание и дизъюнкцию: • А    В = А v В А В А    В 0 0 1 1 1 1 0 1 0 1 0 1 А В А АvВ 0 0 1 0 1 1 1 0 0 1 1 1 1 1 0 0 Эквиваленцию можно выразить  через отрицание, дизъюнкцию и  конъюнкцию: • А ~ В = (А v В) ^ (В v А) А В А В (1) (2) ()^() 1 0 0 0 0 1 0 1 0 1 1 1 1 1 1 0 0 1 11 1 0 1 0 1 1 0 0 А~В 1 0 0 1 Высказывания, у которых таблицы  истинности совпадают, называются  равносильными и обозначаются = • Пусть имеются простые высказывания  А и В. Доказать, что составное  высказывание А ^ В равносильно  составному высказыванию А v В. • Докажите, что: а) А ^ В = А v В б) А ~ В = (А ^ В) v (А ^ В) Высказывания, у которых таблицы  истинности совпадают, называются  равносильными и обозначаются = • а) А ^ В = А v В Высказывания, у которых таблицы  истинности совпадают, называются  равносильными и обозначаются = • А ~ В = (А ^ В) v (А ^ В) Логическая формула • С помощью логических переменных и символов  любое высказывание можно формализовать, то  есть заменить формулой. Результат вычисления  логической формулы есть истина или ложь. • Определение логической формулы: 1. Всякая логическая переменная и символы  «истина» и «ложь» ­ формулы. 2. Если А и В формулы, то А, А ^ В, А v В, А    В, А  ~ В формулы! Тождественно – истинные  формулы •           Формулы, которые принимают значение «истина»  при любых значениях истинности, входящих в них  переменных, называются тождественно – истинными или  тавтологиями. •         Высказывания, которые формализуются  тавтологиями, называются логически истинными  высказываниями. • А v А = «этот треугольник прямоугольный или  косоугольный» = 1 и тогда, когда треугольник  прямоугольный и тогда, когда треугольник  непрямоугольный. Тождественно – ложные  формулы •           Формулы, которые принимают значение «ложь»  при любых значениях истинности, входящих в них  переменных, называются тождественно – ложными  или противоречиями. •         Высказывания, которые формализуются  противоречиями, называются логически ложными  высказываниями. • А ^ А = «Катя – самая высокая девочка в классе и в  классе есть девочки выше Кати» = 0 очевидно, что А  или А – ложно. Указанные операции хорошо  иллюстрируются с помощью  диаграмм Эйлера ­ Вейна. А В А В А отрицание конъюнкция дизъюнкция А ^ В А v В Определите с помощью таблиц истинности,  какие из следующих формул являются  •            тождественно – истинными или  тождественно – ложными. 1.((А v В)    В) ^ (А v В) 2.А ^ (В ^ (А v В)) 3.((С v В)    В) ^ ( А ^ В)    В Определите с помощью таблиц истинности,  какие из следующих формул являются  тождественно – истинными или  тождественно – ложными. •            1.((А v В)    В) ^ (А v В) Определите с помощью таблиц истинности,  какие из следующих формул являются  тождественно – истинными или  тождественно – ложными. •            А ^ (В ^ (А v В)) ((С v В)    В) ^ ( А ^ В)    В •