Логические (булевы) функции основные логические функции


Download 0.87 Mb.
bet13/30
Sana24.03.2023
Hajmi0.87 Mb.
#1290651
1   ...   9   10   11   12   13   14   15   16   ...   30
Bog'liq
дм

Пример 2. По подозрению в совершении преступления задержали Брауна, Джонса и Смита. Вот что они показали:
Браун: Я совершил это. Джонс не виноват.
Джонс: Браун не виноват. Преступление совершил Смит.
Смит: Я не виноват. Виновен Браун.
В процессе следствия выяснилось, что у одного из них оба утверждения ложны, у другого одно ложно, одно истинно, а у третьего оба истинны, а также, что преступник только один. Требуется определить имя преступника, кто из них говорил правду, а кто нет.
Решение. Обозначим буквами BDвысказывания: виноват Браун, виноват Джонс, виноват Смит соответственно. Тогда утверждения, высказанные задержанными, можно записать в виде конъюнкций  , из которых по условию задачи, две ложны, а одна истинна. Истинной будет формула ,  но из этой формулы решение получится только дополнительным рассуждением: пусть = 1, тогда по условию = 0 и = 0. Но тогда из трех конъюнкций, составляющих К две будут верны:  , а это противоречит условию. Значит В=0. Видно, что C=1 удовлетворяет условию задачи, и это решение единственно, так как если предположить, что D = 1, то это будет означать, что  , а значит, что либо В, либо С равно 1, но это противоречит тому, что преступник только один.
Таким образом, преступник – Смит, оба его высказывания ложны, у Брауна одно высказывание ложно, одно нет, а Джонс сказал правду.
Все эти рассуждения используются не только для решения логических задач (которые действительно приходится решать следователям), но и для составления игровых программ (компьютерная игра ШЕРЛОК, содержащая больше 60 тыс. логических задач, составлена с использованием тех же самых конъюнкций, дизъюнкций и отрицаний).

ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ


Приведенный ниже материал далеко не исчерпывает разнообразные разделы общей теории графов, содержит некоторые факты из общей теории, (которые за неимением времени можно даже опускать), а основное внимание уделяется приложениям к теории сетей связи. На взгляд авторов центральной частью раздела является нахождение путей и сечений (разрезов) методами булевой алгебры и теорема Форда–Фалкерсона. Именно из этих разделов и предлагаются индивидуальные задания.

Download 0.87 Mb.

Do'stlaringiz bilan baham:
1   ...   9   10   11   12   13   14   15   16   ...   30




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling