Алгебра логики Учитель физики, математики, информатики Цапов О. В. с. Александров-Гай, 2009 г. - презентация

1 Алгебра логики Учитель физики, математики, информатики Цапов О. В. с. Александров-Гай, 2009 г.

2 1. Формы мышления В основе современной логики лежат учения, созданные ещё древнегреческими мыслителями, хотя первые учения о формах и способах мышления возникли в Древнем Китае и Индии. Основоположником формальной логики является Аристотель, который впервые отделил логические формы мышления от его содержания.

3 Логика Логика – это наука о формах и способах мышления. Это учение о способах рассуждений и доказательств. Законы мира, сущность предметов, общее в них мы познаём посредством абстрактного мышления. Логика позволяет строить формальные модели окружающего мира, отвлекаясь от содержательной стороны. Мышление всегда осуществляется через понятия, высказывания и умозаключения.

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

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

6 Пример 2. Истинное высказывание: «Буква «а» - гласная». Ложное высказывание: «Компьютер был изобретён в середине XIX века».

7 Упражнение 1. Какие из предложений являются высказываниями? Определите их истинность. 1.Какой длины эта лента? 2.Прослушайте сообщение. 3. Делайте утреннюю зарядку! 4. Назовите устройство ввода информации. 5. Кто отсутствует? 6. Париж – столица Англии. 7. Число 11 является простым = Без труда не вытащишь и рыбку из пруда. 10. Сложите числа 2 и Все медведи – бурые. 12. Чему равно расстояние от Москвы до Ленинграда.

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

9 Пример 3. Дано высказывание: «Все углы равнобедренного треугольника равны». Получить высказывание «Этот треугольник равносторонний» путём умозаключений. Пусть основанием треугольника является сторона с. Тогда а=b. Так как в треугольнике все углы равны, следовательно, основанием может быть любая другая сторона, например, а. Тогда b=с. Следовательно а=b=с. Треугольник равносторонний.

10 2. Логические выражения и операции Алгебра – это наука об общих операциях, аналогичных сложению и умножению, которые выполняются не только над числами, но и над другими математическими объектами, в том числе и над высказываниями. Такая алгебра называется алгеброй логики. Алгебра логики отвлекается от смысловой содержательности высказываний и принимает во внимание только истинность или ложность высказывания.

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

12 логическая функция Составное высказывание – логическая функция, которая содержит несколько простых мыслей, соединённых между собой с помощью логических операций. Её символическое обозначение – F (A, B, …). На основании простых высказываний могут быть построены составные высказывания. Логические операции Логические операции – логическое действие.

13 Рассмотрим три базовые логические операции – конъюнкцию, дизъюнкцию и отрицание и дополнительные – импликацию и эквивалентность.

14 логическое выражение Если составное высказывание (логическую функцию) выразить в виде формулы, в которую войдут логические переменные и знаки логических операций, то получится логическое выражение, значение которого можно вычислить. Значением логического выражения могут быть только ЛОЖЬ или ИСТИНА. При составлении логического выражения необходимо учитывать порядок выполнения логических операций, а именно: 1)Действия в скобках; 2)Инверсия, конъюнкция, дизъюнкция, импликация, эквивалентность.

15 Пример 4. Записать в виде логического выражения следующее высказывание: «Летом Петя поедет в деревню и, если будет хорошая погода, то он пойдёт на рыбалку». 1.Проанализируем составное высказывание. Оно состоит из следующих простых высказываний: «Петя поедет в деревню», «Будет хорошая погода», «Он пойдёт на рыбалку». Обозначим их через логические переменные: А = Петя поедет в деревню; B = Будет хорошая погода; С = Он пойдёт на рыбалку. 2. Запишем высказывание в виде логического выражения, учитывая порядок действий. Если необходимо, расставим скобки: F = A & (BC).

16 Упражнение 2. Есть два простых высказывания: А – «Число 10 – чётное»; В – «Волк – травоядное животное». Составьте из них все возможные составные высказывания и определите их истинность. А&BАvB¬А¬А¬В¬ВАВАВАВАВ

17 Упражнение 3. Запишите следующие высказывания в виде логических выражений: 1.Число 17 нечётное и двузначное. 2.Неверно, что корова – хищное животное. 3.Тише едешь – дальше будешь. Решение: 1.А – «Число 17 – нечётное», В – «Число 17 – двузначное» А & В 2. А – «Корова – хищное животное» ¬ А 3. А – «Тише едешь», В – «Дальше будешь» А В

18 3. Таблицы истинности АВ F = А & В F = А v В Логическое умножение (конъюнкция) и логическое сложение (дизъюнкция)

19 Логическое отрицание (инверсия)А F = ¬ А 01 10

20 Пример 5. иF=А&В=0 1.«22=4 и 33=10»; F=А&В=0 илиF=АvВ=1 2.«22=4 или 33=10»; F=АvВ=1 F=¬А=0 3.«224»; F=¬А=0

21 АВ F = А В Логическое следование (импликация) логического следования (импликации), Составное высказывание, образованное с помощью операции логического следования (импликации), ложно тогда и только тогда, когда из истинной предпосылки (первого высказывания) следует ложный вывод (второе высказывание).

22 АВ F = А В Логическое равенство (эквивалентность) логической операции эквивалентности Составное высказывание, образованное с помощью логической операции эквивалентности истинно тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны.

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

24 1. Закон тождества А = А Всякое высказывание тождественно самому себе. 2. Закон непротиворечия А & ¬А = 0 Логическое произведение высказывания и его отрицания является ложным.

25 3. Закон исключённого третьего А v ¬А = 1 Логическое сложение высказывания и его отрицания является истинным. 4. Закон двойного отрицания ¬(¬А) = А Двойное отрицание некоторого высказывания равно исходному высказыванию.

26 5. Законы де Моргана ¬(АvВ) = ¬А & ¬В ¬(А&В) = ¬А v ¬В 6. Закон коммутативности А&В = В&А АvВ = ВvА

27 7. Закон ассоциативности (А&В)&С = А&(В&С) (АvВ)vС = Аv(ВvС) Если в логическом выражении используются только операции логического умножения или только операция логического сложения, то можно пренебрегать скобками или произвольно их расставлять.

28 8. Закон дистрибутивности (А&В)v(А&С) = А&(ВvС) (АvВ)&(АvС) = Аv(В&С) В отличие от обычной алгебры, в алгебре высказываний можно выносить за скобки как общие множители, так и общие слагаемые.

29 Пример 6. Упростить логическое выражение: (А & В) v (А & ¬В). 1. Воспользуемся законом дистрибутивности и вынесем за скобки А: (А & В) v (А & ¬В) = А & (В v ¬В). 2. По закону исключённого третьего В v ¬В = 1, следовательно: А & (В v ¬В) = А & 1 = А.

30 Самостоятельная работа Вариант Соедините правильные определения или обозначения: 1)Логика 2)Дизъюнкция 3)Импликация 4)Высказывание 5)Инверсия 6)Алгебра логики 7)Конъюнкция 8)Логическая константа 9)Эквивалентность 1)АВ 2)Логическое сложение 3)Наука о формах и способах мышления 4)Логическое отрицание 5)ИСТИНА и ЛОЖЬ 6)АВ 7)& 8)Наука об операциях над высказываниями 9)Повествовательное предложение, в котором что-либо утверждается или отрицается

31 Вариант 1 2. Даны высказывания: А={33=9}, В={33=10}. Определите истинность высказываний: 1) А; 4) В; 2) ¬В; 5) ¬А; 3) А&В; 6) АvВ. 3.Заполните таблицу: АВ ¬А¬А¬А¬А АvВАvВАvВАvВ Вариант 2 2. Даны высказывания: А={5+7=13}, В={5+7=12}. Определите истинность высказываний: 1) А; 4) В; 2) ¬В; 5) ¬А; 3) А&В; 6) АvВ. 3.Заполните таблицу:АВ ¬В¬В¬В¬В А&ВА&ВА&ВА&В Самостоятельная работа