[Список тем] [Вступление к этой теме] Страницы темы: [1] [2] [3]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Например, если P(x) и Q(x,y) - одноместный и двухместный предикаты, а q, r - переменные высказывания, то формулами будут слова: q, P(х) , P(x)&Q(x°,y), xP(x) xQ(x,у), (Q(x,у) q) r .
Не является формулой слово: xQ(x,y) P(x) . Здесь нарушено условие п.З, так как в формулу xQ(x,y) переменная x входит связано, а в формулу P(х) переменная x входит свободно.

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

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

О логическом значении формулы логики предикатов можно говорить лишь тогда, когда задано множество М, на котором определены входящие в эту формулу предикаты. Логическое значение формулы логики предикатов зависит от значений трех видов переменных:

• значений входящих в формулу переменных высказываний,
• значений свободных предметных переменных из множества М,
• значений предикатных переменных.

При конкретных значениях каждого из трех видов переменных формула логики предикатов становится высказыванием, имеющим истинное или ложное значение.
В качестве примера рассмотрим формулу:

  yz(P(x,y) P(y,z)).       (1)

в которой двухместный предикат Р(х,у) определен на множестве МхМ, где М = {0,1,2,...,n,...} .

В формулу (1) входит переменный предикат Р(х,у), предметные переменные х, у, z, две из которых у и z — связанные кванторами, а x - свободная.
Возьмем за конкретное значение предиката Р(х,у) фиксированный предикат Р°(х,у): “ х < у ”, а свободной переменной x придадим значение х° = 5 М . Тогда при значениях у, меньших х° = 5 предикат P⁰(x⁰,y) принимает значение ложь, а импликация P(x, y) Р(у, z) при всех z М принимают значение истина, то есть высказывание y z(P°(x,y) Р⁰(у,z)) имеет значение ″истина″.

[Список тем] [Вступление к этой теме] Страницы темы: [1] [2] [3]