• Логіка предикатів першого порядку
  • 3.1. Основні поняття логіки предикатів
  • 3.2. Квантори
  • 3.3. Формули логіки предикатів
  • 3.4. Рівносильність формул логіки предикатів
  • 3.5. Закони і тотожності логіки предикатів
  • 3.6. Властивості числення предикатів першого порядку

Логіка предикатів першого порядку

3.1. Основні поняття логіки предикатів

В розділу 1 формалізація мови у логіці висловлювань здійснюється шляхом розбиття мовних повідомлень на окремі неподільні речення (атоми), а їх змістовне об’єднання – за допомогою символів ~ , → , , , ¬ . Внутрішня структура речень при цьому не враховується. Наприклад, для умовиводу ”Деякі люди геніальні. Сократ ‒ людина. Отже, він геніальний”, інтуїтивно зазначений логічний висновок стосується деяких індивідуумів, до яких Сократ міг і не належати. Тобто, в цьому висловлюванні не врахована внутрішня змістова особливість узагальнення ” деякі ”. А якщо розглянути умовивід „Кожна людина смертна. Оскільки Сократ ‒ людина, то він смертний”, то інтуїтивно зазначений логічний висновок є коректним.

Розглянемо цей умовивід більш детально. Для цього введемо атоми: А – ”кожна людина смертна”; В – ”Сократ - людина” ; С – ”Сократ смертний”.

Тоді умовивід буде відповідати формулі логіки висловлювань А В→ С, або перетворивши яку в нормальну форму, отримаємо

А В → С = ¬( А В ) С = ¬ А ¬ В С.

Остання формула на інтерпретації ( I, I, X ) хибна ( X ), що свідчить про те, що вона не є загальнозначущою. А це означає, що у рамках логіки висловлювань С не є логічним наслідком А і В. Така обмеженість можливостей цієї формалізації пов’язана з тим, що в атомі А не врахована внутрішня змістова особливість узагальнення ”кожний”.

Теорія предикатів враховує внутрішню структуру речень і ґрунтується на тому, що в цих реченнях представлені об’єкти мають певні властивості, або знаходяться між собою у певному відношенні. Наприклад, в висловленні ” Сократ – людина ”, підмет ” Сократ ” є об’єктом, а присудок ” людина ” виражає деяку його властивість. Головним для логіки предикатів є саме друга складова речення, яка фіксується, а значення об’єкту пропонується позначити деякою змінною величиною. Таким чином, можна розглянути речення ” x – людина ”, яке не являється висловлюванням, а є висловлювальною формою, підстановка в яку замість параметра x об’єктів ( значень ) з деякої множини М перетворює форму в висловлювання.

Нехай М – непорожня підмножина декартового добутку M₁хM₂х…хM_n

множин (n [TEX]\geq [/TEX] 1).

Означення 3.1.1. n – місним предикатом, заданим на множині М, називається речення, що містить n змінних x₁,x₂,…,x_n і стає висловленням при кожній заміні їх елементами з відповідних множин a₁,a₂,…,a_n.

n – місний предикат будемо позначати Р( х₁, х₂,... , x_n ), змінні x₁,x₂,…,x_n будемо називати предметними змінними, а елементи множин, які ці змінні пробігають ((a₁,a₂,…,a_n) ϵ М) – предметними константами. Наприклад, над множиною натуральних чисел речення ” х – просте число ” є одномісний предикат, а речення ” х кохає y ” є двомісний предикат на множині людей.

Таким чином, будь-який n – місний предикат можна ототожнити з логічною функцією n аргументів, яка приймає значення із множини {I, X}, тобто

Р ( х, х ,... , x ) : M₁хM₂х…хM_n → { I,X }.

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

Таким чином, предикат Р( х, х ,... , x ) буде визначений, якщо: задана деяка множина М, яку називають областю визначення предиката (предметна область); задана область значень (фіксована множина {I,X }); зазначено правило, за допомогою якого кожному елементу, що взятий у предикатній області, ставиться у відповідальність один із двох елементів із області значень. Предикат, що не має предметних змінних ( n=0 ) є висловлюванням або нульмісним предикатом; якщо п=1, то предикат відповідає властивості; якщо п=2, то предикат є бінарним відношенням; якщо п=3, то предикат – тернарне відношення і т.д.

Приклад 3.1.1. Представити предикатами речення: ”х – ціле число”; ”х ділиться на у”.

Розв’язання. Дії або властивості цих речень оберемо як назву предикатів: ЦІЛЕ, ДІЛИТЬСЯ. Тоді задані висловлювання можна записати у вигляді предикатів таким чином: ЦІЛЕ(х), ДІЛИТЬСЯ(х, у). Перший предикат є одномісним і виражає деяку властивість чисел, а другий двомісним і виражає бінарне відношення подільності на множині чисел.

Над предикатами можна виконувати звичайні логічні операції. Результатом цих операцій будуть нові предикати. Наприклад, нехай Р( х ) позначає предикат ”х ділиться на 2”, а Q ( x ) ‒ предикат ”х ділиться на 3”. Тоді вираз

Р( х ) Q ( x ) позначає предикат ”х ділиться на 2 та х ділиться на 3”, тобто позначає предикат ”х ділиться на 6”.

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

• предметні змінні x₁,x₂,…,x_n ;

• предметні константи a₁,a₂,…,a_n ;

• функціональні символи f_iⁿ , де і =1,2,… вказує порядковий номер символу, а n =1, 2, … вказує на кількість аргументів;

• предикатні символи P_iⁿ, де і=1,2,…вказує порядковий номер символу, а n =0, 1, 2, …вказує на кількість аргументів;

• знаки логічних операцій  ~ , → , , , ¬, ↔;

• квантори  [TEX]\forall ,\exists [/TEX];

• знаки пунктуації – ліва і права дужки та кома.

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

Означення 3.1.2. 1) будь-яка предметна змінна або предметна константа є термом; 2) якщо f - функціональний символ, а ‒ терми, то f() є терм. 3) Ніяких інших термів, крім породжених за допомогою зазначених вище правил, не існує.

Приклад 3.1.2. Записати у вигляді предикатів такі речення: ”Сестра Миколи”, ”Студенти складають іспит”, ”Число х більше числа х - 1”.

Розв’язання 1. Речення ”Сестра Миколи” не може бути ”істинним” або ”хибним”, тому його не можна зобразити у вигляді предиката. Дане речення є деяким елементом предметної області, яке відповідає множині людей.

2. Речення ”Студенти складають іспит” може набувати значення ”істина” або ”хибність”, тому його можна записати у вигляді предиката. У структурі речення можна виділити присудок ”складають”, підмет ”студенти” і додаток ”іспит”. Підмет і додаток можна розглядати як предметні константи, а присудок – як нульмісний предикат. Тому речення ”Студенти складають іспит” можна записати у вигляді нульмісного предиката таким чином: СКЛАДАТИ (студенти, іспит).

3. Присудком у цьому реченні є слово ”більше”. Підмет ”х” і додаток

”х - 1” зобразимо у вигляді термів. Терм ”х - 1” має внутрішню структуру, оскільки в ньому присутній функціональний символ ” мінус ”. Виходячи із цього речення набере вигляду двомісного предиката: БІЛЬШЕ( ( х,1 ), мінус( х,1 ) ), де х – предметна змінна, а 1 – константа.

Приклад 3.1.3. Предикат ”ДОРІВНЮВАТИ ( х ,7 )” записати природною мовою.

Розв’язання. У предикаті 7 є константа, а х – предметна змінна, тому він відповідає твердженню природної мови - х дорівнює 7.

3.2. Квантори

Окрім застосування до предикатів ” звичайних ” логічних операцій (~ , → , , , , ↔) та операції підстановки замість предметних змінних їх конкретних значень, в логіці предикатів використовують так звані операції зв’язування квантором ( операції квантифікації ). Квантори вперше були введені саме в рамках класичної математичної логіки.

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

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

Знак квантора загальності є перевернутою буквою ”А”, що є першою буквою англійського слова ”All”, що означає ” всі ”, а знак квантора існування є перевернутою літерою ”Е”, що є першою буквою англійського слова ” Exist ” і означає ” існування ”. Квантор у природній мові читається як ” всі ”, ”кожен”, ”всякий”, ”який би не був”. Квантор - ”існує (бодай один) ”, ”існують”, ”знайдеться (бодай один) ”, ”знайдуться”, ”деякі”.

Якщо квантор застосовується до предикату, то кажуть, що він навішується на формулу. Наприклад, х₁ Р( х₁,x₂,…,x_n ) – на n – місний предикат навішений квантор загальності, при цьому він зв’язує змінну х₁ , а на інші змінні його дія на розповсюджується. Змінна х₁ в цьому випадку називається пов’язаною, всі інші змінні є вільними. В результаті операції квантифікації місність предикату зміниться ( в даному випадку предикат стане n-1 – місним ).

Важливу роль в логіці предикатів відіграє поняття області дії квантора. Область дії квантора – це предикат, на який даний квантор навішується. Як правило, вона виділяється дужками.

Наприклад, у предиката [TEX]\forall [/TEX]x [TEX]\exists [/TEX]y (x<y[TEX]\wedge [/TEX]z>0)↔(x=z) змінна z вільна, змінна x частково вільна, бо має два зв’язаних і одне вільне входження, а змінна y пов’язана.

Якщо предикат P(x) не містить інших змінних, окрім , вирази [TEX]\exists [/TEX]x P(x) та [TEX]\forall [/TEX]x P(x) є реченнями, що виражають істинні або хибні висловлювання.

Приклад 3.2.1. Висловлювання: ” Всі студенти складають іспити ” і

” Деякі студенти складають іспити на відмінно ” представити засобом логіки предикатів.

Розв’язання. Введемо предикати: Р(x) ‒ ” x – складає іспити ”, Q(x) ‒ ” x – складає іспити на відмінно ”, x M, де М – множина студентів. Тоді шукані представлення матимуть вигляд х Р( х ) і х Q( х ).

Приклад 3.2.2. Для предметної області множини дійсних чисел записати

засобом логіки предикатів такі твердження: ”Існує число, квадрат якого дорівнює

25”; „ Для всіх х є правильним, що ( х + 2 )= х+ 4х + 4 ”.

Розв’язання. Введемо предикат P(х, у) – “ x=y “, який є істинним тоді, коли значення змінної х дорівнює значенню у. У цьому випадку, використовуючи квантори, можна записати:

х P( х , 25 ) ; х P( ( х + 2 ), х+ 4х + 4 ).

3.3. Формули логіки предикатів

Означення 3.3.1. Формулою у логіці предикатів називають формулу, яка задовольняє такі індуктивні визначення.

1. Якщо P - символ n-місного предиката, а t,t,...,t ‒ терми, то

Р( t,t,...,t ) ‒ формула, яку називають атомарною ( елементарною ). Всі предметні змінні атомарних формул – вільні, пов’язаних змінних немає.

1. 2. Якщо P ‒ формула, то ¬ P ‒ також формула. Вільні й пов’язані змінні формули ¬ P ‒ це відповідно вільні та пов’язані змінні формули P .
2. 3. Якщо і ‒ формули і немає таких предметних змінних, які були б пов’язаними в одній формулі, але вільними в іншій, тоді , , , (~) є теж формулами, в яких статус змінних зберігається.
3. 4. Якщо Р ‒ формула, яка містить вільну змінну х, то x P і x P також є формулами. Змінна х у цих формулах стає пов’язаною. Статус інших змінних зберігається.
4. 5. Ніяких інших формул, крім породжених зазначеними вище правилами, не існує.

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

• P ( x,x,x ) ;

• xx P ( x,x,x ) xP ( x,x);.

• x x ( P ( x₁, x₃ ) P ( x₃, x₄ )

Розв’язання. Вираз а) є атомарною формулою, в якій x,x,x - вільні змінні. Вираз б) є формулою, в якій x,x- пов’язані змінні, а x, x ‒ вільні змінні.

Вираз в) не є формулою, оскільки порушено правило 3 означення 3.3.1.

Приклад 3.3.2. Визначити, які змінні є пов’язаними, а які вільними у таких формулах:

1. Р( х,у,z ),; y ( P( x ) x Q( x,y )) ; y ( P( y ) y Q( x,y )) .

Розв’язання. Усі три змінні у формулі а) є вільними. У формулі б) змінна у є пов’язаною, а змінна x – і пов’язаною, і вільною. У формулі в) змінна х є вільною, а змінна у пов’язаною.

Означення 3.3.3. Інтерпретацією формули логіки предикатів називається система, яка складається з непорожньої множини М [TEX]\subset [/TEX] (М₁хМ₂х…хМ_n), яку називають областю інтерпретації, і відповідності, яка кожному предикатному символу P_iⁿ зіставляє певний n – місний предикат, заданий на множині М, кожному функціональному символу f_iⁿ – деяку n – арну алгебраїчну операцію, кожній константі α_i– деякий конкретний елемент із М.

Для кожної інтерпретації на області формула F може набувати істинного І, або хибного Х значення згідно з такими правилами.

1. 1. Якщо задані значення формул F і G, то значень істинності формул , , , (~) можна визначити за допомогою таблиць істинності відповідних логічних операцій.
2. 2. Формула x F набуває значення І, якщо F набуває значення І для кожного х із предикатної області , у протилежному випадку - Х.
3. 3. Формула x F набуває значення І, якщо F набуває значення І для деякого х із предикатної області , у протилежному випадку - Х.

Означення 3.3.4. Формула логіки предикатів називається :

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

2. хибною в даній інтерпретації, якщо вона не виконується на жодному наборі елементів з області інтерпретації;

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

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

Приклад 3.3.3. Побудувати інтерпретацію формул: P( x,x ) ;

xP( x,x ) ; х₂ х₁ Р( х, х ).

Розв’язання. Введемо область інтерпретації – множину цілих додатних чисел Z₊, а замість P(x₁, x₂) введемо предикат ”x₁ ≥ x₂ ”. Перша формула – це саме предикат, побудований на Z₊. Вона є виконуваною і спростовною. Друга формула буде виражати одномісний предикат, вона є хибною. Третя формула – це істинне висловлювання яке стверджує про існування найменшого цілого додатного числа.

3.4. Рівносильність формул логіки предикатів

Нехай формули і мають одну й ту саму множину вільних змінних (зокрема порожню).

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

Приклад 3.4.1. Визначити рівносильність формул

F = P ( x,x ) P( x,x ) і G = P( x,x ) P( x,x ) , які задані на множині M = { a,b } предикатами Q ( x,y ) та Q ( x,y ), наведеними в табл. 3.4.1 і 3.4.2.

Таблиця 3.4.1 

х	у
а	a	І
а	b	Х
b	a	Х
b	b	І

 

 

 

 

 

 

 

 

Таблиця 3.4.2

х	у
a	a	І
a	b	І
b	a	Х
b	b	X

 

 

 

 

 

 

 

 

Розв’язання. Якщо областю інтерпретації є множина М, а в формулах і предикатному символу P зіставляється предикат Q₁( x,y ), то формули і рівносильні в заданій інтерпретації тому, що вони набувають значення І тільки на двох наборах змінних ( a,a,a ) та ( b,b,b,), на інших наборах – Х.

Якщо областю інтерпретації є множина M, а P інтерпретується як предикат

Q₂ ( x,y ), то формули і ‒ нерівносильні в заданій інтерпретації тому, що формула в наборі ( a,b,b ) набуває значення І, а формула ‒ значення Х.

Необхідно виділити, що для логіки предикатів зберігаються всі рівносильності та правила рівносильних перетворень логіки висловлювань.

3.5. Закони і тотожності логіки предикатів

Усі закони і тотожності, які справедливі у логіці висловлювань, залишаються справедливими й у логіці предикатів. Але у логіці предикатів існують додаткові закони , які використовують для еквівалентного перетворення формул, що містять квантори та змінні.

1. Заміна зв’язаної змінної.

Уведення нового позначення зв’язаної змінної не змінює змісту формули логіки предикатів за умови, якщо ніяка вільна змінна у будь-якій частині формули не буде після перейменування зв’язаною змінною , наприклад:

х Р( х ) = у Р( у ) ;

х Р( х ) =у Р( у );

х у Р( х;у ) = z t ( z, t ).

2. Комутативні властивості кванторів.

У логіці предикатів можна змінювати місцями тільки однойменні квантори, наприклад:

х у Р( х,у ) = у х Р( х,у ) ;

х у Р( х,у ) = у х Р( х,у ) ;

х у Р( х,у ) у х Р( х,у ).

Приклад 3.5.1. Для предиката x y ДОРІВНЮЄ( х+1, у ) показати, що зміна місцями кванторів приводить до невідповідності між висловлюваннями до і після зміни місцями кванторів.

Розв’язання. Заданий предикат є висловлюванням і означає, що для будь-якого числа х існує число у, яке більше його на одиницю. Наведене висловлювання є істинним. Але якщо поміняти порядок розташування кванторів на протилежний, то отримаємо таке висловлювання: yx ДОРІВНЮЄ( х+1, у ). Одержане висловлювання означає, що існує таке число у (одне), яке на одиницю більше будь-якого числа х. Це висловлювання не відповідає попередньому і є хибним, що підтверджує закон комутативної властивості кванторів.

3. Дистрибутивні властивості кванторів.

Нехай формула Р ( х ) містить пов’язану змінну х, а формула Q не містить пов’язаної змінної х й обидві вони задовольняють п.3 означення 3.3.1, тоді

х ( Р ( х ) Q ) = х Р ( х ) Q;

х ( Р ( х ) Q ) = х Р ( х ) Q;

х ( Р ( х ) [TEX]\vee [/TEX]Q ) = х Р ( х ) [TEX]\vee [/TEX]Q;

х ( Р ( х ) [TEX]\vee [/TEX]Q ) = х Р ( х ) [TEX]\vee [/TEX]Q .

Доведемо першу з цих рівностей (інші доводять аналогічно). Нехай х,х...,х‒ усі вільні змінні формули х ( Р ( х ) Q ). Тоді вони будуть усіма вільними змінними формули х Р ( х ) Q.

Розглянемо довільну інтерпретацію на множині М . Нехай ( a , a,..., а) ‒ довільний набір значень вільних змінних х,х...,х, де а М . Оскільки формула Q не містить пов’язаної змінної х , то можна визначити значення цієї формули на наборі ( a , a,..., а) у частині , що стосується вільних змінних формули Q. Якщо формула Q на наборі ( a , a,..., а) набула значення Х , то (х Р( х ) Q ) на цьому наборі теж Х і для будь-якого елемента а М на наборі ( a , a,..., а) своїх вільних змінних х,х...,хформула Р( х ) Q набуває значення Х. Звідси випливає, що х Р ( х ) Q на цьому наборі теж дорівнює Х. Якщо формула Q на наборі ( a , a,..., а) набула значення І, то для будь-якого елемента а М на наборі ( a , a,..., а) формула Р( х ) Q й Р( х ) набувають однакових значень істинності. Звідси випливає, що х ( Р( х ) Q ) на наборі ( a , a,..., а) тотожна х Р( х ) Q .

Якщо не вимагати, щоб формула Q не містила пов’язаної змінної х, то справджуватимуться тільки дві рівносильності :

х ( Р ( х ) Q ( х )) = х Р ( х ) х Q х ;

х ( Р ( х ) Q ( х )) = х Р ( х ) х Q ( х ) .

Сформульований дистрибутивний закон справедливий тільки для квантора загальності при кон’юнкції і квантора існування при диз’юнкції , оскільки інші комбінації приводять до нерівностей

х ( Р( х ) Q( х )) х Р( х ) х Q( х );

х ( Р( х ) Q( х )) х Р( х ) х Q х ).

Для подолання цього обмеження дистрибутивного закону, слід використовувати заміну зв’язаної змінної

х Р( х ) Q( х ) = х Р( х ) у Q( у )= х у ( Р( х ) Q( у ) ;

х Р( х ) х Q( х ) = х Р( х ) у Q( у )= х у ( Р( х ) Q( у )).

4. Закон де Моргана для кванторів.

Нехай Р (х) – формула, що містить пов’язані й вільні змінні. Тоді справджуються рівносильності

хР ( х ) = х ¬ Р( х ); (3.5.1)

¬х Р( х ) = х ¬ Р( х ). (3.5.2)

Доведемо спочатку рівносильність 3.5.1. Нехай х,х...,х ‒ множина всіх вільних змінних формули Р , відмінних від пов’язаних змінних х. Покажемо , що на будь-якому наборі значень вільних змінних ( a , a,..., а) , а М, формули ¬х Р( х ) і х ¬ Р( х ) набувають однакових значень істинності. При цьому можливі два випадки.

1. 1. Для будь-якого елемента а М Р( х )= І на наборі ( а , a , a,..., а).
2. 2. Для деякого елемента а М Р ( х ) = Х на наборі ( а, a , a,..., а).
3. У першому випадку для будь-якого елемента а М маємо ¬Р( х ) =Х на наборі ( a , a,..., а). Звідси за означенням х ¬ Р( х ) = Х на наборі ( a , a,..., а), з іншого боку, х Р( х ) = І, а ¬ х Р ( х ) = Х на наборі ( a, , a,..., а) .

У другому випадку для елемента а М маємо ¬ Р ( х ) = І на наборі

( а, a , a,..., а). Звідси х ¬ Р( х ) = І на наборі ( a , a,..., а). З іншого боку, х Р( х ) = Х , а ¬ х Р ( х ) = І на наборі ( a , a,..., а), що і потрібно було довести для рівносильності формули 3.5.1. Доведення рівносильності формули 3.5.2 аналогічне описаному для формули 3.5.1.

3.6. Властивості числення предикатів першого порядку

У цьому параграфі розглядаються основні властивості числення предикатів першого порядку.

Теорема 3.6.1 ( теорема про повноту). Кожна вивідна в численні предикатів першого порядку формула є загальнозначущою.

Доведення. Достатньо впевнитися в тому, що аксіоми АП1‒ АП5 – загальнозначущі формули, і показати, що застосування правил виведення АП1‒ АП3 до загальнозначущих формул веде до одержання тільки загальнозначущих формул.

Загальнозначущість аксіом АП1‒ АП3 (вони ж А1‒ А3) було розглянуто в 2.1, 2.2. Покажемо загальнозначущість формули x А (х) → А (у) (аксіома АП4). Припустимо, що ця формула загальнозначуща, тоді одержимо, що у задовільній предметній області є такий набір значень предметних змінних, при якому x А (х) =I, а А (у) = X. Але оскільки є значення предметних змінних, при яких формула А набуває хибного значення X, тоді згідно з квантором загальності формула x А (х) також повинна набувати значення X. Виникла суперечність і доводить загальнозначущість формули х А (х) → А (у), звідки випливає і загальнозначущість аксіоми АП4. При доведенні аксіоми АП5 припустимо, що формула xi (А → В) → ( А → xi В) незагальнозначуща. Тоді при деякій інтерпретації формула А → xi В набуде значення X, а xi (А → В) – значення I. Якщо А → xi В = X, то А = I, а xi В = X. Оскільки xi (А → В) = I, то для будь-якого xi при В = X повинне виконуватися А = I. Із протиріччя для істинного значення формули А випливає справедливість загальнозначущості аксіоми АП5, що і необхідно було довести.

Теорема 3.6.2. Числення предикатів першого порядку ПL є несуперечною теорією.

Доведення. Припустимо, що для деякої формули А в теорії ПL є дві теореми А і ¬ А. Із факту загальнозначущості будь-якої із цих теорем отримаємо, що А = I і ¬ А = I, але одночасно цього не може бути, що й потрібно було довести.

Теорема 3.6.3. Якщо формула В не залежить від формули А при доведенні Г, А ├ В, то Г ├ В.

Доведення. Доведення виконаємо індукцією за довжиною виведення

, , …, = В. При n = 1 маємо = B і B або належить Г {A}, або є аксіомою. Але В не може збігатися з А, внаслідок незалежності В від А. Отже, Г ├ В.

Нехай теорема справедлива для всіх формул В, довжина виведення яких менша n. Якщо В Г або В – аксіома, то Г ├ В. Якщо ж В – безпосередній наслідок деяких формул із , , …, (однієї або двох) і оскільки В не залежить від А, то від А не залежить жодна із цих формул. Але тоді за припущенням індукції, із Г виводяться формули (одна або дві), а разом з ними – і формула В, що й потрібно було довести.

Теорема 3.6.4 (теорема дедукції). Нехай Г, А ├ В і при цьому нехай існує таке виведення В із Г, А, в якому жодне застосування правила узагальнення до формул, які залежать від А в цьому виведенні, не зв’язується квантором загальності формули А. Тоді Г ├ А → В.

Доведення. Доведення проводиться індукцією за довжиною виведення

, , …, = В. При n = 1 існують дві можливості:

а) Г або є аксіомою;

б) = А.

У першому випадку а) А → В, оскільки це випливає з аксіоми АП1,

→ ( А → ) за правилом МР.

У випадку б), коли А = , то Г ├ → , оскільки А → А – тавтологія.

Нехай тепер теорема справедлива для всіх і < n. Припустимо, що існують індекси k і j, менші і, і що = → . Тоді за припущенням індукції

Г ├ А → і Г ├ А → ( → ). Але за аксіомою АП2 маємо А → ( → ) → → ((А → ) → (А → )) і за правилом МР отримаємо, що Г ├ А → .

Припустимо, нарешті, що існує такий індекс j < i, що = xk B. Тоді за припущенням індукції Г ├ А → і або не залежить від А, або xk не є вільною змінною формули А. Якщо не залежить від А, то за теоремою 7.2.1

Г ├ і застосовуючи правило узагальнення отримаємо Г ├хk . За схемою аксіоми АП1 знаходимо, що → (А → ) і А → ‒ за правилом МР. За припущенням індукції Г ├ А → , за правилом узагальнення Г ├ xk, А → В і, нарешті, за правилом МР отримаємо Г ├ А → xk , тобто Г ├ А → , що й потрібно було довести.

Наслідок 3.6.1. Якщо Г, А ├ В та існує виведення В без застосування правила узагальнення до вільних змінних формули А, то Г ├ А → В.

Наслідок 3.6.2. Якщо формула А замкнена і Г, А ├ В, то Г ├ А → В.

Приклад 3.6.1. Довести, що ├ х у А → х у А.

Розв’язання. Застосуємо предикатні аксіоми, правило МР та узагальнення:

а) х у А – гіпотеза ;

б) х у А → у А – аксіома АП4 ;

в) у А – МР із а), б) ;

г) у А → А – аксіома АП4 ;

д) А – МР із в), г) ;

е) х А – правило узагальнення із д) ;

є) у х А – правило узагальнення із е) .

Теорема 3.6.5 . Якщо формули А (х) і А (у) подібні, то├ х А (х) у А (у).

Доведення. Використовуючи аксіому АП4, маємо ├ х А (х) → А (у). Виходячи з умови теореми 3.6.5 і скориставшись правилом узагальнення, отримаємо

├ у (х А (х) → А (у)). За схемою аксіоми АП5 маємо ├ х А(х)→ у А (у). Аналогічно доводять і формулу ├ у А (у) → х А (х). Для цього необхідно скористатися тавтологією А → ( ¬¬ В → ¬ (А → ¬ В) А→( В → А B), у результаті чого отримаємо х А (х) у А (у).

Теорема 3.6.6 (теорема еквівалентності). Якщо формула В є підформулою А і формула отримана з формули А заміною яких-небудь (можливо, жодного) входжень В формулою С і якщо будь-яка змінна формули В або формули С, що є одночасно пов’язаною змінною формули А, зустрічаються в списку , ,…, , то ├ у1 у2… уk ( В С) → (А A').

Доведення. Доведення виконаємо індукцією за числом зв’язок і кванторів у А. Зауважимо, що якщо жодне входження В насправді не змінюється, то А збігається з A' і формула, яку потрібно вивести, є окремим випадком тавтології В → (А А). Якщо В збігається з А і це єдине входження замінюється на С, то формула, яку необхідно вивести, виводиться із аксіоми АП4. Отже, необхідно вважати, що В є власна підформула формули А і принаймні одне входження В замінюється.

Тепер припустимо, що теорема справедлива для будь-якої формули з меншим числом кванторів і логічних зв’язків, ніж у А.

Випадок 1. А – елементарна формула. Тоді В не може бути власною підформулою формули А.

Випадок 2. А має вигляд ¬D. Тоді нехай A' є ¬D'. За припущенням індукції ├у1 у2… уk ( В С) → ( D D^'). Звідси за допомогою тавтології А В → (¬ А → ¬ В) отримаємо

├ у1 у2… уk ( В С) → (А A').

Випадок 3. А має вигляд D → E. Нехай A'= D^'→ E'. За припущенням індукції

├ у1 у2… уk ( В С) → ( D D^') і ├ у1 у2… уk ( В С) → (Е E'). Застосовуючи тавтологію (( А В) (C D)) → ((A → C) (B → D)),

отримаємо ├ … ( В С) → (А A').

Випадок 4. А має вигляд x D. Тоді A' є x D'. За припущенням індукції ├ у1 у2… уk ( В С) → ( D D'). Змінна х не є вільною змінною формули ├ у1 у2… уk ( В С). Якщо ж припустимо, що це так, то х входила б вільно в В або С, і оскільки х пов’язана в А, то х входила б до переліку , ,…, і була б пов’язаною змінною в у1 у2… уk ( В С), а це суперечить умові. Застосовуючи тепер аксіому АП5, отримаємо у1 у2 …уk ( В С) → ( D D'). Використовуючи х ( А D) → (хА х D), маємо х ( D D^') → (хD хD^'). Користуючись транзитивністю імплікації, остаточно отримаємо

у1 у2…уk (В С) → (хD хD^') або у1у2 … уk ( В С) → (А A'), що й потрібно було довести.

Теорема 3.6.7 (теорема про заміну). Нехай формули А, A', В і С задовольняють умови теореми еквівалентності. Тоді якщо ├ В С, то├ А A', а якщо ├ В С і ├ А, то ├A'. Дана теорема є простим наслідком теореми еквівалентності.

Теорема 3.6.8 (теорема перейменування пов’язаних змінних). Якщо

х В (х) є підформулою формули А, формула В (у) подібна формулі В(х) і A' отримана з А заміною хоча б одного входження х В(х) у А на у В(у), то ├ А A'.

Доведення. Доведення випливає з теорем 3.6.5 і 3.6.7.