Исчисление предикатов с равенством




Скачать 85.79 Kb.
НазваниеИсчисление предикатов с равенством
страница1/2
Дата публикации08.05.2013
Размер85.79 Kb.
ТипДокументы
vbibl.ru > Математика > Документы
  1   2
Исчисление предикатов с равенством

  1. Алфавит

    1. — предметные переменные,

    2. — предметные константы,

    3. — предикатные символы,

    4. — функциональные символы,

    5. — логические связки,

    6. — символы кванторов,

    7. — вспомогательные символы.

  2. Выражения

    1. Термами называются:

      1. любая предметная переменная или предметная константа,

      2. если — термы, и — некоторый функциональный символ, то — тоже терм.

      3. других нет.

    2. Формулами являются (элементарные (атомарные) — первая два вида):

      1. если — предикатная буква, а — термы, то — формула,

      2. если и — термы, то — формула,

      3. если и формулы, то — тоже формулы.


Совокупность I и II — язык ИПР.
Замечание. В формулах подформула называется областью действия квантора соответственно.
Определение. Вхождение x в формулу A называется связным, если оно находится в области действия какого-либо квантора или . В противном случае — свободным вхождением.

Определение. Терм t называется свободным для x в формуле A, если никакое свободное вхождение x в формулу A не находится в области действия никакого квантора или , где y входит в терм t.
Пример (спорный пример, предлагаю не использовать)


Теорема 26. Верно:

  1. Терм, не содержащий переменных, свободен для любой переменной в любой формуле.

  2. Терм x свободен для x в любой формуле.

  3. Если формула A не содержит свободных вхождений x, то любой терм свободен для x в данной формуле1.


Определение. Обозначим и назовем «сигнатурой».
Пусть A — предметная область (то, откуда берутся значения для переменных?), тогда пара называется алгебраической системой.
Примеры


Пусть t — терм сигнатуры и . Пусть — алгебраическая система сигнатуры .
Определение. Значение терма при определим по индукции:

  1. если , то ,

  2. если и , то .


Пример

при


Определение. Формула сигнатуры называется истинной на элементах в алгебраической системе (обозначение ), если:

1) — множество термов сигнатуры , то когда значения термов совпадают на элементах .

2) если — предикатный символ из , и термы , то ,

3) ,

4) ,

5) ,

6) ,

7) ,

8) .
Определение. Формула A сигнатуры называется выполнимой, если существует такая алгебраическая система , что ^ A истинна при некоторых значениях свободных переменных.
Определение. Формула A тождественно истинна, если она в любой алгебраической системе той же сигнатуры истинна при любых значениях свободных переменных.
Определение. Говорят, что формула семантически следует из множества формул ^ Г, если для любой алгебраической системы из истинности всех формул Г при некотором значении свободных переменных всех формул из Г следует истинность формулы A при тех же значениях свободных переменных из A (обозначение: ).
Определение. Если и , то говорят, что A равносильно B (обозначение: ).
Теорема 27. .
Теорема 28. Верно:

1) .

А также, если B не содержит свободных вхождений x, то верно:


Теорема 29. Верно:

1) ,

2) .
Теорема 30. Пусть y не входит в A(x). A(y) получается из A(x) заменой всех свободных вхождений x на y. Тогда:


Теорема 31. Верно:


^ Теорема 32 «О замене».

Пусть A — формула, B — подформула в ней, — результат замены некоторого вхождения B в формуле A на , тогда, если , то .
Определение. Формула вида , где , а кванторов не содержит, а , называется предваренной нормальной формой (ПНФ).
Теорема 33. Всякая формула ИПР равносильна некоторой ПНФ.
Формальное исчисление предикатов с равенством

  1. Алфавит

    1. — предметные переменные,

    2. — предметные константы,

    3. — функциональные символы,

    4. — предикатные символы,

    1. — логические символы,

    2. — вспомогательные символы.

  1. Выражения

    1. Термами являются:

      1. любая предметная переменная или константа,

      2. если — термы, то и — тоже термы,

      3. других нет.

    2. Формулами являются:

  1   2

Добавить документ в свой блог или на сайт

Похожие:

Исчисление предикатов с равенством icon2 Логика предикатов первого порядка
Данная курсовая работа является практическим примером применения онтологического инжиниринга для разработки сложной системы

Исчисление предикатов с равенством icon"Утверждаю" Проректор мгу профессор П. В. Вржещ
Интегральные уравнения и вариационное исчисление мл науч сотруд Колыбасова В. В. 5-49 физфак

Исчисление предикатов с равенством iconПискунов Н. С. Дифференциальное и интегральное исчисление для втузов....
Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования

Исчисление предикатов с равенством iconИсточники информации и методы анализа динамики цен внешней торговли....
Основные понятия статистики внешнеэкономической деятельности

Исчисление предикатов с равенством iconСтруктура программы на Турбо-прологе. Объекты данных Пролога. Сопоставление
Логическое программирование один из подходов к информатике, при котором в качестве языка высокого уровня используется логика предикатов...

Исчисление предикатов с равенством iconЛогико-вероятностное исчисление Рябинина и управление риском и эффективностью в экономике
В течение 10 лет нами выполнялись разработки и исследования по созданию информационной технологии и Software для управления риском...

Исчисление предикатов с равенством iconПротив гностиков. (Против тех, кто утверждает, будто творец мира зол и мир плох)
Когда мы говорим “единое” и когда мы говорим “благо”, мы должны иметь в виду одну и ту же природу и высказывать только одно, не прибавляя...

Исчисление предикатов с равенством icon"протохристианство" («Тисса» 5760)
Недельное чтение "Тисса" начинается словами: "И сказал Господь Моше так: Когда будешь делать поголовное исчисление сынов Израилевых...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница