3.1. Какие из следующих выражений являются предикатами:

а) «х делится на 5» (х Î N);

б) «Река х впадает в озеро Байкал» (х  пробегает множество названий всевозможных рек);

в) «х2  + 2 х + 4» (х Î R);

г) «(х + у)2 = х2  + 2 хy + y2» (x, yÎR);

д) «х есть брат у» (х, у пробегают множество всех людей);

е) «х и у» (x, у пробегают множество всех студентов данной группы);

ж) «х и у лежат по разные стороны от z» (x, у пробегают множество всех точек, а z — всех прямых одной плоскости);

з)         «ctg 45° = 1»;

и) «х  перпендикулярна у» (х, у
пробегают множество всех прямых одной плоскости).

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

а)  «3 + 4 = 7»;

б)  «Вера и Надежда — сестры»;

в)  «Сегодня — вторник»;

г)  «Город Саратов находится на берегу реки Волги;

д)  «sin 30° = 1/2»;

е)  «А. С. Пушкин — великий русский поэт»;

ж)  «32 + 42= 52;

з)  «Река Индигирка впадает в озеро Байкал»;

и)  «».

Построив такой предикат, постарайтесь или точно указать его область истинности, или как-то ее обрисовать.

Решение.
и) Можно указать три предиката, каждый из которых обращается в данное высказывание при соответ­ствующей подстановке.  Первый  предикат одноместный:

«» . Он превращается в данное высказывание при подстановке . Получающееся высказывание истинно. Указанным значением не исчерпыва­ется множество истинности построенного предиката. Как не­трудно  установить, это  множество  следующее:   . Второй  предикат также одноместный: «» (yÎ R). Он превращается в данное высказывание при подста­новке у = 1. Ясно, что этим значением и исчерпывается множество истинности этого предиката. Наконец, можно построить третий предикат, двухместный: «»  . Он превращается в данное высказы­вание при подстановке , у = 1. Его область истинности представляет собой множество упорядоченных пар, сово­купность которых графически изображается в виде бесконеч­ного семейства кривых, называемых тангенсоидами.

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

а)

б)

в)

г)

д)

е)

ж)

з)

и)

к)

л)

Решение. а) Двухместный предикат их «x + y = 7» задан над множеством действительных чисел R. Это означает, что вместо каждой из двух его предметных переменных, х и у могут быть подставлены действительные числа. Если такая подстановка сделана вместо обеих переменных, например «6 + 3 = 7», то предикат превращается в высказывание (в нашем случае ложное). Но данный двухместный предикат «x + y = 7» может быть превращен в высказывание и другим путем: именно путем применения к нему операций квантификации (взятия квантора общности иди квантора существования). Применим сначала к двухместному предикату «x + y = 7» операцию взятая квантора существования по переменной у. Подучим уже одноместный предикат «» от­носительно переменной x, которая пробегает множество R. Говорят, что в получением выражении переменная у связана, а переменная х
свободна. Вместо переменной у мы уже ничего не можем подставлять, в то время как вместо х могут быть подставлены действительные числа, в результате чете одноместный предикат будет превращаться в высказывания. Например, высказывание «» можно прочи­тать так:  «Существует действительное число у, такое, что ». Ясно, что это высказывание истинно. (В качестве такого у, существование которого утверждает это выска­зывание, нужно взять действительное число — 3.) Легко далее понять, что, какое бы действительное число х0 мы ни подста­вили вместо переменной х в предикат «($у) (х + у = 7)», предикат превращается в истинное высказывание. Действи­тельно, в качестве такого числа у, существование которого утверждает высказывание, нужно взять разность 7 — х0. Это обстоятельство согласно определению операции взятия квантора общности означает, что получающееся высказыва­ние «(«х)($у)(х + у = 7)» истинно. Его можно прочитать следующим образом: «Для любого действительного числа су­ществует такое действительное число, сумма которого с пер­вым равна 7». В выражении «(«х)($у)(х + у = 7)» уже нет свободных переменных. Обе переменные х и у стоят под зна­ками кванторов и потому являются связанными. Само же выражение уже не является предикатом, оно есть высказы­вание, истинное, как мы установили. Впрочем, если мы хотим, то, развивая понятие предиката, можем считать, что выска­зывание — это 0-местный предикат, т. е. предикат без перемен­ных. Но мы должны осознавать, что количественный переход от одноместного предиката к 0-местному приводит к качествен­ному скачку, так что 0-местный предикат — это объект ка­чественно иной, нежели предикат одноместный, хотя и под­водимый нами условно под понятие «предикат».

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

и)  Это высказывание можно прочитать так: «Любое дей­ствительное число равно самому себе тогда и только тогда, когда оно больше 1 или меньше 2». Чтобы выяснить,   истинно или ложно это высказывание, будем пытаться искать такое действительное число х0, которое превратило бы одноместный предикат

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

Ясно, что предикат «х = х» превращается в истинное вы­сказывание при подстановке вместо х любого действитель­ного числа, т. е. является тождественно истинным. Спраши­вается: можно ли указать действительное число, которое превратило бы предикат «» в ложное выска­зывание? Нет, потому что, какое бы действительное число мы ни взяли, оно либо больше 1, либо меньше 2 (либо одновремен­но и больше 1, и меньше 2, что вовсе не возбраняется в нашем случае). Следовательно, предикат «» тожде­ственно истинен. Тогда тождественно истинным будет и пре­дикат

.

И значит, данное высказывание

по определению операции взятия квантора общности истинно.

3.4.      Пусть P (x) и Q (x) — одноместные предикаты, заданные на множестве М, такие, что высказывание                     

истинно. Доказать, что высказывание  ложно.

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

а) «| х | < — 3»,                                   « x2 — 3x + 2 = 0 »;

б) «х4
= 16»,                          « x2   =  — 2 »;

в) «х — 1 > 0»,                                   « (x — 2) (х + 5)  =  0»;

г) «sin x = 3»,                        « x2  + 5  = 0»;

д) « х2
+ 5x — 6 > 0»,             « x + 1 =  1 + x »;

е) «х2
£ 0»,                             « x  =  sin p »;

ж) « x3 — 2×2 — 5ч + 6 = 0»,  «| х — 2| = 1».

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

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

а) «х
кратно 3»,         «х четно»;

б) «x 2 = 1»,                «x  -1 = 0»;

      в) «x нечетно»,          «х — квадрат натурального числа»;

г) «x — ромб»,            «x — параллелограмм»;

д) «x — параллелограмм»,    «x — ромб»;

е) «x — русский ученый»,    «x — математик»;

ж) «x — квадрат»,      «x — параллелограмм».

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

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

3.8.
Докажите,  что импликация двух  предикатов, зави­сящих от одних и тех же переменных, с тождественно лож­ным следствием равносильна отрицанию ее посылки.

ЗАПИСИ  НА  ЯЗЫКЕ  АЛГЕБРЫ  ПРЕДИКАТОВ

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

Пример 1. Что означает утверждение «Прямые а и  b не па­раллельны»?

Чтобы раскрыть смысл формулы Ø(а || b), надо найти отрицание формулы  $a (a Ì a & b Ì a) & (a Ç b = Æ Ú a = b).  Имеем   Ø(а || b) = Ø($a(a Ì a & b Ì a) & (a Ç b = Æ Ú a = b)) = Ø$a(a Ì a & b Ì a) Ú Ø(a Ç b = Æ Ú a = b)) = Ø$a(a Ì a & b Ì a) Ú a Ç b ¹ Æ & a ¹ b.

Но формула Ø$a(a Ì a & b Ì a), означающая на русском языке «Не существует плоскости, содержащей обе прямые а и b», передает отношение скрещивания прямых, а формула a Ç b ¹ Æ & a ¹ b, пере­водимая на русский язык предложением «Прямые а и b имеют общие точки,   но  не совпадают»,  выражает отношение пересечения  прямых.

Таким образом, непараллельность прямых означает их пересе­чение или скрещивание. Пример 2. Записать на языке алгебры предикатов так назы­ваемые «аристотелевские категорические суждения» часто исполь­зуемые в рассуждениях: «Все S суть Р», «Некоторые S суть Р», «Ни одно S не суть Р», «Некоторые S не суть Р».

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

В втором столбце дается стандартная словесная формулировка суждений в традиционной логике, а в пятом — их запись на языке алгебры предикатов, при этом S(x) надо понимать как «х обладает свойством S», а Р(х) — как «х обладает свойством Р».

В четвертом столбце показаны отношения между объемами Vs и VР
понятий S и Р, если суждения понимаются в наиболее общем виде, когда они дают исчерпывающую информацию только о субъекте. Например, из суждения «Все S суть Р» ясно, что речь идет обо всех S, объем же предиката не определен: идет ли речь обо всех объектах, обладающих свойством P, или только о некоторых; только ли S суть P, или и другие объекты тоже суть Р. Иногда эту неопределенность в отношении объема предиката Р устраняет контекст, иногда это устранение и не требуется. Чтобы подчеркнуть отношение объема VР к объему Vs, используют более определенную формулировку «Все S и не только S
суть Р» или «Все S и только они суть Р». Вторая формулировка называется общевыделяющим утвер­дительным суждением. Первому суждению отвечает диаграмма Венна, представленная на рис. 1, а, второму—на рис. 1, б. С учетом сказанного суждение «Некоторые S суть Р» в общем виде понимается как «Неко­торые S  и не только они суть Р», чему соответствует диаграмма рис. 2, а, но оно может означать и «Некоторые S
и только они суть S» (рис. 2, б). Суждению «Все S не суть Р», понимаемому в общем виде, соответ­ствует диаграмма на рис. 3, а. Этому же суждению в выделяющей форме «Все S и только они не являются Р» отвечает диаграмма на рис. 3, б. Такая формулировка соответствует описанию отношения между противоречащими понятиями, т. е. такими, объемы которых не пересекаются и исчерпывают объем более общего родового поня­тия. Наконец, суждению «Некоторые S не есть Р» в общем виде соответствует диаграмма на рис. 4, а, а в выделяющем виде «Некото­рые S  и только  они   не  являются Р» — диаграмма   на   рис. 4,  б.                                                                                                                                     Таблица 3.1

Вид суждения	Запись в традиционной логике словесных формулировок	Запись на языке алгебры предикатов	Отношения между объемами Vs и VР
Общеутвердительное	Все S суть P		Рис.1
Частноутвердительное	Некоторые S суть Р		Рис. 2
Общеотрицательное	Ни одно S не суть Р		Рис.3
Частноотрицательное	Некоторые S не суть Р		Рис.4

Пример 3. Проанализировать рассуждение «Все люди смертны; Сократ — человек; следовательно, Сократ смертен». Первая посылка рассуждения есть общеутвердительное суждение (см. пример 2). Введем обозначения: Ч(х): х — человек; С (х): х — смертен; с — Сократ.

Структура  рассуждения:

«х(Ч(х)ÞС(х)), Ч(с) ├ С(с).                                                                       (3.1)

Пусть следование (3.1) не имеет места. Тогда в некоторой области Do должен существовать набор (a, li(x), lj(x)) для (с, Ч(х), С(х)), при котором будут выполняться следующие условия:

«х( li(x) Þ lj (х)) = И;  li(a) = И;  lj(a) = Л.

Но тогда импликация li(a) Þ lj (a) имеет значение Л, а значит, по определению квантора общности, «х( li(x) Þ lj (х)) = Л, что противо­речит первому условию. Поэтому следование 2.8 верное, а исходное рассуждение правильное.

Пример 4. Проанализировать рассуждение: «Всякая хоккейная команда, могущая победить ЦСКА, — команда высшей лиги. Ни одна команда высшей лиги не может победить ЦСКА. Значит ЦСКА непо­бедима».

О  бозначения:    П(x):    команда   х   может    победить    ЦСКА; В (x): команда х из высшей лиги.

Структура   рассуждения:

«х(П(х) Þ В(х)), «х(В(х) Þ ØП(х)) ├ Ø$хП(х).

Устанавливаем, правильно ли полученное следование, методом равносильных преобразований. Пользуясь следствием б) обобщения предложения 1.10, преобразовываем формулу «х(П(х) Þ В(х))&»х(В(х) Þ ØП(х)) Þ Ø$хП(х).

Имеем:     «х(П(х) Þ В(х)) & «х(В(х) Þ ØП(х)) Þ Ø$хП(х) = «х((П(х) Þ В(х)) & (В(х) Þ ØП(х))) Þ Ø$хП(х) = Ø(«х((ØП(х) Ú В(х)) & (ØВ(х) Ú ØП(х))) & $хП(х)) =

= Ø(«х(ØП(х) Ú (В(х) & ØВ(х)))) & $хП(х) = ØЛ = И.

В    этих    равносильных    образованиях    дважды    использовалось свойство конъюнкции  A & ØA= Л и один раз свойство дизъюнкции А Ú Л = А.

Таким образом, исходная формула общезначима, а значит, рас­суждение правильное.

Пример 5. Проанализировать рассуждение: «Если бы какая-ни­будь команда могла обыграть ЦСКА, то и какая-нибудь команда высшей лиги могла бы. «Динамо» (Минск) — команда высшей лиги, а не может обыграть ЦСКА. Значит, ЦСКА непобедима».

Обозначения: П(х): команда х может победить ЦСКА; В(х): команда х из высшей лиги; д — «Динамо» (Минск).

Структура  рассуждения:

«хП(х) Þ $х(В(х)& П(х)), В(д) & ØП(д) ├ Ø$хП(х).                                                (3.2)

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

Следование (3.2) неверно. Чтобы это доказать, достаточно ука­зать хотя бы одну интерпретацию формул, выражающих посылки и заключение, в которой посылки будут принимать значение И, а за­ключение — значение Л. Такой интерпретацией, например, является следующая: D = {1, 2, 3, 4}. В этой интерпретации имеем, после вычислений,

И Þ И,   И &ØЛ ├ ØИ,  или   И, И  ├ Л.

Итак, в этой интерпретации обе посылки имеют значение И, а за­ключение — значение Л. Значит, следование (3.2) неверно, а рас­суждение неправильное.

3.9. Введя подходящие одноместные предикаты на соот­ветствующих областях, переведите следующие высказывания, на язык алгебры предикатов:

а)   Все рациональные числа действительные.

б)   Ни одно рациональное число не является действительным.

в)   Некоторые   рациональные   числа  действительные.

г)   Некоторые рациональные числа не являются действи­тельными.

Решение.  Введем следующие одноместные предикаты

Q (х):
«х — рациональное число»;

R (x):
«х — действительное число».

Тогда перевод приведенных высказываний на язык алге­бры предикатов будет таким:

а)  

б)  

в)  

г)  

3.10.
Введите одноместные предикаты на соответствующих областях и запишите при их помощи следующие высказыва­ния в виде формул алгебры предикатов:

а)   Всякое натуральное число, делящееся на 12, делится на 2, 4 и 6.

б)   Жители Швейцарии обязательно владеют или француз­ским, или итальянским, или немецким языком.

в)   Функция, непрерывная на отрезке [0, 1], сохраняет знак или принимает нулевое значение.

г)   Некоторые змеи ядовиты.

д)   Все собаки обладают хорошим обонянием.

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

а)   Если a есть корень многочлена от одной переменной с вещественными коэффициентами, то  также корень этого мно­гочлена.

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

в)   Через  две  различные точки  проходит единственная прямая.

г)   Каждый студент выполнил по меньшей мере одну ла­бораторную работу.

д)   Если произведение натуральных чисел делится на про­стое число, то на него делится по меньшей мере один из сом­ножителей.

е)   Через три точки, не лежащие на одной прямой,   проходит единственная плоскость.

ж)  Наибольший общий делитель чисел a и b
делится на всякий их общий делитель.

з)   Для каждого действительного числа х существует та­кой у, что для каждого z, если сумма z и 1 меньше у, то сумма х и 2 меньше 4.

и) х — простое число.

к) Каждое четное число, большее четырех, является сум­мой двух простых чисел (гипотеза Гольдбаха).

3.12.
Запишите следующие высказывания на языке алге­бры предикатов:

а)   Существует точно один х, такой, что Р (х).

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

в)   Существует не более двух х, таких, что Р (х).

г)   Существуют точно два различных х, такие, что Р (х).

3.13.
Что можно сказать о множестве М, если для любого предиката   В (х)   на  множестве   М  истинно   высказывание ?

      3.14.
Пусть Р (х) означает «x — простое число», Е (х) означает «х — четное число», О (х) — «х — нечетное число», D (x, y) — «х
делит у» или «у делится на х». Переведите на русский язык следующие символические записи на языке алгебры предикатов, учитывая, что переменные х и у пробе­гают множество натуральных чисел:

а)   P (7);

б)   E (2) & P (2);

в)   ;

г)   ;

д)   ;

е)   ;

ж)  ;

з)   ;

и) 

Решение.
е) Это высказывание можно прочитать так: «Для любого натурального числа х, если оно четное, то для любого натурального числа у, если х делит у, то и у будет четным числом». Мы прочитали это высказывание что называ­ется «с листа», произнесли словами нового языка то, что было написано на старом языке, не вникая в математическую суть утверждения. Вдумаемся теперь в смысл этого утверждения и придадим ему более подобающую русскому языку и более понятную форму: «Всякое натуральное число, делящееся на четное число, само будет четным».

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

a)                  б) .

Сравните логические значения этих высказываний.

Пример 6. Правильно ли следование:

(а)    ├  

(б)        ├  ?

Проверку правильности следования можно проводить и с по­мощью диаграмм Венна, если посылки и заключения — одноместные предикаты, зависящие от одной переменной. Для категорических суждений, каковыми являются в нашем примере посылки и заключе­ния, отношения между объемами понятий S и Р описаны в примере 2. Этим описанием мы и воспользуемся.

Метод диаграмм Венна для случая с одной посылкой состоит в следующем. Изображаем диаграммами все возможные случаи отношений между объемами понятий S и Р, соответствующие по­сылке.

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

(а) Поскольку посылка  является отрицательным суждением, то для нее возможны диаграммы, изображенные на рис. 5.

Рис. 5

Ни на одной из этих диаграмм суждение не верно, так как объемы понятий S и Р не имеют общих элементов.

Значит, следование неправильное.

(б) Так как посылка  является частноутвердительным суждением, то возможные для нее диаграммы приведены на рис. 6.