14.06.2005 Жуланова В. П., КРИПКиПРО Логические операции. - презентация

1 Жуланова В. П., КРИПКиПРО Логические операции

2 Основная идея –логическое доказательство есть вычисление, подобное математическому. Математическая (символическая) логика Основатель – Г. ЛейбницГ. Лейбниц Основатель – Г. ЛейбницГ. Лейбниц Логический язык – для выражения понятий и их отношений. Алгебра человеческого мышления позволит получать новые истины из известных путем точных вычислений.

3 Логика высказываний Разделы логики Логика предикатов Металогика

4 Алгебра высказываний изучает строение (форму, структуру) сложных логических высказываний и способы установления их истинности с помощью алгебраических методов Объекты изучения - высказывания Обозначение высказывания: С=Я иду гулять. С=1, С – истинно; С=0, С – ложно)

5 Примеры высказываний А= Солнце светит для всех Г=А ты любишь информатику? Д=Посмотри в окно А=1 А =(х*х<0) Б= Все ученики любят информатику Б=0 В=1 В=Некоторые из учеников любят информатику Не высказывание А=0 К=2*х-5>0 Не высказывание

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

7 Логическое отрицание (инверсия ) Логическое отрицание (инверсия inverso – лат. переворачивание ) образуется из высказывания с помощью добавления частицы НЕ к сказуемому или использования оборота речи «неверно, что». Обозначение: НЕ U; U; Ū; NOT U Высказывание U Значение высказывания Инверсия Ū Значение инверсии Я люблю петь 1 Я НЕ люблю петь 0

8 Логическое отрицание (инверсия) Инверсия высказывания истинна, когда высказывание ложно, и ложна, когда высказывание истинно. Таблица истинности Таблица истинности U Ū Мнемоническое правило: слово «инверсия» означает, что белое меняется на черное, добро на зло, красивое на безобразное, истина на ложь, ложь на истину, ноль на один, один на ноль

9 Логическое отрицание (инверсия) Графическая иллюстрация Х Х НЕ Х Х – множество учащихся НЕ Х – множество не учащихся Х – множество учащихся НЕ Х – множество не учащихся Высказывание, отрицающееся кратное число раз, имеет то же значение истинности, что и исходное высказывание. Высказывание, отрицающееся не кратное число раз, имеет то же значение истинности, что и инверсия высказывания. А= Неверно, что математика не царица наук. Высказывание, отрицающееся кратное число раз, имеет то же значение истинности, что и исходное высказывание. Высказывание, отрицающееся не кратное число раз, имеет то же значение истинности, что и инверсия высказывания. А= Неверно, что математика не царица наук. В теории множеств соответствует операция – дополнение множества

10 Решить: А=2*2=4 А = А=2*2=4 А = Запишите значения истинности следующих выражений: В=2*2=5 В = В=2*2=5 В = С = в Африке всегда суровые зимы С = С = в Африке всегда суровые зимы С = Выберите пары высказываний, которые являются отрицаниями друг друга: 1.«На улице темно» «На улице светло» 2.«Он сказал правду» «Он не сказал правду» 3. «Это хорошо» «Это плохо» 1.«На улице темно» «На улице светло» 2.«Он сказал правду» «Он не сказал правду» 3. «Это хорошо» «Это плохо» Эти задания выполнить в лекции «Логические операции»

11 Логическое умножение (конъюнкция) образуется соединением двух высказываний в одно с помощью союза И Обозначение: А И В; А В; А & В; А·В; А AND В А= В саду цвели астры В = В саду цвели пионы А & В = В саду цвели астры и пионы

12 Логическое умножение (конъюнкция) Таблица истинности Таблица истинности АВ А И В АВ Астры не цвели Пионы не цвели Ложь Астры не цвели Пионы цвели Ложь Астры цвели Пионы не цвели Ложь Астры цвели Пионы цвели Истина А & В = В саду цвели астры и пионы

13 Логическое умножение (конъюнкция) Конъюнкция двух высказываний истинна тогда и только тогда, когда оба высказывания истинны, и ложна, когда хотя бы одно высказывание ложно Мнемоническое правило: конъюнкция – это логическое умножение. Равенства 0 ·0=0; 0 ·1=0; 1 ·0=0; 1 ·1=1, верные для обычного умножения, верны и для операции конъюнкции Мнемоническое правило: конъюнкция – это логическое умножение. Равенства 0 ·0=0; 0 ·1=0; 1 ·0=0; 1 ·1=1, верные для обычного умножения, верны и для операции конъюнкции

14 Логическое умножение (конъюнкция) Графическая иллюстрация А – множество учащихся В – множество танцоров С= А В – множество учащихся, занимающихся танцами А – множество учащихся В – множество танцоров С= А В – множество учащихся, занимающихся танцами В теории множеств соответствует операция – пересечение множеств А ВС

15 Решить: A = (0&1)&1 B = 1&(1&1)&1 C = 1&(0&1)&1 A = (0&1)&1 B = 1&(1&1)&1 C = 1&(0&1)&1 Найдите значения логических выражений: С = в Африке всегда суровые зимы D = 2*2 = 4 C * D = ? C * D = ? C * D = ? С = в Африке всегда суровые зимы D = 2*2 = 4 C * D = ? C * D = ? C * D = ? С = Россия богата лесами D = Байкал – самое глубокое озеро в мире C * D = ? C * D = ? C * D = ? С = Россия богата лесами D = Байкал – самое глубокое озеро в мире C * D = ? C * D = ? C * D = ? Эти задания решить в лекции «Логические операции»

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

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

18 Нестрогая (дизъюнкция) Таблица истинности Таблица истинности АВ А В АВ Астры не цвели Пионы не цвели Ложь Астры не цвели Пионы цвели Истина Астры цвели Пионы не цвели Истина Астры цвели Пионы цвели Истина А В = В саду цвели астры ИЛИ пионы Обозначение: А ИЛИ В; А В; А В; А+В; А OR В

19 Нестрогая дизъюнкция Нестрогая дизъюнкция двух высказываний ложна тогда и только тогда, когда оба высказывания ложны, и истинна, когда хотя бы одно высказывание истинно. Мнемоническое правило: дизъюнкция – это логическое сложение. Равенства 0 +0=0; 0 +1=1; 1 +0=1, верные для обычного умножения, верны и для операции дизъюнкции, но 1 1=1. Символ (дизъюнкция) образован из первой буквы слова Vel («или»). В слове конъюнкция одна буква И, в слове дизъюнкция – две буквы И, как и в слове ИЛИ. Мнемоническое правило: дизъюнкция – это логическое сложение. Равенства 0 +0=0; 0 +1=1; 1 +0=1, верные для обычного умножения, верны и для операции дизъюнкции, но 1 1=1. Символ (дизъюнкция) образован из первой буквы слова Vel («или»). В слове конъюнкция одна буква И, в слове дизъюнкция – две буквы И, как и в слове ИЛИ.

20 Нестрогая дизъюнкция Графическая иллюстрация А – множество спортсменов В – множество танцоров А В – множество учащихся, занимающихся танцами или спортом А – множество спортсменов В – множество танцоров А В – множество учащихся, занимающихся танцами или спортом В теории множеств соответствует операция – объединение множеств А В

21 Решить: A = (0 v 1) v 1 B = (1 v 1) v (1 v 0) C = (0 v 1) v (1 v 0) A = (0 v 1) v 1 B = (1 v 1) v (1 v 0) C = (0 v 1) v (1 v 0) Найдите значения логических выражений: A = ((0 v 1) & (1 &1)) & (0 v 1) B = ((1 & 0) v (1 & 0)) v 1 C = ((1 & 1) v 0) & (1 v 0) D = ((0 & 0) v 0) & (1 v 1) A = ((0 v 1) & (1 &1)) & (0 v 1) B = ((1 & 0) v (1 & 0)) v 1 C = ((1 & 1) v 0) & (1 v 0) D = ((0 & 0) v 0) & (1 v 1) С = 2*2=5 D = 2*2 = 4 C * D = ? C v D = ? С = 2*2=5 D = 2*2 = 4 C * D = ? C v D = ? Эти задания выполнить в лекции «Логические операции»

22 Логическое следование (импликация) образуется соединением двух высказываний в одно с помощью оборота речи «если…, то…» Обозначение: А В; А В Если число делится на 9, то оно делится на 3 Если коровы летают, то 2+2=5 Если на улице дождь, то асфальт мокрый

23 Логическое следование (импликация) Таблица истинности Таблица истинности АВ А В АВ Дождя нет Асфальт сухой Истина Дождя нет Асфальт мокрый Истина Дождь идет Асфальт сухой Ложь Дождь идет Асфальт мокрый Истина (А В) = Если на улице дождь, то асфальт мокрый А= На улице дождь В = Асфальт мокрый

24 Логическое следование (импликация) Задание 3. Используя таблицу истинности, определите истинность или ложность следующих высказываний Задание 3. Используя таблицу истинности, определите истинность или ложность следующих высказываний Если коровы летают, то 2+2=5 Если 2*2=4, то белые медведи живут в Африке Если белые медведи живут в Африке, то 2*2=4 Выполнить в лекции «Логические операции»

25 Логическое следование (импликация) Импликация двух высказываний ложна тогда и только тогда, когда из истинного высказывания следует ложное. Графическая иллюстрация (А =0) (В=0) А В А В А ВА В (А =0) (В=1) (А =1) (В=1)

26 Решить: А=2*2=4 В=2*2=5 А В А=2*2=4 В=2*2=5 А В Запишите значения истинности следующих выражений: А = 5>3; B = 2=3; C = 4<2; (A v B) & C (A & C) v (B & C) А = 5>3; B = 2=3; C = 4<2; (A v B) & C (A & C) v (B & C) A = Принтер – устройство ввода информации. В = Процессор – устройство обработки информации. С = Монитор – устройство хранения информации. D = Клавиатура – устройство ввода информации. (A & B) & (C v D); (A & B) (B & C); A = Принтер – устройство ввода информации. В = Процессор – устройство обработки информации. С = Монитор – устройство хранения информации. D = Клавиатура – устройство ввода информации. (A & B) & (C v D); (A & B) (B & C); Решить в лекции «Логические операции»

27 Логическое равенство (эквивалентность) образуется соединением двух высказываний в одно с помощью оборота речи «…тогда и только тогда, когда» Обозначение: А В; А В; А ~ В (А В) = Угол называется прямым тогда и только тогда, когда он равен 90º. (А В) = Голова думает тогда и только тогда, когда язык отдыхает. А = Угол прямой В = Угол равен 90º

28 Логическое равенство (эквивалентность) Таблица истинности Таблица истинности АВ А В АВ Число не кратно 3Сумма цифр не кратна 3 Истина Число не кратно 3Сумма цифр кратна 3 Ложь Число кратно 3Сумма цифр не кратна 3 Ложь Число кратно 3Сумма цифр кратна 3 Истина (А В) = Число кратно 3 тогда и только тогда, когда сумма его цифр делится нацело на 3 А= Число делится на 3 без остатка (кратно 3) В = Сумма цифр числа делится нацело на 3

29 Логическое равенство (эквивалентность) Эквивалентность двух высказываний истинна тогда и только тогда, когда оба высказывания истинны или оба ложны. Графическая иллюстрация А В

30 Решить: А=2*2=4 В=2*2=5 А В А=2*2=4 В=2*2=5 А В Запишите значения истинности следующих выражений: А = 5>3; B = 2=3; C = 4<2; (A & B) v C (A v C) & (B & C) А = 5>3; B = 2=3; C = 4<2; (A & B) v C (A v C) & (B & C) A = Принтер – устройство ввода информации. В = Процессор – устройство обработки информации. С = Монитор – устройство хранения информации. D = Клавиатура – устройство ввода информации. (A v B) (C & D); A B; A = Принтер – устройство ввода информации. В = Процессор – устройство обработки информации. С = Монитор – устройство хранения информации. D = Клавиатура – устройство ввода информации. (A v B) (C & D); A B; Решить в лекции «Логические операции»

31 Выполнить задание: Выделите в составных высказываниях простые. Обозначьте каждое из них буквой. Запишите с помощью логических операций каждое составное высказывание: 1. Число 376 четное и трехзначное. 2.Неверно, что Солнце движется вокруг Земли. 3. Если сумма цифр делится на 3, то и число делится на Число делится на 15 тогда и только тогда, когда сумма цифр числа делится на 3. Выделите в составных высказываниях простые. Обозначьте каждое из них буквой. Запишите с помощью логических операций каждое составное высказывание: 1. Число 376 четное и трехзначное. 2.Неверно, что Солнце движется вокруг Земли. 3. Если сумма цифр делится на 3, то и число делится на Число делится на 15 тогда и только тогда, когда сумма цифр числа делится на 3. Решить в лекции «Логические операции»

32 Выполнить задание: Заполните правую колонку таблицы соответствующими названиями логических операций: В естественном языкеВ логике ….и… …или… Неверно, что… … в том и только в том случае…. ….если…, то … …тогда и только тогда, когда … …не… Решить в лекции «Логические операции»

33 Свойства логических операций Инверсия истинна Дизъюнкция ложна Конъюнкция истинна Дизъюнкция истинна Конъюнкция ложна Импликация ложна Эквивалентность истинна тогда и только тогда, когда высказывание ложно ложны оба высказывания истинны истинно хотя бы одно высказывание ложно из истинного высказывания следует ложное высказывание оба высказывания истинны или оба высказывания ложны

34 Логические формулы Логическое выражение (формула) - содержит переменные, соединенные знаками логических операций и скобками, и превращается в высказывание при подстановке вместо переменных простых суждений. А,В – логические переменные Приоритет логических операций: 1)скобки 2)инверсия; 3)конъюнкция; 4) дизъюнкция; 5)импликация и эквивалентность. Приоритет логических операций: 1)скобки 2)инверсия; 3)конъюнкция; 4) дизъюнкция; 5)импликация и эквивалентность.

35 Приоритет логических операций Пример 1. U В С & D Ū Порядок вычисления: 1) Ū 2) С & D 3) U В 4) U В С & D 5) U В С & D Ū Пример 1. U В С & D Ū Порядок вычисления: 1) Ū 2) С & D 3) U В 4) U В С & D 5) U В С & D Ū Скобки; инверсия; конъюнкция; дизъюнкция; импликация и эквивалентность Пример 2. U (В С) & D Ū Порядок вычисления: 1) Ū 2) (В С) 3) (В С) & D 4) U (В С) & D 5) U В С & D Ū Пример 2. U (В С) & D Ū Порядок вычисления: 1) Ū 2) (В С) 3) (В С) & D 4) U (В С) & D 5) U В С & D Ū

36 Приоритет логических операций Задание 2 Ӯ & Ӣ ( Ū & D) У= Человек с детства давал нервам властвовать над собой. И = Человек в юности давал нервам властвовать над собой. U = Нервы привыкнут раздражаться. D = Нервы будут послушны. Задание 2 Ӯ & Ӣ ( Ū & D) У= Человек с детства давал нервам властвовать над собой. И = Человек в юности давал нервам властвовать над собой. U = Нервы привыкнут раздражаться. D = Нервы будут послушны. инверсия; конъюнкция; дизъюнкция; импликация и эквивалентность Запишите словами высказывание, заданное формулой: Выполнить в лекции «Логические операции»

37 Приоритет логических операций Задание 3 (В & Ӣ ) Ū В = Больной поговорил с врачом. И = Больному стало легче. U= Некто является врачом. Задание 3 (В & Ӣ ) Ū В = Больной поговорил с врачом. И = Больному стало легче. U= Некто является врачом. инверсия; конъюнкция; дизъюнкция; импликация и эквивалентность Запишите словами высказывание, заданной формулой: Выполнить в лекции «Логические операции»

38 Задание 4. Определите простые высказывания и составьте формулы сложного высказывания: инверсия; конъюнкция; дизъюнкция; импликация и эквивалентность Сложное высказывание Простые высказывания Форма сложного высказывания Е= Идет дождь, а у меня нет зонта Е= Когда живется весело, то и работа спорится Е= Идет налево песнь заводит, направо сказку говорит Выполнить в лекции «Логические операции»

39 Задание 5. Определите простые высказывания и составьте формулы сложного высказывания: инверсия; конъюнкция; дизъюнкция; импликация и эквивалентность Сложное высказывание Простые высказывания Форма сложного высказывания Е = Ваш приезд не является ни необходимым, ни желательным Е = Поиски врага длились уже три часа, но результатов не было, притаившийся враг ничем себя не выдавал Е = Вчера было пасмурно, а сегодня ярко светит солнце Е - И добродетель стать пороком может, когда ее неправильно приложат. Выполнить в лекции «Логические операции»

40 Пример 3. В классе разбили стекло. Учитель объясняет директору. Это сделал Коля или Саша. Но Саша этого не делал, т.к. сдавал мне зачет. Это сделал Коля. Прав ли учитель? Пример 3. В классе разбили стекло. Учитель объясняет директору. Это сделал Коля или Саша. Но Саша этого не делал, т.к. сдавал мне зачет. Это сделал Коля. Прав ли учитель? К= сделал Коля U = сделал Саша n=2 К= сделал Коля U = сделал Саша n=2 Е=(К U) & Ū К Число строк в таблице истинности = 2 n +2= 4+2 = 6 Число столбцов = n+ число логических операций = 2+4=6 Число строк в таблице истинности = 2 n +2= 4+2 = 6 Число столбцов = n+ число логических операций = 2+4= К U Ū 2 К U 1 2 (К U) & Ū 4 & 3 ( К U) & Ū К Ответ: Учитель прав, так как при всех исходных значениях переменных в столбце 6 получается ИСТИНА (1)

41 Алгоритм построения таблицы истинности 1. Определить число простых высказываний n. 2. Вычислить количество строк (2 n +2) и столбцов (n+число операций). 3. Начертить таблицу и заполнить заголовок. 4. Заполнить столбцы простых высказываний: 1 столбец: 2 n /2=k (чередуем k нулей и k единиц); 2 столбец: k/2=m (чередуем m нулей и m единиц); 3 столбец: m/2=p (чередуем p нулей и p единиц)/ 5. Заполнить остальные столбцы соответственно логическим формулам Е = К Ū Ӣ

42 К U И Ū 2 Ӣ 3 К Ū 1 4 К Ū Ӣ

43 Е = К Ū Ӣ К U И Ū 2 Ӣ 3 К Ū 1 4 К Ū Ӣ

44 Типы сложных высказываний Тождественно истинное (тавтология) – высказывание истинно при всех значениях входящих в него переменных ( обозначается константой 1): U Ū Дождь будет или дождя не будет Тождественно истинное (тавтология) – высказывание истинно при всех значениях входящих в него переменных ( обозначается константой 1): U Ū Дождь будет или дождя не будет Тождественно ложное – высказывание ложно при всех значениях входящих в него переменных (обозначается константой 0): U & Ū Компьютер включен и не включен Тождественно ложное – высказывание ложно при всех значениях входящих в него переменных (обозначается константой 0): U & Ū Компьютер включен и не включен Тождественные (равносильные, эквивалентные) – высказывания, значения которых совпадают при всех возможных значениях входящих переменных: А=В

45 Задание 5. Докажите справедливость следующих тождеств А & (В С) = (А & В) (А & С) А (А & В) = А А (В & С) = (А В) & (А С) А В = А & В А & В = А В