ЛОГІКИ ПЕРШОГО ПОРЯДКУ

ЛОГІКИ ПЕРШОГО ПОРЯДКУ

1. Мова першого порядку

2. Числення предикатів

Означення. Алгебраїчною системою (АС) назвемо об’єкт вигляду А=(А, ГпА ирґ4), де А - непорожня множина, яку називають носієм, або основою АС, ТпЛ та V/ - множини функцій та предикатів, заданих на А.

Нехай П - довільна множина така, що існує тотальне однозначне відображення І:

Елементи множини Г2 трактуватимемо як змінні деяких функцій та предикатів із рпА'^іР/. Такі змінні називають функціональними символами (ФС) та предикатними символами (ПС), іменовані ними функції та предикати називають базовими

1. Мова першого порядку

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

Алфавіт класичної мови першого порядку складається з таких символів:

• предметні імена (змінні)х,у, 2, ...

• функціональні символи/0,/;,/2, ...

• предикатні символиро, рі, Р2, ■■■

• символи логічних операцій -і, => та Ух.

Кожна елементарна мова задається своєю сигнатурою.

Означення. Множину П функціональних та предикатних символів називають сигнатурою. Нехай Рз - множина функціональних символів, Рл - множина предикатних символів. Тоді сигнатура Сі=РзиРз.

В множині Рз може виділятися підмножина константних символів СпсРз.

Означення. Символи , =>, V та предметні змінні називають логічними символами, функціональні та предикатні символи називають нелогічними символами.

Із змінних, констант, функціональних і предикатних символів з допомогою дужок (, ), ком і логічних символів , =>, V будуються вирази, що називаються термами і формулами.

Терми використовують для позначення, назви суб’єктів, формули - для запису тверджень про суб’єкти.

Означення. Індуктивне визначення терма таке:

1. кожне предметна змінна та кожна константа є термом; такі терми назвемо атомарними;

2. якщо її,..., Іп - терми, /- н-арний функціональний символ, то/і\ ..Іп - терм.

Означення. Атомарною формулою називається вираз виду Рі\..лп, де Р - и-арний предикатний СИМВОЛ, її, ..., Іп - терми.

Означення. Індуктивне визначення формули таке:

1. кожна атомарна формула є формулою;

2. якщо Р та О - формули, то Р та Р=РЗ - формули;

3. якщо Р - формула, х - предметна змінна, то МхР - формула.

Множини термів та формул мови 1-го порядку звичайно позначатимемо відповідно як Тг та Рг.

Формули мови 1 -го порядку сигнатури П називатимемо формулами 1 -го порядку сигнатури СІ.

Можна вказати 2 рівні відмінності мов 1-го порядку:

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

2. істотно різні мови, що відрізняються сигнатурами.

Означення. Мова 1-го порядку І’ сигнатури О.' називається розширенням мови 1-го порядку £ сигнатури £2, якщо П’зП.

Приклади мов 1-го порядку

Наведемо кілька прикладів мов 1-го порядку.

Приклад. Мова арифметики Ьаг визначається сигнатурою £2ОГ={0, 1, +, х, =}, де 0 та 1 - константні символи, + та х - бінарні функціональні символи, = - бінарний предикатний символ.

Терм мови арифметики назвемо арифметичним термом.

Формулу мови арифметики назвемо арифметичною формулою.

Наприклад, 1+1 - замкнений арифметичний терм; хх(у+г) - арифметичний терм; Зг(х+г=у) - арифметична формула.

Приклад. Мова теорії множин Ь!е, визначається сигнатурою П5(.,={є, =), де є та = - бінарні предикатні символи.

Наприклад, гєх - атомарна формула, Уг(2єл:->2єу) - формула, ЗхЗу(у є х) - замкнена формула мови Ь!е,. Зауважимо, що останні дві формули відповідно означають "хсу" та "існує 0".

2. Числення предикатів

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

Означення. Числення предикатів (теорія першого порядку) - це аксіоматична теорія, символами якої є:

• пропозиційні зв’язки , =>;

• квантор загальності V;

• допоміжні символи: кома та дужки “(“,

• предметні змінніх,у,...;

• предметні константи а,

• функціональні СИМВОЛИ

• предикатні символи ро, рирі,...

Введемо наступне позначення . Нехай А - деяка формула, х - змінна, І - терм. Будемо називати терм І доступніш для підстановки замість змінної х у формулу А, якщо жодне вільне входження х в А не знаходиться в частині VуВ, де В - формула (частина формули А) і у - змінна терма І. Через А (і) позначимо формулу, що отримана з формули А заміною змінної х в всіх її вільних входженнях термом І.

Використаємо нові логічні символи для скорочення запису формул:

(А лВ) позначає формулу (А=> В);

(А V В) позначає формулу (А => В) { * ЗхА позначає формулу \/хА .

Аксіоми числення предикатів розбиваються на логічні аксіоми та власні. Наступні формули є логічними аксіомами числення предикатів.

А, Я =>(£=> Я);

А2 (А=>(В=> О) => ((А =>В)=>(А=> С));

А, (В =>!)=> ((В => А) => В).

А^МхА(х)=>А(у), якщо у вільно для х в формулі А(х).

А;. Ух(А=>В(х)) => (А^УхВ(х)), якщо А не містить вільних входжень х.

Власні аксіоми формулюються окремо для кожної конкретної предметної області. В ЧП два правила виведення:

юр:[endif]--А,(А => В)

В

ОЕ№ введення V:[endif]--В => А(х)

----------- (х не входить вільно в В).

В=>МхА(х)

Означення. Вивідністю з гіпотез Г в ЧП називається скінченна послідовність формул така, що для кожного і (1 <і<р) формула А є або аксіомою ЧП, або одна з гіпотез з Г, або безпосередній наслідок попередніх формул, що взяті як посилки правила виведення ЧП.

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

Г,А\-В Г|-<А=>В)[endif]--В) ">

справедливе для ЧП.[endif]--Теорема про дедукцію: Правило

е

Вільні входження предметних змінних в формулу або терм можна замінювати термами. Позначимо Р х [1\,..., і„\ формулу, отриману із формули Р заміною всіх вільних входжень змінних хі, хп на терми її,..., Іп відповідно. Аналогічно визначаємо терм А,, [<і {п]

При заміні вільних входжень предметних змінних термами можливі колізії, коли вільна змінна стає зв’язаною. Наприклад, нехай Р - це формула Зг(х+г=у). Тоді Рх[и\ - це формула Зг(и+г=уУ, Рх[г\ - це формула 3г(г+г=у); отже, маємо колізію.

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

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

![endif]--![endif]--![endif]--![endif]--