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


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


Подписи к слайдам:
Логические основы построения компьютера.

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

  • Решение логических задач
  • Автор:
  • Сергеев Евгений Викторович
  • МОУ СОШ №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 < 5», В = «2 = 5»
  • (A  В) → С, где А = «212 делится на 3», В = «212 делится на 4» и С = «212 делится на 12»
  • А  В  С, где А = «212 – трехзначное число», В = «212 делится на 3» и С = «212 делится на 4»

Задача 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 = 4, то 2 > 3
  • если 2  2 = 5, то 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
  • 0
  • 0
  • 1
  • 1
  • B
  • 0
  • 1
  • 0
  • 1
  • A  B
  • 0
  • 0
  • 0
  • 1
  • A  (А  B)
  • 0
  • 0
  • 1
  • 1

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

  • Таблицы истинности
  • A
  • 0
  • 0
  • 1
  • 1
  • B
  • 0
  • 1
  • 0
  • 1
  • A  B
  • 0
  • 1
  • 1
  • 1
  • A  (А  B)
  • 0
  • 0
  • 1
  • 1

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

  • Таблицы истинности
  • A
  • 0
  • 0
  • 1
  • 1
  • B
  • 0
  • 1
  • 0
  • 1
  • ¬A
  • 1
  • 1
  • 0
  • 0
  • ¬B
  • 1
  • 0
  • 1
  • 0
  • A  B
  • 0
  • 1
  • 1
  • 1
  • ¬(A  B)
  • 1
  • 0
  • 0
  • 0
  • ¬A  ¬B
  • 1
  • 0
  • 0
  • 0

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

  • Таблицы истинности
  • A
  • 0
  • 0
  • 1
  • 1
  • B
  • 0
  • 1
  • 0
  • 1
  • ¬A
  • 1
  • 1
  • 0
  • 0
  • ¬B
  • 1
  • 0
  • 1
  • 0
  • A  B
  • 0
  • 0
  • 0
  • 1
  • ¬(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

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

  • Конъюнкция
  • A
  • 0
  • 0
  • 1
  • 1
  • B
  • 0
  • 1
  • 0
  • 1
  • A  B
  • 0
  • 0
  • 0
  • 1
  • Дизъюнкция
  • A
  • 0
  • 0
  • 1
  • 1
  • B
  • 0
  • 1
  • 0
  • 1
  • А  В
  • 0
  • 1
  • 1
  • 1
  • Импликация
  • A
  • 0
  • 0
  • 1
  • 1
  • B
  • 0
  • 1
  • 0
  • 1
  • A → B
  • 1
  • 1
  • 0
  • 1
  • Эквиваленция
  • A
  • 0
  • 0
  • 1
  • 1
  • B
  • 0
  • 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