1.2. Класифікація формул логіки предикатів. Логічне слідування

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

Термом називається:

1. будь-яка предметна змінна або константа;

2) якщо - n-місний функціональний символ, а – терми, то - терм ;

3. ніяких інших, крім утворених за 1) та 2), термів немає.

Наприклад, нехай - 2-місний функціональний символ "сума(х,y)", а - 2-місний функціональний символ "степінь (x,y)", задані на множині натуральних чисел, тоді вирази (5,x), (3,y), ( (x,2),3), ( (х_,у)_,3) є термами, які за допомогою алгебраїчних символів можна було б відповідно записати "5+x", " ", " +3", " ". Припідстановці замість змінних конкретних значень терм не перетворюється на висловлення, на відміну від формули.

Формулою називається:

1) якщо -n-місний предикатний символ, а — терми, то, ( ₎- елементарна формула логіки предикатів;

1. якщо А і В- формули логіки предикатів, то слова також є формулами логіки предикатів;

2. якщо А- формула, а х- вільна змінна вА, то і також формули логіки предикатів;

3. всі інші слова, крім тих, що утворені за правилами пунктів 1 - 3 не є формулами логіки предикатів.

Як і валгебрі висловлень, деякі дужки можна опускати, пам’ятаючи про порядок виконання операцій. Якщо в області дії квантора знаходиться елементарна формула, дужки можна не писати. Формула називається замкнутою, якщо вона не має вільних входжень змінних, і відкритою, якщо є вільні змінні. Наприклад, — відкрита формула, бо є вільні входження змінної у. Якщо змінна зв’язана, в області дії квантора її можна перейменувати, при цьому всі її вільні входження залишаються без зміни. [2, ст 26]

Процес перетворення формули на висловлення і саме це висловленняназивають інтерпретацією формули логіки предикатів. Щоб побудувати інтерпретацію, потрібно:

1. Вибрати область інтерпретації М;

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

3. Якщо формула замкнута, то при підстановці заданих предикатів вона вже перетвориться на висловлення, якщо відкрита - на предикат. Щоб цей предикат перетворити на висловлення, потрібно замість вільних змінних підставити предметні константи з області М.

Одна і та ж формула в різних інтерпретаціях або в одній інтерпретації при різних заміщеннях вільних змінних константами може перетворюватися як в істинне, так і в хибне висловлення. Наприклад, замкнута формула перетворюється в істинне висловлення "Для довільного натурального числа існує число, більше за нього", якщо на множині натуральних чисел задати предикат і в хибне мисловлення "Кожен чоловік має сина", якщо на множині всіх чоловіків задати предикат Р(х,у)- "х батько у".

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

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

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

Формула логіки предикатів може бути:

• логічно загальнозначущою (тавтологією), якщо вона істинна в будь- якій інтерпретації;

• суперечністю (тотожно хибною), якщо вона хибна в будь-якій інтерпретації;

• виконуваною, якщо вона виконувана хоча б в одній інтерпретації;

• спростовною, якщо вона спростовна хоча б в одній інтерпретації. Якщо формулаА тавтологія логіки предикатів, то це записують ⊨А.

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

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

Формула В є логічним наслідком формули А (А⊨В), якщо вона перетворюється в істинне висловлення на будь-якому наборі елементів з області довільної інтерпретації, на якому А перетворюється в істинне висловлення.

Можна довести, що А⊨В тоді і тільки тоді, коли ⊨ .Із тавтологій, що містять імплікацію (доведення далі), можна отримати деякі важливі схеми логічного слідування. Наприклад, ⊨ — правило універсальної конкретизації; ⊨ — правило екзистенціального узагальнення. [1, cт.18]

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

Найбільш часто вживані схеми логічного висновку - силогізми Арістотеля. Це схеми, що складаються з трьох простих висловлень типуА, E,I та O, з яких перші два - посилки, а третє - висновок. У кожному з силогізмів розглядаються три властивості (предикати) S, М та Р. Перша (велика) посилка пов’язує М і Р, друга (мала) пов’язує М і S, а висновок пов’язує S і Р. У залежності від положення М у посилках, розрізняють чотири фігури силогізму:

І II III IV

МхР, SyM⊨SzPРхМ, SyM⊨SzPМхР, MyS⊨SzPРхМ, MyS⊨SzP

Тут буквами х, у та z позначено одне з чотирьох висловлень типу А, Е, І чи

О, що пов’язує властивості S, М та Р. Отже, у кожній фігурі є 4 4∙4 = 64 модуси силогізму. Всього різних модусів силогізму 256. Арістотель встановив, що правильними з них є лише 19 (по 4 у І та II фігурах, 6 у III і 5 у IV фігурі). Силогізми позначають трьома літерами (ААА, ЕIO, АЕЕ і т.п.) за виглядом висловлень, які пов’язують властивості. Для полегшення запам’ятовування правильних силогізмів кожному присвоюють ім’я (Barbara, Ferio, Camestresі т.п.) - латинське слово, яке містить тільки ті голосні букви, що входять до позначення силогізму. Наприклад, Barbara це силогізм ААА першої фігури MAP, SAM⊨SAP, який можна прочитати «Всі М Р. Всі S М. Отже, всі S Р» або записати формулами логіки предикатів , . Прикладом такого судження може бути: «Всі ромби - паралелограми. Всі квадрати - ромби. Отже, всі квадрати — паралелограми».