Решение логических задач с помощью таблиц истинности.

⇐ ПредыдущаяСтр 4 из 8Следующая ⇒

Задача. По обвинению в ограблении перед судом предстали А, В, С. Следствием установлено:

1) Если А не виновен или В виновен, то С виновен;

2) Если А невиновен, то С виновен.

Виновен ли А?

Решение. Запишем на языке алгебры логики факты, установленные следствием:

1) (`А+В) ® С; 2) = `А ® С.

F = (`А+В) ® С & `А ®`С

Составим таблицу истинности:

А	В	С	`А	`С	`А+В	(`А+В) ® С	`А ®`С	F

Проанализируем все строки, где F=1. Анализ таблицы показывает, что сложное высказывание истинно во всех случаях, когда А- истинно, т.е. А виновен в ограблении.

Вернемся к решению задачи 7 (дело Батончика, Ленчика и Пончика, с. 8).

Решение:

Обозначим буквами следующие утверждения:

Б – «Батончик утаил клад»;

Л – «Ленчик утаил клад»;

П – «Пончик утаил клад».

Тогда каждое из заявлений, состоящие из двух утверждений, можно представить так:

заявление Батончика - `Б, П;

заявление Ленчика - `П, Б;

заявление Пончика - `П, `Л.

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

Версии	Высказывания из двух заявлений
	Батончика	Ленчика	Пончика
	`Б	П	`П	Б	`П	`Л
1. Батончик утаил клад – Б
2. Ленчик утаил клад – Л
3. Пончик утаил клад – П

Анализируя таблицу и учитывая условие задачи (один дважды солгал – 0 0, другой дважды сказал правду – 1 1, третий один раз солгал, один раз сказал правду – 0 1 ), делаем вывод: версия 3 соответствует условию задачи, значит, клад утаил Пончик.

Задача. В финал шахматного турнира вышли Аркадий, Володя, Саша. Болельщики высказали свои предположения:

1 болельщик: А. займет 1-ое место.

2 болельщик: С. не будет последним.

3 болельщик: В. не будет на 1-ом месте.

После игр оказалось, что двое болельщиков ошиблись, а один угадал. Как закончился финал?

Решение.

«Ключ» к решению задачи: 0 0 1

Запишем логические высказывания болельщиков: 1. А₁ 2.`С₃3.`В₁

Составим таблицу истинности, рассмотрев все возможные варианты исхода турнира:

Варианты исхода турнира	Предположения
А	В	С	А₁	`С₃	`В₁

Проанализировав условие задачи и результаты таблицы, делаем вывод:

На 1 месте – В, на 2- ом – С, на 3-ем – А.

Задача. Петя, Вася и Маша остались дома одни. Кто-то из них съел варенье. На вопрос мамы, кто это сделал, они сказали:

А) Петя: «Я не ел. Маша тоже»

Б) Вася: «Маша действительно не ела. Это сделал Петя»

В) Маша: «Вася врет. Это он съел».

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

Ключ: 1 1 1 1 1 0

Решение.

П: `П, `М;

В: `М, П;

М: `М, П, В

	Высказывания
Версии	Петя	Вася	Маша
	`П	`М	`М	П	`М × П	В
Петя съел
Вася съел
Маша съела

1 × 1 =`1 = 0

Анализ условия задачи и таблицы позволяют сделать вывод: «Вася съел варенье».

Самостоятельная работа №2.

1) Проверить равносильность формул;

2) Составить таблицу истинности для формулы;

3) Решить задачу.

Основные законы логики

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

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

Приведение формулы к нормальной форме основывается на применении основных формул алгебры логики.

1. Основные законы логики	А = А; А А= 0; А +`А = 1; = А = А – закон двойного отрицания.
2. Свойства констант	`0 = 1; А+0=А; А+1=1	`1 = 0; А 0 = 0; А 1 = А
3. Закон идемпотентности (равносильности)	А + А = А	А А = А
4. Законы коммутативности	А + В = В + А	А В = В А
5. Законы ассоциативности	(А + В) + С = А + (В + С)	А (В С) = (А В) С
6. Законы дистрибутивности	А+(В С) = (А+В) (А+С)	А (В+С) = А В + А С
7. Законы поглощения	А + АВ = А	А (А + В) = А
8. Законы исключения (склеивания)	А В + `А В = В	(А + В) (`А + В ) = В

Доказать законы можно, упросив левую (правую) часть тождества.

Справедливы также равенства:

9. Законы де Моргана

А + В =`А `В; А В =`А +`В; `А +`В = А В; `А ` В = А + В.

Эти законы, а также равенства записанные ниже, можно доказать с помощью таблиц истинности, выписав все входящие в формулу подформулы.

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

10. А®В =`А + В 11. А «В = А В +`А `В = (`А + В) (А +`В) 12. А " В = А `В + `А В

Пример. Доказать тождество:

( А + В + С )( А +`В + С )(А +`В +`С )(`А +`В + С )(`А +`В +`С ) =А`В +`ВС

Расставим порядок действий в левой части тождества:

( А + В + С ) ( А +`В + С ) (А +`В +`С ) ( `А +`В + С ) ( `А +`В +`С )

Выполним действия, применяя логические законы:

1) ( ( А + С ) + В ) ( ( А + С ) +`В ) = А + С (по закону исключения)

2) ( (`А +`В )+С ) ( (`А +`В ) +`С ) = `А +`В (по закону исключения)

3) ( А + С ) ( ( А +`В +`С ) = (А + А`В + А`С + АС) + `ВС +`СС = А + `ВС

= А (з-н поглощения)

4) ( А + `ВС ) (`А +`В ) = А`В + (А`ВС +`ВС) = А`В +`ВС (по закону поглощения)

Упражнения.

1. С помощью таблиц истинности докажите 9-12 законы алгебры логики.

2. Упростите формулы, используя законы склеивания:

1) A B C+`А B C;

2) A B C + B C;

3) (`А +`В + С )(`А + В C).

3. Упростите формулы, используя законы поглощения:

1) A + A B + A B C + A D F;

2) A B+A B C+A B D;

3) A (A+B) (A+C);

4) A B (A C+A B).

4. Упростите формулы, используя законы алгебры логики:

1) A `C + C ( B +`C) + ( A +`B) C;

2) A ( B +`C) + `A B;

3) (`А+C) A C ( B +`C) B C;

4) A + B + C +`B + (A +`B + C `A + B + C) + `A `B;

5) (А®В)«(`А®(`В + С));

6) (А + В) ®(`В + С).

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

Разнообразие логических задач очень велико. Способов их решения тоже немало. Но наибольшее распространение получили следующие способы:

1) с помощью таблиц истинности;

2) путем составления логического уравнения (формулы) и приведения его к нормальной форме;

3) путем составления логического уравнения и решения его с помощью ЭВМ.

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

⇐ Предыдущая 1 2 345 6 7 8 Следующая ⇒