Алгебра высказываний Тема урока

Алгебра высказываний (алгебра логики) - это математический аппарат, с помощью которого записывают, вычисляют и преобразовывают логические высказывания. Создателем математической логики является живший в ХIХ веке английский математик Джордж Буль, в честь которого эта алгебра названа булевой алгеброй высказываний или алгеброй логики. В 20 веке алгебра логики стала математическим основанием работы ПК.

Для алгебры логики можно определить понятия: логической переменной логической операции логической функции

Логическая переменная это простое высказывание, содержащее только одну мысль. Ее символическое обозначение латинская буква (например, A,B,X,Y). Значением логической переменной могут быть только константы ИСТИНА и ЛОЖЬ (1 и 0). Пример: А=6 четное число, A=1 D=Рим столица Франции, D=0

составное высказывание, содержит несколько простых высказываний, соединенных между собой с помощью логических операций

Рассмотрим два простых высказывания А=«Число 10-четное», В=«Число 10 –отрицательное» В нашем случае первое высказывание истинно (А = 1), а второе ложно (В = 0).

Логические операции - это логическое действие: конъюнкция, дизъюнкция и инверсия (базовые лог. операции) КонъюнкцияДизъюнкцияИнверсия Название логическое умножение логическое сложение логическое отрицание Обозначение А В, A&B А В Ā, ¬A Союз в естественном языке А и В (а, но) (and) А или В (or) Не А (not) Примеры «Число 10 четное и отрицательное» = ЛОЖЬ F(A,B)= А В=0 «Число 10 четное или отрицательное» = ИСТИНА F(A,B)= А В=1 «Неверно, что число 10 – четное» = ЛОЖЬ, «Неверно, что число 10 – отрицательное» = ИСТИНА F(A)= Ā=0, F(B)= B=0

Логические операции – импликация, эквивалентность (дополнительные лог. операции) ИмпликацияЭквивалентность Название логическое следованиелогическое равенство Обозначение А В, А – условие, В - следствие А В, А В, А~ В Союз в естественном языке Если А, то В; когда А, тогда В; А тогда и только тогда, когда В Примеры «Если число 10 - четное, то является отрицательным» = ЛОЖЬ F(A,B)= А В=0 «Число 10 - четное тогда и только тогда, когда отрицательно» = ЛОЖЬ F(A,B)= А В=0

Таблица истинности - таблица, определяющая значение сложного высказывания при всех возможных значениях простых высказываний

Таблица истинности инверсии (логического отрицания) А Ā Диаграмма Эйлера-Венна «Неверно, что число 10 – четное» = ЛОЖЬ, «Неверно, что число 10 – отрицательное» = ИСТИНА F(A)= Ā=0, F(B)= B=1

Таблица истинности конъюнкции и дизъюнкции АВ F=A B Диаграмма Эйлера-Венна «Число 10 четное и отрицательное» = ЛОЖЬ F(A,B)= А В=0 «Число 10 четное или отрицательное» = ИСТИНА F(A,B)= А В=1

Таблица истинности импликации и эквивалентности АВ F=A B «Если число 10 - четное, то является отрицательным» = ЛОЖЬ F(A,B)= А В=0 «Число 10 - четное тогда и только тогда, когда отрицательно» = ЛОЖЬ F(A,B)= А В=0

Примеры импликации а) { Если 2x2 = 4, то через Смоленск протекает Днепр} б){Если через Смоленск протекает Енисей, то 2x2 = 4} в){Если через Смоленск протекает Енисей, то 2x2 = 5} г){Если все ученики класса напишут контрольную работу по физике на отлично, то слоны в Африке живут} д){Если через Смоленск протекает Енисей, то все ученики класса напишут контрольную работу по физике на отлично} е){Если 2 х 2 = 4, то через Смоленск протекает Енисей} ж){Если через Смоленск протекает Днепр, то Луна сделана из теста}

Доказательство импликации ABAB Есть тучи1 Идет дождь1 Нет туч0 Нет дождя0 Если есть тучи, то идет дождь111 Если есть тучи, то нет дождя100 Если нет туч, то идет дождь011 Если нет туч, то нет дождя001

Примеры эквивалентности Рассмотрим возможные значения сложного высказывания, являющегося эквивалентностью: {Учитель утверждает, что 5 в четверти ученику он поставит тогда и только тогда, когда ученик получит 5 на зачете}. а) Ученик получил 5 на зачете и 5 в четверти б) Ученик не получил на зачете 5, и учитель не поставил ему 5 в четверти в) Ученик не получил на зачете 5, но учитель поставил ему 5 в четверти г) Ученик получил 5 на зачете, но учитель не поставил ему 5 в четверти

Доказательство эквиваленции ABAB Выучил урок1 Получу «5»1 Не выучил урок0 Получу «2»0 Выучил урок – тогда и только тогда получу «5»111 Выучил урок – тогда и только тогда получу «2»100 Не выучил урок – тогда и только тогда получу «5»010 Не выучил урок – тогда и только тогда получу «2»001

Домашнее задание § 3.2