Метод резолюций и фразы Хорна

Для порождения логических следствий используется очень простая схема рассуждений. Пусть А, В, X – формулы. Предположим, что две формулы (A Ú X) и (B Ú Ø X) истинны. Если X – истинна, то, следовательно, В истинна. Наоборот, если X ложна, то можно заключить, что А – истинна. В обоих случаях (A Ú В) истинна. Получается правило

{ A Ú X, B Ú Ø X } ú= A Ú В,

которое можно записать в виде:

{Ø X Ú A, X Ú B } ú= A Ú В.

Это правило называется правилом резолюций.

Лемма. Пусть S ₁ и S ₂ – дизъюнкты нормальной формы из множества S, l – высказывание. Если l входит в дизъюнкт S ₁ и Øl – в дизъюнкт S ₂, то дизъюнкт r = (S ₁\{l}) Ú (S ₂\{Øl}) является логическим следствием нормальной формы S. Дизъюнкт r называется резольвентой дизъюнктов S ₁ и S _2.

Следствие. Нормальные формы S и S È { r } эквивалентны.

Алгоритм поверки на выполнимость.

1. выбираем l, S ₁, S ₂, такие что lÎ S ₁ и ØlÎ S ₂.

2. вычисляем резольвенту r;

3. заменяем S на S È { r }.

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

Пример метода резолюций. Проверим выполнимость множества

S ={ P Ú q, P Ú r, Ø q ÚØr, Ø P }.

Дизъюнкты удобно пронумеровать:

1. P Ú q

2. P Ú r

3. Ø q ÚØ r

4. Ø P

Вычисляем и добавляем резольвенты. В скобках указаны S ₁, S ₂:

5. q (1,4)

6. r (2,4)

7. Ø q (3,6)

8. 0 (5,7). Множество невыполнимо!

 

Представим функцию импликации в виде минимальной ДНФ с помощью формулы:

A ® C º Ø А Ú C.

Тогда с учётом правила де Моргана импликации:

(A ₁ Ù A ₂ Ù ¼ Ù A_M) ® (B Ú C)

будет соответствовать формула:

Ø А ₁ Ú Ø А ₂ Ú ¼Ú Ø А _M Ú B Ú C.

Перенесём положительные литералы вперед и получим:

B Ú C ÚØ А ₁ Ú Ø А ₂ Ú ¼Ú Ø А _M.

Такую формулу называют фразой Хорна, положительные литералы (B, C) называют альтернативными следствиями, негативные (Ø А ₁, Ø А ₂, ¼, Ø А _M) – необходимыми посылками.

Хорновский дизъюнкт называется точным, если он содержит одну позитивную литеру. Если он не содержит позитивных литер, то называется негативным.

Точный дизъюнкт выражает некоторое правило: негативные литеры соответствуют гипотезам (которые представлены высказываниями), а позитивные заключения.

Унитарный позитивный хорновский дизъюнкт представляет собой некоторый факт, т.е. заключение, не зависящее от каких-либо гипотез.

Задача состоит в том, что надо проверить некоторую цель, логически выведенную из множества фактов и правил.

Алгоритм построения резолюций для множества фраз Хорна упрощается. Рассмотрим алгоритм построения резолюций, если множество S записано с помощью фраз Хорна.

1. При условии ЛОЖЬ Ï S, выбираем P и С, такие что:

P – унитарный позитивный дизъюнкт из S;

C – дизъюнкт из S, содержащий Ø P;

2. Вычисляем резольвенту r.

3. Заменяем множество S на (S /{ C }È{ r }).

Таким образом, на каждом этапе одна фраза Хорна заменяется другой, и некоторый атом удаляется из одного дизъюнкта. Отсюда следует, что выполнение алгоритма всегда завершается, какая бы стратегия ни была принята при выборе P и С. Если N – число атомов, первоначально присутствующих в S (с учётом повторений), то процедура вычисления резольвенты будет выполняться N раз.

Существует два случая завершения алгоритма: либо порождён пустой дизъюнкт, тогда множество будет не выполнимым, либо получено множество S, не содержащее дизъюнктов для вычисления очередной резольвенты, тогда множество S будет выполнимым.

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

Пример построения фраз Хорна. Пусть предметная область описана в виде:

{Ø А Ú (B Ù D), B ® C, A Ú D }.

Представим её в виде фраз Хорна.

Ø А Ú (B Ù D) º (Ø А Ú B) Ù (Ø А Ú D). Этому высказыванию соответствует две фразы Хорна: (Ø А Ú B) и (Ø А Ú D).

B ® C º Ø В Ú C.

A Ú D – является фразой Хорна.

Итак, имеем предметную область, описанную фразами Хорна:

{Ø А Ú B, Ø А Ú D, Ø В Ú C, A Ú D }

Метод резолюций применяется в качестве механизма доказательства при реализации принципа дедукции.

Для доказательства того, что некое заключение C является логическим следствием множества гипотез { H ₁, …, H_N }, нужно применить резолюцию к множеству { H ₁,… H_N,^Ø C }. Эти гипотезы и отрицание заключения должны иметь вид дизъюнкций.

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

 

Пример выполнения задания

Для следующего рассуждения:

Студент пойдёт домой или останется в университете. Он не останется в университете. Следовательно, студент пойдёт домой.

1) выяснить, являются ли они логически правильными, доказательство провести методом прямого вывода, методом «от противного»;

2) выразить описание задачи через фразы Хорна и провести доказательство, используя метод резолюций.

Решение:

Введем следующие обозначения простых высказываний:

P – Студент пойдёт домой;

q – Студент останется в университете.

Запишем это рассуждение символически с помощью указанных обозначений: P Ú q, Ø q, P. Истинность следствия будет определяться истинностью имеющихся высказываний:

{ P Ú q, Ø q } ú= P.

1)

а) Доказательство проведем методом прямого вывода. Пронумеруем аксиомы:

P Ú q                                                                                              (1)

Ø q                                                                                                 (2)

Из (2) Þ q = 0,                                                                            (3)

из (3) и (1) Þ P, т.е. искомый вывод.

б) Применим принцип дедукции: { P Ú q, Ø q, Ø P } ú= 0. Введём ещё одно высказывание

Ø Р                                                                                                (4)

Тогда из (4) и (1) Þ q,                                                                (5)

из (5) и (2) Þ ЛОЖЬ, то есть противоречие. Значит, верно, что P равно ИСТИНА.

2) Введем множество S = { P Ú q, Ø q, Ø P }, которое является описанием нашей предметной области и уже представлено фразами Хорна.

Невыполнимость множества S докажем с помощью резолюций:

1. P Ú q,

2. Ø q,

3. Ø P,

4. P (1,2).

5. 0 (ЛОЖЬ).

Можно считать, что данное рассуждение логически правильное.

 

ТЕМА 5

Основные понятия, связанные с предикатами

Задание 1

Варианты 1-10: Из предикатов согласно варианту с помощью кванторов постройте всевозможные высказывания и определите, какие из них истинны, а какие ложны (х Î R).

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

 

№ вар.	Предикаты
1
2
3
4
5
6
7
8
9
10	t wx:val="Cambria Math"/><w:b/><w:i/><w:sz w:val="24"/><w:lang w:val="EN-US"/></w:rPr><m:t>y</m:t></m:r><m:r><m:rPr><m:sty m:val="bi"/></m:rPr><w:rPr><w:rFonts w:ascii="Cambria Math" w:h-ansi="Cambria Math"/><wx:font wx:val="Cambria Math"/><w:b/><w:i/><w:sz w:val="24"/></w:rPr><m:t>| ≤ 3</m:t></m:r></m:oMath></m:oMathPara></w:p><w:sectPr wsp:rsidR="00000000" wsp:rsidRPr="00990591"><w:pgSz w:w="12240" w:h="15840"/><w:pgMar w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></wx:sect></w:body></w:wordDocument>">
№ вар.	Высказывания
11
12
13
14
15

 

Примеры выполнения задания 1

Пример 1. Из следующего предиката с помощью кванторов постройте всевозможные высказывания и определите, какие из них истинны, а какие ложны (х Î R): x² = 25.

Решение: Из этого одноместного предиката с помощью кванторов можно построить два высказывания: «("x)(x² = 25)» и «($x)(x² =25)».

Первое высказывание читается так: «Квадрат любого действительного числа равен 25». Оно ложно и с точки зрения здравого смысла, и согласно определению операции взятия квантора общности: предикат «x²=25» не является тождественно истинным, и потому высказывание «("x)(x² = 25)» ложно.

Второе высказывание читается так: «Существует действительное число, квадрат которого равен 25». Это высказывание истинно, так как предикат «х² = 25» не является тождественно ложным.

Пример 2. Прочитайте следующие высказывания и определите, какие из них истинные, а какие ложные, считая, что все переменные пробегают множество действительных чисел: ($y) ("x) (x+y=7).

Решение: Высказывание «($y) ("x) (x+y=7)» можно прочитать так: «Существует такое действительное число, которое после прибавления к любому действительному числу в сумме дает 7».

Нетрудно понять, что это утверждение ложно. В самом деле, рассмотрим одноместный предикат ("x) (x+y=7) относительно переменной у, применением к которому квантора существования получается данное высказывание. Ясно, что какое бы действительное число ни подставить вместо предметной переменной у, например, «("x)(x+4=7)», предикат будет превращаться в ложное высказывание (высказывание «("x)(x+4=7)», ложно, так как одноместный предикат «(x+4=7)» превращается в ложное высказывание, например, при подстановке вместо переменной х числа 5). Поэтому высказывание «($y) ("x) (x+y=7)», получающееся из одноместного предиката «("x) (x+y=7)» применением операции взятия квантора существования по у, ложно.

 

Задание 2

Варианты 1-8: Найдите множества истинности предикатов, заданных над указанными множествами, согласно варианту.

Варианты 9-15: Изобразите на координатной прямой множества истинности заданных на R одноместных предикатов согласно варианту.

 

№ вар.	Предикаты
1
2
3
4
5
6
7
8	«x 1 < x 2», M 1 = {1, 2, 3, 4, 5}, M 2 ={3, 5, 7}
9
10
11
12
13
14
15

Примеры выполнения задания 2

Пример 1. Найдите множества истинности следующих предикатов, заданных над указанными множествами:

«x₁ + x₂<0»,M₁={-3,-2,-1,0, 1,2,3}, M₂={-3,1, 2}.

Решение: Множеством истинности этого предиката будет подмножество декартова произведения множеств М₁ и М₂ т.е. множества М₁ × М₂ = {(-3, -3), (-3, 1), (-3, 2), (-2, -3), (-2, 1), (-2, 2), (-1, 1), (-1, -3), (-1, 2), (0, -3), (0, 1), (0, 2), (1, -3), (1, 1), (1, 2), (2, -3), (2, 1), (2, 2), (3, -3), (3, 1), (3, 2)}, состоящие из всех таких упорядоченных пар (х₁, х₂), что x₁ ϵ M₁, x₂ ϵ M₂ и x₁ + x₂ <0.

Выберем из множества М₁ × М₂ все такие пары: Р⁺ = {(-3, -3), (-3, 1), (-3, 2), (-2, -3), (-2, 1), (-1, -3), (0, -3), (1, -3), (2, -3)}. Это и есть множество истинности данного предиката.

Пример 2. Изобразите на координатной прямой множества истинности следующего заданного на R одноместного предиката: | x+2 | < 5.

Решение: Множество истинности данного предиката представляет собой множество решений неравенства. Поэтому, прежде чем изобразить это множество на числовой прямой, найдем его, т. е. решим данное неравенство. Абсолютная величина некоторого числа меньше 5 тогда и только тогда, когда само число больше -5 и меньше 5: -5 < х+2 < 5.

Первое из этих неравенств равносильно следующему: -7 < х, а второе – следующему: х < 3.

Решением неравенства и областью истинности данного предиката является пересечение двух множеств: ] – 7, ∞[ ᴖ ] - ∞, 3[ = ] – 7, 3[.

 

Задание 3

Варианты 1-11: Выразите множества истинности предикатов согласно варианту через множества истинности входящих в них элементарных предикатов.

Варианты 12-15: Выясните, равны ли множества истинности предикатов согласно варианту.

 

№ вар.	Предикаты
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

 

Примеры выполнения задания 3

Пример 1. Выразите множества истинности следующего предиката через множества истинности входящих в него элементарных предикатов:

Решение: Для того чтобы выразить множества истинности Q данного предиката через множество истинности входящих в него элементарных предикатов, сначала выразим операции ↔ и → через, Ù, Ú, а затем:

Пример 2. Выясните, равны ли множества истинности следующих предикатов:

((P(x) →(Q(x) Ú R(x)))→Q(x)) и Q(x) Ù (P(x)→ R(x))

Решение: Чтобы выяснить, равны ли множества истинности данных предикатов, сначала найдем множества истинности каждого из них, а затем сравним их. Для нахождения множеств истинности сначала выразим → и ↔ через, Ù, Ú. Первый предикат:

Второй предикат:

Сравнивая полученные множества истинности предикатов, делаем вывод, что они равны.

 

Задание 4

Варианты 1-8: Задайте множество так, чтобы над ним предикаты согласно варианту были равносильны.

Варианты 9-15: Докажите согласно варианту утверждения, считая, что каждый из двух предикатов зависит от одних и тех же переменных, пробегающих одни и те же соответственные множества.

 

№ вар.	Предикаты
1	«х кратно 3»; «х кратно 7»
2	«х^2 – х – 2 = 0»; «х^3 + 1 = 0»
3	«Город х находится на берегу реки Волги», «Город х находится на берегу реки Свияги»
4	«х – простое число», «х – четное число»
5	«Диагонали в четырехугольнике х равны», «Четырехугольник х – параллелограмм»
6	«Диагонали в четырехугольнике х взаимно-перпендикулярны», «Четырехугольник х – ромб»
7	«х – треугольник», «Биссектриса одного из внутренних углов треугольника х является его медианой»
8	«х делится на 3», «х делится на 9»
№ вар.	Утверждения
9	Конъюнкция двух предикатов есть опровержимый предикат тогда и только тогда, когда по меньшей мере один из данных предикатов опровержим
10	Конъюнкция двух предикатов есть тождественно истинный предикат тогда и только тогда, когда оба данных предиката тождественно истинны
11	Дизъюнкция двух предикатов есть выполнимый предикат тогда и только тогда, когда по меньшей мере один из данных предикатов выполним
12	Дизъюнкция двух предикатов есть тождественно ложный предикат тогда и только тогда, когда оба данных предиката тождественно ложны
13	Эквивалентность двух предикатов с тождественно истинным одним членом равносильна ее второму члену
14	Конъюнкция тождественно истинного предиката и любого предиката есть предикат, равносильный последнему: T (x) Ù P (x) ↔ Р(x)
15	Дизъюнкция тождественно ложного предиката и любого предиката есть предикат, равносильный последнему: F (x) Ú P (x) ↔ P (x)

 

Примеры выполнения задания 4

Пример 1. Задайте множество так, чтобы над ним следующие предикаты были равносильны: «Треугольник х – равнобедренный», «Три высоты треугольника х равны между собой».

Решение: Ясно, что требуемое множество нужно искать среди подмножеств множества всех треугольников. Элементы этого множества должны быть одновременно и равнобедренными треугольниками, и такими треугольниками, у которых все три высоты равны между собой. Можно показать, что три высоты в треугольнике равны между собой тогда и только тогда, когда этот треугольник равносторонний. Поскольку, кроме того, всякий равносторонний треугольник является равнобедренным, то искомым множеством может быть, например, множество всех равносторонних треугольников. Другое множество, над которым два данных предиката равносильны, – множество всех неравнобедренных треугольников.

Пример 2. Докажите следующие утверждения, считая, что каждый из двух предикатов зависит от одних и тех же переменных, пробегающих одни и те же соответственные множества: Конъюнкция тождественно ложного предиката и любого предиката есть тождественно ложный предикат:F (x) Ù P (x) ↔ F (x)

Решение: Вычислим множество истинности . Следовательно, предикат F(x) ˄ P(x) тождественно ложен.

 

Задание 5

Варианты 1-8: Задайте множество так, чтобы над ним предикаты согласно варианту были равносильны.

Варианты 9-15: Определите согласно варианту, является ли один из предикатов, заданных на множестве действительных чисел, следствием другого.

 

№ вар.	Предикаты
1	«| x | < 3», «x^2– 3x + 2 = 0»
2	«x^4 = 16», «x^2 = -2»
3	«x -1 > 0», «x^2 = -2»
4	«sin x = 3», «x^2 + 5 = 0»
5	«x^2 + 5x – 6 > 0», «x + 1 = 1 + x»
6	«x^2 ≤ 0», «x = sin π»
7	«-5<x», «x<5»
8	«lg x ≤ 1», «1 ≤ х ≤ 10»
9	«х кратно 3», «х четно»
10	«x^2 = 1», «x - 1 = 0»
11	«х нечетно», «х – квадрат натурального числа»
12	«х – ромб», «х – параллелограмм»
13	«х – параллелограмм», «х – ромб»
14	«х – русский ученый», «х – математик»
15	-5 < x, x > 5

 

Примеры выполнения задания 5

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

«x³ – 2x² – 5x + 6 = 0», «| x – 2 | = 1»

Решение: Второй предикат превращается в истинное высказывание лишь при двух подстановках: х = 1 и х = 3. Нетрудно проверить, что эти подстановки превращают и первый предикат в истинное высказывание (являются корнями кубического уравнения). Поэтому первый предикат является следствием второго.

Пример 2. Задайте множество М значений предметной переменной так, чтобы на этом множестве второй предикат был бы следствием первого:

«х – квадрат, «х – параллелограмм».

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

 

ТЕМА 6