Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Формалізоване числення предикатів

Читайте также:
  1. Алгоритми переведення чисел з однієї позиційної системи числення в іншу
  2. Загальні поняття про системи числення.
  3. Класифікація предикатів.
  4. Класифікація формул логіки предикатів
  5. Наведемо приклади переводу чисел з однієї системи числення до іншої.
  6. Платники, об’єкт оподаткування, ставки та порядок обчислення акцизного податку та мита.
  7. Позиційні системи числення
  8. Порядок обчислення та строки сплати податку на прибуток.
  9. Рівносильність і наслідок предикатів
  10. Усні обчислення

Лекція 14

 

План

1. Формалізоване числення предикатів.

2. Теорія формального виводу.

Формалізоване числення предикатів

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

Задамо мову числення предикатів.

Алфавіт числення предикатів складається із предметних змінних х 1, х 2, …, предметних констант с 1, с 2, …, (символів виділених елементів), предметних букв Р1, Р2, …, Рk , …, функціональних змінних f ′′1, f ′2, …, f ′l , …, а також знаків логічних зв’язок Ø і Ù, кванторів " і $ та дужок (,). При цьому верхні індекси предикатних і функціональних букв визначають число аргументів відповідно предиката чи функції, які можуть бути підставленими замість цих букв.

Поняття формули визначається двома етапами. Спочатку визначаються терми. Ними є окремо взяті предметні змінні й константи, а також вирази вигляду f n (t 1, …, tn), де f n - n -місний функціональний символ; t 1, …, tn) - терми.

Наведемо означення формули:

а) якщо Рn - предикатна буква, t 1, …, tn - терми, то Рn (t 1, …, tn), - формула; при цьому всі входження змінних в цю формулу називаються вільними;

б) якщо F 1, F 2 - формули, то формулами є Ø F 1, (F 1 ® F 2 ); причому всі входження змінних, вільних в F 1, F 2 є вільними і в формулах указаних видів; крім того, можна вважати, що в F 1 і F 2 немає предметних змінних, які зв’язані в одній формулі і вільні в іншій;

в) якщо F (х) - формула, яка містить вільне входження змінної х, то " хF (х) і $ хF (х) - формули; при цьому входження змінної х в них називається зв’язаним; входження ж всіх інших предметних змінних в ці формули залишаються вільними (зв’язаними), якщо вони були вільними (зв’язаними) у формулі F (х) (формула F (х) називається областю дії квантора);

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

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

Сукупність G = { с 1, с 2, …; f 1, f 2, …; Р 1, Р 2, …, } називається сигнатурою числення предикатів. Якщо в сигнатурі відсутні функціональні символи (а отже, і функціональні терми) то таке числення предикатів називається чистим численням предикатів. Воно будується для довільної предметної області й не залежить від взаємозв’язків між предметами в цій області. Це чисто логічна теорія. Якщо ж такі зв’язки є і вони описуються функціями на цій предметній області, то виникає логічна теорія відповідної математичної дисципліни, або, як говорять, деяка формальна математична теорія.

Система аксіом числення предикатів. Дана система складається із двох груп із яких перша - це аксіоми формалізованого числення висловлень:

 

(Al): ;

(A2): ;

(A3): ,

 

де під F, G, H розуміються довільні формули числення предикатів.

Друга група аксіом - це власне предикатні аксіоми (схеми аксіом), тобто аксіоми з кванторами. Виберемо в їх значенні так звані аксіоми Бернайса:

 

(РА1): ;

(РА2): ,

 

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

Суттєвість останньої вимоги можна пояснити наступним прикладом. Розглянемо в значенні формули F (x) формулу $ у Р (х, у), де ця вимога порушена: вільне входження х знаходиться в області дії квантора $ у. Підставивши цю формулу в аксіому (РА1), одержимо формулу " х $ уР (х, у) ® $ уР (у, у), яка не є загальнозначущою. Дійсно, предикат А (х, у): х < у на множині дійсних чисел перетворює її в хибне висловлення: " х $ уР (х < у) ®$ уР (у < у).

 

Правила виводу. До правила виводу МР числення висловлень додаються ще два правила:

 

-правило, або правило узагальнення: ;

-правило, або правило конкретизації:

за умови, що G (x) містить вільне входження х, a F не містить.

Остання вимога також є суттєвою. Його порушення може привести до хибних висновків із істинних посилок.

 




Дата добавления: 2015-04-11; просмотров: 29 | Поможем написать вашу работу | Нарушение авторских прав

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | <== 13 ==> |


lektsii.net - Лекции.Нет - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав