Алгебра логики
<<  Понятие об алгебре высказываний Алгебра высказываний  >>
Алгебра высказываний
Алгебра высказываний
А ? В «Учащийся Иванов хорошо успевает по английскому языку и любит
А ? В «Учащийся Иванов хорошо успевает по английскому языку и любит
¬p ¬(¬p)
¬p ¬(¬p)
А ? В, где А = «45 кратно 3», В = «42 кратно 3» А
А ? В, где А = «45 кратно 3», В = «42 кратно 3» А
Задача 4: Составьте таблицу истинности для функции А
Задача 4: Составьте таблицу истинности для функции А
Если 2
Если 2
Задача 6: Какие из следующих высказываний противоречивы
Задача 6: Какие из следующих высказываний противоречивы
А ? с а
А ? с а
p ? p p
p ? p p
x ? (y
x ? (y
X ? (y
X ? (y
(X ? y)
(X ? y)
X ? (y
X ? (y
X ? y
X ? y
(X ? y)
(X ? y)
((X ? y)
((X ? y)
(А ? в)
(А ? в)
(А ? ¬а)
(А ? ¬а)
А ? (А
А ? (А
A 0 0 1 1
A 0 0 1 1
A 0 0 1 1
A 0 0 1 1
A 0 0 1 1
A 0 0 1 1
A 0 0 1 1
A 0 0 1 1
Задача 17:
Задача 17:
Пусть: М1 = «Математика первым уроком» М2 = «Математика вторым уроком»
Пусть: М1 = «Математика первым уроком» М2 = «Математика вторым уроком»
(М1 ? М2)
(М1 ? М2)
Задача 18:
Задача 18:
Задача 18
Задача 18
Задача 18
Задача 18
Задача 19
Задача 19
Выразим эти высказывания на формальном языке логики: К
Выразим эти высказывания на формальном языке логики: К
Задача 20
Задача 20
Пусть: Первый ответ «Да» Второй ответ «Да» Третий ответ «Да» Четвертый
Пусть: Первый ответ «Да» Второй ответ «Да» Третий ответ «Да» Четвертый
Таблицы истинности
Таблицы истинности

Презентация на тему: «Алгебра высказываний». Автор: Кабинет информатики. Файл: «Алгебра высказываний.ppt». Размер zip-архива: 360 КБ.

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

содержание презентации «Алгебра высказываний.ppt»
СлайдТекст
1 Алгебра высказываний

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

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

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

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

работать на компьютере»

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

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

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

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

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

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

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

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

3 ¬p ¬(¬p)

¬p ¬(¬p)

p ? q p ? ¬q

p ? q ¬p ? q

¬p ? ¬q q ? p

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

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

4 А ? В, где А = «45 кратно 3», В = «42 кратно 3» А

А ? В, где А = «45 кратно 3», В = «42 кратно 3» А

¬В, где А = «45 кратно 3», В = «12 кратно 3» А ? В, где А = «2 < 5», В = «2 = 5» (A ? В) ? С, где А = «212 делится на 3», В = «212 делится на 4» и С = «212 делится на 12» А ? В ? С, где А = «212 – трехзначное число», В = «212 делится на 3» и С = «212 делится на 4»

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

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

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

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

¬В

A 0 0 1 1

B 0 1 0 1

¬B 1 0 1 0

A ? ¬B 1 0 1 1

6 Если 2

Если 2

2 = 4, то 2 < 3 если 2 ? 2 = 4, то 2 > 3 если 2 ? 2 = 5, то 2 < 3 если 2 ? 2 = 5, то 2 > 3

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

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

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

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

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

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

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

8 А ? с а

А ? с а

d b ? c c ? d

А ? с а ? d b ? c c ? d

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

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

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

¬А ¬b ¬c ¬d

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

9 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)

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

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

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

10 x ? (y

x ? (y

z) (x ? y) ? z ? z) x ? y ? z (x ? y) ? (z ? ¬y) ((x ? y) ? z) ? ((x ? z) ? (y ? z))

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

11 X ? (y

X ? (y

z) x ? (1 ? 1) x ? 1 0 ? 1 0 (ложь)

x ? (y ? z)

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

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

12 (X ? y)

(X ? y)

z (0 ? 1) ? z 0 ? z 0 ? 1 0 (ложь)

(x ? y) ? z

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

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

13 X ? (y

X ? (y

z) x ? (1 ? 1) x ? 1 0 ? 1 1 (истина)

x ? (y ? z)

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

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

14 X ? y

X ? y

z 0 ? 1 ? z 0 ? z 0 ? 1 1 (истина)

x ? y ? z

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

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

15 (X ? y)

(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.5: Даны значения: x = 0, y = 1, z = 1. Определите логические значения высказываний

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

16 ((X ? y)

((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))

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

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

17 (А ? в)

(А ? в)

(а ? ¬в) а ? (в ? ¬в) а ? (в ? ¬в) а ? ( 1 ) а

(А ? в) ? (а ? ¬в)

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

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

18 (А ? ¬а)

(А ? ¬а)

в ( 1 ) ? в в

(А ? ¬а) ? в

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

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

19 А ? (А

А ? (А

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

А ? (а ? в) ? (в ? ¬в)

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

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

20 A 0 0 1 1

A 0 0 1 1

B 0 1 0 1

A ? B 0 0 0 1

A ? (а ? b) 0 0 1 1

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

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

21 A 0 0 1 1

A 0 0 1 1

B 0 1 0 1

A ? B 0 1 1 1

A ? (а ? b) 0 0 1 1

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

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

22 A 0 0 1 1

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

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

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

23 A 0 0 1 1

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

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

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

24 Задача 17:

Задача 17:

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

25 Пусть: М1 = «Математика первым уроком» М2 = «Математика вторым уроком»

Пусть: М1 = «Математика первым уроком» М2 = «Математика вторым уроком»

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

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

26 (М1 ? М2)

(М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 вариант – Информатика, Математика, Физика

Задача 17. Решение. Раскрытие скобок

М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:

Задача 18:

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

28 Задача 18

Задача 18

Решение

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

29 Задача 18

Задача 18

Решение (продолжение)

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

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

(¬(А ? в) ? ¬а) ? (¬(¬а) ? (а ? в) ) ? ¬(¬а)

30 Задача 19

Задача 19

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

31 Выразим эти высказывания на формальном языке логики: К

Выразим эти высказывания на формальном языке логики: К

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

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

(К·¬ж ? ¬к·ж) ? (ж·¬д ? ¬ж·д) ? (д·¬к·¬ж ? ¬д·(к ? ж))

32 Задача 20

Задача 20

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

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

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

ответ «Да» Пятый ответ «Да»

Тогда: A ? ¬E B ? D A ? B D ? ¬E ? ¬D ? ¬E Отсюда:

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

(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 Таблицы истинности

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

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

Конъюнкция

Дизъюнкция

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

«Алгебра высказываний»
http://900igr.net/prezentacija/algebra/algebra-vyskazyvanij-85274.html
cсылка на страницу
Урок

Алгебра

35 тем
Слайды