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

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

Читайте также:
  1. Исчисление
  2. Исчисление и декларирование там платежей.
  3. Исчисление и последствия несоблюдения процессуальных сроков
  4. Исчисление процессуальных сроков
  5. Исчисление средней гармонической
  6. Микроуровень влючает определение налоговой нагрузки на ХС и исчисление налоговой нагрузки на работника.

Исчисление предикатов называют еще теорий первого порядка.

В исчислении предикатов, так же как и в исчислении высказываний, на первом по важности месте стоит проблема разрешимости.

Но в исчислении высказываний проблема разрешимости состояла в решении вопроса является ли данная сложная функция тождественно истинной, выполнимой или тождественно ложной.

Теперь же вопрос следует поставить иначе. Принимает ли данная функция значение 1 при:

а) любых предметных переменных и любых предикатах,

б) на некотором множестве предметных переменных и любых предикатах,

в) при некоторых значениях предметных переменных и любых предикатах,

г) является ли она тождественно ложной, т.е. невыполнимой?

Таким образом, в логике предикатов, в отличие от логики высказываний, нет эффективного способа для распознавания общезначимости функций.

Поэтому в исчислении предикатов указывается некоторая совокупность формул, которые называются аксиомами и составляют аксиоматическую теорию, и указывается конечное множество отношений между формулами, составляющее правила вывода.

Аксиоматическая теория и правила вывода и составляют исчисления предикатов.

Символами исчисления предикатов или алфавитом исчисления предикатов являются символы предметных переменных, символы предикатов, логические символы (отрицание и импликация), символы кванторов, а также скобки и запятая.

Сформулируем аксиомы исчисления предикатов и правила вывода исчисления предикатов.

Аксиомы исчисления предиката.

Пусть A, B и C - любые формулы.

Аксиома 1. A → (B→C).

Аксиома 2. (A → (B→C)) →((A → B) (A→C)).

Аксиома 3. (неB→неA) →((неB → A)→ B).

Аксиома 4. ( хi) A(хi) → A(хj), где формула A(хi) не содержит переменной хj.

Аксиома 5. A(хi) → ( хj) A(хj), где формула A(хi) не содержит переменной хj.

Правила вывода исчисления предикатов.

(1) Пусть (А(х) → В) и В не содержит переменной х, тогда

((( x)A(x) → В)

Это правило связывания квантором существования.

(2) Пусть В → А(х) и В не содержит переменной х, тогда

(В → (( x)A(x)))

Это правило связывания квантором общности.

(3) Связанную переменную формулы В можно заменить другой переменной, не являющейся свободной в В. Это правило переименования связанной переменной.

 

Контрольные вопросы

1. Что называется предикатом? Приведите примеры предикатов.

2. Какой предикат называется разрешимым, тождественно истинным. Тождественно ложным?

3. Перечислите операции, которые можно осуществить над предикатами. Как применяются предикаты в алгебре? Что такое множество истинности предиката?

4. Из чего состоит алфавит логики предикатов? Что такое квантор?

5. Что называется формулой логики предикатов?

6. Сформулируйте основные правила построения формул.

7. В чем состоит смысл термина «интерпретация» в логике предикатов?



8. Сформулируйте основные правила перехода к новым равносильным формулам.

9. Какая формула называется непротиворечивой, противоречивой, общезначимой?

10. Какая формула называется приведенной? Что такое приведенная форма?

11. Какая формула называется нормальной формой? Сформулируйте алгоритм приведения формулы к нормальной форме.

12. Что называют исчислением предикатов?

13. Сформулируйте аксиомы исчисления предикатов.

 


Дата добавления: 2015-07-07; просмотров: 181 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
W(х1, х2, ..., хп); U(х,у),....| Тонкинская

mybiblioteka.su - 2015-2021 год. (0.006 сек.)