Алгебра логики
<<  Решение логических задач Логические задачи на уроках математики в начальной школе  >>
Решение логических задач
Решение логических задач
Логические функции одной переменной
Логические функции одной переменной
Логические функции двух переменных
Логические функции двух переменных
Логическое умножение Коньюнкция
Логическое умножение Коньюнкция
Конъюнкция двух логических переменных истинна тогда и только тогда,
Конъюнкция двух логических переменных истинна тогда и только тогда,
Свойства конъюнкции
Свойства конъюнкции
Логическое сложение Дизъюнкция
Логическое сложение Дизъюнкция
Дизъюнкция двух логических переменных ложна тогда и только тогда,
Дизъюнкция двух логических переменных ложна тогда и только тогда,
Свойства дизъюнкции
Свойства дизъюнкции
Логическое отрицание Инверсия
Логическое отрицание Инверсия
Инверсия логической переменной истинна, если сама переменная ложна, и,
Инверсия логической переменной истинна, если сама переменная ложна, и,
Логическое следование Импликация
Логическое следование Импликация
A
A
Логическая равносильность Эквиваленция
Логическая равносильность Эквиваленция
Выражение A
Выражение A
Сложение по модулю «2»
Сложение по модулю «2»
Выражение A
Выражение A
A+B=B+A
A+B=B+A
(A+B)+C=A+(B+C) (A
(A+B)+C=A+(B+C) (A
(A+B)?C=(A
(A+B)?C=(A
Закон инверсии Формулы де Моргана
Закон инверсии Формулы де Моргана
Формулы склеивания (закон исключения)
Формулы склеивания (закон исключения)
Формулы поглощения
Формулы поглощения
Решение логических задач
Решение логических задач
1. Является ли данная функция тождественно-истинной
1. Является ли данная функция тождественно-истинной
1 способ
1 способ
2
2
A
A
A
A
A
A
A
A
A
A
A
A
2. Следующие два высказывания истинны: «неверно, что если магазин А
2. Следующие два высказывания истинны: «неверно, что если магазин А
«Если магазин А организует распродажу, то магазин С тоже» A
«Если магазин А организует распродажу, то магазин С тоже» A
Из двух магазинов В и С организует распродажу только один
Из двух магазинов В и С организует распродажу только один
Это возможно только в одном случае, когда A=1, B=1, С=0
Это возможно только в одном случае, когда A=1, B=1, С=0
3. На олимпиаде по информатике студенты A, B, C и D заняли первые
3. На олимпиаде по информатике студенты A, B, C и D заняли первые
D – первый или B – второй: D1+B2=1 C – первый или A – четвертый:
D – первый или B – второй: D1+B2=1 C – первый или A – четвертый:
3. Сформулируйте на естественном языке отрицание следующего
3. Сформулируйте на естественном языке отрицание следующего
«Виктор пойдет на рыбалку» - A «Будет солнечная погода» - B «Будет
«Виктор пойдет на рыбалку» - A «Будет солнечная погода» - B «Будет
Будет солнечная погода и нежарко, а Виктор не пойдет на рыбалку
Будет солнечная погода и нежарко, а Виктор не пойдет на рыбалку
Дизъюнктивно-нормальная форма
Дизъюнктивно-нормальная форма
Конъюнктивно-нормальная форма
Конъюнктивно-нормальная форма
Табличный способ приведения к СДНФ
Табличный способ приведения к СДНФ
Табличный способ приведения к СКНФ
Табличный способ приведения к СКНФ
Если условится из двух форм, СДНФ и СКНФ, отдавать предпочтение той,
Если условится из двух форм, СДНФ и СКНФ, отдавать предпочтение той,
Дана таблица истинности логической функции от трех переменных
Дана таблица истинности логической функции от трех переменных
A
A
4. Построить схему электрической цепи для подъезда трехэтажного здания
4. Построить схему электрической цепи для подъезда трехэтажного здания
Сначала построим таблицу истинности для требуемой функции
Сначала построим таблицу истинности для требуемой функции
x1
x1
Теперь по таблице истинности построим дизъюнктивно-нормальную форму
Теперь по таблице истинности построим дизъюнктивно-нормальную форму
Решение логических задач
Решение логических задач
Стрелка Пирса (символ Лукашевича)
Стрелка Пирса (символ Лукашевича)
Стрелка Пирса (символ Лукашевича)
Стрелка Пирса (символ Лукашевича)
Штрих Шеффера
Штрих Шеффера
Штрих Шеффера
Штрих Шеффера
Дана таблица истинности логической функции от трех переменных
Дана таблица истинности логической функции от трех переменных
A
A
A
A
5. После традиционного вечера встречи с выпускниками школы в
5. После традиционного вечера встречи с выпускниками школы в
Алгоритм решения задач на приведение множеств во взаимно-однозначное
Алгоритм решения задач на приведение множеств во взаимно-однозначное
Правила экстраполяции в плоскости
Правила экстраполяции в плоскости
Правило множественного проектирования
Правило множественного проектирования
Предмет
Предмет
Иван преподает химию и живет в Витебске
Иван преподает химию и живет в Витебске

Презентация: «Решение логических задач». Автор: PohodinaEN. Файл: «Решение логических задач.ppt». Размер zip-архива: 335 КБ.

Решение логических задач

содержание презентации «Решение логических задач.ppt»
СлайдТекст
1 Решение логических задач

Решение логических задач

2 Логические функции одной переменной

Логические функции одной переменной

x

F1

F2

F3

F4

0

0

0

1

1

1

0

1

0

1

3 Логические функции двух переменных

Логические функции двух переменных

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

x1

x2

F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

F11

F12

F13

F14

F15

F16

4 Логическое умножение Коньюнкция

Логическое умножение Коньюнкция

conjunctio – лат. – связываю Соединение двух простых высказываний A и B в одно составное с помощью союза «и» (а, но) называют логическим умножением или конъюнкцией, а результат операции — логическим произведением. Указание о логическом перемножении простых высказываний A и B обозначается так: AB, A?B, A&B.

5 Конъюнкция двух логических переменных истинна тогда и только тогда,

Конъюнкция двух логических переменных истинна тогда и только тогда,

когда оба высказывания истинны. Это определение можно обобщить для любого количества логических переменных, объединенных конъюнкцией. A?B?C=1, только если A=1, B=1, C=1.

A?B

A

B

0

0

0

0

1

0

1

0

0

1

1

1

6 Свойства конъюнкции

Свойства конъюнкции

Закон исключения констант

Закон исключения констант

Закон равносильности

Закон противоречия

7 Логическое сложение Дизъюнкция

Логическое сложение Дизъюнкция

disjunctio – лат. – различаю Соединение двух простых высказываний A и B в одно составное с помощью союза «или», употребляемого в неисключающем смысле, называется логическим сложением или дизъюнкцией, а полученное составное высказывание — логической суммой. Указание о необходимости выполнить логическое сложение высказываний A и B записывается так: A+B или A?B.

8 Дизъюнкция двух логических переменных ложна тогда и только тогда,

Дизъюнкция двух логических переменных ложна тогда и только тогда,

когда оба высказывания ложны. Это определение можно обобщить для любого количества логических переменных, объединенных дизъюнкцией. A+B+C=0, только если A=0, B=0, C=0.

A

B

A+B

0

0

0

0

1

1

1

0

1

1

1

1

9 Свойства дизъюнкции

Свойства дизъюнкции

Закон исключения констант

Закон исключения констант

Закон равносильности

Закон исключенного третьего

10 Логическое отрицание Инверсия

Логическое отрицание Инверсия

inversio – лат. – переворачиваю Присоединение частицы «не» к сказуемому данного простого высказывания A называется операцией логического отрицания или инверсией или Присоединение слов «Неверно, что …» ко всему данному высказыванию A называется операцией логического отрицания Указание выполнить логическое отрицание над высказыванием A записывается так:

11 Инверсия логической переменной истинна, если сама переменная ложна, и,

Инверсия логической переменной истинна, если сама переменная ложна, и,

наоборот, инверсия ложна, если переменная истинна. закон двойного отрицания

A

0

1

1

0

12 Логическое следование Импликация

Логическое следование Импликация

implicatio – лат. – тесно связываю Логическое следование соответствует обороту «если…, то…», обозначается A?B или A?B. Читается: если А, то В; из А следует В; А имплицирует В; А достаточно для В; В необходимо для А; А только тогда, когда В.

13 A

A

B

A ? B

0

0

1

0

1

1

1

0

0

1

1

1

Высказывание A?B ложно в том и только в том случае, когда условие (первое высказывание A) истинно, а следствие (второе высказывание B) ложно.

Правило контрапозиции (перевертывания)

Представление импликации через конъюнкцию, дизъюнкцию и инверсию

14 Логическая равносильность Эквиваленция

Логическая равносильность Эквиваленция

Aequivalens – фр. – Равноценное или равнозначное соответствует оборотам речи: «тогда и только тогда» «в том и только в том случае» обозначается A?B или A?B.

15 Выражение A

Выражение A

B истинно в том и только в том случае, когда оба исходных высказывания одновременно истинны или одновременно ложны.

A

B

A ? B

0

0

1

0

1

0

1

0

0

1

1

1

16 Сложение по модулю «2»

Сложение по модулю «2»

Соединение двух простых высказываний A и B в одно составное с помощью союза «или», употребляемого в исключающем смысле, называется строгой дизъюнкцией, сложение по модулю «2», исключающее «или». Обозначается A?B.

17 Выражение A

Выражение A

B истинно в том и только в том случае, когда значения исходных высказываний не равны между собой.

A ? B

A

B

0

0

0

0

1

1

1

0

1

1

1

0

18 A+B=B+A

A+B=B+A

A?B=B?A

Закон коммутативности Переместительный закон

19 (A+B)+C=A+(B+C) (A

(A+B)+C=A+(B+C) (A

B) ? C= A ?(B ? C)

Сочетательный закон Закон ассоциативности

20 (A+B)?C=(A

(A+B)?C=(A

C)+(B?C) (A?B)+C=(A+C)?(B+C)

Распределительный закон Закон дистрибутивности

21 Закон инверсии Формулы де Моргана

Закон инверсии Формулы де Моргана

22 Формулы склеивания (закон исключения)

Формулы склеивания (закон исключения)

23 Формулы поглощения

Формулы поглощения

24 Решение логических задач
25 1. Является ли данная функция тождественно-истинной

1. Является ли данная функция тождественно-истинной

Способы решения: Упрощение функции Построение таблицы истинности

26 1 способ

1 способ

27 2

2

4

5

3

1

2 способ

28 A

A

B

C

1

2

3

4

5

0

0

0

0

0

1

0

1

0

0

1

1

1

0

0

1

0

1

1

1

0

1

1

1

29 A

A

B

C

1

2

3

4

5

0

0

0

0

0

0

1

0

0

1

0

1

0

1

1

1

1

0

0

1

1

0

1

1

1

1

0

1

1

1

1

1

30 A

A

B

C

1

2

3

4

5

0

0

0

0

1

0

0

1

0

1

0

1

0

1

0

0

1

1

1

0

1

0

0

1

0

1

0

1

1

0

1

1

0

1

0

1

1

1

1

0

31 A

A

B

C

1

2

3

4

5

0

0

0

0

1

1

0

0

1

0

1

1

0

1

0

1

0

0

0

1

1

1

0

1

1

0

0

1

0

0

1

0

1

1

0

1

1

1

0

1

0

0

1

1

1

1

0

1

32 A

A

B

C

1

2

3

4

5

0

0

0

0

1

1

1

0

0

1

0

1

1

0

0

1

0

1

0

0

1

0

1

1

1

0

1

0

1

0

0

1

0

0

0

1

0

1

1

0

1

1

1

1

0

1

0

0

0

1

1

1

1

0

1

1

33 A

A

B

C

1

2

3

4

5

0

0

0

0

1

1

1

1

0

0

1

0

1

1

0

1

0

1

0

1

0

0

1

0

0

1

1

1

0

1

0

1

1

0

0

1

0

0

0

1

1

0

1

1

0

1

1

1

1

1

0

1

0

0

0

1

1

1

1

1

0

1

1

1

34 2. Следующие два высказывания истинны: «неверно, что если магазин А

2. Следующие два высказывания истинны: «неверно, что если магазин А

организует распродажу, то магазин С тоже»; «из двух магазинов В и С организует распродажу только один». Какие магазины организуют распродажу?

35 «Если магазин А организует распродажу, то магазин С тоже» A

«Если магазин А организует распродажу, то магазин С тоже» A

C «Неверно, что если магазин А организует распродажу, то магазин С тоже» Из условия известно, что это высказывание истинно. Следовательно:

36 Из двух магазинов В и С организует распродажу только один

Из двух магазинов В и С организует распродажу только один

37 Это возможно только в одном случае, когда A=1, B=1, С=0

Это возможно только в одном случае, когда A=1, B=1, С=0

То есть, магазины A и B проводят распродажу, а магазин С – нет.

38 3. На олимпиаде по информатике студенты A, B, C и D заняли первые

3. На олимпиаде по информатике студенты A, B, C и D заняли первые

четыре места. Когда их спросили о распределении мест, они дали три ответа: D – первый или B – второй; C – первый или A – четвертый; D – второй или B – третий. Как распределились места, если в каждом ответе только одно утверждение истинно?

39 D – первый или B – второй: D1+B2=1 C – первый или A – четвертый:

D – первый или B – второй: D1+B2=1 C – первый или A – четвертый:

C1+A4=1 D – второй или B – третий: D2+B3=1

(D1+B2)(C1+A4)(D2+B3)=1

(D1C1+B2C1+D1A4+B2A4)(D2+B3)=1

B2C1D2+D1A4D2+B2A4D2+B2C1B3+D1A4B3+B2A4B3=1

D1A4B3=1

Следовательно, D – первый, С – второй, B – третий, A – четвертый.

40 3. Сформулируйте на естественном языке отрицание следующего

3. Сформулируйте на естественном языке отрицание следующего

высказывания: "Виктор пойдет на рыбалку только при солнечной погоде, если не будет жарко".

41 «Виктор пойдет на рыбалку» - A «Будет солнечная погода» - B «Будет

«Виктор пойдет на рыбалку» - A «Будет солнечная погода» - B «Будет

жарко» - C Перефразируем высказывание: «Если будет солнечная погода и не будет жарко, то Виктор пойдет на рыбалку». Тогда исходное высказывание имеет вид:

42 Будет солнечная погода и нежарко, а Виктор не пойдет на рыбалку

Будет солнечная погода и нежарко, а Виктор не пойдет на рыбалку

43 Дизъюнктивно-нормальная форма

Дизъюнктивно-нормальная форма

ДНФ — является логической суммой элементарных конъюнкций. Совершенная ДНФ – логическая сумма элементарных конъюнкций, в каждой из которых присутствуют все переменные данной функции.

44 Конъюнктивно-нормальная форма

Конъюнктивно-нормальная форма

КНФ — является логическим произведением элементарных дизъюнкций. Совершенная КНФ – логическое произведение элементарных дизъюнкций, в каждой из которых присутствуют все переменные данной функции.

45 Табличный способ приведения к СДНФ

Табличный способ приведения к СДНФ

Составляем таблицу истинности данной функции. Рассматриваем только те строки таблицы, в которых функция принимает значение 1. Каждой такой строке соответствует конъюнкция всех аргументов (без повторений). Причем аргумент, принимающий значение 0, входит в нее с отрицанием; значение 1 – без отрицания. Наконец, образуем дизъюнкцию всех полученных конъюнкций.

46 Табличный способ приведения к СКНФ

Табличный способ приведения к СКНФ

Составляем таблицу истинности данной функции. Рассматриваем только те строки таблицы, в которых функция принимает значение 0. Каждой такой строке соответствует дизъюнкция всех аргументов (без повторений). Причем аргумент, принимающий значение 0, входит в нее без отрицания; значение 1 – с отрицанием. Наконец, образуем конъюнкцию всех полученных дизъюнкций.

47 Если условится из двух форм, СДНФ и СКНФ, отдавать предпочтение той,

Если условится из двух форм, СДНФ и СКНФ, отдавать предпочтение той,

которая содержит меньше букв, то СДНФ предпочтительней, если в столбце значений функции таблицы истинности меньше единиц; СКНФ – если в этом столбце меньше нулей.

48 Дана таблица истинности логической функции от трех переменных

Дана таблица истинности логической функции от трех переменных

Построить логическую формулу, реализующую эту функцию.

A

B

C

F(A, B, C)

0

0

0

1

0

0

1

1

0

1

0

1

0

1

1

1

1

0

0

0

1

0

1

0

1

1

0

1

1

1

1

1

49 A

A

B

C

F

0

0

0

1

1

0

0

1

1

1

0

1

0

1

1

0

1

1

1

1

1

0

0

0

0

1

0

1

0

0

1

1

0

0

1

1

1

1

0

1

50 4. Построить схему электрической цепи для подъезда трехэтажного здания

4. Построить схему электрической цепи для подъезда трехэтажного здания

чтобы выключателем на любом этаже можно было бы включить и выключить свет во всем подъезде.

51 Сначала построим таблицу истинности для требуемой функции

Сначала построим таблицу истинности для требуемой функции

Переменными функции будут выключатели на каждом этаже подъезда. Свет будет включаться при условии, что во включенном состоянии находятся нечетное количество выключателей. Свет будет выключен, если во включенном состоянии будут четное количество выключателей или ни одного.

52 x1

x1

x2

x3

F(x1, x2, x3)

0

0

0

0

0

0

1

1

0

1

0

1

0

1

1

0

1

0

0

1

1

0

1

0

1

1

0

0

1

1

1

1

53 Теперь по таблице истинности построим дизъюнктивно-нормальную форму

Теперь по таблице истинности построим дизъюнктивно-нормальную форму

Отберем те строки в таблице истинности, которые в результате дают единицу. Для каждой строки строится конъюнкция всех переменных. Если переменная в этой строке равна нулю, то она берется с отрицанием, если единице – без отрицания. Затем соединим все полученные конъюнкции операциями дизъюнкции.

54 Решение логических задач
55 Стрелка Пирса (символ Лукашевича)

Стрелка Пирса (символ Лукашевича)

логическая операция с двумя переменными, соответствует обороту речи «ни…, ни…», обозначается следующим образом: Выражение истинно в том и только в том случае, когда оба высказывания A и B ложны.

56 Стрелка Пирса (символ Лукашевича)

Стрелка Пирса (символ Лукашевича)

A

B

A?B

0

0

1

0

1

0

1

0

0

1

1

0

57 Штрих Шеффера

Штрих Шеффера

логическая операция с двумя переменными, соответствует обороту речи «не… или не…», обозначается следующим образом Выражение A|B ложно в том и только в том случае, когда оба высказывания A и B истинны.

58 Штрих Шеффера

Штрих Шеффера

A

B

A|B

0

0

1

0

1

1

1

0

1

1

1

0

59 Дана таблица истинности логической функции от трех переменных

Дана таблица истинности логической функции от трех переменных

Построить логическую формулу и схему, реализующую эту функцию.

A

B

C

F(A, B, C)

0

0

0

0

0

0

1

0

0

1

0

1

0

1

1

0

1

0

0

1

1

0

1

1

1

1

0

0

1

1

1

0

60 A

A

B

C

F(A, B, C)

0

0

0

0

0

0

1

0

0

1

0

1

0

1

1

0

1

0

0

1

1

0

1

1

1

1

0

0

1

1

1

0

61 A

A

B

C

¬A

&

¬(A?B?¬C)

&

¬((¬(A?B?¬C))?(¬(A?¬B)))

&

&

&

¬(A?¬B)

¬B

&

¬C

62 5. После традиционного вечера встречи с выпускниками школы в

5. После традиционного вечера встречи с выпускниками школы в

стенгазете появилась заметка о трех наших бывших учениках. В ней было сказано, что Иван, Андрей и Борис стали учителями. Теперь они преподают разные дисциплины: один из них – математику, второй – физику, а третий – химию. Живут они тоже в разных городах: Минске, Витебске, Харькове. В заметке было также написано, что их первоначальные планы осуществились не полностью: Иван живет не в Минске. Андрей – не в Витебске. Житель Минска преподает не математику. Андрей преподает не физику. Повезло только жителю Витебска: он преподает любимую им химию. Можно ли по этим данным определить, кто где живет и что преподает?

63 Алгоритм решения задач на приведение множеств во взаимно-однозначное

Алгоритм решения задач на приведение множеств во взаимно-однозначное

соответствие

Строится пространственная система координат XYZ, на осях проставляются названия множеств и элементы этих множеств. Читается условие задачи. Если пара элементов в двух множествах находится в соответствии, то точка, лежащая на пересечении соответствующих прямых становится центром темного кружка, в противном случае – белого кружка. Применяется правило экстраполяции. Применяется правило проектирования. Повторять шаги 3)-4) пока это возможно. Если в сложившейся ситуации возможности экстраполяции и проектирования исчерпаны, а задача не решена, то делается допущение о цвете фигуры в какой-либо свободной вершине сетки. В случае противоречия допущение отклоняется цвет фигуры в данной точке меняется на противоположный.

64 Правила экстраполяции в плоскости

Правила экстраполяции в плоскости

«Темная» экстраполяция. Если на горизонтали (вертикали) все фигуры, кроме одной, светлы, то свободная занимается темной фигурой. «Светлая» экстраполяция. Если на горизонтали (вертикали) имеется «темная» фигура, то все фигуры на ней – светлые. Множественная экстраполяция. Если две (n) параллели в плоскости одинаково светло раскрашены везде за исключением двух (n) неокрашенных вершин, то на двух (n) параллелях другого направления, проходящих через эти вершины вне данных прямых вставляются светлые фигуры.

65 Правило множественного проектирования

Правило множественного проектирования

«Темная» фигура в своей плоскости проектируется на координатные оси. Прямые, проведенные через проекции в двух других плоскостях, раскрашиваются одинаково.

66 Предмет

Предмет

Имена

Город

Ф

Х

М

И

А

Б

М

В

Х

67 Иван преподает химию и живет в Витебске

Иван преподает химию и живет в Витебске

Андрей преподает математику и живет в Харькове. Борис преподает физику и живет в Минске.

«Решение логических задач»
http://900igr.net/prezentacija/algebra/reshenie-logicheskikh-zadach-71480.html
cсылка на страницу

Алгебра логики

19 презентаций об алгебре логики
Урок

Алгебра

35 тем
Слайды
900igr.net > Презентации по алгебре > Алгебра логики > Решение логических задач