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

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

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

Браун: «Я совершил это. Джон не виноват».

Джон: «Браун не виноват. Преступление совершил Смит».

Смит: «Я не виноват, виновен Браун».

Необходимо определить имена старика, мошенника и чиновника и кто из них виноват, если известно, что преступник один.

Решение этой задачи начинается с введения обозначений: буквами Б, Д и С обозначим высказывания: «виноват Браун», «виноват Джон» и «виноват Смит» соответст­венно. Тогда утверждения, высказанные задержанными, можно записать в виде конъюнкций:

Б Ù Ø Д, Ø Б Ù С, Б Ù Ø С,

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

L = (Б Ù Ø Д) Ú (Ø Б Ù С) Ú (Б Ù Ø С).

Таблица истинности этой формулы имеет вид:

Б	Д	С	Б Ù Ø Д	Ø Б Ù С	Б Ù Ø С	L

Из таблицы видно, что формула L истинна в пяти из восьми случаев. Случай, представленный в пятой строке, следует ис­ключить из рассмотрения, так как здесь оказываются истинными две конъюнкции, а это противоречит усло­вию задачи. В строках 4, 6 и 7 оказываются истинными по два высказывания: Д и С, Б и С, Б и Д, соответственно, что также противоречит условию задачи. Следователь­но, справедлив случай 7, то есть преступник – Смит. Он – известный мошенник, и оба его высказывания лож­ны: Б Ù Ø С º 0. При этом высказывания Б и Д ложны. Значит, истинна пара высказываний Джона, а у Брауна первое высказывание ложно, а второе истинно. Отсюда ясно, что Джон – уважаемый в городе старик, а Браун – Малоизвестный чиновник.

Практическое задание.

1. Составить таблицы истинности для следующих логических выражений:

1.

2.

3.

4.

5.

6.

7.

8.

9.

2. Упростить логические выражения: 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11)

3. По следующим таблицам истинности восстановить логические выражения:

x	y	z	f

1)).

2.

6.

x	y	f

x	y	f

8.

x	y	z	f

9.

x	y	z	f

7.

x	y	f

x	y	z	f

5.

3.

x	y	z	f

4.

x	y	z	f

4. Нарисовать логические схемы по выражениям 1.2,1.3, 3.1, 3.2, 3.4, 3.6.

2.

5. Упростить логические схемы

x y f z  

&

&

&

1.

4.

3.

x f y   z

º

&

6.

x y f z  

&

&

8.

7.

5.

6. Пусть три цеха A, B, C снабжаются электроэнергией от небольшой электростанции, на которой установлены два генератора тока X и Y. Мощность генератора X в два раза больше мощности Y. Если в электроэнергии нуждается один цех, то достаточно включить генератор Y, если поступили заявки от двух цехов, то необходимо включить генератор X. Оба генератора включаются, если заявки поступили от всех цехов. В соответствии с этими требованиями сконструируйте устройство (нарисуйте его схему), которое управляло бы работой генераторов.

7. Нарисовать схему устройства, обрабатывающего решения трех судей (A, B, C) на спортивных состязаниях. Если судья считает, что результат надо засчитать, он нажимает кнопку, подавая сигнал «1». Сигнал на табло с надписью «результат засчитан», устройство выдает только тогда, когда все судьи или два из них нажали свои кнопки, но при этом одним из них должен быть обязательно судья A, поскольку он является старшим судьей.

Дата добавления: 2015-04-24