Алгоритм решения:
Кодирование: обозначение искомых с помощью булевых переменных (принимающих значения 0, 1) и описание содержания этих переменных.
Запись условия в виде системы логических уравнений, в правых частях которых — единицы.
Замечание. Если правая часть уравнения — нуль, то отрицанием левой части она приводится к единице.
Образование конъюнкции левых частей системы и приравнивание ее единице. Полученное уравнение называется характеристическим. Оно равносильно исходной системе уравнений: каждое решение системы является решением характеристического уравнения, и наоборот.
Обоснование. Пусть некоторый порядок значений переменных является решением системы уравнений. При подстановке в характеристическое уравнение он обращает каждый сомножитель конъюнкции в единицу, следовательно, и конъюнкция равна единице.
Верно и обратное — каждое решение характеристического уравнения (обращающее конъюнкцию в единицу) обращает в единицу все сомножители конъюнкции, следовательно, удовлетворяет системе уравнений.
Приведение левой части характеристического уравнения к ДНФ (в частности, к СДНФ).
Замечание. При раскрытии скобок в левой части характеристического уравнения по второму распределительному закону значительные упрощения получаются за счет использования законов противоречия, исключенного третьего, исключения повторений (сомножителей, слагаемых), а также поглощения.
Приравнивание каждого слагаемого СДНФ, независимо от других, единице и извлечение из уравнений (левые части которых — конъюнкции переменных или их отрицаний) значений переменных. Каждый их набор является решением задачи.
Обоснование. Каждый набор найденных значений переменных обращает в единицу хотя бы одно слагаемое дизъюнкции, т. е. является решением характеристического уравнения.
Замечание. Если после упрощений в ДНФ осталось одно слагаемое, задача имеет единственное решение, если более одного — несколько решений. В случае, когда в левой части характеристического уравнения все слагаемые уничтожаются, задача не имеет решения (данные не совместны).
Применим этот алгоритм к решению задачи.
Задача. (Кто смотрит телевизор?)
Семья состоит из пяти человек: Алексей (А), Вера (В), Глеб (Г), Даша (Д), Евгений (Е).
Если телевизор смотрит А, то смотрит и В;
смотрят либо Д, либо Е, либо оба вместе;
смотрят либо В, либо Г, но не вместе;
Д и Г либо смотрят вместе, либо вовсе не смотрят;
если смотрит Е, то смотрят А и Д.
Кто смотрит телевизор?
Решение:
Записываем в виде системы логических уравнений:
Преобразуем в характеристическое уравнение:
Приведем левую часть характеристического уравнения к СДНФ:
Получили одно слагаемое, следовательно, задача имеет единственное решение. Приравнивание каждого слагаемого СДНФ единице и извлечение из уравнения значение переменных.
Таким образом, получили ответ: телевизор смотрят Глеб и Даша.
Статьи по теме:
Разработка программы по изучению раздела «кулинария» с использованием
информационных технологий
Свою нагрузку на новый учебный год преподаватель обычно узнает в конце текущего, следовательно, у него есть время и возможность спланировать (а по существу, «запрограммировать») свою деятельность, согласовав ее с программой и календарными сроками выполнения. Чтобы правильно организованный учебно-тр ...
Диагностика фонематических процессов у младших школьников с
нарушением произносительной стороны речи
Цель данного исследования состоит в изучении развития фонематических процессов у младших школьников с нарушением произносительной стороны речи (дислалией, дизартрией, ринолалией). Задачи: 1. Рассмотреть методики по изучению развития фонематических процессов у детей с нарушением произносительной сто ...
Психолого-педагогическое изучение дошкольников с
недостатками слуха
На заседаниях психолого-педагогической комиссии проводится всестороннее обследование детей раннего и дошкольного возраста с нарушениями слуха. Первоначально комиссия рассматривает необходимую документацию: выписку из истории развитияребенка, предварительные диагнозы и заключения специалистов, перви ...