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

Что такое Логика Предикатов

Логика Предикатов — раздел логических теорий, в котором изучаютсяобщезначимые связи между высказываниями о свойствах и отношенияхпредметов. в основе логики предикатов лежит формализованный язык,отображающий субъективно-предикатную структуру высказываний. См. такжеИсчисление предикатов.

Значение слова Логика Предикатов по Логическому словарю:

Логика Предикатов — или: Функциональная логика, теория квантификации, кванторная логика,  — основ­ной раздел современной (математической, символической) логики, в котором описываются выводы, учитывающие внутреннюю (субъектно-предикатную) структуру высказываний. Л. п. является расши­ренным вариантом логики высказываний. В Л. п.

— в дополнение к средствам логики высказываний -вводятся логические операторы” («для всех») и $ («для некото­рых» или «существует»), называемые кванторами общности и существования соответственно.

Для выявления субъектно-пре­дикатной структуры высказываний вводится бесконечный пере-   чень индивидных переменных: х, у, z, …, х1, у1, zl, …, представляющих различные объекты, и бесконечный перечень предикатных переменных: Р, Q, R, …, Р1, Q1, Л1, …, представляющих свойства и отношения объектов.

Индивидные переменные принимают значения в произвольной (непустой) области. наряду с этими переменными могут вводиться инди­видные константы, или имена собственные. Запись (“х)Р (х) означает «Всякий х обладает свойством Р». ($х)Р(х) — «Некоторые х обладают свойством Р». ($x)Q(xy) — «Су­ществует х, находящийся в отношении Q с у» и т. п.

Подлинной переменной является только сво­бодная переменная: вместо нее можно подставить одно из ее значений и получить осмысленное выражение. Связанные пере­менные называются фиктивными. Формула Л. п. называется общезначимой, если она истинна в каждой интерпретации. Тавтология логики высказываний явля­ется частным случаем общезначимой формулы.

В Л. п., в отличие от логики высказываний, нет эффективного процесса, позволя­ющего для произвольно взятой формулы решить, является она общезначимой или нет. Для Л. п. доказан ряд важных теорем, характеризующих ее ос­новные свойства (см.: Непротиворечивость, Полнота, Разрешимость теории).

Определение «Логика Предикатов» по БСЭ:

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

В более сложных исчислениях предикатов описываются логические законы, связывающие объекты исследования с отношениями между этими объектами.
В классическом исчислении предикатов употребляются следующие знаки: 1) т. н. предметные переменные — буквы х, у, z,…, которые содержательно рассматриваются как неопределённые имена объектов исследования теории.

2) предикатные переменные — знаковые комплексы вида Pm, Qn, Rl,… (m, n, l — натуральные числа), причём, например, Qn означает произвольное n-местное отношение между объектами. 3) знаки для логических связок: конъюнкции &, дизъюнкции V, импликации
, отрицания ¬, означающие соответственно «… и…», «… или…», «если…, то…», «неверно, что…».

4) знаки для Кванторов
(квантор всеобщности),
(квантор существования), означающие соответственно
«для всех…» и «существует… такое, что…». 5) запятая, скобки (для уточнения строения формул).
Если Qn есть n-местная предикатная переменная, a x1,…, xn — предметные переменные, то выражение Qn (x1,…, xn) есть, по определению, атомарная (элементарная) формула.

Индекс n у предикатной переменной в атомарной формуле обычно опускается. Содержательно Q (x1,…, xn) означает высказывание, гласящее, что объекты x1,…, xn связаны отношением Q.
Формулами считаются атомарные формулы, а также выражения, получаемые из них посредством следующих операций образования новых формул из уже полученных:1) если &phi. и &psi. — формулы, то (&phi.

& &psi.), (&phi. V &psi.), (&phi. &psi.) и ¬ &phi. — также формулы.

2) если &phi. — формула и х — предметная переменная, то x&phi., x&phi. — формулы. Определением формулы заканчивается описание языка исчисления предикатов.

Вхождение предметной переменной х в формулу &phi. называется связанным, если х входит в часть &phi. вида x&psi. или x&psi. или стоит непосредственно после знака квантора. Несвязанные вхождения переменной в формулу называются свободными.
Если найдётся хоть одно свободное вхождение x в &phi., то говорят, что переменная x входит свободно в &phi. или является параметром &phi.. Интуитивно говоря, формула &phi. с параметрами выражает некоторое условие, которое превращается в конкретное высказывание, если (конкретизировав предварительно область объектов) приписать определённые значения входящим в формулу параметрам и предикатным буквам. Связанные же переменные не имеют самостоятельного значения и служат (вместе с соответствующими кванторами) для обозначения общих утверждений или утверждений существования.
Если &phi. — формула, а x и y — предметные переменные, то через &phi.(x|y) будет обозначаться результат замещения всех свободных вхождений x в &phi. на y (а если при этом y оказалось на месте x в части формулы вида y&psi. или y&psi., то следует дополнительно заменить все связанные вхождения y в эту часть на переменную, не входящую в &phi.. это делается для того, чтобы не допустить искажения смысла &phi. при замене x на y).
Пусть &phi., &psi., &eta. — произвольные формулы, а x и y — предметные переменные. Тогда формулы следующих видов принимаются в качестве аксиом классического исчисления предикатов:1. (&phi.(&psi.&eta.)),2. ((&phi.(&psi.&eta.))((&phi.&psi.)(&phi.&eta.))),3. ((&phi.&&psi.)&phi.),4. ((&phi.&&psi.)&psi.),5. (&phi.(&psi.(&phi.&&psi.))),6. ((&phi.&eta.)((&psi.&eta.)((&phi. V &psi.)&eta.))),7. (&phi.(&phi. V &psi.)),8. (&psi.(&phi. V &psi.)),9. (¬&phi.)(&phi.&psi.)),10. ((&phi.&psi.)((&phi.¬&psi.)¬&phi.))11. (&phi. V ¬&phi.),12. (x&phi.&phi.(x/y)),13. (&phi.(x/y) x&phi.).

В исчислении предикатов употребляются след. три правила вывода. 1) Правило вывода заключений: из формул &phi. и (&phi.&psi.) выводится формула &psi.. Два кванторных правила вывода: 2) из формулы (&phi.&psi.), где

&psi. не содержит свободно x, можно вывести (&phi.x&psi.). 3) из формулы (&phi.&psi.), где &psi. не содержит свободно x, можно вывести (x&phi.&psi.).
В отличие от других формулировок исчисления (см., например, Логика, раздел Предмет и метод современной логики), здесь &phi., &psi. и &eta. не принадлежат языку рассматриваемого исчисления, а обозначают его произвольные формулы. поэтому каждая из записей 1-13 есть аксиомная схема,
«порождающая» при подстановке вместо греческой буквы некоторую конкретную аксиому. специальных правил подстановки при этой формулировке не надо.
Интуиционистское исчисление предикатов отличается от классического лишь тем, что закон исключенного третьего (аксиома 11) исключается из числа аксиом. Различие двух исчислений отражает различие в их истолкованиях. Истолкование логических связок &, &or.,
, ¬ в исчислениях предикатов таково же, как и в соответствующих исчислениях высказываний. Что касается истолкования кванторов, то в классическом исчислении предикатов кванторы трактуются с точки зрения актуальной бесконечности. Точнее, каждая формула получает значение
«истина» или «ложь», если определить модель исчисления предикатов, т. е. определить множество объектов, приписать каждой предикатной букве формулы некоторое отношение на этом множестве и приписать всем параметрам формулы некоторые объекты в качестве значений. Формула называется классически общезначимой, если она в любой модели принимает значение «истина».
Как показал К. Гёдель, в классическом исчислении предикатов выводимы все классически общезначимые формулы, и только они. Эта теорема Гёделя и представляет собой точное выражение идеи формализации логики: в классическом исчислении предикатов выводятся все логические законы, общие для всех моделей.
В интуиционистском же истолковании утверждение, что некоторая формула истинна, требует проведения некоторого математического построения. Например, xy&phi. истинно с интуиционистской точки зрения, только если имеется общий метод, позволяющий находить для каждого x соответствующее y.
Истинность x (&phi. V ¬&phi.) предполагает наличие метода для определения истинного члена дизъюнкции (&phi. V ¬&phi.) для каждого значения параметра x. Например, классически общезначимые формулы, выражающие закон исключенного третьего
(&phi. V ¬&phi.) или закон пронесения отрицания через всеобщность (¬x&phi.x¬&phi.), интуиционистски необщезначимы (теория моделей развивается, однако, и для интуиционистского исчисления предикатов).
Л. п. является обычным базисом для построения логических исчислений, предназначенных для описания тех или иных дисциплин (прикладных исчислений). С этой целью язык исчисления предикатов «конкретизируется»: к нему добавляют предикатные символы и знаки операций, выражающие специфические отношения и операции рассматриваемой дисциплины. Например, если мы стремимся описать истинные суждения арифметики натуральных чисел, то можно добавить операции сложения, умножения, отношение делимости и т.п. Затем, кроме аксиом и правил вывода исчисления прецикатов (логических постулатов), в исчисление вводятся аксиомы, выражающие специфические законы изучаемого предмета (прикладные, специфические аксиомы). Таким образом строится, например, Формальная арифметика.
Помимо классического и интуиционистского исчислений предикатов, имеются и др. логические системы, описывающие логические законы, выразимые иными логическими средствами или с иных методологических позиций. Сюда относятся исчисления модальной логики, вероятностной логики, индуктивной логики и др.
Лит.: Клини С. К., Введение в метаматематику, пер. с англ., М., 1957.
А. Г. Драгалин.

Источник: https://xn----7sbbh7akdldfh0ai3n.xn--p1ai/logika-predikatov.html

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

Предикаты вслед за высказываниями являются следующим важным предметом, исследуемым математической логикой.

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

Понятие предиката

В высказывании все четко: это — конкретное утверждение о конкретных объектах — истинное или ложное. Предикат — предложение, похожее на высказывание, но все же им не являющееся: о нем нельзя судить, истинно оно или ложно. Дадим точное определение.

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

Для n-местного предиката будем использовать обозначение . Переменные называют предметными, а элементы множеств , которые эти переменные пробегают, — конкретными предметами.

Поэтому предикат называют также функцией-высказыванием.

Рассмотрим пример. Предложение “Река впадает в озеро Байкал” является одноместным предикатом, определенным над множеством всех названий рек.

Подставив вместо предметной переменной название “Баргузин”, получим высказывание “Река Баргузин впадает в озеро Байкал”. Это высказывание истинно.

Подставив вместо предметной переменной название “Днепр”, получим ложное высказывание “Река Днепр впадает в озеро Байкал”.

Другой пример. Предложение (выражение) “” является двухместным предикатом, заданным над множествами . Множества, на которых задан двухместный предикат, совпадают (говорят, что “двухместный предикат задан на множестве “). Пара действительных чисел 2, 2 превращает данный предикат в истинное высказывание: “”, а пара чисел 2, 3 — в ложное: “”.

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

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

Иногда эту функцию и называют предикатом.

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

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

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

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

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

Приведем примеры предикатов.

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

Этот же предикат являет собой пример опровержимого, но не тождественно ложного предиката (продумайте!).

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

Отметим некоторые достаточно очевидные закономерности взаимосвязей между предикатами различных типов (рекомендуется осмыслить их):

1) каждый тождественно истинный предикат является выполнимым, но обратное неверно;2) каждый тождественно ложный предикат является опровержимым, но обратное неверно;3) каждый не тождественно истинный предикат будет опровержимым, но, вообще говоря, не будет тождественно ложным;

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

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

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

Множество истинности “-местного предиката представляет собой n-арное отношение между элементами множеств . Если предикат — одноместный, заданный над множеством , то его множество истинности является подмножеством множества .

Например, множеством истинности двухместного предиката “Точка принадлежит прямой “, заданного на множестве всех точек плоскости и на множестве всех прямых этой плоскости, является бинарное отношение принадлежности (инцидентности) между точками и прямыми плоскости. Другой пример.

Наконец, если “” — одноместный предикат над , то , или .

В терминах множества истинности легко выразить понятия, связанные с классификацией предикатов (определение 18.2). В самом деле, n-местный предикат , заданный на множествах , будет:

а) тождественно истинным тогда и только тогда, когда ;
б) тождественно ложным тогда и только тогда, когда ;
в) выполнимым тогда и только тогда, когда ;
г) опровержимым тогда и только тогда, когда .

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

Равносильность и следование предикатов

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

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

Утверждение о равносильности двух предикатов и символически будем записывать так: .

Отношение равносильности предикатов является отношением эквивалентности, так что совокупность всех n-местных предикатов, определенных на множествах , распадается на непересекающиеся классы равносильных предикатов (все они определяют одну и ту же функцию, заданную на множествах и принимающую значения в двухэлементном множестве ).

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

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

Рассмотрим простой пример. Пусть требуется решить уравнение (найти множество истинности предиката): . Преобразуем его равносильным образом:

Отметим следующее немаловажное обстоятельство: может быть так, что два предиката равносильны, если их рассматривать над одним множеством, и неравносильны, если их рассматривать над другим (в частности, объемлющим первое) множеством. Такова, например, ситуация с предикатами: и .

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

Другими словами (в терминах множеств истинности), можно сказать, что предикат является следствием предиката тогда и только тогда, когда .

Утверждение о том, что предикат является следствием предиката , будем символически записывать так: .

Например, одноместный предикат, определенный на множестве натуральных чисел, ” делится на 3″ является следствием одноместного предиката, определенного на том же множестве, ” делится на 6″. Из двух предикатов, упомянутых перед последним определением, первый будет следствием второго, если считать, что оба предиката заданы на множестве целых чисел.

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

Теорема 18.6. Каждые два тождественно истинных (тождественно ложных) предиката, заданных на одних и тех же множествах, равносильны. Обратно, всякий предикат, равносильный тождественно истинному (тождественно ложному) предикату, сам является тождественно истинным (тождественно ложным) предикатом.

Теорема 18.8. Пусть и — два n-местных предиката, определенные на одних и тех же множествах, такие, что есть следствие . Тогда:

а) если тождественно истинный (выполнимый), то и тождественно истинный (выполнимый);

б) если тождественно ложный (опровержимый), то и тождественно ложный (опровержимый).

Доказательство теоремы 18.8:

а) Поскольку , поэтому . Если теперь тождественно истинный предикат, то

(где — множества, на которых определены n-местные предикаты и ).

Но . Поэтому , а, значит, предикат — тождественно истинный предикат. Если же — выполнимый предикат, то . Но . Тогда и — выполнимый предикат.

б) Пусть — тождественно ложный предикат. Тогда . Но , поэтому . Следовательно, предикат — тождественно ложный. Наконец, пусть — опровержимый предикат. Тогда . Поскольку, кроме того,

и , то .

Следовательно, предикат — опровержимый.

Отыщите самостоятельно в настоящем и предыдущем пунктах данной лекции утверждения, обосновывающие остальные сформулированные теоремы.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).

Источник: http://MathHelpPlanet.com/static.php?p=logika-predikatov