logo search
Лекции ДМ

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

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

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

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

  1. Р( .), F( .) - одноместные предикатные перемен­ные; q(.,.,...,.), R(.,.,...,.) n-местные предикатные переменные. P0(.), Q0(. , . , …,.) - символы постоянных предика­тов.

  2. Символы логических операций:, v, ,- .

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

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

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

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

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

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

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

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

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

Например, если Р(х) и Q(x, у) - одноместный и двухме­стный предикаты, а q, r - переменные высказывания, то формулами будут слова: q, Р(х), P(x)Q(x°,y),

хР(х) xQ(x, у),

Не является формулой слово: xQ(x, y)  Р(х). Здесь нарушено условие п.3, так как в формулуxQ(x, y) пе­ременная х входит связано, а в формулу Р(х) перемен­ная х входит свободно.

Выражение у(уР(х,у))VQ(x) не является формулой, т.к. квантор всеобщности на у навешан на формулу уР(х,у), в которой переменная у уже связана квантором существования.

Выражение у, хР(х, у) не является формулой, т.к. переменной х не присвоен квантор.

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

  1.