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

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

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

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

3. Р(.). F(.) - одноместные предикатные переменные; Q( .........). R(.......) - n-местные предикатные переменные. P⁰(.). Q⁰( ...,.....) - символы постоянных предикатов.

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

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

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

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

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

2. Если F( .,.....,.) – n-местная предикатная переменная или постоянный предикат, а x_1, х_2,... х_n предметные переменные или предметные постоянные (не обязательно все различные) , то F(х_l, х_2,..., х_n) есть формула.

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

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

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

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

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

Лекция №4 Равносильные формулы логики предикатов.

Определение 5. Две формулы логики предикатов А и В (AB) называются равносильными на области М, если они принимают одинаковые значения при всех значениях входящих в них переменных, отнесенных к области М.

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

Все равносильности алгебры высказываний верны, если в них вместо переменных высказываний подставить формулы логики предикатов. Но, кроме того, имеют место равносильности самой логики предикатов.

1. 

2. 

3. 

4. 

5. 

6. 

7. 

8. 

9. 

10. 

11. 

12. 

13. 

14. 

15. 16.

Предваренная нормальная форма (п.Н.Ф.)

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

Среди нормальных форм формул логики предикатов важное значение имеют так называемые предваренные нормальные формы. В них кванторные операции либо полностью отсутствуют, либо используются после всех операций алгебры логики, то есть предваренная нормальная форма формулы логики предикатов имеет вид: В результате этих алгебраических преобразований может быть получена формула вида: Â_x1 Â_x2 ¼Â_xn(M), где ÂÎ{"; $} , а М – матрица формулы. Кванторную часть формулы Â_x1 Â_x2 ¼Â_xn иногда называют префиксом ПНФ.

Теорема. Всякая формула логики предикатов может быть приведена к предваренной нормальной форме.