Разработка технологий повторения темы Логика высказываний (стр. 5 из 24)

Алгоритм приведение к СКНФ:

1. Формулу приводят к КНФ;

2. Прибавляют нули, представленные в виде конъюнкций каждой недостающей переменной с ее отрицанием;

3. С помощью второго распределительного закона приводят эти сомножители к суммам первой степени, т. е. не содержащим произведений;

4. Исключают повторения сомножителей.

Пример:

2-Й СПОСОБ — ТАБЛИЧНЫЙ

Составим таблицу истинности для функции

x	y	z
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

Алгоритм приведение к СДНФ:

1. Строим таблицу истинности;

2. Рассматриваем только те строки таблицы, в которых формула принимает значение 1;

3. Каждой такой строке соответствует конъюнкция всех аргументов (без повторений). Аргумент, принимающий значение 0, входит в нее с отрицанием, значение 1 — без отрицания;

4. Образуем дизъюнкцию всех полученных конъюнкций.

Пример: В нашей таблице первую строку опускаем: функция принимает значение 0. Второй строке соответствует конъюнкция

третью строку опускаем и т. д.

СДНФ:

Приведение к СКНФ:

1.Строим таблицу истинности;

2.Рассматриваем только те строки таблицы, где функция принимает значение 0;

3.Каждой такой строке соответствует дизъюнкция всех переменных (без повторений). Аргумент, принимающий значение 0, берется без отрицания, значение 1 — с отрицанием;

4.Образуют конъюнкцию полученных дизъюнкций.

В нашем примере первой строке таблицы соответствует дизъюнкция

вторую строку опускаем и т. д.

СКНФ:

Замечания:

1) Если условиться из двух совершенных форм, СДНФ и СКНФ, отдавать предпочтение той, которая содержит меньше букв, то СДНФ предпочтительнее, если в столбце значений функции таблицы истинности меньше единиц; СКНФ — если в этом столбце меньше нулей.

2) В обычной, школьной алгебре мы знаем, что нет общего метода перехода от табличного задания функции к аналитическому. В алгебре высказываний, как видим, такой метод существует /5,7/.

1.2.3 Решение логических задач с помощью логики высказываний

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение:

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

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

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

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

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

1.3 Эвристические методы решения логических задач

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

1.3.1 Прием конкретизации задачи

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

Задача 1. Три ученицы — Галя, Лида и Наташа — в соревнованиях по гимнастике заняли три первых места. Когда же девочек спросили, кто из них занял первое место, они дали три разных ответа.

Галя: «Я заняла первое место»;

Лида: «Я заняла не первое место»;

Наташа: «Я заняла не третье место, однако, вы учтите, что один из ответов моих подруг правильный, а другой — неправильный».

Кто занял в соревнованиях первое место, если Наташин ответ во всем правдив?

Решение: Итак, Наташа заняла не третье место, а первое или второе. Проанализируем ответы других девочек. Галя сказала, что заняла первое место. Правдив ли ее ответ? Это неизвестно. Конкретизируем задачу. Пусть Галя сказала правду. Тогда она заняла первое место. В этом случае Лида сказала неправду, т.е. неверно, что она заняла не первое место. Но тогда получилось, что и Галя, и Лида заняли первое место, а это противоречит условию.

Выполним конкретизацию по-другому. Пусть Галя сказала неправду, тогда, значит, ответ Лиды правдив. Следовательно, Галя заняла второе или третье место, а Лида также заняла не первое место, а второе или третье. Тогда получим, что первое место заняла Наташа.

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

Задача 2. Четыре ученицы - Мария, Нина, Ольга и Поля - участвовали в лыжных соревнованиях и заняли четыре первых места. На вопрос, кто какое место занял, они дали три разных ответа:

1) «Ольга заняла первое место, Нина — второе»;

2) «Ольга — второе, Поля — третье»;

3) «Мария - второе, Поля четвертое».

Отвечавшие при этом признали, что одна часть каждого ответа верна, а другая - неверна. Какое место заняла каждая из учениц?

Решение: Проанализируем ответы девочек.

1) «Ольга заняла первое место, Нина — второе».

Что здесь истина? Неизвестно. Конкретизируем условие: пусть первая часть ответа - истина, а вторая часть - ложь. Исходя из этого, запишем предполагаемые истинные и ложные высказывания в таблице 1. Теперь легко видеть, что в правом столбце таблицы оказалось два противоречивых утверждения: Ольга и Нина не могут одновременно занимать второе место. Значит, хотя бы одно из этих высказываний действительно ложное.

Таблица 1

истина	ложь
Ольга – I место Поля - III место Мария - II место	Нина - II место Ольга - II место Поля - IV место

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

Строго говоря, это решение неполное, так как мы не доказали, что других ответов быть не может. Для этого надо продолжить конкретизацию. Предположим, что первая часть ответа 1) неверна. Это означает, что верно следующее предположение: