Формулы алгебры предикатов и их классификация

В логике предикатов будем пользоваться следующей символикой:

1. Символы p, q, r, …- переменные высказывания, принимающие два значения: 1- истина, 0 – ложь.

2. Предметные переменные – x, y, z, …, которые пробегают значения из некоторого множества М;

x⁰, y⁰, z⁰ – предметные константы, т. е. значения предметных переменных.

3. P(·), Q(·), F(·), … - одноместные предикатные переменные;

Q(·,·,…,·), R(·,·, …,·) – n-местные предикатные переменные.

P⁰(·), Q⁰(·,·, …,·) – символы постоянных предикатов.

4. Символы логических операций:

5. Символы кванторных операций:

6. Вспомогательные символы: скобки, запятые.

Определение формулы логики предикатов.

1. Каждое высказывание как переменное, так и постоянное, является формулой (элементарной).

2. Если F(·,·, …,·) – n-местная предикатная переменная или постоянный предикат, а x₁, x₂,…, x_n– предметные переменные или предметные постоянные (не обязательно все различные), то F(x₁, x₂,…, x_n) есть формула. Такая формула называется элементарной, в ней предметные переменные являются свободными, не связанными кванторами.

3. Если А и В – формулы, причем, такие, что одна и та же предметная переменная не является в одной из них связанной, а в другой – свободной, то слова есть формулы. В этих формулах те переменные, которые в исходных формулах были свободны, являются свободными, а те, которые были связанными, являются связанными.

4. Если А – формула, то – формула, и характер предметных переменных при переходе от формулы А к формуле не меняется.

5. Если А(х) – формула, в которую предметная переменная х входит свободно, то слова являются формулами, причем, предметная переменная входит в них связанно.

6. Всякое слово, отличное от тех, которые названы формулами в пунктах 1 – 5, не является формулой.

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

Опр. Интерпретацией формулы алгебры предикатов называется совокупность, состоящая из не пустых множеств М1,М2,…..Мn, на которых принимают значения предметные переменные, значений предикатных переменных P0,Q0,…… входящих в данную формулу.

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

Опр.   Формула называется тождественно ложной- если в любой интерпретации она обращается в ложное высказывание или в тождественно ложный предикат.

Опр.   Формула называется выполнимой, если существует интерпретация, в которой она обращается в истинное высказывание или в выполнимый предикат.

Опр.  Формула называется опровержимой, если существует интерпретация, в которой она обращается в ложное высказывание или в выполнимый предикат.

Приведённые формы формул алгебры предикатов.

Опр. Приведённой формой формулы называется такая формула, равносильная исходной, которая содержит только логические связки дизъюнкции, конъюнкции и отрицания, причём отрицание относится только к предикатными переменным.

 

Предварённая нормальная форма формул алгебры предикатов.

Опр. Предварённой нормальной формой называется такая формула, в которой кванторы находятся в начале формулы и их область действия совпадает со всей формулой.

Теорема:

Для любой формулы логики предикатов существует равносильная ей предварённая нормальная форма.

Логическое следование формул логики предикатов.

Опр. Формула G называется логическим следствием формулы F, если в любой интерпретации, в которой F обращается в тождественно истинный предикат формула G также обращается в тождественно истинный предикат.

 

Проблема разрешения.

В алгебре высказываний эта проблема разрешается положительно,т.е. существует алгоритм, устанавливающий выполнимость формулы, этим алгоритмом является таблица истинности.

В 1936 г. Американский математик А. Чёрч доказал, что не существует алгоритма, разрешающего установить алгебру предикатов.

Для частных видов формул проблема решается полностью.

Вид

1. Формулы, заданные на нечётных множествах.

Пусть М={a1,a2,….an}- множество, заданное на конечном числе.

Для F- формула на M возможны два варианта:

а) либо формула F не содержит кванторов F(x1,……xm)

б) либо формула F содержит кванторы.

2. в первом случае как решается проблема:

Путём непосредственной подстановки в формулу значений предметных переменных.

Каждая переменная может принимать n значений.

Всего n*m наборов.

Теорема:

Если формула выполнима на каком либо множестве, то она выполнима на любом множестве с большим числом элементов.

 

 

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

Алфавит исчисления предикатов состоит из символов трех категорий:

3. Символы первой категории: Эти символы будем называть переменными высказываниями.

2. Символы второй категории: они носят общее название логических связок. Первый из них – знак дизъюнкции или логического сложения, второй – знак конъюнкции или логического умножения, третий – знак импликации или логического следования и четвертый – знак отрицания.

3. Третью категорию составляет пара символов (), называемая скобками.

Других символов исчисление предикатов не имеет.

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

Ф исчисление предикатов – независимая, полная, непротиворечивая, но разрешимой она не будет.

Опр. Термом исчисления предикатов называется:

1) Отдельно взятые предметные переменные.

2) Если t1,t2,…tn термы, то f(t1,t2,…tn) терм, где f функциональный символ.

Опр. Формулой исчисления предикатов называется

1) P(t1,t2,…tn), где ti- терм, Р- предметная буква.

2) Если F1,F2 формулы, то ⌐F1, (F1–›F2) формулы. Причём все переменные входящие в F1,F2 свободно, остаются свободными и в данных формулах.

Формулы, в которых все переменные кроме x входят свободно.

3) Других формул нет!

Замечание: Таким образом определённое исчисление предикатов называется исчислением первого порядка.

Опр. Сигнатурой исчисления предикатов называется следующая совокупность символов

∂={c1,c2,…….cn, b1^c1…….,p1^j1…pn^jn…}

Если сигнатура не содержит функциональных символов, то исчисление предикатов называется чистым исчислением предикатов.

Замечание:

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

Опр. Выводом (доказательством) формулы F из совокупности формул Г={Г1,Г2,…..,Гk} называется последовательность формул В1,В2,……Вn, в которых:

1. Последняя формула совпадает с выводимой формула Вn=F.

2. Каждая формула этой совокупности является либо аксиомой, либо одна из формул совокупности Г, либо получена из предыдущих с помощью правила вывода, если (Вi) первая из формул, содержащая свободно, то в дальнейших формулах не может быть применимо правило конкретизации, или обобщения по переменной x.

Опр. Интерпретацией формальной теории называется совокупность М, состоящая из множества предметов М<=M,m- арных операций на М P1^m,…..Pn^m.

Интерпретация называется моделью формул этой теории, если любая формула в данной интерпретации тождественно истинна.

Теорема: Если в модели М выполняются все формулы совокупности Ф и из совокупности формул Ф выводима F Ф|-F, то формула F выполняется в модели М.