Министерство образования и науки Российской Федерации

Дальневосточный федеральный университет

Школа естественных наук

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

Логика предикатов

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

Владивосток

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

2013

УДК 510.6

ББК 22.12

К 93

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

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

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

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

УДК 510.6

ББК 22.12

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

§ 1. Основные понятия

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

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

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

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

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

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

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

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

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

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

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

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

Примеры:

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

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

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

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

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

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

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

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

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

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

Определение. Множеством истинности предиката , заданного на множествах называется совокупность всех упорядоченныхn-систем (n-арок) ,> в которых, таких, что данный предикат обращается в истинное высказывание при подстановке . Это множество будем обозначатьP⁺.

Таким образом, P⁺ = {<}

Множество истинности n-местного предиката представляет собойn-арное отношение между элементами множеств _.

Пусть P(x) – одноместный предикат, M – область определения предиката P(x). множество истинности предиката

То есть является подмножеством множества M: .