Решение логических задач средствами алгебры логики

Обычно используется следующая схема решения:

1. изучается условие задачи;

2. вводится система обозначений для логических высказываний;

3. конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;

4. определяются значения истинности этой логической формулы;

5. из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.

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

Решение. Введем обозначения: А – 1-й урок русского языка, В – 2-й урок русского языка, - 1-й урок математики, С – 3-й урок математики, - 2-й урок физкультуры, - 3-й урок физкультуры. Составим логическую формулу, опираясь на условие задачи: (А v В) Λ ( v C) Λ ( v ). Таблица истинности для нее будет иметь вид:

Переменные	Промежуточные логические формулы	Функция
A	B	C				АvВ	v C	v	(АvВ) Λ ( v C)	(АvВ) Λ ( v C) Λ ( v )

Ответ. Анализируя таблицу, приходим к выводу, что расписание может быть представлено в двух вариантах:

	1 вариант	2 вариант
1 урок	математика	русский
2 урок	русский язык	физкультура
3 урок	физкультура	математика

Пример 3. Брауну, Джонсу и Смиту предъявлено обвинение в соучастии в ограблении банка. В ходе следствия Браун сказал, что преступники были на синем "Бьюике", Джонс сказал, что это был черный "Крайслер", Смит утверждал, что это был "Форд", но не синий. Каждый указал неправильно либо марку, либо цвет автомобиля. Определим истинный цвет и истинную марку автомобиля.

Рассмотрим простые высказывания вида:

х = "машина – синяя",

у = "машина – Бьюик",

z = "машина – черная",

u = "машина – Крайслер",

v = "машина – Форд".

На их основе высказывание Брауна можно записать в виде сложного логического выражения вида , высказывание Джонса – в виде , а высказывание Смита – в виде . Так как в каждом из этих выражений одна из переменных принимает значение "истина", то истинны и дизъюнкции вида: . По определению конъюнкции, . Это выражение мы взяли из-за однозначности равенства 1 конъюнкции и неоднозначности (многовариантности) его равенства нулю. Упростим выражение:

Мы использовали тот факт, что одновременно не могут быть истинными два высказывания относительно цвета или два высказывания относительно марки машины. Так как конъюнкция истинна только тогда, когда , то заключаем, что автомобиль был черным "Бьюиком".