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

ЛОГИКА ПРЕДИКАТОВ

Учебное пособие

Владивосток

Издательский дом Дальневосточного федерального университета

УДК 510.6

ББК 22.12

К 93

Курочкина, И. А.

К93 Логика предикатов: учебное пособие / И. А. Курочкина. – Владивосток: Издательский дом Дальневосточного федерального университета, 2013. – 44 с.

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

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

УДК 510.6

ББК 22.12

© Курочкина И.А., 2013

Основные понятия

Определение. n ‑местным предикатом, определенном на множествах называется предложение, содержащее n переменных превращающееся в высказывание при подстановке вместо этих переменных любых конкретных элементов из множеств соответственно.

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

Переменные называют предметными.

Элементы множеств , которые эти элементы пробегают – конкретные предметы:

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

Это высказывание может быть либо истинным, либо ложным, то есть его логическое значение равно 1 или 0.

Следовательно, данный предикат определяет функцию n -аргументов, заданную на множествах и принимающий значение в двухэлементном множестве {0,1}. Эту функцию и называют предикатом.

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

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

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

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

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

Примеры:

1) Одноместный предикат «Город x расположен на берегу реки Волги».

Определен на множестве названий городов, является выполнимым.

2) Одноместный предикат «» определен на множестве R, тождественно истинный.

3) Двухместный предикат «» задан на множестве R, тождественно ложный.

Утверждения:

1. Любой тождественно-истинный предикат является выполнимым, обратное неверно.

2. Любой тождественно-ложный является опровержимым, обратное неверно.

3. Любой не тождественно-истинный предикат будет опровержимым.

4. Любой не тождественно-ложный предикат будет выполнимым.