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

4. Р(х) Q(x).

Решение. В соответствии с условием имеем IP 2, 4, 6,...,2n,... ,

IQ 3, 6, 9,...,3n,... . Тогда:

1.I P&Q IP IQ = 6,12,...,6n,... ;

2.I P Q I P IQ = 2, 3, 4, 6,...,2n, 3n,... ;

3.IP СI P = N \ IP 1,3,5,...,2n 1,... ;

4.I P Q СI P IQ = 1, 3,5,...,2n 1,... {3, 6,9,...,3n,...}.

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

Задача 237. На диаграмме (рис. 20) заданы области истинности пре-

обозначены теми же буквами, что и предикаты.

Рис. 20. Области истинности предикатов А(х), В(х), С(х) для задачи 237

Заштрихуйте области истинности предиката:

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

Задача 238. Записать предикат, полученный в результате логических операций над предикатами Р(х), Q(x) и R(x), область истинности которого заштрихована на рис. 21.

113

M

IA IQ

IR

Рис. 21. Диаграмма области истинности предиката Р(х)&Q(x)&R(x)

Решение. Так как здесь I I P IQ I R , то искомый предикат имеет

вид

Р(х) & Q(x) & R(x).

Задача 239. Запишите предикаты, полученные в результате логических операций над предикатами Р(х), Q(x) и R(x), области истинности которых (I) заштрихованы на рис. 22.

Рис. 22. Исходные данные для задачи 239

114

Задача 240. Предикаты А(х) и В(х) определены на некотором множестве М. В каком отношении должны находиться области истинности IА и IВ этих предикатов, чтобы:

1) А(х) В(х) принимал значение И:

а) для всех х из М; б) для всех х из А; в) для всех х из В; г) ни для одного значения х из М (принимал значение Л при всех

значениях х из М)?

2) А(х) В(х) принимал значение И:

а) для всех х из М; б) ни для одного значения х из М?

на множестве М = М1 М2 R R. Найти множество истинности предиката А(х, y) B(х, y) и изобразить его с помощью кругов Эйлера-Венна.

Решение.

Так как А(х, y) B(х, y) =( А(х, y) B(х, y) )&( B(х, y) А(х, y) ), то

Рис. 23. Диаграмма области истинности А(х, y) B(х, y)

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

Задача 242. На множестве М = {1, 2, 3, ..., 20} заданы предикаты: А(х) : «х не делится на 5»; В(х) : «х – четное число»; С(х) : «х – число простое»;

D(х) : «х кратно 3».

Найдите множество истинности следующих предикатов:

115

Задача 243. Изобразите на диаграммах Эйлера-Венна области истинности для следующих предикатов:

1.Р(x) & Q(x) ;

2.Р(x) Q(x) ;

3.P(x) Q(x) R(x) & Q(x) ;

4.P(x) (Q(x) Q(x)) ;

5.P(x) & Q(x) R(x) .

4.3. Кванторные операции над предикатами

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

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

Одной из таких операций является подстановка вместо предметных переменных их значений. Если в предикат Р(x1, x2,..., xn) подставить вме-

116

сто всех предметных переменных какие-нибудь их значения а1, а2,..., аn, то получим высказывание Р(а1, а2,..., аn), истинное или ложное, относящееся к конкретной подстановке предметов (а1, а2,..., аn).

Например, если в двухместном предикате «х делится на у» подставить вместо переменных х, у пару чисел (6,2), получим истинное высказывание «6 делится на 2», если же подставить пару чисел (5,2), то получим ложное высказывание «5 делится на 2». Каждое из этих высказываний относится к определенной паре чисел.

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

Квантор всеобщности. Пусть Р(х) - какой-нибудь предикат, тогда квантор всеобщности - это операция, которая сопоставляет Р(х) высказывание

Это высказывание (4.1) записывается х Р(х) и читается «Для всех х

Р от х».

Определение. Под выражением х Р(х) понимают высказывание, истинное, тогда, когда Р(х) истинно для каждого элемента х из множества М и ложное в противном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное высказывание будет «Для всякого х Р(х) истинно». Переменную х в предикате Р(х) называют свободной (ей можно придавать различные значения из М), в высказывании х Р(х) перемен-

ную х называют связанной квантором .

Определение. Пусть Р(х) – предикат, определенный на множестве М. Под выражением х Р(х) понимают высказывание, которое является истинным, если существует хотя бы один элемент х М, для которого Р(х) истинно, и ложным в противном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное выражение будет «Существует х, при котором Р(х) истинно». Символ называют квантором существования. В высказывании х Р(х) переменная х связана квантором .

Например:

1) Если Р(х) - предикат «х - простое число», то х Р(х) - ложное высказывание «Всякое число - простое», а х Р(х) - истинное высказывание «Существует число х такое, что оно - простое».

117

2) Пусть на множестве N натуральных чисел задан предикат Р(х): «Число х кратно 5». Используя кванторы, из данного предиката можно получить высказывания х N Р(х) - «Все натуральные числа кратны 5»;х N Р(х) - «Существует натуральное число, кратное 5».

Очевидно, первое из этих высказываний ложно, а второе истинно. Кванторные операции применимы и к многоместным предикатам. Например, на множестве М задан двухместный предикат Р(х,у).

Применение кванторной операции к предикату Р(х,у) по переменной х ставит в соответствие двухместному предикату Р(х,у) одноместный предикат х Р(х,у) (или одноместный предикат х Р(х,у)), зависящий от переменной у и не зависящий от переменной х. К ним можно применить кванторные операции по переменной у, которые приведут уже к высказываниям следующих видов:

у х Р(х,у), у х Р(х,у), у х Р(х,у), у х Р(х,у).

Выводы:

-высказывание х Р(х) истинно только в том единственном случае, когда Р(х) - тождественно истинный предикат;

-высказывание х Р(х) ложно только в том единственном случае, когда Р(х) - тождественно ложный предикат;

-если в n-местном предикате связать кванторами k переменных

(k n), то получим логическую функцию (n-k) свободных переменных, то есть (n-k)-местный предикат, в частности при k=n получается 0-местный предикат, или высказывание.

Пример 244. Задан двухместный предикат Р(х,у): «x<y», определенный на множестве действительных чисел х, у D. Осуществим анализ влияния кванторов, их расположения на характер высказывания: {И, Л}.

1)х у Р(х,у) - «для всякого х и всякого у выполняется x<y» - ложно.

2)у х Р(х,у) - «для всякого у и всякого х выполняется x<y» - ложно.

3)х у Р(х,у) - «существует х и существует у, такие что x<y» - истинно.

4)у х Р(х,у) - «существует у и существует х, такие что x<y» - истинно.

5)х у Р(х,у) -«для всякого х существует у, такое что x<y» - истинно.

Выводы:

- высказывания 1) и 2) оба ложны и имеют один и тот же смысл; высказывания 3) и 4) оба истинны и имеют один и тот же смысл. Структуры 1) и 2), так же как структуры высказываний 3) и 4), отличаются лишь порядком следования одноместных кванторов. Как видно, изменение порядка одноместных кванторов не влияет на смысл и значение истинности высказывания;

118

-высказывание 5) - истинно, а 6) - ложно. Структуры этих высказываний отличаются лишь порядком разноименных кванторов, что приводит

кизменению смысла и, возможно, значения истинности высказывания. Высказывание 5) утверждает об отсутствии в множестве D наибольшего числа, высказывание 6) - о наличии такого числа;

-высказывание 7) - ложно, а высказывание 8) - истинно. Второе утверждает о наличии в D наименьшего числа, первое - об отсутствии такого числа. Структуры этих высказываний, так же как и высказываний 5) и 6) отличаются лишь порядком разноименных кванторов.

Задача 245. Задан предикат Q(x,y): «х:у», определенный на множе-

стве натуральных чисел N N. Применить кванторные операции к предикату «у является делителем х». Осуществить анализ восьми возможных высказываний и оценить влияние изменения порядка следования кванторов на смысл и логическое значение высказывания

Решение. Так как высказывание y х Q(х, y) означает, что для вся-

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

Высказывание x y Q(х, y) означает, что есть натуральное число х,

которое делится на любое натуральное число у. Это высказывание, очевидно, ложно. Дальнейший анализ по аналогии с примером 208 проведите самостоятельно.

Замечание. Квантор общности можно рассматривать как обобщение конъюнкции, а квантор существования - как обобщение дизъюнкции.

Пусть предикат Р(х) определен на множестве M={a1, a2,..., an}, содержащем конечное число элементов, тогда высказывание х Р(х) равносильно конъюнкции Р(a1) Р(a2) ... Р(an), то есть х Р(х)=

Р(a1) Р(a2) ... Р(an), а высказывание х Р(х) - дизъюнкции

Р(a1) Р(a2) ... Р(an), то есть х Р(х)=Р(a1) Р(a2) ... Р(an).

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

1.х2 + 3х + 2 = 0;

2.х4 – 3х + 8 = 0;

3.Любое простое число р не имеет делителей, отличных от себя и 1;

4.Натуральное число n не меньше 1.

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

119

го предиката можно, разумеется, использовать и функциональную символику, например, N(x)) и x >0 (этот одноместный предикат можно обозначить через Р(х)).

После выделения этих двух одноместных предикатов высказывание «Всякое натуральное число больше нуля», рассматриваемое в рамках логики высказываний как элементарное, на языке логики предикатов запишется следующим образом:

x x N x 0 или x N(x) Р(х) или x N Р(х) .

Пример 247. «Треугольник АВС равен треугольнику А1В1С1».

Для записи этого предложения на языке логики предикатов поговорим о предикате равенства.

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

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

– рефлексивностью (предмет х совпадает с самим собой);

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

Эти условия, выражающие предикат равенства, выражаются следу-

Из (4.2) и (4.3) выводим свойства симметричности

x y x y y x

и транзитивности

x y z x y z x z .

Задача 248. Даны предикаты Р(х) : х2 + х +1>0 и Q(х) : х2 – 4х + 3 =0,

определенные на множестве R. Требуется установить, какие из следующих высказываний истинны и какие ложны:

1. х Р(х) ;

120