- •2. Элементы логики предикатов
- •2.1. Формулы логики предикатов и их преобразование Сводка теории
- •Определение
- •Определение
- •Определение
- •Определение
- •Определение
- •Замечания
- •Утверждение 2.1
- •Утверждение 2.2
- •Примеры
- •Пример 2.3
- •Замечания
- •Примеры
- •Контрольные вопросы
- •3. Исчисление высказываний и исчисление предикатов
- •3.1. Общее представление об исчислении высказываний Сводка теории
- •Примеры
- •3.2. Общее представление об исчислении предикатов Сводка теории
- •Примеры
- •Решение
- •Решение
- •Решение
- •Решение
- •Решение
- •Индивидуальное задание (контрольная работа) правила выполнения и оформления индивидуального задания
- •Варианты индивидуального задания
- •Варианты формул для заданий 2 - 7:
- •Литература
- •2. Элементы логики предикатов 34
- •2. Элементы логики предикатов 34
- •Сергей Михайлович Воротников
- •Введение в математическую логику
- •Учебное пособие
- •681013, Комсомольск-на-Амуре, пр. Ленина, 27
2. Элементы логики предикатов
2.1. Формулы логики предикатов и их преобразование Сводка теории
Функция n переменных (n = 1,2,...) с непустой областью определения, множество значений которой содержится во множестве {1,0}, называется n-местным предикатом.
Если область определения n-местного предиката имеет вид , т.е. все независимые переменные пробегают одно и то же множество, то говорят, что предикат определен на множестве М.
n-местный предикат может, в частности, принимать для всех наборов значений независимых переменных одно и то же значение, т.е. быть тождественно-истинным или тождественно-ложным.
Если в многоместном предикате фиксировать значения некоторых, но не всех независимых переменных, получается новый предикат с меньшим числом мест.
Если F – свойство элементов множества M и F(x) – соответствующий этому свойству предикат (определенный на M), то предложение: «все элементы множества M обладают свойством F» или «каждый (или любой, или всякий) элемент множества M обладает свойством F»- записывается в виде: ; а предложение: «во множестве M существует (или есть, или имеется, или найдется) элемент, обладающий свойством F» – в виде .
Читаются эти выражения так: «Для всякого (или для всех) »; «Существует x такое, что F(x)».
Выражения и называются квантором общности (или всеобщности) и квантором существования соответственно. При этом обычно говорят: «квантор по переменной x».
Можно рассматривать постановку квантора общности и квантора существования перед знаками предикатов («навешивание» кванторов или «квантификация») как особые операции.
Навешивание квантора общности есть операция, сопоставляющая одноместному предикату F(x) высказывание – истинное, если F(x) тождественно-истинен, и ложное в противном случае. Навешивание квантора существования есть операция, сопоставляющая одноместному предикату F(x) высказывание – ложное, если F(x) тождественно ложен, и истинное в противном случае.
Операции навешивания кванторов общности и существования сопоставляют каждому n-местному предикату (n-1)-местные предикаты и соответственно. В последних двух предикатах переменная называется связанной, остальные переменные – свободными (или параметрами).
Логико-математический язык первого порядка (первой ступени) L задается набором из четырех множеств:
a) (индивидные) переменные x, y, z, ...;
b) n-местные (индивидные) функциональные символы F, G, H, ... для каждого n;
c) n-местные (индивидные) предикатные символы P, B, S, ... для каждого n;
d) логические связки и кванторы.
Любой 0-местный функциональный символ является (индивидной) константой, 0-местный предикатный символ – логической (пропозициональной) константой.
Если задан язык L, то можно определить некоторые правильно построенные тексты, составленные из символов L и вспомогательных символов – скобок и запятых. Эти тексты называются выражениями языка L и подразделяются на термы и формулы.
Определение
i) Переменная языка L есть терм;
ii) если – k-местный функциональный символ языка L и - термы, то выражение F( ) есть терм языка L. Коротко это запишем в виде правила вывода:
.
Это обобщенное индуктивное определение показывает, что каждый терм имеет один и только один вид из следующих двух: переменная или константа (из правила ii как 0-местная функция) языка L, либо функция от термов. Таким образом, термы – это те выражения языка, значениями которых являются индивиды. Роль термов состоит в том, чтобы описывать именные формы и имена индивидов.