double arrow

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


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

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

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

x0, y0, z0 предметные константы, т. е. значения предметных переменных.

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

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

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

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

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

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

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

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

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

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 выполняется в модели М.

 







Сейчас читают про: