що досягла певного віку. p> Рівність x = O (y), означає В«Батьком y є xВ». p> Зауважимо, що функції можуть формулюватися у вигляді відносин і в цьому сенсі введення функціональних символів може бути надмірною, але в тому випадку, коли область визначення неперервна, замінити функцію ставленням вельми проблематично, тоді все одно доводиться задавати відношення з використанням функції приналежності. У дискретному випадку функції виправдовуються тим, що вони допомагають істотно спростити запис вираження. br/>
Алфавіт ІП
Словник ІП містить:
Константи - a, b, c
Змінні - х, y, z
Функціональні - f, g, h
предикатні-P, Q, R
Висловлювання - p, q, r
Пропозіціональние зв'язки -
Квантори спільності -.
Розглянемо поняття формули - спочатку введемо поняття терма по індукції:
Предметні константи і змінні - це терми
Якщо t1 ... tn - це терми, і f - n-місна функція, то f (t1 ... tn) - теж терм, інших немає.
Атомарна формула - це предикат, в який підставлені терми A (t1 ... tn).
Якщо С і B - формули, то - формули, інших немає, решта виражаються через них. У формулі змінна може бути вільною (стоїть поза області квантора) або зв'язковою (в області дії квантора). Формула, яка не містить вільних змінних, називається пропозицією. p> Приклад: нехай маємо формулу. У першому випадку зв'язкова, у другому вільна. p> Висловлювання можна сприймати як 0-арний предикат. p> Позначення с - Сократ, H - В«бути людиноюВ», M - В«бути смертнимВ».
В
навішування квантора загальності предикату ми фактично зіставляємо k-арний предикат який правдивий тоді і тільки тоді, коли правдивий вихідний предикат з цими значеннями і будь-яким значенням x0.
За аналогією навішуванням квантора існування та (к +1) - арного предиката Р (х0, ..., хк) отримуємо к-арний предикат. Сущ. х0 Р (х0, х1, ..., хк) - цей предикат правдивий тоді і тільки тоді, коли початковий предикат для тих же значень змінних правдивий хоча б на 1 з можливих значень х0.
Поняття підстановки в ЛП
Згідно з визначенням терма, безліч всіх термів T (F) містить так само безліч змінних Х. Підстановкою називається відображення v: X-> T (F) таке що для всіх х прин. Х за винятком деякого підмножини з Х має місце v (x) = x, тобто в тому випадку коли х потрапляє в це кінцеве рахункове безліч Х вона замінюється деяким, зазначеним для неї термом, в іншому випадку - залишається собою. F - безліч функцій, застосовуваних теорією. T - безліч термів теорії з урахуванням безлічі функціональних символів F.
Розповсюдивши підстановку v до деякої функції v : T (F) -> T (F) думаємо:
1) Якщо те
) Якщо t - символ константи, то
) Якщо для деякої n-арної операції F, то
Терм називається результатом підстановки v до терму t. p> Приклад: нехай у нас присутні 3 змінні. Будемо розглядати функції властиві теорії множин, тобто
,
Введемо підстановку:
В
Тоді:
В
Підстановку часто записують у вигляді пар {xi = ti}
Нехай задані 2 терма s і t. І треба знайти підстановку, що робить їх рівними. Підстановка v називається уніфікатором s і t якщо. p> уніфікатор називається найбільшим спільним уніфікатором s і t і позначається mgu (s, t) = v. Якщо для будь-якого іншого уніфікатора w тих же самих термів s і t існує така підстановка, що композиція. Композицію можна розглядати як суперпозицію. Якщо для термів існує хоча б 1 уніфікатор, то серед уніфікаторів існує найбільший спільний. p> При проведенні підстановок потрібно слідувати правилам:
1) Підстановки застосовуються тільки для вільних змінних (у тому числі і функціональних), у всіх місцях їхнього входження в дану форму.
2) Змінну можна замінити константою, але не навпаки.
3) Не слід замінювати змінні містять ту ж саму змінну тобто - Неправильна. (Один пункт пропустив)
) Одна функція не може підставлятися замість іншої але може
) Не можна замість вільної змінної запровадити вже пов'язану, інакше вводиться підстановка входження змінної не повинно потрапляти в область дії квантора, який зв'язує дану змінну, а якщо ми замінюємо вільну змінну, то робимо це для всіх її входжень. p align="justify"> A (x: = t) - отримуємо з формули А заміною x на t.
Поняття інтерпретації в ЛП. Здійснимість, общезначімость, нездійсненність і суперечливість формул
Інтерпретації.
Говоримо, що задана інтерпретаціяI для формули або безліч формул I, якщо задано не порож...
