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

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

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

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

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

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

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

18. Теорема. Всякая формула, получающаяся из тавтологии

алгебры высказываний заменой входящих в нее пропозициональных

переменных произвольными предикатными переменными, является

тавтологией логики предикатов.

Теорема (законы де Моргана для кванторов). Следующие

формулы логики предикатов являются тавтологиями:

a)

б)

Док-тво. Докажем тождественную истинность

формулы а). Данная формула замкнута, т.е. не

имеет свободных предметных переменных. Поэтому, подставив в эту

формулу вместо предикатной переменной Р(х) любой

конкретный одноместный предикат А(х), определенный на некотором

множестве М, получим высказывание

. (1)

Для док-тва его истинности нужно убедиться, что обе

части экви-сти одновременно истинны или

одновременно ложны. В самом деле, выс-ие ⌐( x)(A(x)) истинно тогда

и только тогда, когда высказывание ( х)(А(х)) ложно, что

возможно на основании определения 20.1 тогда и только тогда,

когда предикат А(х) опровержим. Далее, опровержимость предиката А(х) означает выполнимость его отрицания ⌐А(х),

Итак, высказывание ⌐( x)(A(x)) истинно

тогда и только тогда, когда истинно высказывание ( х)( ⌐ A(х)).

Следовательно, высказывание (1) истинно,чтд.

19. Теорема. Всякая формула, получающаяся из тавтологии

алгебры высказываний заменой входящих в нее пропозициональных

переменных произвольными предикатными переменными, является

тавтологией логики предикатов.

Теорема (законы пронесения кванторов через

конъюнкцию и дизъюнкцию). Следующие формулы логики предикатов

являются тавтологиями:

а) ( х)(Р(х) ^ Q(x)) <=> ( x)(P(x)) ^ ( x)(Q(x));

б) ( х)(Р(х) v Q(x)) <=> ( х)(Р(х)) v ( x)(Q(x));

в) ( х)(Р(х) v Q <=> ( x)(P(x)) v Q;

г) ( х)(Р(х)^Q) <=> ( х)(Р(х))^Q.

Док-во, а) Подставим вместо предикатных

переменных Р(х) и Q(x) конкретные предикаты А(х) и В(х), определенные

на некотором множестве М. Формула превратится в высказывание

( х)(А(х)^В(х)) <=> ( x)(A(x))^( х)(В(х)). (1)

Докажем его истинность. На основании определения высказывание ( х)(А(х)^В(х)) истинно <=> предикат А(х)^В(х) тождественно истинен, возможно в том и только в том случае, когда

оба предиката А(х) и В(х) тождественно истинны. Далее,

тождественная истинность предикатов А(х) и В(х) равносильна, ввиду

определения, истинности высказываний ( х)(А(х)) и ( х)(В(х))

соответственно, что равносильно истинности их конъюнкции

( x)(A(x)) ^ ( х)(В(х)). Итак, левая и правая части

эквивалентности (1) одновременно истинны и одновременно ложны, что дает

истинность всего высказывания (1) и тождественную истинность доказываемой формулы.