Подчипаев Д.О._к семинару

Отношения. Высказывания. Предикаты. Унарные и бинарные предикаты. Кванторы. Исчисление пр едикатов. Применение предикатов в математической практике.

Отношения

Отношение — матем атическая структура, которая формально определяет свойства различных объектов и их взаимосвязи. Отношения обычно классифицируются по количеству связываемых объектов (ар ность) и собственным свойствам (симметричность, транзитивность и пр.). В математике примерами отношений являются равенс тво (=), коллинеарность, делимость и т. д.

Отношение также мо жет быть задано предикатом на n-й декартовой степени множества M: n-ка принадле жит отношению тогда и только тогда, когда предикат на ней возвращает значение 1 (или «истинно»). Таким образом, можно дать альтернативное определение отношения: если задано отображе ние ,

то отношением называется прообраз единицы в . Тако е определение бывает полезно в информатике и математической логике.

Высказывания

Высказывание — предложение, выражающее суждение. Если суждение,

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

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

Виды высказываний

Логические высказывания принято подразделять на составные (или сложные) и

элементарные. Составные логические высказывания — выска зывания, содержащие логические постоянные. С оставные высказывания строятся на основе других высказываний. Логическое значение сложного высказывания определяется логическим значением входящих в его состав высказываний и теми логическими постоянными, с

помощью которых оно построено.

1

Подчипаев Д.О.

Отношения. Высказывания. Предикаты. Унарные и бинарные предикаты. Кванторы. Исчисление предикатов. Применение предикатов в математической практике.

Элементарные логические высказывания — это высказывания не относящиеся к составным. Примером элементарного высказывания может служить 5 < 7. Примером составного логического высказывания может служить если 5 < 7, то 5 — чётное число.

Предикаты

Предикатом называется функция, которая возвращает логическое значение.

Понятие предиката обобщает понятие высказывания.

В высказывании все четко: это — конкретное утверждение о конкретных

объектах — истинное или ложное. Предикат — предложение, похожее на

высказывание, но все же им не являющееся: о нем нельзя судить, истинно оно или

ложно. Дадим точное определение.
Определение Определенным	на множествах				n-местным
предикатом называется предложение,	содержащее	переменных					,

превращающееся в высказывание при подстановке вместо этих переменных любых

конкретных элементов из множеств

соответственно.

Для n-местного предиката будем использовать обозначение

.

Переменные

называют

предметными,

а элементы

множеств

, которые эти переменные пробегают, —

конкретными предметами.

Всякий n-местный

предикат

, определенный

на

множествах

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

множествах и принимающую значения в множестве всех высказываний. Поэтому

предикат называют также функцией-высказыванием.

Рассмотрим пример. Предложение "Река впадает в озеро Байкал" является

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

Подставив вместо предметной переменной название "Баргузин", получим

высказывание "Река Баргузин впадает в озеро Байкал". Это высказывание истинно.

Подставив вместо предметной переменной название "Днепр", получим ложное высказывание "Река Днепр впадает в озеро Байкал".

2

Подчипаев Д.О.

Отношения. Высказывания. Предикаты. Унарные и бинарные предикаты. Кванторы. Исчисление предикатов. Применение предикатов в математической практике.

Другой пример. Предложение (выражение) " " является двухместным предикатом, заданным над множествами . Множества, на которых задан двухместный предикат, совпадают (говорят, что "двухместный предикат задан на множестве "). Пара действительных чисел 2, 2 превращает данный предикат в истинное высказывание: " ", а пара чисел 2, 3 — в ложное: " ".

Классификация предикатов

Определение Предикат , заданный на множествах

, называется:

а) тождественно истинным, если при любой подстановке вместо переменных

любых конкретных предметов

из множеств

;

соответственно он превращается в истинное высказывание

б) тождественно ложным, если при любой подстановке вместо переменных

любых конкретных предметов из множеств

соответственно он превращается в ложное высказывание;

в) выполнимым (опровержимым), если существует по меньшей мере один

набор конкретных предметов из множеств

соответственно, при подстановке которых вместо соответствующих предметных

переменных в предикат

последний превратится в истинное (ложное)

.

высказывание

Приведем примеры предикатов.

Одноместный предикат

"Город

расположен на берегу реки Волги",

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

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

иначе, не удовлетворяют этому предикату (например, Прага, Якутск и т.д.). Этот же предикат являет собой пример опровержимого, но не тождественно ложного предиката

(продумайте!).

3

Подчипаев Д.О.

Отношения. Высказывания. Предикаты. Унарные и бинарные предикаты. Кванторы. Исчисление предикатов. Применение предикатов в математической практике.

Отметим достаточно очевидные закономерности взаимосвязей между

предикатами различных типов (рекомендуется осмыслить их):

1)каждый тождественно истинный предикат является выполнимым, но обратное неверно;

2)каждый тождественно ложный предикат является опровержимым, но обратное неверно;

3)каждый не тождественно истинный предикат будет опровержимым, но,

вообще говоря, не будет тождественно ложным;

4) каждый не тождественно ложный предикат будет выполнимым, но, вообще

говоря, не будет тождественно истинным.

Множество истинности предиката

Определение Множеством истинности предиката

, заданного

на множествах

,

называется совокупность всех

упорядоченных n-

систем

, в которых

, таких, что данный

предикат обращается

в истинное высказывание

при

подстановке

. Это множество будем обозначать

. Таким образом,

Множество

истинности n-местного предиката

представляет

собой n-арное отношение между элементами множеств

.

Если

предикат

— одноместный,

заданный над множеством

,

то его множество

истинности

является подмножеством множества

.

Например, множеством истинности двухместного предиката "Точка

принадлежит

прямой

", заданного

на множестве

всех

точек плоскости

и на

множестве

всех

прямых

этой

плоскости,

является

бинарное

отношение

принадлежности (инцидентности) между точками и прямыми плоскости. Другой

пример. Множество истинности двухместного предиката ,

заданного на множестве , есть множество всех таких пар действительных чисел,

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

4

Подчипаев Д.О.

Отношения. Высказывания. Предикаты. Унарные и бинарные предикаты. Кванторы. Исчисление предикатов. Применение предикатов

вматематической практике.

Втерминах множества истинности легко выразить понятия, связанные с классификацией предикатов. В самом деле, n-местный предикат ,

заданный на множествах

, будет:

а)

тождественно

истинным

тогда

и

только

тогда,

когда

;

б) тождественно ложным тогда и только тогда, когда

;

в) выполнимым тогда и только тогда, когда

;

г) опровержимым тогда и только тогда, когда

.

Равносильность и следование предикатов

Определение Два n-местных предиката

и

,

заданных над одними и теми же множествами

, называются

равносильными, если набор предметов (элементов)

превращает первый предикат в истинное высказывание

в том и только

в том случае, когда этот набор предметов превращает второй предикат в истинное

высказывание

.

Другими словами (на языке множеств истинности), предикаты

и

равносильны тогда и только тогда, когда их множества истинности

совпадают.

.

Утверждение о равносильности двух предикатов

и

символически будем

записывать так:

. Отношение равносильности предикатов является отношением

эквивалентности, так что совокупность всех n-местных предикатов, определенных на

множествах , распадается на непересекающиеся классы равносильных

предикатов (все они определяют одну и ту же функцию, заданную на множествах

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

равносильным преобразованием первого.

Рассмотрим простой пример. Пусть требуется решить уравнение (найти

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

Подчипаев Д.О.

Отношения. Высказывания. Предикаты. Унарные и бинарные предикаты. Кванторы. Исчисление предикатов. Применение предикатов в математической практике.

Ответ: — множество всех решений данного уравнения (множество истинности данного предиката).

Отметим следующее немаловажное обстоятельство: может быть так, что два

предиката равносильны, если их рассматривать над одним множеством, и

неравносильны, если их рассматривать над другим (в частности, объемлющим первое)

множеством. Такова, например, ситуация с предикатами:

и

.

Определение Предикат

, заданный

над

множествами

, называется следствием

предиката

,

заданного над

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

в истинное высказывание превращается предикат

.

Другими словами (в терминах множеств истинности), можно сказать, что

предикат

является следствием предиката

тогда и только тогда, когда

.

Утверждение о том, что предикат

является следствием предиката

, будем

символически записывать так:

.

Например, одноместный предикат, определенный на множестве натуральных

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

Логические операции над предикатами

Над предикатами можно проделывать те же самые логические операции, что и над высказываниями: отрицание, конъюнкцию, дизъюнкцию, импликацию,

эквивалентность. Рассмотрим эти операции в их связи с операциями над множествами.

Отрицание предиката

Определение

Отрицанием n-местного предиката

,

определенного на множествах

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

же множествах,

(читается:

определенный на тех

обозначаемый

6

Подчипаев Д.О.

таков, что для любых предметов является отрицанием

Отношения. Высказывания. Предикаты. Унарные и бинарные предикаты. Кванторы. Исчисление предикатов. Применение предикатов в математической практике.

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

Другими словами, предикат высказывание

высказывания

.

Например, нетрудно понять, что отрицанием одноместного предиката "

",

определенного

на множестве

, является

одноместный предикат "

",

определенный на том же множестве

. Отрицанием предиката "Река

впадает в озеро

Байкал" является предикат "Река

не впадает в озеро Байкал" (оба одноместных

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

рек). Отрицанием предиката

"

" является предикат "

"

.

Конъюнкция двух предикатов

Определение Конъюнкцией n-местного

предиката

,

определенного

на множествах

,

и m-местного предиката

,

определенного

на множествах

,

называется новый

(n+m)-местный

предикат,

определенный

на

множествах

,

обозначаемый

(читается "

"),

и

который превращается в истинное

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

Другими словами, предикат

таков, что для

любых предметов

и

высказывание

.

является

конъюнкцией

высказываний

и

Например, конъюнкцией двух одноместных предикатов "

" и "

",

определенных на

, будет одноместный предикат "

", записываемый

короче в виде: "

"

7

Подчипаев Д.О.

Отношения. Высказывания. Предикаты. Унарные и бинарные предикаты. Кванторы. Исчисление предикатов. Применение предикатов

в математической практике.

Пример. Конъюнкцией двух одноместных предикатов "

" и "

",

заданных на

, является двухместный предикат "

", заданный на

,

который равносилен предикату "

", определенному также на

.

Операцию конъюнкции можно применять к предикатам, имеющим общие

переменные. В

этом случае число

переменных в новом

предикате равно числу

, где

— число переменных первого предиката,

—

число переменных

второго предиката, —

число переменных общих для обоих предикатов.

Дизъюнкция двух предикатов

Определение Дизъюнкцией n-местного предиката

,

определенного

на

множествах

,

и m-местного

предиката

,

определенного на множествах

, называется новый

(n+m)-местный

предикат, определенный на множествах

и

,

(читается "

обозначаемый

или

"),

который

превращается

в истинное

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

Другими словами,

предикат

таков, что для

любых предметов

и

высказывание

является дизъюнкцией

.

высказываний

и

Операцию дизъюнкции, как и операцию конъюнкции, можно применять, в

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

8

Подчипаев Д.О.

Отношения. Высказывания. Предикаты. Унарные и бинарные предикаты. Кванторы. Исчисление пр едикатов. Применение предикатов

в математической практике.

Дизъюнкцией одноместных предикатов "

" и "

", определенных на

, является двухместный предикат "

", определенный на

, который

равносилен предикату " x^2+ y^2\ne0" над .

Импликация и эквивалентность двух предикатов

Импликация

определяется

как такой

предикат, что для любых предметов

и

высказывание

является

импликацией

высказываний

и

. Аналогично

определяется

эквивалентность двух преди катов.

Ун арные и бинарные предикаты

С помощью предикато в часто определяют критерии сортировки или поиска. В

зависимости от способа при менения предикаты делятся на унарн ые и бинарные.

Унарные предикаты

Унарный предикат проверяет некоторое свойство одного аргумента.

Типичный пример - функция, используемая в качестве критерия поиска первого простого числа

Бинарные предик аты обычно сравнивают некоторое свойство двух аргументов. Например, чтобы отсортировать элементы по нестандартному критерию,

программист передает алгоритму простую предикатную ф ункцию. Это может понадобиться, если, наприме р, элементы не могут корректно работать с оператором <

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

Кванторы

Ква́нтор — общее название для логических операций, огр аничивающих область истинности какого-либо предиката и создающих высказывание. Чаще всего

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

9

Подчипаев Д.О.

Отношения. Высказывания. Предикаты. Унарные и бинарные предикаты. Кванторы. Исчисление пр едикатов. Применение предикатов в математической практике.

∙ Квантор существова ния (обозначение: , читается: «существует…» или

«найдётся…»).

Вматематической логике приписывание квантора к формуле называется

связыванием или квантифик ацией.

Вмногозначных логиках также вводятся и другие квантор ы, например, квантор плюральности (квантор Решера) (обозначается перевёрнутой M, читается «для

большинства …»).

Примеры

Обозначим предикат «x делится на 5». Использ уя квантор общности,

можно формально записать следующие высказывания (конечно, ложные):

1.любое натуральное чи сло кратно 5;

2.каждое натуральное число кратно 5;

3.все натуральные числа кратны 5;

следующим образом:

.

Следующие (уже исти нные) высказывания используют квантор существования:

1.существуют натуральные числа, кратные 5;

2.найдётся натуральное число, кратное 5;

3.хотя бы одно натуральное число кратно 5.

Их формальная запись:

.
Пусть на множестве простых чисел задан предикат	: «Простое число

нечётно». Подставим перед этим предикатом слово «любое». Получим ложное высказывание «любое прост ое число нечётно» (это высказыван ие ложно, так как 2 —

простое чётное число).

Подставив перед данным предикатом			слово			«существует», получим
истинное высказывание «С уществует простое			число		,	являющееся нечётным»
(например,	).
						10

Подчипаев Д.О.