Презентация по информатике и ИКТ на тему Алгебра высказываний.

Основы логики Алгебра высказываний Алгебра высказываний Алгебра высказываний была разработана для того, чтобы определять истинность или ложность составных высказываний, не вникая в их содержание Логические переменные Логические переменные – простые высказывания, содержащие только одну мысль. Обозначаются буквами латинского алфавита: A, B, C…Логические переменные могут принимать лишь два значения: «ИСТИНА» (1) или «ЛОЖЬ» (0) Логические переменные Например, два простых высказывания:А = «2  2 = 4»истина (1)В = «2  2 = 5»ложь(0)являются логическими переменными А и В В алгебре высказываний высказывания обозначаются именами логических переменных, которые могут принимать лишь два значения: «ИСТИНА» (1) или «ЛОЖЬ» (0) В алгебре высказываний над логическими переменными (над высказываниями) можно производить определенные логические операции, в результате которых получаются новые высказывания Составные высказывания Высказывания, состоящие из нескольких простых суждений и содержащие в себе более, чем одну простую мысль, называются логическими функциямиОбозначаются F(A,B,C…)Также могут принимать значения «ИСТИНА» или «ЛОЖЬ» в зависимости от того, какие значения имеют входящие в их состав логические переменные и от действий над ними Логические операции Конъюнкция (логическое умножение, «И»)Дизъюнкция (логическое сложение, «ИЛИ»)Инверсия (логическое отрицание, «НЕ»)Импликация (логическое следование, «Если А, то В»)Эквивалентность (логическое равенство, «А тогда и только тогда, когда В») Объединение двух или нескольких высказываний в одно с помощью союза «И» называется операцией логического умножения, или конъюнкцией Логическая функция, полученная в результате конъюнкции, истинна тогда и только тогда, когда истинны все входящие в него логические переменные Конъюнкция. Определите истинность логической функции «2  2 = 5» И «3  3 = 10»«2  2 = 5» И «3  3 = 9»«2  2 = 4» И «3  3 = 10»«2  2 = 4» И «3  3 = 9»Истинна только функция (4) Запись конъюнкции на формальном языке алгебры высказываний F(A,B) = A & B или F(A,B) = A  BТакже может встретиться запись, типа:F(A,B) = A * B илиF(A,B) = A and B Значение логической функции определяется по ее таблице истинности Таблица истинности показывает какие значения принимает логическая функция при всех возможных значениях логических переменных Таблица истинности для конъюнкции A B A  B 2  2 = 5 3  3 = 10 ЛОЖЬ 2  2 = 5 3  3 = 9 ЛОЖЬ 2  2 = 4 3  3 = 10 ЛОЖЬ 2  2 = 4 3  3 = 9 ИСТИНА Таблица истинности для конъюнкции A B A  B 0 0 0 0 1 0 1 0 0 1 1 1 Объединение двух или нескольких высказываний в одно с помощью союза «ИЛИ» называется операцией логического сложения, или дизъюнкцией Логическая функция, полученная в результате дизъюнкции, истинна тогда, когда истинна хотя бы одна из входящих в него логических переменных Дизъюнкция. Определите истинность логической функции «2  2 = 5» ИЛИ «3  3 = 10»«2  2 = 5» ИЛИ «3  3 = 9»«2  2 = 4» ИЛИ «3  3 = 10»«2  2 = 4» ИЛИ «3  3 = 9»Ложна только функция (1), остальные истинны Запись дизъюнкции на формальном языке алгебры высказываний F(A,B) = A  B Также может встретиться запись, типа:F(A,B) = A + BилиF(A,B) = A or B Таблица истинности для дизъюнкции A B A  B 2  2 = 5 3  3 = 10 ЛОЖЬ 2  2 = 5 3  3 = 9 ИСТИНА 2  2 = 4 3  3 = 10 ИСТИНА 2  2 = 4 3  3 = 9 ИСТИНА Таблица истинности для дизъюнкции A B A  B 0 0 0 0 1 1 1 0 1 1 1 1 Присоединение частицы «НЕ» к высказыванию называется операцией логического отрицания, или инверсией Логическое отрицание (инверсия) делает истинное высказывание ложным, а ложное – истинным [логическая отрицательная единица, перевертыш] Инверсия Пусть A = «2  2 = 4»– истинное высказывание, тогдаF(A) = «2  2 ≠ 4»– ложное высказывание Запись инверсии на формальном языке алгебры высказываний F(A) = ¬AилиF(A) = ĀТакже может встретиться запись, типа:F(A) = not А Таблица истинности для инверсии А ¬А 0 1 1 0 Таблицы истинности основных логических функций Логическое умножение A 0 0 1 1 B 0 1 0 1 A  B0001 Логическое сложение Логическое отрицание A 0 1 A 0 0 1 1 B 0 1 0 1 А  В0111 Дополнительные логические функции Импликацию и эквивалентность можно выразить через конъюнкцию, дизъюнкцию и отрицание, поэтому их называют дополнительными логическими функциями:Импликация:А → В = ¬A  В или А  В = ¬A  В илиА  В = ¬A  В Эквивалентность:А ↔ В = (¬A  В)  (¬B  A) или А  В = (¬A  В)  (¬B  A) или А ≡ В = (¬A  В)  (¬B  A) Импликация Объединение двух высказываний, из которых первое является условием, а второе – следствием из него, называется импликацией (логическим следованием) Импликация Импликация ложна тогда и только тогда, когда условие истинно, а следствие ложноПример: Если выучишь материал, то сдашь зачет Это высказывание ложно только тогда, когда материал выучен, а зачет не сдан, т.к. сдать зачет можно и случайно, например если попался единственный знакомый вопрос или удалось воспользоваться шпаргалкой Таблица истинности для импликации A B A → B 0 0 1 0 1 1 1 0 0 1 1 1 Эквивалентность Эквивалентность – это логическая операция, объединяющая два простых высказывания в одно составное и которое является истиннымтогда и только тогда, когдаоба исходных высказывания одновременно либо истинны, либо ложны. Таблица истинности для эквивалентности A B A  B 0 0 1 0 1 0 1 0 0 1 1 1 Переместительный Дизъюнкция:X  Y ≡ Y  XКонъюнкция:X  Y ≡ Y  X Основные законы алгебры высказываний Сочетательный Дизъюнкция:X  (Y  Z) ≡ (X  Y)  ZКонъюнкция:X  (Y  Z) ≡ (X  Y)  Z Основные законы алгебры высказываний Распределительный Дизъюнкция:X  (Y  Z) ≡ X  Y  X  ZКонъюнкция: X  (Y  Z) ≡ (X  Y)  (X  Z) Основные законы алгебры высказываний Правила де Моргана Дизъюнкция: ¬(X  Y) ≡ ¬X  ¬YКонъюнкция: ¬(X  Y) ≡ ¬X  ¬Y Основные законы алгебры высказываний Идемпотенции Дизъюнкция: X  X ≡ XКонъюнкция: X  X ≡ X Основные законы алгебры высказываний Поглощения Дизъюнкция: X  (X  Y) ≡ XКонъюнкция: X  (X  Y) ≡ X Основные законы алгебры высказываний Склеивания Дизъюнкция: (X  Y)  (¬X  Y) ≡ YКонъюнкция: (X  Y)  (¬X  Y) ≡ Y Основные законы алгебры высказываний Переменная со своей инверсией Дизъюнкция: X  ¬X ≡ 1Конъюнкция: X  ¬X ≡ 0 Основные законы алгебры высказываний Операция с константами Дизъюнкция: X  0 ≡ X, X  1 ≡ 1Конъюнкция: X  0 ≡ 0, X  1 ≡ X Основные законы алгебры высказываний Двойного отрицания ¬(¬X) ≡ X Основные законы алгебры высказываний Порядок действий Действия в скобкахОтрицаниеКонъюнкция ДизъюнкцияИмпликацияЭквивалентность