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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

х ( Р ( х ) Q ) = х Р ( х ) 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. Для будь-якого елемента а М Р( х )= І на наборі ( а , a , a ,..., а ).

2. Для деякого елемента а М Р ( х ) = Х на наборі ( а , a , a ,..., а ).

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

( a , , a ,..., а ) .

У другому випадку для елемента а М маємо

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