Теми рефератів
> Реферати > Курсові роботи > Звіти з практики > Курсові проекти > Питання та відповіді > Ессе > Доклади > Учбові матеріали > Контрольні роботи > Методички > Лекції > Твори > Підручники > Статті Контакти
Реферати, твори, дипломи, практика » Лекции » Альтернативні системи аксіом

Реферат Альтернативні системи аксіом





нє безліч Р зване областю інтерпретації. Кожному символу зіставляється елемент з Р, кожному символу предиката зіставляється ставлення. Кожному символу функції р Реальний функція з безлічі G. Формула здійсненна, якщо є інтерпретація, в якій вона істина. p align="justify"> Визначення: Замиканням формул А з параметрами х1, х2, .., хn є формула види: для кожного х1, х2, .. хn А. Формула обчислення предикатів називається загальнозначущої, якщо її замикання істинно в будь інтерпретації. При перевірці загальної значущості формул важливо пам'ятати, що за її параметрами беруться квантори загальності. Наприклад, квадрат дійсного числа позитивний, але воно не загальнозначуще, тому що 0 в квадраті = 0, що не є позитивним числом. Загальнозначущим буде твердження квадрат будь-якого дійсного числа неотрицателен. Формула називається нездійсненним, якщо замикання її заперечення загальнозначуще. Формула здійсненна якщо не вірно, що вона нездійсненна. Загальзначимість формули - це узагальнення тавтології в ІВ. Можна сформулювати це твердження більш формально. Інтерпретація називається моделлю формул або безліччю формул, якщо на ній всі формули тотожно істини. Формули А і В еквівалентні, якщо кожна з них є логічним наслідком іншої. br/>

загальнозначуща тавтологію


Загальнозначущі формули - це узагальнення тавтологію в обчисленні висловлювань. Обчислення висловлювань дозволять виводити всі тавтології з деякого набору базисних тавтологію (названих аксіомами) за допомогою деяких правил виводу (насправді єдиного правила modusponens). p align="justify"> 1) Нехай A - тавтологія, x1,. . . , Xn - набір пропозіціональних змінних, які входять в A, а F1,. . . , Fn - формули ВП. Тоді формула A (F1, ..., Fn) общезначима.

2) Доведемо, що формула ? x ? y A (x, y)? ? y ? x A (x, y) общезначима.

Інтерпретацію бінарного предикатного символу зручно представляти у вигляді орієнтованого графа (бути може, нескінченного). Множествовершін графа збігається з областю інтерпретації, а впорядкована пара (x, y) належить множествуребер графа тоді і тільки тоді, коли пара (x, y) належить відношенню [A]. p align="justify"> При такому розумінні посилка написаної формули означає, що в графі є вершина x, з которойідут ребра в усі інші вершини. Але тоді длялюбой вершини графа знайдеться яке у неї ребро (воно виходить з вершини x). Саме це і утверждаетзаключеніе формули. br/>

Обчислення предикатів 1-го порядку


Кажуть, що задано числення предикатів першого порядку, коли:

) задано алфавіт:

Вѕ рахункового безлічі X символів змінних;

Вѕ рахункового безлічі P предикатних символів;

Вѕ рахункового безлічі F функціональних символів;

Вѕ символів пропозиційних зв'язок? і В¬

Вѕ кванторного символу ? (квантор загальності);

Вѕ службових символів: дужок закриває) і відкриває (, а також символу коми ,.

2) введено поняття формули;

) задані аксіоми числення висловів:


A? (B? A) (A1)

(A? (B? C))? ((A? B)? (A? C)) (A2)

(В¬ B? В¬ A)? ((В¬ B? A)? B) (A3)


і кванторниесхеми аксіом:


? xA? A (x: = t) в умовах (A4)

? x (A? B)? (A? ? xB) в умовах (A5)


) задані правила виведення:

Вѕ modus ponens:

якщо виведені формули A і A? B, то виведена формула B.

Вѕ правилом узагальнення (Gen):

якщо виведена формула A, то виведена формула ? xA .

загальнозначуща для кожного Хa Г  A (x: = t)

Теорема. Якщо терм t вільний для змінної x у формулі A, то формула


Назад | сторінка 7 з 11 | Наступна сторінка





Схожі реферати:

  • Реферат на тему: Формула Гріна
  • Реферат на тему: Інтерполяційна формула Гаусса
  • Реферат на тему: Наближене обчислення певного інтеграла за допомогою квадратурної формули Че ...
  • Реферат на тему: Чисельне інтегрування, формула Сімпсона
  • Реферат на тему: Розширена формула тотального успіху