АЛГЕБРА ЛОГИКИ. ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ

Цель: 1. Алгебра логики 2. Логические операции

3 Булева алгебра Двоичное кодирование – все виды информации кодируются с помощью 0 и 1. Задача – разработать оптимальные правила обработки таких данных. Джордж Буль разработал основы алгебры, в которой используются только 0 и 1 (алгебра логики, булева алгебра). Почему "логика"? Результат выполнения операции можно представить как истинность (1) или ложность (0) некоторого высказывания.

Историческая справка Идею возможности математизации логики высказал еще в 17 в. немецкий логик Готфрид Вильгельм Лейбниц. Он попытался создать универсальный язык, с помощью которого каждому понятию и суждению можно было бы дать числовую характеристику и установить правила оперирования с этими числами, которые позволили бы сразу определить, истинно данное высказывание или ложно. То есть он предполагал, что споры между людьми можно будет разрешать посредством вычислений. В середине 19 века, английский логик Джордж Буль перенес на логику законы и правила человеческих действий, ввел логические операции, предложил способ записи высказываний в символической форме. В развитии математической логики приняли участие многие выдающиеся математики и логики конца 19 и 20 века: Гедель (Австрия), Гильберт (Германия), Клини (Америка), Пост (Америка), Тьюринг (Англия), Черч (Америка), российские ученые Колмогоров, Новиков, Марков и др.

Алгебра логики (алгебра высказываний) - – раздел математической логики, изучающий строение сложных логических высказываний и способы установления их истинности с помощью алгебраических методов.

Высказывание – повествовательное предложение, относительно которого можно сказать истинно оно или ложно.

7 Обозначение высказываний A – Сейчас идет дождь. B – Форточка открыта. простые высказывания (элементарные) Составные высказывания строятся из простых с помощью логических связок (операций) "и", "или", "не", "если … то", "тогда и только тогда" и др. Любое высказывание может быть ложно (0) или истинно (1). ! A и B A или не B если A, то B не A и B A тогда и только тогда, когда B Сейчас идет дождь и открыта форточка. Сейчас идет дождь или форточка закрыта. Если сейчас идет дождь, то форточка открыта. Сейчас нет дождя и форточка открыта. Дождь идет тогда и только тогда, когда открыта форточка.

Примеры высказываний и предложений, не являющихся высказываниями А= Солнце светит для всех=1 – истинное высказывание. В=Все ученики любят информатику=0 – ложное высказывание. С=Некоторые из учеников любят информатику=1 – истинное высказывание. Д=А ты любишь информатику? – не высказывание, так как не является повествовательным предложением.

Е= Посмотри в окно – не высказывание, так как является побудительным предложением. Ж=(x*x<0)=0 – ложное высказывание, так как какое бы x мы не взяли, произведение x*x будет неотрицательным. З=2*x-5>0 – не высказывание, так для одних значений x это выражение будет истинным, и в то же время для других значений x – ложным. И= Крокодилы летают очень низко – высказывание.

Последний пример показывает, что истинность или ложность высказываний не обязательно должна определяться здравым смыслом. Вопрос о том, летают или не летают крокодилы, может волновать зоологов, но никак не логиков, так как им этот потрясающий факт безразличен. Логика как наука интересуется весьма своеобразно понимаемой истинностью или ложностью высказываний, которая не зависит от знаний, жизненного опыта человека и его субъективного отношения к тому, о чем говорится в высказывании, а устанавливается с помощью некоторых специально разработанных объективных методов.

Задания: Определите, какие из ниже перечисленных фраз являются высказываниями с точки зрения алгебры логики. Определите значения высказывания (истина или ложь)

а) число 8456 является совершенным б) без труда не выловишь и рыбку из пруда Ложь Истина в) как хорошо быть генералом! Не высказывание г) революция может быть мирной и немирной. Истина д) зрение бывает нормальное или у человека бывает дальнозоркость или близорукость Истина е) познай самого себя Не высказывание

Инверсия Логическое отрицание (инверсия) образуется из высказывания с помощью добавления частицы «не» к сказуемому или использования оборота речи «неверно, что…».

14 Операция НЕ (инверсия) Если высказывание A истинно, то "не А" ложно, и наоборот. Ане А таблица истинности операции НЕ также:, not A (Паскаль), ! A (Си) Таблица истинности логического выражения Х – это таблица, где в левой части записываются все возможные комбинации значений исходных данных, а в правой – значение выражения Х для каждой комбинации.

Из таблицы истинности следует, что инверсия высказывания истинна, когда высказывание ложно, и ложна, когда высказывание истинно. Операцию инверсии можно графически проиллюстрировать с помощью диаграмм Эйлера-Венна: Ане А таблица истинности операции НЕ также:, not A (Паскаль), ! A (Си) A

Конъюнкция Логическое умножение (конъюнкция) образуется соединением двух высказываний в одно с помощью союза «И».

17 Операция И (логическое умножение, конъюнкция) ABА и B 1 0 также: A·B, A B, A and B (Паскаль), A && B (Си) конъюнкция – от лат. conjunctio соединение A B Высказывание "A и B" истинно тогда и только тогда, когда А и B истинны одновременно.

Из таблицы истинности следует, что конъюнкция двух высказываний истинна тогда, когда оба высказывания истинны, и ложна, когда хотя бы одно высказывание ложно. Операцию конъюнкции можно графически проиллюстрировать с помощью диаграмм Эйлера-Венна: ABА и B A B A·BA·B

Дизъюнкция Логическое сложение (дизъюнкция) образуется соединением двух высказываний в одно с помощью союза «ИЛИ».

Выделяют Строгую и Нестрогую дизъюнкцию Например, в предложении Обычно в 8 вечера я смотрю телевизор или пью чай. Союз ИЛИ взят в неисключающем смысле. (можно или смотреть телевизор, или пить чай, или и смотреть телевизор и пить чай). Такая операция называется Нестрогая дизъюнкция. В высказывании Данный глагол I или II спряжения. Союз ИЛИ используется в исключающем смысле. Такая операция называется строгой дизъюнкцией.

Примеры строгих и нестрогих дизъюнкций: Высказывание Петя сидит на западной или восточной трибуне стадиона Студент едет в электричке или читает книгу Оля любит писать сочинения или решать логические задачи Сережа учится в школе или окончил ее Завтра дождь будет или не будет Давайте бороться за чистоту. Чистота достигается так: или не сорить или часто убирать Земля движется или по круговой или по эллиптической орбите. Числа можно складывать или перемножать Дети бывают или воспитанные или не наши

22 Операция ИЛИ (логическое сложение, дизъюнкция) ABА или B 1 0 также: A+B, A B, A or B (Паскаль), A || B (Си) дизъюнкция – от лат. disjunctio разъединение Высказывание "A или B" истинно тогда, когда истинно А или B, или оба вместе.

Из таблицы истинности следует, что дизъюнкция двух высказываний ложна тогда и только тогда, когда оба высказывания ложны, и истинна, когда хотя бы одно высказывание истинно. ABА или B A B A+B диаграмма Эйлера-Венна

24 Операция "исключающее ИЛИ" Высказывание "A B" истинно тогда, когда истинно А или B, но не оба одновременно. AB А B 0 0 также: A xor B (Паскаль), A ^ B (Си) сложение по модулю 2: А B = (A + B) mod 2 арифметическое сложение, 1+1=2 остаток

Из таблицы истинности следует, что операция строгой дизъюнкции двух высказываний истинна тогда и только тогда, когда только одно из высказываний истинно, и ложна, когда оба высказывания ложны или истинны. ABА или B диаграмма Эйлера-Венна A B A B

26 A A = (A B) B = Свойства операции "исключающее ИЛИ" A 0 = A 1 = A 0 ? AB А B A

Импликация Логическое следование (импликация) образуется соединением двух высказываний в одно с помощью оборота речи «если…, то…».

28 Импликация ("если …, то …") Высказывание "A B" истинно, если не исключено, что из А следует B. A – "Работник хорошо работает". B – "У работника хорошая зарплата". ABА B

Из таблицы истинности следует, что импликация двух высказываний ложна тогда и только тогда, когда из истинного высказывания следует ложное. ABА или B диаграмма Эйлера-Венна A B A B

Эквивалентность Логическое равенство (эквивалентность) образуется соединением двух высказываний в одно при помощи оборота речи «… тогда и только тогда, когда…»

31 Эквиваленция ("тогда и только тогда, …") Высказывание "A B" истинно тогда и только тогда, когда А и B равны. ABА B

Из таблицы истинности следует, что эквивалентность двух высказываний истинна тогда и только тогда, когда оба высказывания истинны или оба ложны. ABА или B диаграмма Эйлера-Венна A B A B