Алгебра высказываний Решение Решение логических логических задач Автор: Сергеев Евгений Викторович МОУ СОШ 4 г. Миньяра Челябинской области sergeev73@mail.ru. - презентация

1 Алгебра высказываний Решение Решение логических логических задач Автор: Сергеев Евгений Викторович МОУ СОШ 4 г. Миньяра Челябинской области

2 Задача 1: Составьте сложное высказывание в словесной форме из простых, заданных математическим формулировкам: Высказывание А: Высказывание А: «Учащийся Иванов хорошо успевает по английскому языку» Высказывание В: Высказывание В: «Учащийся Иванов любит работать на компьютере». А В «Учащийся Иванов хорошо успевает по английскому языку и любит работать на компьютере» А В «Учащийся Иванов хорошо успевает по английскому языку или любит работать на компьютере» А ¬В «Учащийся Иванов хорошо успевает по английскому языку и не любит работать на компьютере» ¬(А В) «не (учащийся Иванов хорошо успевает по английскому языку и любит работать на компьютере)» «Учащийся Иванов плохо успевает по английскому языку и не любит работать на компьютере» А В «учащийся Иванов хорошо успевает по английскому языку, поэтому он любит работать на компьютере» А ¬В «учащийся Иванов хорошо успевает по английскому языку, поэтому он не любит работать на компьютере» В А «учащийся Иванов хорошо успевает по английскому языку, потому, что он любит работать на компьютере»

3 Задача 2: Пусть p и q обозначают высказывания: p = «Я учусь в школе» q = «Я люблю информатику» составьте и запишите следующие высказывания: ¬p¬(¬p) «Я не учусь в школе» «не(Я не учусь в школе)» «Я учусь в школе» «Я учусь в школе и люблю информатику» «Я учусь в школе и не люблю информатику» «Я учусь в школе или люблю информатику» «Я не учусь в школе или люблю информатику» «Я не учусь в школе или я не люблю информатику» «Я люблю информатику, потому, что учусь в школе» p q p ¬q p q ¬p q ¬p ¬q q p

4 Задача 3: Обозначьте элементарные высказывания буквами и запишите высказывания на формальном языке алгебры высказываний 1.45 кратно 3 и 42 кратно кратно 3 и 12 не кратно если 212 делится на 3 и на 4, то 212 делится на – трехзначное число, которое делится на 3 и на 4 1.А В, где А = «45 кратно 3», В = «42 кратно 3» 2.А ¬В, где А = «45 кратно 3», В = «12 кратно 3» 3.А В, где А = «2 < 5», В = «2 = 5» 4.(A В) С, где А = «212 делится на 3», В = «212 делится на 4» и С = «212 делится на 12» 5.А В С, где А = «212 – трехзначное число», В = «212 делится на 3» и С = «212 делится на 4»

5 Задача 4: Составьте таблицу истинности для функции А ¬В A0011A0011 B0101B0101 ¬B¬B A ¬ B

6 Задача 5: Какие из следующих импликаций истинны 1.если 2 2 = 4, то 2 < 3 2.если 2 2 = 4, то 2 > 3 3.если 2 2 = 5, то 2 < 3 4.если 2 2 = 5, то 2 > 3 истиналожьистинаистина Таблицы истинности

7 Задача 6: Какие из следующих высказываний противоречивы 1.a = 1, a b = 0 2.a = 1, a b = 0 3.a = 1, a b = 1 4.a = 1, a b = 1 5.a = 0, a b = 1 6.a = 0, a b = 1 7.a = 0, a b = 0 8.a = 0, a b = 0 истиналожьистинаистиналожьистинаистинаистина Таблицы истинности

8 Задача 7: Пусть: а = «7 – простое», b = «7 – составное», с = «8 – простое» и d = «8 – составное» Определите истинность высказываний 1. а с 2. а d 3. b c 4. c d ложьистиналожьложь 5. а с 6. а d 7. b c 8. c d истинаистиналожьистина 9. ¬а 10. ¬b 11. ¬c 12. ¬d ложьистинаистиналожь

9 истинаистинаистиналожьистинаистинаистинаистинаистинаистиналожьложьистинаистина Задача 8: Какие из следующих высказываний истинны 1. p p 2. p ¬p 3. ¬(p ¬p) 4. p ¬p 5. ¬p p 6. p p 7. (p p) p 8. ¬(p (p ¬p)) 9. (p p) ¬p 10. p p (¬p p p) 11. p (p ¬p) 12. ¬(¬p p) 13. ¬(p ¬p) 14. (p p) (p p)

10 Задача 9: Даны значения: x = 0, y = 1, z = 1. Определите логические значения высказываний 1.x (y z) 2.(x y) z 3.x (y z) 4.x y z 5.(x y) (z ¬y) 6.((x y) z) ((x z) (y z))

11 Задача 9.1: Даны значения: x = 0, y = 1, z = 1. Определите логические значения высказываний x (y z) x (1 1) x (ложь) x (y z) Таблицы истинности

12 Задача 9.2: Даны значения: x = 0, y = 1, z = 1. Определите логические значения высказываний (x y) z (0 1) z 0 z (ложь) (x y) z Таблицы истинности

13 Задача 9.3: Даны значения: x = 0, y = 1, z = 1. Определите логические значения высказываний x (y z) x (1 1) x (истина) x (y z) Таблицы истинности

14 Задача 9.4: Даны значения: x = 0, y = 1, z = 1. Определите логические значения высказываний x y z 0 1 z 0 z0 z0 z0 z (истина) x y z Таблицы истинности

15 Задача 9.5: Даны значения: x = 0, y = 1, z = 1. Определите логические значения высказываний (x y) (z ¬y) (x y) (z ¬1) (x y) (z 0) (0 1) (1 0) (ложь) (x y) (z ¬y) Таблицы истинности

16 Задача 9.6: Даны значения: x = 0, y = 1, z = 1. Определите логические значения высказываний ((x y) z) ((x z) (y z)) ((0 1) z) ((0 1) (1 1)) (( 1 ) z) (( 0 ) ( 1 )) (1 1) (0 1) (истина) ((x y) z) ((x z) (y z)) Таблицы истинности

17 Задача 10: Упростите выражение: (А В) (А ¬В) (А В) (А ¬В) А (В ¬В) А ( 1 ) А (А В) (А ¬В) Таблицы истинности

18 Задача 11: Упростите выражение: (А ¬А) В (А ¬А) В ( 1 ) В В (А ¬А) В Таблицы истинности

19 Задача 12: Упростите выражение: А (А В) (В ¬В) А (А В) (В ¬В) А (А В) ( 1 ) А (А В) 1 {з-н поглощения} А 1 А А (А В) (В ¬В) Таблицы истинности

20 Задача 13: Доказать справедливость закона поглощения для дизъюнкции: А (А В) А по таблицам истинности Таблицы истинности A0011A0011 B0101B0101 A B A (А B)

21 Задача 14: Доказать справедливость закона поглощения для конъюнкции: А (А В) А по таблицам истинности Таблицы истинности A0011A0011 B0101B0101 A B A (А B)

22 Задача 15: Доказать справедливость первого закона де Моргана: ¬(А В) ¬А ¬В по таблицам истинности Таблицы истинности A0011A0011 B0101B0101 ¬A¬A ¬B¬B A B ¬(A B) ¬A ¬B

23 Задача 16: Доказать справедливость второго закона де Моргана: ¬(А В) ¬А ¬В по таблицам истинности Таблицы истинности A0011A0011 B0101B0101 ¬A¬A ¬B¬B A B ¬(A B) ¬A ¬B

24 Задача 17: Составить расписание занятий так, чтобы математика была первым или вторым уроком, информатика первым или третьим уроком, а физика – вторым или третьим. В расписании всего три урока. Сколько вариантов расписания с такими условиями можно составить?

25 Задача 17. Решение Пусть: М1 = «Математика первым уроком» М1 = «Математика первым уроком» М2 = «Математика вторым уроком» М2 = «Математика вторым уроком» И1 = «Информатика первым уроком» И1 = «Информатика первым уроком» И3 = «Информатика третьим уроком» И3 = «Информатика третьим уроком» Ф2 = «Физика вторым уроком» Ф2 = «Физика вторым уроком» Ф3 = «Физика третьим уроком» Ф3 = «Физика третьим уроком» Тогда расписание можно свести к выражению: (М1 М2) (И1 И3) (Ф2 Ф3)

26 Задача 17. Решение. Раскрытие скобок (М1 М2) (И1 И3) (Ф2 Ф3) (М1 И1 М1 И3 М2 И1 М2 И3) (Ф2 Ф3) М1·И1·Ф2 М1·И3·Ф2 М2·И1·Ф2 М2·И3·Ф2 М1·И1·Ф3 М1·И3·Ф3 М2·И1·Ф3 М2·И3·Ф3 Выбираем только непротиворечивые комбинации: Ответ: 1 вариант – Математика, Физика, Информатика 2 вариант – Информатика, Математика, Физика М1·И1·Ф2 М1·И3·Ф2 М2·И1·Ф2 М2·И3·Ф2 М1·И1·Ф3 М1·И3·Ф3 М2·И1·Ф3 М2·И3·Ф3

27 Задача 18: В одной из смежных аудиторий может быть либо кабинет информатики, либо кабинет физики. На одной двери написано: «В одном из этих двух кабинетов точно есть кабинет информатики», а на двери другого: «Кабинет информатики не здесь». Известно также, что высказывания на табличках тождественны. Определить, где какой кабинет

28 Задача 18. Решение Пусть: А= «Информатика в кабинете 1», В= «Информатика в кабинете 2» Тогда: ¬А= «Физика в кабинете 1», ¬В= «Физика в кабинете 2» Высказывание «В одном из этих двух кабинетов точно есть кабинет информатики»: Х = А В, Высказывание «Кабинет информатики не здесь»: Y = ¬А Исходя из условия: X Y, т.е. Y = (¬X Y) (¬Y X ) (¬X Y) (¬Y X ) ¬Y Заменяем X и Y их выражениями: (¬(А В) ¬А) (¬(¬А) (А В) ) ¬(¬А)

29 Задача 18. Решение (продолжение) (¬(А В) ¬А) (¬(¬А) (А В) ) ¬(¬А) (¬(А В) ¬А) (¬(¬А) (А В) ) ¬(¬А) Упрощаем выражение: ((¬А ¬В) ¬А) (А (А В)) А ((¬А ¬В) ¬А) (А (А В)) А (¬(А В) ¬А) (¬(¬А) (А В) ) ¬(¬А) ((¬А ¬В) ¬А) (А (А В)) А ((¬А ¬В) ¬А) (А (А В)) А ((¬А ¬А) (¬В ¬А)) (А А В А) ((¬А ¬А) (¬В ¬А)) (А А В А) (¬А (¬В ¬А)) (А В) (¬А (¬В ¬А)) (А В) ¬А (А В) ¬А (А В) (¬А А) (¬А В) (¬А А) (¬А В) ¬А В Т.о. выражение ¬А В соответствует высказыванию: «Физика в кабинете 1 и информатика в кабинете 2»

30 Задача 19. Следователь допрашивает Клода, Жака и Дика. Клод утверждает, что Жак лжет, Жак обвинял во лжи Дика, а Дик призывает не слушать ни того, ни другого. Кто из допрашиваемых говорил правду? Решение: Пусть показания свидетелей будут назваться буквами К, Ж и Д. Тогда известно, что: 1. Если Клод сказал правду (К), то Жак лжет (¬Ж), иначе (если Клод солгал, ¬К), то Жак сказал правду (Ж) 2. Если Жак сказал правду (Ж), тогда Дик не прав, (¬Д), иначе лжет Жак (¬Ж), а Дик – прав (Д) 3. Если лжет Дик (Д), то Клод и Жак правы (Ж и К), иначе последние лгут (¬(Ж и К)), а Дик – прав (Д)

31 Задача 19. Решение Выразим эти высказывания на формальном языке логики: 1. К ¬Ж ¬К Ж 2. Ж ¬Д ¬Ж Д 3. Д ¬К ¬Ж ¬Д (К Ж) Задача будет решена, если все три высказывания будут истинны, т.е. истинна их конъюнкция: (К·¬Ж ¬К·Ж) (Ж·¬Д ¬Ж·Д) (Д·¬К·¬Ж ¬Д·(К Ж)) (К·¬Ж · Ж·¬Д К·¬Ж · ¬Ж·Д ¬К·Ж · Ж·¬Д ¬К·Ж · ¬Ж·Д) (К·¬Ж · Ж·¬Д К·¬Ж · ¬Ж·Д ¬К·Ж · Ж·¬Д ¬К·Ж · ¬Ж·Д) (Д·¬К·¬Ж ¬Д·К ¬Д·Ж) (Д·¬К·¬Ж ¬Д·К ¬Д·Ж) (К·¬Ж · ¬Ж·Д ¬К·Ж · Ж·¬Д) (Д·¬К·¬Ж ¬Д·К ¬Д·Ж) (К·¬Ж · ¬Ж·Д·Д·¬К·¬Ж К·¬Ж · ¬Ж·Д·¬Д·Ж К·¬Ж · ¬Ж·Д·¬Д·Ж ¬К·Ж · Ж·¬Д·Д·¬К·¬Ж ¬К·Ж · Ж·¬Д·¬Д·Ж ¬К·Ж · Ж·¬Д·¬Д·Ж ¬К·Ж · Ж·¬Д·¬Д·Ж ¬К·Ж · Ж·¬Д·¬Д·Ж ¬К ¬Д Ж Итак, только Жак говорил правду (К·¬Ж ¬К·Ж) (Ж·¬Д ¬Ж·Д) (Д·¬К·¬Ж ¬Д·(К Ж))

32 Задача 20. Нерадивый студент сдает компьютерный тест. Все ответы сводятся к ответам типа «Да» или «Нет». Один правильный ответ – один балл. Студенту известно, что: Первый и последний ответы противоположны Первый и последний ответы противоположны Второй и четвертый ответы одинаковы Второй и четвертый ответы одинаковы Хотя бы один из первых двух ответов – «Да» Хотя бы один из первых двух ответов – «Да» Если четвертый ответ «Да», то пятый – «Нет» Если четвертый ответ «Да», то пятый – «Нет» Ответов «Да» больше, чем ответов «Нет» Ответов «Да» больше, чем ответов «Нет» Требуется получить 4 или более баллов

33 Задача 20. Решение Пусть: A.Первый ответ «Да» B.Второй ответ «Да» C.Третий ответ «Да» D.Четвертый ответ «Да» E.Пятый ответ «Да» Тогда: 1.A ¬E 2.B D 3.A B 4.D ¬E ¬D ¬E Отсюда: (A ¬E) (B D) (A B) (¬D ¬E) A¬EBD (A B) (¬D ¬E) A¬EBD (A¬D A¬E B¬D B¬E) A¬EBD A¬EBD A¬EBD

34 Таблицы истинности Конъюнкция A0011A0011 B0101B0101 A B 0 1 Дизъюнкция A0011A0011 B0101B0101 А В 0 1 Импликация A0011A0011 B0101B0101 A B Эквиваленция A0011A0011 B0101B0101 А В