UML_4822 дм практикум

- истинно. Однако высказывание x A x y B y - «Всякое натуральное

число четно или всякое натуральное число нечетно» - ложно. Задача 264. Докажите следующие равносильности:

1)x A(x) x A(x) ;

2)x A(x) x A(x) ;

3)с& x A(x) х (с & A(x));

4)с (x A(x)) х (с & A(x));

5)x A(x) B(x) x A(x) x B(x) ;

6)x (с (A(x))) с x A(x) ;

7)x (с & (A(x))) с & x A(x);

8)x (с A(x)) с x A(x) ;

9)x (A(x) с) x A(x) с .

Задача 265. Найдите отрицание следующих формул:

1)x (A(x) & B(x) & C(x));

2)x (A(x) y B( y)) ;

3)x (A(x) y B( y));

4)x (A(x) B(x)) & x (S(x) & R(x)) ;

5)x (R(x) Q(x)) ;

6)x y z (P(x, y, z) Q(x, y, z)) .

Ответ. 1) x A x B x C x ;

2)x A x & y B y ;

3)x A x & y B y ;

4)x A x & B x x S x R x ;

5)x R x & Q x Q x & R x ;

6)x y z P x, y, z & Q x, y, z .

Задача 266. Пусть А(х) и В(х) – любые предикаты. Какие из следу-

Ответ. Формуле (*) равносильны формулы 2) и 7), а остальные не равносильны.

131

Задача 267. Доказать, что для любой формулы предикатов можно построить ей равносильную формулу, не содержащую: 1) кванторов существования; 2) кванторов общности.

Ответ: 1) x F (x) x F (x) ;

2) x F(x) x F (x) .

Необходимо убедиться в их равносильности.

Пример 268. Доказать, что не являются равносильными формулы

x (P(x) & Q(x)) и x P(x) & x Q(x) .

Доказательство. Приведем контрпример. Пусть Р(х) – любой не тождественно истинный и не тождественно ложный предикат, а Q(x) тоже не тождественно истинный и не тождественно ложный предикат. Тогда

x P(x) x Q(x) не равносильны.

Доказательство аналогично предыдущему примеру. Задача 270. Докажите, что:

1) x y F(x) & G( y) y x F(x) & G( y) ;

2) то же с заменой & на V;

3) можно ли в 1) и 2) заменить F(x) и G(y) двухместными предикатами, зависящими от х и у?

Ответ: 1) Равносильность справедлива, поскольку

x y F(x) & G( y) x F(x) & y G( y) x F(x) & y G( y);y x F(x) & G( y) y x F(x) &G( y) x F(x) & y G( y).

2) доказательство аналогично п.1).

Задача 271. Пусть А(х) и В(х) - два одноместных предиката, определенных на множестве М, таких, что истинным является высказывание

Указание. Для доказательства достаточно данную формулу упростить с помощью равносильных преобразований.

Задача 272. Каким условиям будут удовлетворять области истинности предикатов А(х) и В(х), определенных на множестве М, если истинны высказывания?

1) x A(x) B(x) & x A(x) & B(x) ; 2) x A(x) & B(x) & x A(x) B(x) ; 3) x A(x) & B(x) x A(x) B(x) .

Ответ.

1) I A IB ;

132

2)I A , I B – любое подмножество М;

3)I A IB или I A IB = .

Задача 273. Пусть предикат P(x, y) определен на множестве М = N

N и означает «x < y».

1) Какие из следующих предикатов тождественно истинные и какие тождественно ложные:

а) x P(x, y) ; б) x P(x, y) ; в) у P(x, y) ; г) у P(x, y) ?

2)Для тех предикатов из 1), которые не являются ни тождественно истинными, ни тождественно ложными укажите область истинности и область ложности.

3)Какие из следующих предложений истинны и какие ложны:

Ответы:

1) а) не тождественно истинный и не тождественно ложный преди-

кат;

б) тождественно ложный предикат; в) тождественно истинный предикат; г) тождественно ложный предикат.

2) Для предиката а) x P(x, y) =Q( y) IQ 2, 3, 4,... . 3) истинны предложения б), ж), а остальные – ложны.

Пример 274. Показать, что кванторы общности и существования не перестановочны, то есть высказывания x y A(x, y) и y x A(x, y) могут,

вообще говоря, иметь различные значения.

Решение. Пусть А(х) - предикат «х делит у». Тогда утверждениеx y A(x, y) : «Для всякого х существует такое у, что х делит у», очевидно, истинно, между тем как y x A(x, y) : «Существует такое у, что любое х

делит у» - ложно.

Этот пример показывает, что порядок следования разноименных кванторов существенен. Приведенные высказывания не равносильны.

4.6. Понятия общезначимости и выполнимости формул логики предикатов. Предваренная нормальная форма

Особый интерес представляют формулы, которые тождественно истинны на всякой области. Такие формулы называют общезначимыми.

Связано с понятием общезначимости и понятие выполнимости фор-

мул.

133

Определение. Формулу А логики предикатов называют выполнимой в области М (или в другой области), если существуют значения переменных, входящих в эту формулу и отнесенных к области М (или к другой области), при которых формула А принимает истинные значения.

Определение. Формула А называется тождественно истинной (ложной) в области М, если она принимает истинные (ложные) значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области.

Из приведенных определений можно сделать следующие выводы:

-если формула общезначима, то она и выполнима в этой области;

-если формула тождественно истинна (ложна) в области, то она и выполнима (не выполнима) в этой области.

Пример 275. Доказать выполнимость формулы A x y P(x, y) .

Решение. Если предикат Р(х,у) «x<y», определенный в области М=Е Е, где E={0,1,..., n,...}, то формула А тождественно истинна в области М, и, следовательно, выполнима в заданной области.

А если в качестве предиката Р(х,у) взять «y<x», то формула будет тождественно ложной в области М, и, следовательно, не выполнимой в этой области.

Пример 276. Формула x y P x & P y выполнима. Убедимся в

этом. Для этого рассмотрим предикат Р(х) - «число х - четно», определенный в области М=Е Е, где E={0,1,..., n,...}. Эта формула тождественно истинна в области М и выполнима в этой области. Однако, если предикат «число х - четно» рассматривать в области четных чисел М=Е1 Е1, где Е1

- множество четных чисел, то формула x y P x & P y будет тожде-

ственно ложной в области М, и, следовательно, не выполнимой.

Пример 277. Доказать, что следующая формула является общезна-

A x P x Q x P x & xQ x .

Решение. Считая, что формула А определена на любой области М, проведем равносильные преобразования:

Ax P(x) Q(x) x P(x) & xQ(x)

x(P(x) Q(x)) x P(x) & xQ(x)

x P x Q x xP x xQ x x P(x) & Q(x) x P(x) xQ(x)

x (P(x) & Q(x) xQ(x) x P(x) x P x & Q x Q x xP x

x P x Q x xP x x P x xP x xQ x 1 xQ x 1,

то есть формула А тождественно истинна для любых одноместных предикатов Р(х) и Q(x) и в любой области.

134

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

1)y x P x, y x y P x, y ;

2)x P x Q x x P x xQ x ;

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

Задача 281. Даны формулы:

1) B x A x A t ; 2) B A t x A x .

Можно ли привести пример формулы А(х) такой, чтобы приведенные формулы были выполнимы.

Ответ. 1) нельзя; 2) можно. Необходимо обосновать ответы.

Для решения приведенных задач установим связь между общезначимостью и выполнимостью формул ЛП посредством теорем.

Теорема А. Для того, чтобы формула А была общезначимой, необходимо и достаточно, чтобы ее отрицание было не выполнимо.

Доказательство.

Необходимость. Если формула А общезначима, то, очевидно, что Ā - тождественно ложная формула в любой области, и поэтому формула Ā не выполнима.

Достаточность. Пусть Ā не выполнима в любой области, тогда по определению невыполнимой формулы Ā - тождественно ложная в любой области. Значит, формула А - тождественно истинная формула в любой области, и, следовательно, она общезначима.

Теорема Б. Для того, чтобы формула А была выполнимой, необходимо и достаточно, чтобы формула Ā была не общезначима.

Задача 282. Какие из нижеприведенных формул являются общезна-

135

6) x Ф1(х) Ф2 (х) хФ1(х) уФ2 (х) ; 7) x R x x R x ;

8) x R x x R x ;

9) x R x & xQ x x R x &Q x ; 10) x R x xQ x x R x Q x .

Ответ. Общезначимыми являются формулы 1), 3), 5), 6), 8), 9). Задача 283. Докажите тождественную ложность формулы

x y F(x) F( y) & F(x) F( y) & F(x)) .

Указание. Подвергнуть данную формулу равносильным преобразованиям.

видно, тождественно ложна, то и формула А тождественно ложна. Определение. Формула логики предикатов имеет нормальную фор-

му, если она содержит только операции &, и кванторные операции, а операция отрицания отнесена к элементарным формулам.

Среди нормальных формул логики предикатов важное значение имеют так называемые предваренные нормальные формы (п.н.ф.), в ко-

торых кванторные операции либо полностью отсутствуют, либо используются после всех операций алгебры логики.

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

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

Пример 285. Пусть дана формула x y A x, y x y B x, y . Приве-

сти ее к п.н.ф.

Решение. Вначале в соответствии с теоремой де Моргана вынесем кванторы за знак отрицания:

136

x y A x, y x y B x, y x y A x, y x y B x, y .

Затем в соответствии с (4.8), (4.19) и (4.20) перечня равносильностей вынесем кванторы существования за скобку:

x y A x, y x y B x, y x y A x, y y B x, y .

Для того, чтобы вынести кванторы всеобщности, нужно предварительно переименовать переменные.

Примечание. Квантор всеобщности нельзя выносить за скобки, если выражения объединены знаком дизъюнкции: формулы x A x x B x

и x A x B x не равносильны (!). Действительно, первая формула

утверждает, что один из предикатов А(х) или В(х) тождественно истинен, между тем как вторая формула означает, что дизъюнкция предикатов A x B x тождественно истинна.

Можно найти примеры двух не тождественно истинных предикатов, дизъюнкция которых тождественно истинна. Для таких предикатов вторая формула будет истинна, а первая ложна. С другой стороны, если первая формула истинна, то, очевидно, истинна и вторая. Таким образом, можно

сказать, что вторая формула является логическим следствием первой:

x A x x B x x A x B x .

Аналогично, можно убедиться, что истинна формула

x A x B x x A x x B x ,

но знак импликации нельзя заменить знаком равносильности.

И все-таки имеется возможность в несколько иной форме выносить квантор всеобщности и квантор существования за скобки и в этих случаях.

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

Истинность этих равносильностей можно легко уяснить. Так, левая часть уравнения (4.23) принимает значение И в том и только в том случае, если А(х) истинно для всех х, или же если С истинно, то есть истинно и высказывание x A x C . Предположим, наоборот, что высказывание

x A x C - истинно: если при этом С И, то и левая часть имеет значение И. Если же С Л, то формула x A x C принимает значение И для

всех х. Левая часть принимает при этом опять значение И. Аналогично доказательство и формулы (4.24).

137

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

Следовательно, согласно формуле равносильности (4.23), можно утверждать следующую цепочку равносильностей:

x A x x B x x A x y B y

x A x y B y x y A x B y ,

Вывод. Равносильности (4.25) и (4.26), как мы видим, позволяют в несколько иной форме выносить кванторы за скобки. Приведенные равносильности (4.8)-(4.11), (4.16), (4.21) и (4.22) позволяют выражениям ЛП сопоставлять формулы некоторого стандартного вида, так называемые п.н.ф.

А теперь вернемся к решению начатого примера.

x y A x, y x y B x, y x y A x, y y B x, y .

Для того, чтобы вынести кванторы всеобщности, нужно переименовать переменные:

x y A x, y y B x, y x y A x, y z B x, zx y A x, y z B x, z x y z A x, y B x, z .

Последняя формула уже имеет предваренную нормальную форму. Окончательно получаем

x y A x, y x y B x, y x y z A x, y B x, z .

Задача 286. Привести к п.н.ф. формулу

A x y P(x, y) & x y Q(x, y) .

Решение. Проведем равносильные преобразования в соответствии с примером 285:

Ax y P(x, y) & x y Q(x, y) x y P(x, y) & z Q(x, z)

x y P(x, y) & z Q(x, z) x y z P(x, y) & Q(x, z) .

Задача 287. Привести к п.н.ф. следующие формулы логики предика-

тов:

7) B x y P(x, y) x y Q(x, y) ; 8) B x y P(x, y) x y Q(x, y).

138

Ответ. 1) x y z u P(x, y, z,u) ;

2)x (R(x) Q(x, y)) ;

3)x ( p & R(x)) ;

4)x y ( A(x) & A( y) A( y) & A(x)) ;

5)x y ( A(x) B( y)) ;

6)x z y P(x, y) & Q(z, y) ;

7)x y z P(x, y) Q(x, z) ;

8)x y z P(x, y) Q( y, z) .

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

x P(x) & x Q(x) x (P(x) & Q(x)) ; p & x P(x) x ( p & P(x)) ;

p x P(x) x ( p P(x)) ; p x P(x) x ( p P(x)) ;

x P(x) x Q(x) x (P(x) Q(x)) ; c x P(x) x (c P(x)) ;

c & x P(x) x (c & P(x)) ; c x P(x) x (c P(x)) ;

x P(x) & x Q(x) x y (P(x) & Q( y)) ;x P(x) x Q(x) x y (P(x) Q( y)) .

4.7. Анализ рассуждений, правила вывода средствами логики предикатов

На языке ЛП мы уже можем провести анализ высказываний, приведенных в разделе 4.1 в качестве иллюстраций недостаточности ЛВ для такого анализа.

Пример 288. Высказывание «Всякое целое число - рациональное число; 1 - целое число; следовательно, 1 - рациональное число» проанализировать средствами ЛП.

Решение. Введем два одноместных предиката, определенных на множестве вещественных чисел С(х) - «х есть целое число» и R(x) - «х есть рациональное число».

Используя эти предикаты и квантор , первую посылку можно сформулировать так: «Для всякого х, если х - целое число, то х - рациональное число» и записать в принятых обозначениях

x (C(x) R(x)).

139

В этих же обозначениях вторая посылка запишется - С(1), а заключение R(1). Установим правильность этого рассуждения, то есть убедимся, что при истинности посылок его заключение не может быть ложным.

Так как x (C(x) R(x)) - истинное высказывание, то предикат C(x) R(x) при подстановке вместо переменной х любого ее значения обращается в истинное высказывание.

Подставим х=1, получим C(1) R(1). Теперь C(1) R(1), C(1)|-R(1)

по ПЗ. Если под С и R понимать предикатные переменные, а под 1 - название какого-нибудь элемента из области определения предикатов C(x) и R(x) (можно вместо 1 писать а), то мы установим правильность не только заданного в примере рассуждения, но и любого рассуждения такой же

представляющего собой одно из возможных обобщений ПЗ в ЛП.

По этой схеме можно установить, в частности, и правильность рассуждения: «Всякий ромб - параллелограмм; ABCD - ромб; следовательно, ABCD - параллелограмм».

В этом случае С(х) обозначает предикат «х - ромб»; R(x) - предикат «х - параллелограмм», определенные, например, на множестве четырехугольников, а элемент а этого множества - четырехугольник ABCD.

Важно отметить, что в традиционной логике большое внимание уделяется четырем типам категорических высказываний, которые обычно обозначаются заглавными латинскими буквами A, E, I, O:

A - общеутвердительное высказывание «Всякое S суть Р»:x(S(x) P(x)), что означает: «Для всех х, если х обладает свойством S, то х обладает и свойством Р»;

E - общеотрицательное высказывание «Никакое S не есть Р»:x S x P x , что означает: «Для всех х, если х обладает свойством S, то он не обладает и свойством Р»;

140