Спирина, М.С. Дискретная математика

• если А, В — формулы, х — переменная, то А(х), (А), (А -> В), V* Л(х, ...) и Зх А(х, ...) — формулы. 3. Аксиомы: • исчисления высказываний: Рх\ { А ( В _-> А));_Р2: ((А -» (В —> С)) —> ((Л —> В) —> (Л —> С)); Р2. (В —> /1) • кванторные: Р4: УхЛ(*) -» Л(у); Р5: А(х) -э ЗуА(у). 4. Правила вывода: • /?,: ^ ^ — modus ponens] В Построенная формальная теория S описывает весьма общие объекты, поэтому нужно ее интерпретировать в то, с чем можно работать. Под предикатом будем понимать следующее. Произвольная функция Р : Мп —> В, заданная на произвольном множестве М, называется «-местным предикатом Р (х ь ..., х„). Причем в такой трактовке Р уже задает семантическую характеристику. Заметим, что предикаты дают возможность математически ана­ лизировать суждения. В классической логике предикатом называ­ ется сказуемое суждения, т.е. то, что утверждается или отрицается относительно субъекта этого суждения, имени предмета мысли, фиксирующее его определенные свойства. А в математической логике понятие предиката рассматривается как тождественное суждению, содержащему местоимения, т.е. пропозиционная фун­ кция, аргументами которой служат имена. Например, о высказы- вательной форме «Он получил специальность программиста» нельзя сказать, истинна она или ложна, пока не произведена замена местоимения «он» на существительное: «М.А. Иванов стал про­ граммистом» (истинно), «Дом стал программистом» (ложно). Далее подробно опишем все составляющие формальной тео­ рии исчисления предикатов в такой интерпретации. Язык логики предикатов. Символами X, Y, Z, Хп Yh ... в логике предикатов принято обозначать предметные переменные , т.е. от­ дельные предметы — имена. Они могут быть простыми и сложны­ ми. Если такие предметы (имена) не содержат дополнительной информации о себе, то они называются собственными (простыми), например «земля», «студент» и др. Если такое имя содержит наряду с самим предметом его отдельные свойства, то оно является слож­ ным, например «автор романа «Анна Каренина», «перпендикуляр­ ные прямые», «взаимно-однозначное соответствие» и др. Символами a, b, с, а„ bh ... принято обозначать константы или предметные постоянные , т. е. конкретные значения имен предметов . Г> . Л — 7 и у Л ) 2' Л - > У х В Д А -> В(х) — введение квантора общности; . п . Ж*) -» В 3' ЗхА{х)~*В — введение квантора существования. 225