Поняття предиката

     Випадок2. Він аналогічний випадку 1.

     Випадок3. Тут формула G може мати такий вигляд:

     3.1) ;

     3.2) ;

     3.3) ;

     3.4) ;

     3.5) ;

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

     Випадок3.2. Він аналогічний випадку 3.1.

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

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

     Випадок3.5. Він аналогічний випадку 3.3.

     Випадок4. Формула має довжину . За індуктивним припущенням існує зведена форма цієї формули з тією самою множиною вільних та зв’язаних змінних. Тоді - зведена форма формули .

     Випадок5. Він аналогічний випадку 4. Теорему доведено.

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

     Приклад. Розглянемо такі формули:

1. - нормальна формула.
2. - зведена формула, що не є нормальною.

 

Теорема2.

      Для будь – якої зведеної формули існує рівносильна їй нормальна формула тієї самої довжини.

     Така  формула називається нормальною формулою заданої зведеної формули.

     Доведення проведемо методом індукції за довжиною n формули. При n=1 формула є атомарною і, отже, нормальною.

     Припустимо, що твердження теореми справджується  для всіх формул, довжина яких менша  від n. Нехай F - формула завдовжки n. Тоді формула F має вигляд: або .

     Випадок1. За умовою - зведена формула. Тоді та також є зведеними формулами, довжина яких менша від n. За індуктивним припущенням існують рівосильні їм нормальні формули та відповідно, де . Якщо формули й не містять символів кванторів, то - нормальна форма завдовжки n формули .

     Нехай, наприклад, формула  містить символ квантора. Тоді має вигляд:  , де (випадок коли має вигляд , є аналогічним).Якщо змінна х входить в формулу , то тільки як зв’язна (інакше порушується означення формули). Застосувавши правило перейменування зв’язаних змінних, перейдемо до формули , рівносильної і такої, що не має змінної х. Очевидно, - зведена формула тієї самої довжини, що й . За правилом винесення квантора за дужки .

     Оскільки  , за індуктивним припущенням існує рівносильна нормальна їй формула тієї самої довжини. Тоді - нормальна форма формули тієї самої довжини.

     Випадок2. Він аналогічний випадку 1.

     Випадок3. Оскільки формула - зведена, є атомарною формулою, і тоді - нормальна формула.

     Випадок4. Тут - зведена формула, . За індуктивним припущенням існує рівосильна їй нормальна формула тієї самої довжини. Тоді - нормальна форма формули завдовжки n.

     Випадок5. Він аналогічний випадку 4. Теорему доведено.

Теорема3.

      Для будь – якої формули  існує рівносильна їй нормальна формула. 

 

       Здійснюваність. Загальнозначущість.

      Розглянемо  деяку інтерпретацію з множиною М.

     Означення 4. Кажуть, що формула А є здійснюваною в заданій інтерпретації, якщо існує набір áа₁, ..., а_nñ, а_і є М, значень вільних змінних х₁ ,...,х_n формули А такий, що А½_<а₁,..., а_n> = 1. Кажуть, що формула А є істинною в заданій інтерпретації, якщо вона набуває значень 1 у будь-якому наборі áа₁, ..., а_nñ, а_і є М, значень своїх вільних змінних х₁ ,...,х_n . Кажуть, що формула А є загальнозначущою або тотожно-істинною (в логіці предикатів), якщо вона – істинна в кожній інтерпретації. Кажуть, що формула А є здійснюваною (в логіці предикатів), якщо існує інтерпретація, в якій А – здійснювана формула.

      Очевидно, формула А є загальнозначущою тоді і тільки тоді, коли формула Ā не є здійснюваною, і здійснюваною тоді і тільки тоді, коли формула Ā не є загальнозначущою.

      Очевидно, якщо F і G – рівносильні (в логіці предикатів) формули, то

F ~ G є загальнозначущою  формулою.  

Твердження 1.

Формула

(" х) А(х) ® А(y)       (4),

де  змінна у не входить  у формулу А(х), – загальнозначуща.

      Нехай - усі вільні змінні формули . Тоді - перелік вільних змінних формули (4). Розглянемо довільну інтерпретацію з множиною .

     Нехай , де - довільний набір значень вільних змінних формули (4). Доведемо, що

.

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

,

або для будь – якого елемента у наборі значень вільних змінних

      

      У першому випадку

        і тоді

       .

      У другому випадку

       ; , і тоді

       .

Твердження 2.

Формула А(у) ® ($ х) А(х), де змінна у не входить у формулу А (х), є загальнозначущою.

     У наслідок попереднього твердження формула  - загальнозначуща. Маємо:

     

     Отже, формула  є загальнозначущою. Як зазначилося вище, одноіменні квантори можна переставляти. Тому формули

      ~

      ~

будуть загальнозначущими.

     Загальнозначущою  є також формула . Однак формула не є загальнозначущою. Справді, нехай формула - це атомарна формула . Розглянемо інтерпретацію, областю якої є множина цілих чисел; символу поставимо у відповідність предикат x<y.

     Тоді  формула  в цій інтерпретації є істиною, а формула - хибною. 

Твердження  3.

Нехай А – тотожньо-істина формула логіки висловлення, а  - список її змінних. Підставивши замість кожної змінної , k=1,2,...,n, формули логіки предикатів , дістанемо загальнозначущу формулу логіки предикатів.

     Задача  розпізнавання загальнозначущості формул логіки предикатів істотно складніша, ніж формул логіки висловлень. Так само, як і в логіці висловлень, вона називається проблемою розв’язуваності і формулюється так: указати ефективний спосіб (алгоритм) розпізнавання загальнозначущості формул (тобто чи є задана формула загальнозначущою).

     Загалом ця проблема в логіці предикатів - нерозв’язувана. Тому наводимо це твердження без доведення. 

Теорема 2 (теорема  Черча).

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

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

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

Твердження  4. 

Нехай, F – формула, що містить n одномісних предикатних символів. Для того, щоб формула F була здійснюваною, необхідно й достатньо, щоб вона була здійснюваною в усіх інтерпретаціях áM, f ñ із множиною М, які містять не більше як 2 ⁿ елементів.

       Нехай в інтерпритаціях та одномісними предикатними символами формули поставлені у відповідність предикати і , j=1,2,... . Кажуть, що інтерпретації та - гоморфні, якщо існує сур’єкція така, що  для будь – якого і для будь – якого . Тоді, як випливає з індуктивного означення, формула, що містить тільки одномісні предикатні символи, в гоморфних інтерпретаціях одночасно або здійснювана, або нездійснювана.

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

       Число таких підмножин  не перевищує числа наборів з 1 і 0 завдовжки n, тобто не перевищує . Виберемо в кожній з цих підмножин по одному представнику і складемо з них множину . Тоді інтерпретацї та , де - обмеження функції на , - гомоморфні, й, отже, формула F є здійснювоною в інтерпретації з множиною , що містить не більш як елементів. Звідси випливає твердження 4.

       Задача  розпізнавання загальнозначущості формул логіки предикатів є складна. Вона називається проблемою розв’язуваності і формулюється так: вказати ефективний спосіб розпізнавання загальнозначущості формул (тобто чи є задана формула загальнозначущою). Загалом ця проблема в логіці предикатів – нерозв’язана. Тому твердження наводяться без доведень. 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

Література:

1. Ю. В. Капітонова, С. Л. Кривий, О. А. Летичевський, Г. М. Луцький, М. К. Печорін: Основи дискретної математики. – Київ, “Наукова Думка”, 2002.

2. Ю. М. Бардачов, Н. А. Соколова, В. Є. Ходаков:  Дискретна математика / За ред. доктора технічних наук, професора В. Є. Ходакова. – Київ: “Вища школа”, 2002.