Похожие работы
|
2. элементы логики предикатов формулы логики предикатов и их преобразование - страница №1/4
2 . Элементы логики предикатов 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, либо функция от термов. Таким образом, термы – это те выражения языка, значениями которых являются индивиды. Роль термов состоит в том, чтобы описывать именные формы и имена индивидов. ОпределениеЕсли P – k-местный предикатный символ языка L, а суть термы, то выражение P() называется атомарной (или элементарной) формулой. В частности, если P – пропозициональная буква (0-местный предикатный символ), то P сама по себе является атомарной формулой. Определениеi) Каждая атомарная формула есть формула; ii) , т.е. если уже построена формула A, то разрешается построить новую формулу ; подобным образом следует трактовать и следующий пункт: iii) , где – любая логическая связка; iv) , т.е. если уже построена формула A, и x – произвольная переменная языка L, то разрешается построить новую формулу ; так же следует трактовать и следующий пункт: v) . Как уже отмечалось, вхождение переменной x в формулу A может быть связанным (если оно попадает в область действия квантора по x или в саму кванторную приставку с переменной x) или свободным. Заметим, что одна и та же переменная может иметь и свободные, и связанные вхождения в одну и ту же формулу. Переменная x называется свободной переменной формулы A, или параметром A, если x входит (хотя бы один раз) свободно в A. Формула, не содержащая параметров, называется замкнутой (она является высказыванием). Свободные и связанные переменные играют различные роли в формуле. Во-первых, вместо связанной переменной нельзя подставить конкретное значение – получится бессмысленное выражение. Во-вторых, связанная переменная не имеет самостоятельного значения, ее можно заменить на другую переменную, и смысл формулы от этого не изменится. Все формулы: , , - выражают один и тот же предикат, одну и ту же функцию от x, z. Такая операция называется переименованием связанной переменной. При переименовании связанной переменной смысл формулы не меняется, если при этом никакая свободная переменная в любой подформуле данной формулы не может после переименования оказаться связанной. Например, если в формуле мы решим заменить переменную y на переменную x, то получится формула , которая имеет совершенно иной смысл, чем исходная формула. Формула зависит уже лишь от одного параметра z, а не от двух. Причина состоит в том, что после неудачного переименования связанной переменной y первое вхождение переменной x, которое раньше было свободным, стало связанным. Это явление называют коллизией переменных при переименовании связанных переменных. Коллизия переменных недопустима. Главным рабочим инструментом в логике предикатов, как и в логике высказываний, служит понятие равносильности формул. ОпределениеФормулы Ф и Y равносильны (Ф Y), если:
Разумеется, все вхождения одного и того же предикатного символа как в Ф, так и в Y должны замещаться одним и тем же предикатом. ОпределениеФормула называется тождественно-истинной (тождественно-ложной), если при любом замещении входящих в нее предикатных символов конкретными предикатами она переходит в тождественно-истинный (тождественно-ложный) предикат (если она не замкнута) или в истинное (ложное) высказывание (если она замкнута). Замечания1) Тождественно-истинная формула и тождественно-истинный предикат – не одно и то же. Тождественная истинность конкретного предиката относится только к его области определения, в то время как тождественная истинность формулы – это «абсолютная истинность», истинность для любых предметных областей. Аналогично – для тождественной ложности. 2) Из определения непосредственно следует, что формула со свободными переменными тождественно-истинна тогда и только тогда, когда тождественно-истинна формула . 3) Отрицание тождественно-истинной формулы есть, очевидно, формула тождественно-ложная, а отрицание тождественно-ложной – тождественно-истинная. I) Перестановка одноименных кванторов: ; (I.1) . (I.2) 2) Связь между разноименными кванторами: ; (II.1) . (II.2) 3) Вынесение кванторов за скобки:
Замечание Условие, чтобы формула Ф не содержала свободной переменной x, в соотношениях (III.1 – III.4) является существенным: если оно не выполнено, то соотношения могут нарушаться (после вынесения квантора переменная x в формуле Ф из свободной может превратиться в связанную). 4) Переименование связанных переменных:
Замечание Все введенные равносильности останутся справедливыми, если заменить в них F(x) (соответственно F(x, y)) любой формулой G, содержащей свободную переменную x (соответственно x и y) и, возможно, также и другие свободные переменные. Отметим в общем виде самый простой из частных случаев, когда для доказательства равносильности формул логики предикатов удается воспользоваться средствами логики высказываний. Утверждение 2.1Если в равносильных формулах логики высказываний заменить элементарные высказывания произвольными предикатными символами так, чтобы одно и то же элементарное высказывание заменялось в обеих формулах одним и тем же символом, то возникающие при этом формулы логики предикатов будут также равносильны. Утверждение 2.2Если в тождественно-истинной формуле логики высказываний заменить элементарные высказывания произвольными предикатными символами, то возникающая при этом формула логики предикатов также тождественно-истинна (то же справедливо для тождественно-ложных формул). С помощью свойств кванторов можно производить над формулами логики предикатов тождественные преобразования, причем ввиду утверждения 2.1 в этих преобразованиях можно использовать также любые равносильности логики высказываний. Производя тождественные преобразования в определенном порядке, можно для каждой формулы получить ей равносильную, имеющую особенно простое строение. ПримерыПример 2.1 Записать фразы в виде формул логики предикатов, указав области определения используемых предикатов: а) если х делится на у и у делится на z, то х делится на z; б) х – простое число. Решение а) Разбивая фразу на простые предложения, видим, что используется только одно свойство двух объектов, поэтому введем предикат = « делится на «. Речь идет, очевидно, о делимости нацело, поэтому областью определения предиката будет множество целых чисел: . Структура всей фразы описывается конструкцией «если..., то...», значит, самой внешней (последней) связкой нашей формулы будет импликация. Посылка этой импликации описывается конъюнкцией простых предложений, поэтому итоговая формула имеет вид: б) Самый простой подход: ввести предикат = « – простое число», который и описывает всю фразу. Но математические термины должны быть определены однозначно (что такое «простое» число, которое записывается одной цифрой? или которое записано с помощью повторения одной цифры? или которое можно легко запомнить или записать?), поэтому точный смысл этой фразы может быть воспроизведен с помощью строгого определения. То есть « делится только на 1 и на себя» или, еще точнее, «либо , либо и если делится на любое , то, или , или «. В последней фразе использован предикат делимости (см. пункт а), предикат равенства = «« и квантор всеобщности. Поскольку понятие простого числа обычно вводят только для натуральных чисел, то . Формула, описывающая последнюю фразу, имеет вид: . Пример 2.2 Указать свободные и связанные вхождения переменных в формулы: а) ; б) ; в) . Проанализируем область действия каждого квантора, отмечая связанные вхождения общей прямой с засечками снизу, а свободные вхождения переменных стрелочкой сверху. Отметим, что в третьей формуле F и G – функциональные символы (в теориях первого порядка аргументом предиката не может выступать другой предикат). а) ; б) ; в) . Пример 2.3Доказать тождественную истинность формул: а) ; б) . Будем преобразовывать бескванторную часть формул, используя основные логические законы. а) . Значит, исходная формула тождественно истинна. б) . Значит, исходная формула тождественно истинна. Пример 2.4 Доказать тождественную ложность формул: а) ; б) . Решение Будем преобразовывать бескванторную часть формул, используя основные логические законы. а). Значит, исходная формула тождественно ложна. б) Значит, исходная формула тождественно ложна. Задачи2.1. Записать фразы в виде формул логики предикатов, указав области определения используемых предикатов: а) «Если произведение двух чисел делится на простое число, то на него делится хотя бы один из сомножителей»; б) «Через всякую точку, не лежащую на прямой, можно провести прямую, перпендикулярную данной»; в) «Через каждые две точки можно провести прямую, причем, если эти точки различны, то такая прямая единственна»; г) «Когда у некоего деятеля денег в избытке, он может воспевать что угодно, в том числе и отсутствие денег»; д) «Всякий кулик свое болото хвалит, а чужое хает». 2.2. Пусть – одноместный, – двухместный, – трехместный функциональные символы. Являются ли термами следующие слова: а) ; б) ; в) ? 2.3. Пусть , , – те же, что и в задаче 2.2, – одноместный, – трехместный предикатные символы. Являются ли формулами следующие слова: а) ; б) ; в) ; г) ? а) ; б) . а) Найти такие два замещения предикатного символа конкретным предикатом в формуле , чтобы при одном замещении получилось истинное предложение, при другом – ложное. б) То же для формулы . в) То же для формулы . 2.6. Доказать тождественную ложность формул: а) ; б) . а) ; |
|