Презентация "Алгебра высказываний. Решение логических задач" – проект, доклад

Алгебра высказываний

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

Задача 1: Составьте сложное высказывание в словесной форме из простых, заданных математическим формулировкам:

Высказывание А: «Учащийся Иванов хорошо успевает по английскому языку» Высказывание В: «Учащийся Иванов любит работать на компьютере».

А  В «Учащийся Иванов хорошо успевает по английскому языку и любит работать на компьютере»

А  В «Учащийся Иванов хорошо успевает по английскому языку или любит работать на компьютере»

А  ¬В «Учащийся Иванов хорошо успевает по английскому языку и не любит работать на компьютере»

¬(А  В) «не (учащийся Иванов хорошо успевает по английскому языку и любит работать на компьютере)» ≡ «Учащийся Иванов плохо успевает по английскому языку и не любит работать на компьютере»

А → В «учащийся Иванов хорошо успевает по английскому языку, поэтому он любит работать на компьютере»

А → ¬В «учащийся Иванов хорошо успевает по английскому языку, поэтому он не любит работать на компьютере»

В → А «учащийся Иванов хорошо успевает по английскому языку, потому, что он любит работать на компьютере»

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

¬p ¬(¬p)

«Я не учусь в школе» «не(Я не учусь в школе)» ≡ «Я учусь в школе» «Я учусь в школе и люблю информатику» «Я учусь в школе и не люблю информатику» «Я учусь в школе или люблю информатику» «Я не учусь в школе или люблю информатику» «Я не учусь в школе или я не люблю информатику» «Я люблю информатику, потому, что учусь в школе»

p  q p  ¬q p  q ¬p  q ¬p  ¬q q → p

Задача 3: Обозначьте элементарные высказывания буквами и запишите высказывания на формальном языке алгебры высказываний

45 кратно 3 и 42 кратно 3 45 кратно 3 и 12 не кратно 3 2 ≤ 5 если 212 делится на 3 и на 4, то 212 делится на 12 212 – трехзначное число, которое делится на 3 и на 4

А  В, где А = «45 кратно 3», В = «42 кратно 3» А  ¬В, где А = «45 кратно 3», В = «12 кратно 3» А  В, где А = «2

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

A 0 0 1 1 B 0 1 0 1 ¬B 1 0 1 0 A  ¬B 1 0 1 1

Задача 5: Какие из следующих импликаций истинны

если 2  2 = 4, то 2 3 если 2  2 = 5, то 2 3

истина ложь истина истина

Таблицы истинности

Задача 6: Какие из следующих высказываний противоречивы

a = 1, a  b = 0 a = 1, a  b = 0 a = 1, a  b = 1 a = 1, a  b = 1 a = 0, a  b = 1 a = 0, a  b = 1 a = 0, a  b = 0 a = 0, a  b = 0

истина ложь истина истина ложь истина истина истина

Задача 7: Пусть: а = «7 – простое», b = «7 – составное», с = «8 – простое» и d = «8 – составное» Определите истинность высказываний

а  с а  d b  c c  d

ложь истина ложь ложь

а  с а  d b  c c  d

истина истина ложь истина

¬а ¬b ¬c ¬d

ложь истина истина ложь

истина истина истина ложь истина истина истина

истина истина истина ложь ложь истина истина

Задача 8: Какие из следующих высказываний истинны

p → p p  ¬p ¬(p  ¬p) p  ¬p ¬p → p p  p (p  p) → p

¬(p  (p  ¬p)) (p → p)  ¬p p  p  (¬p → p  p) p  (p  ¬p) ¬(¬p → p) ¬(p  ¬p) (p  p) → (p  p)

Задача 9: Даны значения: x = 0, y = 1, z = 1. Определите логические значения высказываний

x  (y  z) (x  y)  z x → (y → z) x  y → z (x  y)  (z  ¬y) ((x  y)  z)  ((x  z)  (y  z))

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

x  (y  z) x  (1  1) x  1 0  1 0 (ложь)

x  (y  z)

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

(x  y)  z (0  1)  z 0  z 0  1 0 (ложь)

(x  y)  z

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

x → (y → z) x → (1 → 1) x → 1 0 → 1 1 (истина)

x → (y → z)

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

x  y → z 0  1 → z 0 → z 0 → 1 1 (истина)

x  y → z

Задача 9.5: Даны значения: x = 0, y = 1, z = 1. Определите логические значения высказываний

(x  y)  (z  ¬y) (x  y)  (z  ¬1) (x  y)  (z  0) (x  y)  (z  0) (0  1)  (1  0) 0  1 0 (ложь)

(x  y)  (z  ¬y)

Задача 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) 1  1 1 (истина)

((x  y)  z)  ((x  z)  (y  z))

Задача 10: Упростите выражение: (А  В)  (А  ¬В)

(А  В)  (А  ¬В) А  (В  ¬В) А  (В  ¬В) А  ( 1 ) А

(А  В)  (А  ¬В)

Задача 11: Упростите выражение: (А  ¬А)  В

(А  ¬А)  В ( 1 )  В В

(А  ¬А)  В

Задача 12: Упростите выражение: А  (А  В)  (В  ¬В)

А  (А  В)  (В  ¬В) А  (А  В)  ( 1 ) А  (А  В)  1 {з-н поглощения} А  1 А

А  (А  В)  (В  ¬В)

Задача 13: Доказать справедливость закона поглощения для дизъюнкции: А  (А  В) ≡ А по таблицам истинности

A  B 0 0 0 1 A  (А  B) 0 0 1 1

Задача 14: Доказать справедливость закона поглощения для конъюнкции: А  (А  В) ≡ А по таблицам истинности

A  B 0 1 1 1 A  (А  B) 0 0 1 1

Задача 15: Доказать справедливость первого закона де Моргана: ¬(А  В) ≡ ¬А  ¬В по таблицам истинности

¬A 1 1 0 0 ¬(A  B) 1 0 0 0 ¬A  ¬B 1 0 0 0

Задача 16: Доказать справедливость второго закона де Моргана: ¬(А  В) ≡ ¬А  ¬В по таблицам истинности

¬(A  B) 1 1 1 0 ¬A  ¬B 1 1 1 0

Задача 17:

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

Задача 17. Решение

Пусть: М1 = «Математика первым уроком» М2 = «Математика вторым уроком» И1 = «Информатика первым уроком» И3 = «Информатика третьим уроком» Ф2 = «Физика вторым уроком» Ф3 = «Физика третьим уроком» Тогда расписание можно свести к выражению: (М1  М2)  (И1  И3)  (Ф2  Ф3)

Задача 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

Задача 18:

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

Задача 18. Решение

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

Задача 18. Решение (продолжение)

(¬(А  В)  ¬А)  (¬(¬А)  (А  В) )  ¬(¬А) Упрощаем выражение: ((¬А  ¬В)  ¬А)  (А  (А  В))  А 

(¬(А  В)  ¬А)  (¬(¬А)  (А  В) )  ¬(¬А)

((¬А  ¬В)  ¬А)  (А  (А  В))  А  ((¬А  ¬А)  (¬В  ¬А))  (А  А  В  А)  (¬А  (¬В  ¬А))  (А  В)  ¬А  (А  В)  (¬А  А)  (¬А  В)  ¬А  В Т.о. выражение ¬А  В соответствует высказыванию: «Физика в кабинете 1 и информатика в кабинете 2»

Задача 19.

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

Задача 19. Решение

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

(К·¬Ж  ¬К·Ж)  (Ж·¬Д  ¬Ж·Д)  (Д·¬К·¬Ж  ¬Д·(К  Ж))

Задача 20.

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

Задача 20. Решение

Пусть: Первый ответ «Да» Второй ответ «Да» Третий ответ «Да» Четвертый ответ «Да» Пятый ответ «Да»

Тогда: A  ¬E B  D A  B 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

Конъюнкция Дизъюнкция А  В 0 1 1 1 Импликация A → B 1 1 0 1 Эквиваленция А  В 1 0 0 1

1 2 3 4 5 6 7 8 9 9.1 9.2 9.3 9.4 9.5 9.6

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24