Кванторные операции над предикатами

1) Пусть Р(х) – одноместный предикат, заданный на М. Операция связывания квантор общности предиката Р состоит в получении высказывания, которое по определению истинно, если Р(х) тождественно истинен на М, и ложно иначе. Это новое высказывание обозначим хР(х) («для любого хР(х)»,  - «квантор общности»).

 

хР(х) = истина, если Р(х) тождественно истинен на М;

ложь, если Р(х) опровержим.

Пример 1. М ≡ R; Р(х): «х²>0» (опровержим), хР(х) =ложь.

Операция связывания на М предиката Р(х) квантором существования называется операцией получения высказывания хР(х) («существует хР(х)»), которая определяется следующим образом:

хР(х) = истина, если Р(х) выполним на М;

ложь, если Р(х) тождественная ложь.

Переменная х здесь также называется связанной. В примере 1 хР(х)=истина (т.к. Р(х) выполнимо на М).

 

2) Пусть теперь Р(х) – одноместный предикат Р(х)=Р(x_1,x₂,…,x_n) по определению операция связывания квантором общности по переменной х есть операция перехода к (n-1)-местному предикату Р*(x_1,x₂,…,x_n), который при каждом фиксированном наборе переменных (x_1,x₂,…,x_n) принимает следующие значения: истина, если Р при выьранном наборе переменных тождественно истинен как предикат х₁ (на данной предметной области), иначе – ложь.

Обозначения: х₁Р(x_1,x₂,…,x_n).

Операция связывания квантора существования приводит к (n-1)-местному предикату, х₁Р(x_1,x₂,…,x_n), который при всяком фиксированном наборе переменных (x_1,x₂,…,x_n) принимает значение истины, если Р выполним как предикат от х₁ на данной предметной области и значение лжи иначе.

Проясним эти определения на частном случае применения предиката Р(х, у):

P*(y)= xP(x, y)= истина, если Р(х, у) выполним как предикат от х;

ложь иначе.

Аналогично вводится хР(х).

В общем случае в данных выше определениях переменная x₁ называется связанной, а остальные свободными.

Пример. Р(х, у): «х≥у» на N. Рассмотрим предикат хР(х)=истина. у=1 – при таком у Р тождественно истинен. Возьмем любое другое значении у, тогда может найтись х, который меньше у, т.е. Р становится опровержимым как предикат от х.

 

3) После того, как произошло связывание предиката по какой-либо переменной, остальные переменные остаются свободными и тогда можно производить повторное связывание квантором любого из них. Пусть, например, имеется предикат Р*(x_2,x₃,…,x_n)=х₁Р(x_1,x₂,…,x_n). Теперь можно ввести, например, связывание по х₃ предикатом, который определяется как х₁Р(x_1,x₂,…,x_n)=х₃Р*(x_2,x₃,…,x_n) и т.п.

 

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

1) Алфавит состоит из объединения множеств следующих символов:

а) Символы предикатных переменных (х, у, …, x_1, x₂, …, x_n …);

б) Символы 0-местных предикатных переменных P, Q, …

в) Символы n-местных предикатных переменных P, Q, …

г) Символы логических операций ┐, /\, \/, →, ↔;

д) Символы кванторных операций , .

2) Формулы:

а) По определению 0-местныя предикатная переменная (формула);

б) Результат подстановки на свободные места различных предметных переменных в n-местную предикатную переменную, т.е. Р(x_1,x₂,…,x_n) есть формула, все указанные предметные переменные в этой формуле называются свободными.

в) Если переменная x_j в формуле Р(x_1,x₂,…,x_n) свободна, тох_jР(x_1,x₂, x_j,…,x_n) – формула. Все переменные, которые были свободны в формуле Р кроме х_j остаются в полученной формуле свободными, а переменная х_j теперь называется связанной.

Могло быть так, что в формуле Р до применения связываний по х_j уже были связанные переменные. Они остаются связанными и в полученной формуле.

г) Если Р – формула, то ┐Р – также формула, причем все переменные, которые были свободны, остаются такими же в полученных формулах.

д) Если P и Q формулы, то P/\Q, P\/Q также формулы. При этом те предметные переменные, которые были свободны в P и Q, остаются такими же в полученных формулах.

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

3) Интерпретация формул.

Рассмотрим теперь конкретное множество М значений предметной переменной х=(x_1,x₂,…,x_n) и формулу F, которая на М определяется только для указанных х. Если на место каждой предикатной переменной, участвующей в F, записать конкретный предикат (в нем столько же мест, сколько переменных), то получим конкретный предикат на М. Если теперь выбрать и зафиксировать х, то предикат превратится в высказывание. Это и называется интерпретацией формулы F.

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

Классификация формул.

1) Формула называется тождественно истинной на М, если всякая ее интерпретация есть истина, иначе она опровержима.

2) Формула тождественно ложна на М, если всякая ее интерпретация является ложью.

3) Формула является тавтологией, если она тождественно истинна на каждой предикатной области М.

4) Формула является противоречием, если она будет тождественной ложью на каждой предметной области М.

1) Пусть дана предметная область М, формулы F и G на М. Говорят, что на М формулы F и G равносильны и записывают F ≡ G (на М), если при подстановке в формулы F и G на место предикатных переменных конкретных предикатов, получаются всякий раз равносильные на М предикаты. Другими словами, соответствующие интерпретации формул F и G на каждом элементе из М совпадают.

 

2) Говорят, что F и G равносильны, если они равносильны на всякой предметной области М и записывают F ≡ G.

 

3) Теорема. F ≡ G тогда и только тогда, когда эквиваленция F↔G является тавтологией.

Доказательство очевидно. Тавтология означает, что всегда интерпретация формул F и G является истинным высказыванием или ложным высказыванием одновременно, но тогда их интерпретации совпадают, что равносильно F ≡ G. Эта теорема дает нам готовый набор равносильных формул, если воспользоваться уже доказанными тавтологиями.

Пример. (x(Р(х) \/В))≡((x(Р(х) \/В), где В – предикатная переменная, либо 0-местная, либо с произвольным количеством мест, но среди свободных в ней переменных не должен содержаться х.

 

4) Очевидно, что соотношение равносильности обладает свойствами рефлексивности, симметричности и транзитивности (следует из определения).

 

5) Равносильными называются такие преобразования формулы F, которые приводят к формуле, равносильной F. В силу транзитивности соотношения равносильности, мы можем выполнить цепочку равносильных преобразований, получая всякий раз формулу, равносильную предыдущей. В итоге исходная и заключительная формулы оказываются равносильными.