Презентация на тему: Алгебра высказываний. Решение логических задач

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

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

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

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

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

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

Задача 6: Какие из следующих высказываний противоречивы a = 1, a b = 0a = 1, a b = 0a = 1, a b = 1a = 1, a b = 1a = 0, a b = 1a = 0, a b = 1a = 0, a b = 0a = 0, a b = 0 истиналожьистинаистиналожьистинаистинаистина

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

Задача 8: Какие из следующих высказываний истинны ¬(p (p ¬p))(p → p) ¬pp 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) zx → (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 10 10 (ложь)

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

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

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

Задача 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 10 (ложь)

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

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

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

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

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

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

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

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

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

Пусть:М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», В= «Информатика в кабинете 2»Тогда:¬А= «Физика в кабинете 1», ¬В= «Физика в кабинете 2»Высказывание «В одном из этих двух кабинетов точно есть кабинет информатики»: Х = А В,Высказывание «Кабинет информатики не здесь»: Y = ¬АИсходя из условия: X Y, т.е. Y = (¬X Y) (¬Y X ) (¬X Y) (¬Y X ) ¬YЗаменяем X и Y их выражениями:(¬(А В) ¬А) (¬(¬А) (А В) ) ¬(¬А)

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

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

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

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

Пусть:Первый ответ «Да»Второй ответ «Да»Третий ответ «Да»Четвертый ответ «Да»Пятый ответ «Да» Тогда:A ¬EB DA BD → ¬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

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