Формы записи высказываний. Алгоритмические способы решения логических задач

Аналитическое образование » Разработка технологий повторения темы "Логика высказываний" » Формы записи высказываний. Алгоритмические способы решения логических задач

Страница 5

Алгоритм решения:

Кодирование: обозначение искомых с помощью булевых переменных (принимающих значения 0, 1) и описание содержания этих переменных.

Запись условия в виде системы логических уравнений, в правых частях которых — единицы.

Замечание. Если правая часть уравнения — нуль, то отрицанием левой части она приводится к единице.

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

Обоснование. Пусть некоторый порядок значений переменных является решением системы уравнений. При подстановке в характеристическое уравнение он обращает каждый сомножитель конъюнкции в единицу, следовательно, и конъюнкция равна единице.

Верно и обратное — каждое решение характеристического уравнения (обращающее конъюнкцию в единицу) обращает в единицу все сомножители конъюнкции, следовательно, удовлетворяет системе уравнений.

Приведение левой части характеристического уравнения к ДНФ (в частности, к СДНФ).

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

Приравнивание каждого слагаемого СДНФ, независимо от других, единице и извлечение из уравнений (левые части которых — конъюнкции переменных или их отрицаний) значений переменных. Каждый их набор является решением задачи.

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

Замечание. Если после упрощений в ДНФ осталось одно слагаемое, задача имеет единственное решение, если более одного — несколько решений. В случае, когда в левой части характеристического уравнения все слагаемые уничтожаются, задача не имеет решения (данные не совместны).

Применим этот алгоритм к решению задачи.

Задача. (Кто смотрит телевизор?)

Семья состоит из пяти человек: Алексей (А), Вера (В), Глеб (Г), Даша (Д), Евгений (Е).

Если телевизор смотрит А, то смотрит и В;

смотрят либо Д, либо Е, либо оба вместе;

смотрят либо В, либо Г, но не вместе;

Д и Г либо смотрят вместе, либо вовсе не смотрят;

если смотрит Е, то смотрят А и Д.

Кто смотрит телевизор?

Решение:

Записываем в виде системы логических уравнений:

Преобразуем в характеристическое уравнение:

Приведем левую часть характеристического уравнения к СДНФ:

Получили одно слагаемое, следовательно, задача имеет единственное решение. Приравнивание каждого слагаемого СДНФ единице и извлечение из уравнения значение переменных.

Таким образом, получили ответ: телевизор смотрят Глеб и Даша.

Страницы: 1 2 3 4 5 


Статьи по теме:

Cущность личностно-ориентированного обучения на уровне теории и практики обучения в отечественной и зарубежной науке
В терминологическом плане корректнее было бы говорить о личностно-ориентированном образовании. Однако это вызвало бы значительную терминологическую путаницу и необходимость при каждом использовании термина "личностно-ориентированное образование" оговаривать контекст его использования, смы ...

Характеристика детей с отклонениями в поведении
Каждый человек отличается своеобразием реакций на воздействия окружающей среды. Поведение проявляется в индивидуально-своеобразных формах, не всегда адекватных. Всестороннее и многоплановое изучение отклоняющегося поведения учеными педагогами, психологами, социологами говорит о том, что природа отк ...

Приемы ознакомления детей с городецкой росписью и методика обучения рисованию элементов
В детском возрасте, когда ребенок особо эмоционально относится к окружающему миру, особое значение имеет реализация его потребности в художественном творчестве. Знакомство детей с различными видами народного декоративно-прикладного искусства на занятиях по декоративному рисованию поможет научить их ...

Copyright © 2014-2021 - All Rights Reserved - www.vojxf.site