Тема 6.3. Логіка предикатів.

[основна: 2, 4, 7, 8, 9, 10, 11, 12; додаткова: 12, 14]

Вказівки щодо використання літературних джерел.

Варто усвідомити обмеженість виражувльних засобів мови числення висловлювань і в плані їх розширення розглядати змінні, константи, предикати, функції, квантори. Розглядаючи змінні, константи, предикати, функції і квантори як символи певної нової і багатшої мови, важливо правильно розуміти їхнє значення. Адже тільки в цьому випадку можна сподіватися на формування спроможності зображувати за допомогою формул логіки предикатів різноманітні знання про область застосування, що цікавить дослідника.

Рекомендується область застосування розглядати, в першу чергу, як множину об'єктів, над якими визначені деякі операції. Нас цікавлять властивості і відношення об'єктів і результатів застосування до них операцій. Результати операцій ми можемо записати за допомогою функцій, а властивості і відношення об'єктів та результатів операцій - за допомогою предикатів.

Предикати з константами дозволяють визначити прості висловлювання про об'єкти. Використання змінних у предикатах дозволяє узагальнити ці знання на всю множину об'єктів. Звідси походить уявлення про предикат як функцію, що ставить у відповідність кожному об'єкту (комбінації об'єктів для предикатів місткості 2 і більше) із множини об'єктів - просте висловлювання.

Квантори можна розглядати як логічну операцію, що узагальнює певним чином значення істинності згаданих вище простих висловлювань.

Множина об’єктів разом з відповідністю, що відносить константам об'єкти з цієї множини, функціям - операції над об'єктами цієї множини, предикатам - відношення на цій множині об'єктів звичайно називається інтепретацією і розглядається як засіб надання формулам логіки предикатів змісту. Навчившись встановлювати за визначеної інтепретації значення істинності елементарної формули, можна переходити до оволодіння процедурою встановлення значення істинності довільної формули логіки предикатів за визначеної інтепретації.

Використовуючи інтепретації, формули логіки предикатів можна розбивати на класи на підставі тих значень істинності, що вони набувають за конкретної інтепретації (всіх інтепретацій). Рекомендується повправлятися в доборі інтепретацій для надання визначеним формулам потрібного значення істинності, зробити спробу визначити структурні особливості формул кожного із класів істинності.

Визначення алгебри предикатів доцільно розглядати в порівнянні з визначенням алгебри висловлювань. Вар­то звернути увагу на деякої особливості визначення тотожних формул у логіці предикатів, зокрема виділення тотожних за інтепретації та тотожних у логіці предикатів формул. Набір тотожностей, що характеризують операції алгебри предикатів, включає тотожності булевої алгебри і тотожності, що зв'язують двоїсті квантори за допомогою заперечення. Відношення логічного слідування займає важливе місце й у логіці предикатів.

Потім рекомендується досліджувати особливості алгебраїчного методу встановлення значення істинності формул логіки предикатів. Закріпіть навички алгебраїчних перетворень формул логіки предикатів, зробіть спробу створити деяку процедуру спрощення формул довільного виду. Важливо усвідомити обмеженість введених тотожностей алгебри предикатів для встановлення логічної істинності деяких формул із класів логічно істинних формул та протиріч.

Аналіз нормальних форм логіки предикатів пов'язуйте з доведенням того, що довільна формула логіки предикатів може бути представлена у відповідній формі, встановленням корисності нормальних форм для вирішення важливих проблем логіки. Необхідно підкреслити, що перетворення довільної формули логіки предикатів у скулемівську стандартну форму зберігає значення істиності тільки для суперечливих формул. Закріпіть навички перетворення формул логіки предикатів у нормальні форми.

Матеріал про теорії першого порядку варто розглядати в плані поглиблення уявлень про аксіоматичні системи. Мова теорій першого порядку містить багаті виражувальні засоби. При побудові виводів у теоріях першого порядку важливо дотримуватися рекомендацій, що сформульовані для числення висловлювань, збагачуючи їх прийомами роботи з аксіомами і правилами виведення, що характеризують властивості кванторів.

З метою більш глибокого проникнення в таємниці аксіоматичного підходу рекомендується використову­ва­ти різноманітні визначення теорій першого порядку, що побудовані на різних наборах логічних зв'язок, логічних аксіом і правил виведення. Уважно досліджуйте теорію S арифметики, інші приклади теорій першого порядку і зробіть спробу аксіоматизувати який-небудь із розділів математики. Сформуйте уявлення про моделі теорій першого порядку.

Закріплення навичок природного виведення варто сполучати з дослідженням дедуктивних властивостей теорії першого порядку. Зверніть увагу на результати про загальні властивості виводу, що переносяться з числення висловлювань у числення предикатів. Перед тим, як досліджувати теорему дедукції, її доведення, зробіть спробу усвідомити причини того, чому вона не має місця в численні предикатів у загальному вигляді. Переконайтеся в тому, що загальна схема доведення теореми дедукції, що була застосована в численні висловлювань, працює й у численні предикатів. Сформуйте глибокі уявлення про замикання формул логіки предикатів, що будуть широко використовуватися в курсі.

Зміст модельних властивостей теорій першого порядку і значення їх із точки зору оцінки корисності теорій як інструментарія для одержання нових результатів у порівнянні з темою 6.2 не змінилися. Проте, у достатньо багатих теоріях першого порядку ми зіштовхуємося з дуже важливими явищами їхньої принципової нерозв’язуваності і неможливості встановлення несуперечливості засобами самих теорій. Познайомтесь із методами доведення несуперечливості і повноти числення предикатів. Усвідомте сутність редукції, проблеми характеризації. Повторіть повний цикл досліджень для теорій першого порядку з рівністю.

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

Означення теорії першого порядку Т.