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

    Можливими є два випадки:

      для будь-якого елемента а є М А(х)ê_á а, а_{1, ....,}а_nñ = 1;

      для деякого елемента  а₀  є М А(х)ê_á а₀, а_{1, ....,}а_nñ = 0;

   У першому  випадку для будь-якого елемента а є М маємо А(х)ê_á а,а_{1, ....,}а_nñ = 0. Звідси за означенням ($ х) Ā(х)ê_á а_{1, ....,}а_nñ = 0. З іншого боку, в цьому випадку  (" х) А(х)ê_á а_{1, ....,}а_nñ = 1. Звідси (" х) А(х)ê_á а_{1, ....,}а_nñ = 0.

   У другому  випадку для елемента а₀  є М маємо Ā(х)ê_á а₀,а_{1, ....,}а_nñ =1. Звідси ($ х) Ā(х)ê_á а_{1, ....,}а_nñ =1. З іншого боку, в цьому випадку (" х) А(х)ê_á а_{1, ....,}а_nñ = 0. Звідси (" х) А(х)ê_á а_{1, ....,}а_nñ = 1. Рівносильність (2) доведено.

    Доведемо  тепер рівносильність (3). Застосуємо рівносильність () до формули Ā^х. Тоді (" х) Ā(х) º  ($ х) Ā(х) º  ($ х) А(х). Застосувавши рівносильність 11 основних рівносильностей логіки висловлень, дістанемо: ($ х) А(х)º (" х) Ā(х) º (" х) Ā(х). 

       

2. Винесення квантора за дужки.

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

($ х)( А(х)& В) º ($ х) А(х)& В;                                   

(" х)( А(х)& В) º (" х) А(х)& В;

($ х)( А(х)Ú В) º ($ х) А(х)Ú В;                                   

(" х)( А(х)Ú В) º (" х) А(х)Ú В;

    Доведемо  першу з цих  рівностей (інші доводяться аналогічно).

 

      Нехай, х_і,1 ,...,х_і,n   - усі вільні змінні формули ($ х)( А(х)& В). Тоді вони ж будуть усіма  вільними змінними формули ($ х) А(х)& В.

      Розглянемо  довільну інтерпретацію з множиною М. Нехай, áа₁, ..., а_nñ, а_і є М – довільний набір значень вільних змінних х_і,1 ,...,х_і,n . Оскільки формула В не  містить вільної змінної х, можна визначити значення цієї формули в наборі áа₁, ..., а_nñ (точніше, в його частині, що стосується вільних змінних формули В). Якщо  Вê_á а_{1, ....,}а_nñ = 0 , то (($ х) А(х)& В) _á а_{1, ....,}а_nñ = 0 і для будь-якого елемента а з множини М у наборі значень áа₁, ..., а_nñ своїх вільних змінних х, х_і,1 ,...,х_і,n формула  А(х)& В  набуває значень 0. Звідси  ($ х) А(х)& В½_á а_{1, ....,}а_nñ = 0. Якщо   Вê_< а_{1, ....,}а_{n >} =1 , то для будь-якого елемента а з множини М у наборі значень áа, а₁, ..., а_nñ формули А(х)& В й А(х) набувають однакових істинностей. Звідси,  (($ х) А(х)& В)½_á а_{1, ....,}а_nñ = ($ х) А(х)½ _á а_{1, ....,}а_nñ = ($ х) А(х)& В½_á а_{1, ....,}а_n.

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

      (" х) (А(х)) & В(х) º (" х) А(х) & (" х) В(х);

      ($ х) (А(х) Ú В(х)) º ($ х) А(х) Ú ($ х) В(х). 

       

3. Переставлення однойменних кванторів.

        Для кванторів $ та" маємо

(" у) (" х) А(х, у) º  (" х) (" у) А(х, у);

($ у) ($ х) А(х, у) º  ($ х) ($ у) А(х, у). 

       

4. Перейменування  зв’язаних змінних.

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

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

      Розглянемо  спосіб спрощення формул, що спирається на зведені рівносильності. Під довжиною формули тут і далі розумітимемо загальне число символів предикатів, логічних символів та символів кванторів, які входять до неї. Так, формула (" х₁) А₁⁽²⁾ (х₁, х₂) & ($ х₃) А₂⁽¹⁾(х₃) має довжину 5.

      Формули, в яких із логічних символів застосовуються тільки символи &, Ú, ¯ ,  причому символ ¯ зустрічається лише перед символами предикатів, будемо називати зведеними. 

      Приклад.

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

1. А₁⁽¹⁾ (х₁) Ú А₂⁽²⁾ (х₁, х₂).
2. (" х₁)  А₁⁽¹⁾ (х₁) & ($ х₂) Ā₂⁽²⁾(х₂, х₃).

3. (" х) А₁⁽¹⁾ (х₁) ® ($ х₂) Ā₁⁽¹⁾(х₂).

 Лише  перші дві формули є зведеними. 

Теорема1.

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

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

     Користуючись  рівносильностями логіки висловлень, легко вказати формулу, рівносильну  заданій, що містить із логічних символів тільки &, Ú, ¯. Тому будемо вважати, що формули, які розглядаються, містять тільки ці логічні символи.

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

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

     Формула F має вигляд: або .

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