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

Способы решения задач Алгебраический способ (с помощью алгебры высказываний или таблиц истинности) 1) выделить элементарные (простые) высказывания и обозначить их буквами; 2) записать условие задачи на языке алгебры логики, соединив простые высказывания в сложные с помощью логических операций; 3) составить единое логическое выражение для всех требований задачи; 4) используя законы алгебры логики, упростить полученное выражение и вычислить все его значения либо построить таблицу истинности для рассматриваемого выражения; 5) выбрать решение - набор значений простых высказываний, при котором логическое выражение является истинным; 6) проверить, удовлетворяет ли полученное решение условию задачи.

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

Графический способ Метод графов применяется тогда, когда между объектами существует много связей. Граф позволяет наглядно представить эти связи и определить, какие из них не противоречат условиям задачи. Метод диаграмм Эйлера-Венна позволяет графически решать математические задачи на основе применения теории множеств.

Задача 1. «Сосуд» Условие задачи: Алеша, Боря и Гриша нашли в земле сосуд. Рассматривая удивительную находку, каждый высказал по 2 предположения: Алеша: «Этот сосуд греческий и изготовлен в V веке». Боря: Этот сосуд финикийский и изготовлен в III веке». Гриша: «Этот сосуд не греческий и изготовлен в IV веке». Учитель истории сказал ребятам, что каждый из них прав только в одном из двух предположений. Где и в каком веке изготовлен сосуд?

1 способ. Решим задачу с помощью алгебры высказываний 1) Переведем условие задачи на язык логики высказываний (выделим простые высказывания и обозначим их буквами). Пусть А - сосуд греческий; В - сосуд финикийский; С3 - сосуд изготовлен в 3 веке; С4 - сосуд изготовлен в 4 веке; С5 - сосуд изготовлен в 5 веке.

2) Запишем условие задачи на языке алгебры логики, соединив простые высказывания в сложные с помощью логических операций. Алеша прав: А=1 или С5=1, т.е. А & ¬С5۷ ¬А & С5 = 1. Боря прав: В=1 или С3=1, т.е. В & ¬С3۷ ¬В & С3 = 1. Гриша прав: не А=1 или С4=1, т.е. ¬А & ¬С4۷ А & С5 = 1. Сосуд может быть изготовлен только в одном из веков, т.е. С3 & С4 & ¬С5۷ С3 & ¬С4 & С5۷ ¬С3 & С4 & С5 = 1. и только в одной из стран, т.е. В &¬А۷ ¬В & А = 1.

3) Составим единое логическое выражение для всех требований задачи. Получили 5 тождественно истинных высказываний, их логически перемножаем. Результат должен быть тождественно истинным высказыванием. (А & ¬С5۷ ¬А & С5) & (В & ¬С3۷ ¬В & С3) & & (¬А & ¬С4۷ А & С5) & (В &¬А۷ ¬В & А) & & (С3 & С4 & ¬С5۷ С3 & ¬С4 & С5۷ ¬С3 & С4 &С5)= 1

4) Используя законы алгебры логики, упростим полученное выражение и вычислим все его значения. Умножим скобки: 1 на 3 и 2 на 4, получаем: (А & С4 & ¬С5۷ ¬А & ¬С4 & С5)&(В &¬А & ¬С3۷ ¬В & А & С3) & & (С3 & С4 & ¬С5۷ С3 & ¬С4 & С5۷ ¬С3 & С4 &С5) = = (А & С4 & ¬С5 & ¬В & С3۷ В &¬А & ¬С3 & С4 & ¬С5) & & (С3 & С4 & ¬С5۷ С3 & ¬С4 & С5۷ ¬С3 & С4 &С5) = = ¬В &А & С3 & С4 & ¬С5۷ В &¬А & ¬С3 & ¬С4 & С5 = = 0 ۷ В &¬А & ¬С3& ¬С4 & С5 = В &¬А & ¬С3 & ¬С4 & С5

5) Выбираем решение, при котором логическое выражение является истинным В &¬А & ¬С3 & ¬С4 & С5. 6) Проверяем, удовлетворяет ли полученное решение условию задачи и делаем вывод сосуд финикийский изготовлен в 5 веке.

2 способ. Решим задачу с помощью таблицы Пусть Алеша: «Этот сосуд греческий и изготовлен в V веке» = А. Боря: Этот сосуд финикийский и изготовлен в III веке» = Б. Гриша: «Этот сосуд не греческий и изготовлен в IV веке» = Г. 3 век 4 век 5 век греческийАА,Б,ГБ финикийскийГБА,Б,Г Получаем противоречие высказыванию Гриши. Вывод: сосуд финикийский изготовлен в 5 веке.

Задача 2. «Компьютер» Условие задачи: Компьютер вышел из строя (нет изображения на экране монитора), однако неизвестно какое устройство не работает (монитор, видеокарта или оперативная память). Можно предположить следующее: - Если монитор не исправен или видеокарта неисправна, то оперативная память неисправна; - Если монитор исправен, то оперативная память исправна. Исправен ли монитор?

Решим задачу с помощью таблицы истинности 1) Переведем условие задачи на язык логики высказываний (выделим простые высказывания и обозначим их буквами). Пусть А - монитор неисправен; В - видеокарта неисправна; С - оперативная память неисправна. 2) Запишем условие задачи на языке алгебры логики, соединив простые высказывания в сложные с помощью логических операций. (¬А۷ В) С и ¬А ¬С 3) Составим единое логическое выражение для всех требований задачи. Пусть F (A, B, C) = ((¬А۷ В) С) & (¬А ¬С).

4) Составим для данного высказывания таблицу истинности: F (A, B, C) = ((¬А۷ В) С) & (¬А ¬С) АВС¬А¬А ۷ В(¬А ۷ В) С ¬С ¬А ¬С F (A,B,C)

5) Выбираем решение, при котором логическое выражение является истинным. Решить данную задачу - значит указать, при каких значениях А полученное сложное высказывание истинно. Необходимо проанализировать все строки таблицы истинности, где F = 1. Анализ таблицы показывает, что сложное высказывание истинно во всех случаях, когда А - истинно, т.е. вероятнее всего неисправен монитор. 6) Проверяем, удовлетворяет ли полученное решение условию задачи и делаем вывод неисправен монитор.

Задача 3. «Ученики» Условие задачи: В классе 36 человек. Ученики этого класса посещают математические, физический и химический кружки, причем математический кружок посещают 18 человек, физический - 14, химический кроме того известно, что 2 человека посещают все три кружка, 8 человек - и математический и физический, 5 - и математический и химический, 3 - и физический и химический. Сколько учеников класса не посещают никаких кружков?

Решим задачу с помощью кругов Эйлера-Венна Множество всех учеников класса на рисунке изобразим большим кругом. Внутри круга расположим три пересекающихся круга меньшего диаметра: М - круг изображает множество членов математического кружка; Ф – физического кружка; X - химического кружка. МФ Х

МФ Х Дадим имена множествам. Пусть МФХ - множество ребят, каждый из которых посещает все 3 кружка. МФ - множество занимающихся и в математическом, и в физическом кружке (и, возможно, также в химическом). МФ¬Х - и в математическом, и в физическом, но не в химическом и т. д. МФХМФХ МФ¬ХМФ¬Х Впишем нужные имена множеств в области, изображенные на рисунке: М¬ФХМ¬ФХ ¬МФХ¬МФХ М¬Ф¬ХМ¬Ф¬Х ¬МФ¬Х¬МФ¬Х ¬М¬ФХ¬М¬ФХ ¬М¬Ф¬Х¬М¬Ф¬Х

В область МФХ впишем число 2, так как все три кружка посещают 2 ученика. Теперь обратимся к числовым данным. Множество МФ состоит из 8 человек. Но это множество является объединением множеств МФХ и МФ¬Х, причем в МФХ входят 2 человека. Значит, на долю МФ¬Х остается 6 человек. Теперь рассмотрим множество MX, состоящее из 5 человек. Оно также состоит из двух частей: на МФХ приходится 2 человека, значит, на М¬ФХ - 3. Рассмотрим теперь множество М, в которое входят 18 учеников. Оно состоит из четырех частей. Количественный состав трех подмножеств мы уже нашли: это 2, 6 и 3. Значит, в подмножество М¬Ф¬X, входит 18 - ( ) = 7 человек. Аналогично определим количество учащихся в множествах ¬МФХ, ¬МФ¬Х, ¬М¬ФХ. Три пересекающихся круга образуют 7 непересекающихся областей, изображающих непересекающиеся подмножества учеников, каждый из которых посещает хотя бы 1 кружок. Просуммируем цифры в этих областях: = 28 человек посещает кружки. Значит, = 8 ребят не посещают никаких кружков. Ответ: в классе 8 учеников, не посещающих кружки. МФХМФХ МФ¬ХМФ¬Х М¬ФХМ¬ФХ ¬МФХ¬МФХ М¬Ф¬ХМ¬Ф¬Х ¬МФ¬Х¬МФ¬Х ¬М¬ФХ¬М¬ФХ ¬М¬Ф¬Х¬М¬Ф¬Х МФ Х