Основи дискретного аналізу

ОСНОВИ ДИСКРЕТНОГО  АНАЛІЗУ.  
Автори: Н.Д.Федоренко,В.В.Демченко

 

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

 

 

      Предикатом називають функціональне висловлювання, а висловлювання - предикатною константою. Логіка предикатів - це розширення логіки висловлювань за рахунок використання предикатів в ролі логічних функцій. Ці функції дещо відмінні від функцій Буля. Булеві функції однорідні, тобто, і область значень і область зміни аргументів або істинні, або хибні. Для предикатів область зміни логічна, а область значень - предметна. Розглянемо приклади логічних функцій. Нехай маємо ряд простих висловлювань:  
 
= "4 ділиться на 2"  
 
= "5 ділиться на 2"  
 
= "6 ділиться на 2"  
 
. . . . . . . . . . . . . . . . . . .  
 
= "100 ділиться на 2".      

 Замість цих висловлювань, які  або істинні, або хибні, можна  ввести так званий одномісний предикат = "х ділиться на 2", де областю визначення х є .      

 Означення 1. Одномісним предикатом , визначеним на множині , називається вираз, який після підстановки в нього замість предметів із області визначення перетворюється на висловлювання.      

 Означення 2. Область визначення, від якої залежить предикат, називається предметною областю. Елементи із області визначення називаються предметними змінними. В наведеному вище прикладі змінимо ряд висловлювань на інші: = "4 ділиться на 2" = "8 ділиться на 4" = "5 ділиться на 6" . . . . . . . . . . . . . . . . . . . = "100 ділиться на 98".      

  Тут можна ввести двомісний  предикат  ={х ділиться на y} з додатковою предметною областю . Предикат задає відношення ділення на двох множинах та .      

  Розглянемо ще один предикат   
=" має хобі ", де ; .      

  Цей предикат задає відношення на множині людей і множині їх можливих хобі. В загальному випадку - містний предикат задає -містне відношення.      

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

 Операції над предикатами. Предикат - це функціональне висловлювання, що приймає значення {0;1}, тому над предикатами визначені всі булеві операції: , а також дві нові - операції навішування кванторів: - всезагальності ( - перевернута буква А, що є першою буквою англійського слова ALL - "всі"); - існування ( - перевернута буква Е, перша буква англійського слова Exist "існування").      

 Розглянемо приклади:      

1. Всі люди смертні. Сократ - людина. Отже Сократ смертний.      

2. Деякі люди геніальні. Сократ людина. Отже Сократ геніальний.  
 
Якщо в першому випадку висновок вірний, то в другому правило стосується деяких індивідуумів і Сократ міг до них і не належати. Термін "для всіх" в логіці предикатів і називають квантором всезагальності . Термін "деякі ", або "існує хоча б один називають квантором існування . Навішуючи квантори перед предикатами ми їх або посилюємо , або послаблюємо . Семантика: ="Для всякого предмету властивість виконується". ="Деякі х мають властивість ".      

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

 Визначення терму.      

1. Кожна предметна змінна або  кожна предметна постійна є  терм.      

2. Функціональний символ  , де - терми, є терм.      

3. Інших термів не існує.      

 Визначення формули.      

1. , де - предикатний символ, - терми - атомарна формула.      

2. Якщо А та В - формули, х  - предметна змінна, то формулами  є . ; ; ; ;      

4. Інших формул не існує.      

 Вирази  та , визначаються аналогічно численню висловлень. Формула, що не містить вільних змінних, називається замкнутою. Наприклад: , обидва входження х - зв'язні, y - вільна змінна.  
 
- замкнута формула.      

 Сказати "для всіх х  властивість Р істинна" - це  теж саме, що сказати "кон'юнкція  всіх значень предикатної функції  істинна".  
 
     

 Квантор існування означає диз'юнкцію всіх значень предикатної функції.  
 
     

 Обидва квантори можна заперечувати, виражати один через другий  на основі закону де Моргана:  
 
.  
 
.  
 
Звідси:  
 
.  
 
.      

 Щоб осмислити формули заперечення  кванторів розглянемо приклад: Нехай = "х парне число" з предметною областю . Предикатна функція пробіжить ряд істинних та хибних значень:  
 
 
 
тоді = "не всі парні" = "існують такі , які непарні"= .      

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

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

 Означення. Формула логічно загальнозначуща, якщо при довільній інтерпретації вона істинна.      

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

 Логічно загальнозначущі формули  являються виділеними формулами  алгебри предикатів.  
 
Так як область визначення предикатів може бути нескінчена, то, очевидно, таблиця істинності не може служити алгоритмом для визначення істинності предикатів.  
 
Можна будувати таблиці істинності на обмежених областях.  
 
Нехай предметна область предикатом складається з двох конкретних значень Складемо таблицю істинності (таблиця 24) всіх можливих інтерпретацій, враховуючи, що  
 
     

 Таблиця 25.  
 
     

 З таблиці випливають три  елементарні клаузи:      

I. - аксіома порядку, або .  
 
Її дію продемонструємо на відомому уже прикладі: "Для всіх х справедливе правило: Якщо х - людина, то х смертний. Сократ людина, отже, Сократ смертний".  
 
Введемо предикати:  
 
"х - людина"; "х - смертний", а = "Сократ". Складемо клаузу, що відповідає легенді:  
 
.  
 
Щоб її довести, перенесемо другу посилку вправо за знак метаімплікації, цього досить, щоб вона задовольняла аксіомі порядку і предикатній формі:  
 
.      

II.      

III.      

 Доведемо деякі тотожності  та клаузи.      

1.  
 
Дійсно:  
 
.      

2. доводиться аналогічно.      

3. Дійсно:      

  ,  
 
де:  
 
.  
 
Клауза зводиться до аксіоми порядку: , отже вона правильна.      

4. Аналогічно доводиться клауза -  
 
.      

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

 Нехай двомісний предикат  має предметну область . Складемо таблицю істинності (табл. 26) для всіх можливих інтерпретацій.      

 В таблиці прийняті скорочення:  
 
 
 
 
 
На основі таблиці можна встановити істинність клауз: (m,n) приймають значення а або в).      

 Таблиця 25.  
 
     

8. .      

9. .      

10. .      

11. .      

12. .      

13. .      

14. .      

15. .      

16. .      

17. .      

18. .      

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