Игошин Математическая логика и теория алгоритмов (1019110), страница 36

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 36)

Наконец, двухместный предикат «х'+ уз < 0», заданный также на множестве действительных чисел, является тождественно ложным предикатом, потому что любая пара действительных чисел превращает его в ложное высказывание (не удовлетворяет ему). Отметим некоторые достаточно очевидные з а к о н о м е р н ости взаимосвязей между предикатами различных типов (рекомендуется осмыслить их): 1) каждый тождественно истинный предикат является выполнимым, но обратное неверно; 2) каждый тождественно ложный предикат является опровержимым, но обратное неверно; 3) каждый не тождественно истинный предикат будет опровержимым, но, вообще говоря, не будет тождественно ложным; 4) каждый не тождественно ложный предикат будет выполнимым, но, вообще говоря, не будет тождественно истинным.

Множество истинности нредиката. Опведеееиие 18.3. Множеством истинности предиката Р(х„хн ...„х„), заданного на множествах Мо Мм ..., М„, называется совокупность всех упорядоченных л-систем (аь ан ..., а»), в которых а~ а Мь аг в Мн ..., а„а М„, таких, что данный предикат обращается в истинное высказывание Р(а„ан ..., а«) при подстановке х, = аь хз = ан ..., х, = а„. Это множество будем обозначать Р'. Таким образом, Р' = Иао ан ..., а»): Х(Р(ао ан ..., а«)) = 1). Множество Р' истинности п-местного предиката Р(х„хь ..., х„) представляет собой п-арное отношение между элементами множеств М„Мн ..., М„.

Если предикат Р(х) — одноместный, заданный над множеством М, то его множество истинности Р' является подмножеством множества М: Р+ ~ М. Например, множеством истинности двухместного предиката «Точка х принадлежит прямой у», заданного на множестве Е всех точек плоскости и на множестве Г всех прямых этой плоскости, является бинарное отношение принадлежности (инцидентности) между точками и прямыми плоскости. Другой пример.

Множество истинности двухместного предиката Я(х, у): «х'+ у' = 9», заданного на множестве Я', есть множество всех таких пар действительных чисел, которые являются координатами точек плоскости, образующими окружность с центром в начале координат и радиуса 3. Наконец, если А(х): «~а~ > 2» — одноместный предикат над Я, то А' = ] —, -2 1 () ) 2, + В терминах множества истинности легко выразить понятия, связанные с классификацией предикатов (определение 18.2). В самом деле, л-местный предикат Р(х„хп ..., х„), заданный на множествах Мь Мн ..., М„, будет: а) тождественно истинным тогда и только тогда, когда Р' = = М, х Мз х ... х М„; !48 б) тождественно ложным тогда и только тогда, когда Р' = О; в) выполнимым тогда и только тогда, когда Р' ~ И; г) опровержимым тогда и только тогда, когда Р' ~ М, х Мз х ... х М„.

На языке множеств истинности еше более отчетливо прояс~иются закономерности взаимосвязей между предикатами различных типов, отмеченные в конце предыдущего пункта. Проанализируйте их еше раз. Равносильность и следование предивзтов. ОпРедеяеиое 18.4. Два л-местных предиката Р(х„хп ..., х„) и 0(хп хп ..., х„), заданных над одними и теми же множествами Мо Мп ..., М„„называются равносильными, если набор предметов (элементов) а, о Мо ат о е Мз, ..., а„о М„превращает первый предикат в истинное высказывание Р(ан аз, ..., а,) в том и только в том случае, когда этот набор предметов превращает второй предикат в истинное высказывание 0(аь ам ..., а„).

Другими словами (на языке множеств истинности), предикаты Р(хн хь ..., х„) и 0(хн хп ..., х„) равносильны тогда и только тогда, когда их множества истинности совпадают: Р' = Д'. Утверждение о равносильности двух предикатов Р и Д символически будем записывать так: Р с~ Д. Отношение равносильности предикатов является отношением эквивалентности, так что совокупность всех л-местных предикатов, определенных на множествах М„Мп ..., М„, распадается на непересекающиеся классы равносильных предикатов (все они определяют одну и ту же функцию, заданную на множествах Мп Мп ..., М„и принимающую значения в двухэлементном множестве (О, 1)).

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

При таком поиске мы проделываем над уравнением и неравенством различные преобразования, и здесь важно, чтобы эти преобразования были равносильными, т.е. чтобы найденное множество оказалось бы множеством истинности именно исходного уравнения или неравенства. Аналогична ситуация при решении систем уравнений или неравенств. Рассмотрим простой п р и м е р. Пусть требуется решить уравнение (найти множество истинности предиката): 4х — 2 = -Зх — 9. Преобразуем его равносильным образом: 4х- 2 = -Зх- 9 с=> 4х+ Зх = = -9+ 2 «=> х = -1.

О т в е т: (-1) — множество всех решений данного уравнения (множество истинности данного предиката). Отметим следующее немаловажное обстоятельство: может быть так, что два предиката равносильны, если их рассматривать над одним множеством, и неравносильны, если их рассматривать над 149 другим (в частности, объемлющим первое) множеством. Такова, например, ситуация с предикатами: ~х у = 15 и,Гх.,/у = 15 (см. М 9.22, г Задачника).

Определение 18.5. Предикат Ц(хь хъ ..., х„), заданный над множествами Мь Мъ ..., М„, называется следствием предиката Р(хь х,, ..., х„), заданного над теми же множествами, если он превращается в истинное высказывание на всех тех наборах значений предметных переменных из соответствующих множеств, на которых в истинное высказывание превращается предикат Р(х„х,, ..., х„). Другими словами (в терминах множеств истинности), можно сказать, что предикат (г является следствием предиката Р тогда и только тогда, когда Р' а Ц'.

Утверждение о том, что предикат Д является следствием предиката Р, будем символически записывать так: Р =» Ц. Например, одноместный предикат, определенный на множестве натуральных чисел, «п делится на 3» является следствием одноместного предиката, определенного на том же множестве, «и делится на 6». Из двух предикатов, упомянутых перед последним определением, первый будет следствием второго, если считать, что оба предиката заданы на множестве к целых чисел. Язык множеств истинности позволяет установить взаимосвязь между понятиями равносильности и следования предикатов: два предиката, определенные на одних и тех же множествах, равносильны тогда и только тогда, когда каждый из них является следствием другого.

Кроме того, этот же язык дает возможность без труда установить следующие простые теоремы. Теорема 18.б. Каждые два тождественно истинных (тождественно ложных) предиката, заданных на одних и тех же множествах, равносильны. Обратно, всякий предикат, равносильный тождественно истинному (тождественно ложному) предикату, сам является тождественно истинным (тождественно ложным) предикатом. Теорема 18.7. Каждый тождественно истинный и-местныйпредикат является следствием любого другого п-местного предиката, определенного на тех же множествах. Каждый и-местный предикат является следствием любого тождественно ложного и-местного предиката, определенного на тех же множествах.

Теорема 18.8. Пусть Р(хн хз, ..., х„) и О(хн хз, ..., х„) — два и-местных предиката, определенные на одних и тех же множествах, такие, что Д(хь хн ..., х„) есть следствие Р(х„хп ..., х„). Тогда: а) если Р(х„хз, ..., х„) тождественно истинный (выполнимый), то и Д(хь хн ..., х„) тождественно истинный (выполнимый); б) если Д(хь хн ..., х„) тождественно ложный (опровержимый), то и Р(х„х„..., х„) тождественно ложный (опровержимый). Доказательство теоремы 18.8, а. Поскольку Р =ь (г, поэтому Р' а Д'. Если теперь Р тождественно истинный предикат, то Р' = М, х Мз х ... х М„(где Мп Мп ..., ̄— множества, 150 на которых определены п-местные предикаты Р и О).

Но Ц' а М, х х М, х ... х М„. Поэтому О' = М, х Мг х ... х М„, а, значит, предикат Π— тождественно истинный предикат. Если же Р— выполнимый предикат, то Р'еИ. Но Р'~ 1г'. Тогда 0'и И и Π— выполнимый предикат. б) Пусть Π— тождественно ложный предикат. Тогда Д'= Я. Но р ~ Ц', поэтому Р' = О. Следовательно, предикат Р— тождественно ложный. Наконец, пусть 0 — опровержимый предикат.

Тогда О'~ М, х Мз х ... х М„. Поскольку, кроме того, Р'а Ц' и Р'~ М, х х Мг х ... х М„, то Р+ и М, х Мз х ... х М„. Следовательно, предикат Р— опровержимый. П Отьпците самостоятельно в настоящем и предыдущем пунктах данного параграфа утверждения, обосновывающие остальные сформулированные теоремы. ф 19. Логические операции иад предикатами Над предикатами можно проделывать те же самые логические операции, что и над высказываниями: отрицание, конъюнкцию, дизъюнкцию, импликацию, эквивалентность. Рассмотрим эти операции в их связи с операциями над множествами (см. а 8). Отрицание предиката.

Определение 19.1. Отрицанием п-местного предиката Р(хп хг, ..., х„), определенного на множествах Мь Мп ..., М„, называется новый и-местный предикат, определенный на тех же множествах, обозначаемый — Р(х„хъ ..., х„) (читается: «неверно, что Р(хп х,, ..., х„)»), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых исходное высказывание превращается в ложное высказывание. Другими словами, предикат -Р(х„х„..., х„) таков, что для любых предметов а, е Мь аз е Мъ ..., а„е М„высказывание — Р(аь ап ..., а„) является отрицанием высказывания Р(а„ан ..., а„). Например, нетрудно понять, что отрицанием одноместного предиката «х < 3», определенного на множестве Я, является одноместный предикат «х > 3», определенный на том же множестве Я. Отрицанием предиката «Река х впадает в озеро Байкал» является предикат «Река х не впадает в озеро Байкал» (оба одноместных предиката определены на множестве названий рек).

Характеристики

Список файлов книги