23. Логика предикатов. Понятие предиката. Одноместные, двухместные и многоместные предикаты.

Понятие предиката.

Предикат- представляет собой функцию субъекта и выражения свойств о субъекте.

Средства, предоставляемые логикой высказываний, оказываются недостаточными для анализа многих математических рассуждений. В алгебре логики не рассматриваются ни структура высказываний, ни, тем более, их содержание. В то же время и в науке, и в практике используются заключения, существенным образом зависящие как от структуры, так и от содержания используемых в них высказываний.

Например, в рассуждении «Всякий ромб – параллелограмм; ABCD – ромб; следовательно, ABCD – параллелограмм» посылки и заключение являются элементарными высказываниями логики высказываний и с точки зрения этой логики рассматриваются как целые, неделимые, без учёта их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.

Поэтому возникает необходимость в расширении логики высказываний и построении такой логической системы, средствами которой можно исследовать структуру и содержание тех высказываний, которые в логике высказываний рассматриваются как элементарные.

Логика предикатов, как и традиционная формальная логика, расчленяет элементарное высказывание на субъект(буквально – подлежащее, хотя оно может играть и роль дополнения) и предикат (буквально – сказуемое, хотя оно может играть и роль определения).

Субъект – это то, о чем что-то утверждается в высказывании, а предикат – это то, что утверждается о субъекте. Логика предикатов – это расширение логики высказываний за счет использования предикатов в роли логических функций.

Например, в высказывании «7 – простое число», «7» – субъект, «простое число» – предикат. Это высказывание утверждает, что «7» обладает свойством «быть простым числом».

            Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывательную форму «х – простое число». При одних значениях х (например, х = 13, х = 17) эта форма дает истинные высказывания, а при других значениях х (например, х = 10, х = 18) эта форма дает ложные высказывания.

Определение 1. Одноместным предикатом Р(х) называется всякая функция одного переменного, в которой аргумент xпробегает значения из некоторого множества M, а функция при этом принимает одно из двух значений: истина или ложь.

Множество M, на котором задан предикат, называется областью определения предиката.

Множество , на котором предикат принимает только истинные значения, называется областью истинности предиката Р(х).

Так, предикат  P(x) – «х – простое число» определён на множестве N, а множество   для него есть множество всех простых чисел.

Определение 2.  Предикат Р(х), определённый на множестве M, называется тождественно истинным (тождественно ложным), если .

Определение 3. Двухместным предикатом P(x,у) называется функция двух переменных х и у, определённая на множестве М=М₁×М₂ и принимающая значения из множества {1,0}.

            В качестве примеров двухместных предикатов можно назвать предикаты: Q(x,у) – «х = у» предикат равенства, определённый на множестве R²=R×R; F(x,у) – «х || у» прямая х параллельна прямой у, определённой на множестве прямых, лежащих на данной плоскости.

Аналогично определяется n-местный предикат.

Говорят, что предикат Р(х) является следствием предиката Q(х)  , если ; и предикаты Р(х) и Q(х)равносильны , если .

Приведём примеры к изложенному материалу.

Пример 1. Среди следующих предложений выделить предикаты и для каждого из них указать область истинности, еслиM=R для одноместных предикатов и M=R×R  для двухместных предикатов:

1) х + 5 = 1; 

2) при х = 2 выполняется равенство х² – 1 = 0;
3) х² – 2х + 1 = 0;
4) существует такое число х, что х³ – 2х + 1 = 0;
5)  х + 2 < Зх – 4;
6) однозначное неотрицательное число х кратно 3;
7) (х + 2) – (3х – 4);
8) х² + у²  > 0.

Решение. 1) Предложение является одноместным предикатом Р(х), I_P = {– 4};
2) предложение не является предикатом. Это ложное высказывание;
3) предложение является одноместным предикатом Р(х), I_P = {1};
4) предложение не является предикатом. Это истинное высказывание;
5) предложение   является одноместным предикатом Р(х), I_P = (3; +∞);
6) предложение   является одноместным предикатом Р(х), I_P = {0; 3; 6; 9};
7) предложение не является предикатом;
8) предложение является двухместным предикатом Q(х,y), I_Q = R×R \ {(0,0)}.

Пример 2. Изобразить на декартовой плоскости область истинности предиката .

Решение.  Неравенство, составляющее исходный предикат, ограничивает часть плоскости, заключенную между ветвями параболы х = у², она изображена серой частью рисунка:


24.Логические операции над предикатами: конъюнкция, дизъюнкция, отрицание, импликация. Кванторные операции. Кванторы всеобщности и существования.

Логические операции над предикатами

Предикаты, так же, как высказывания, принимают два значения и и л (1, 0), поэтому к ним применимы все операции логики высказываний.

Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов.

Пусть на некотором множестве М определены два предиката Р(х) и Q(х).

Определение 4. Конъюнкцией двух предикатов Р(х) и Q(х) называется новый предикат Р(х)&Q(х), который принимает значение «истина» при тех и только тех значениях , при которых каждый из предикатов Р(х) и Q(х) принимает значение «истина» и принимает значение «ложь» во всех остальных случаях. Очевидно, что  областью истинности предиката Р(х)&Q(х) является общая часть областей истинности предикатов Р(х) и Q(х), т.е. пересечение .

Так, например, для предикатов   Р(х):  «х – четное число» и   Q(х):  « х кратно 3» конъюнкцией Р(х)&Q(х) является предикат «х – четное число и х кратно 3», то есть предикат «х делится на 6».

Определение 5. Дизъюнкцией двух предикатов Р(х) и Q(х) называется новый предикат , который принимает значение «ложь» при тех и только тех значениях ,  при которых каждый из предикатов принимает значение «ложь» и принимает значение «истина» во всех остальных случаях. Ясно, что областью истинности предиката  является объединение областей истинности предикатов Р(х) и Q(х), то есть объединение  .

Определение 6. Отрицанием предиката Р(х) называется новый предикат , который принимает значение «истина» при всех значениях , при которых предикат Р(х) принимает значение «ложь», и принимает значение «ложь» при тех значениях , при которых предикат Р(х) принимает значение «истина». Очевидно, что, .

Определение 7. Импликацией  предикатов  Р(х) и Q(х) называется новый предикат , который является ложным при тех и только тех значениях , при которых одновременно Р(х) принимает значение «истина», а Q(х) – значение «ложь» и принимает значение «истина» во всех остальных случаях.

Так как при каждом фиксированном  справедлива равносильность   ,  то  .

Ясно, что при выполнении логических операций над предикатами к ним применимы и равносильности алгебры логики.

Пример 3. Пусть даны предикаты А(х,у) и В(х,у), определенные на множестве . Найти множество истинности предиката  и изобразить ее с помощью кругов Эйлера-Венна.

Решение.  Так как , то .

 изображена серой частью рисунка:

Можно рассматривать и обратную задачу: «Зная область истинности предиката, полученного в результате применения логических операций к некоторым предикатам, записать этот предикат».

            Пример 4. Записать предикат, полученный в результате логических операций над предикатами Р(х), Q(х) и R(х), область истинности которого изображена серой частью рисунка:



Решение.  Так как здесь , то искомый предикат имеет вид: .
Кванторные операции над предикатами

Пусть имеется предикат Р(х), определенный на множестве М. Если , то при подстановке а вместо х в предикат Р(х) получится высказывание Р(а). Такое высказывание называется единичным. Наряду с образованием из предикатов единичных высказываний в логике предикатов рассматривается еще две операции, которые превращают одноместный предикат в высказывание.

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

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

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

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

Пример 5. Пусть на множестве N натуральных чисел задан предикат Р(х): «Число х кратно 5». Используя кванторы, из данного предиката можно получить высказывания:  – «Все натуральные числа кратны 5»;  – «Существует натуральное число, кратное 5». Очевидно, первое из этих высказываний ложно, а второе истинно.

Ясно, что высказывание  истинно только в том единственном случае, когда Р(х) – тождественно истинный предикат, а высказывание  ложно только в том единственном случае, когда Р(х) – тождественно ложный предикат.

Кванторные операции применяются и к многоместным предикатам. Так, применение к двухместному предикату  Q(х,у) квантора всеобщности по переменной х дает одноместный предикат , зависящий от у. К этому предикату можно применить кванторную операцию по переменной у. В результате получим или высказывание  или высказывание .

Таким образом, может быть получено одно из восьми высказываний:   , , , , , , , .

Легко показать, что перестановка любых кванторов местами, вообще говоря, изменяет логическое значение высказывания.

Пример 6. Пусть предикат Q(х,у): «ху» определен множестве   N × N. Показать, что высказывания  и  имеют различные логические значения.

Решение.  Так как высказывание  означает, что для всякого натурального числа у существует натуральное число х такое, что у является делителем х, то это высказывание истинно. Высказывание  означает, что есть натуральное число х, которое делится на любое натуральное число у. Это высказывание, очевидно, ложно.

Далее рассмотрим предикат Р(x), определенный на конечном множестве М = {а₁, а₂, …, а_n}.

Если предикат Р(x) является тождественно истинным, то истинными будут высказывания Р(а₁), Р(а₂),..., Р(а_n). При этом истинными будут высказывание  и конъюнкция Р(а₁)&Р(а₂)&...&Р(а_n).

Если же хотя бы для одного элемента  Р(а_k) окажется ложным, то ложными будут высказывание  и конъюнкция Р(а₁)&Р(а₂)&...&Р(а_n). Следовательно, справедлива равносильность

.

Нетрудно показать, что справедлива и равносильность

.

Это означает, что кванторные операции обобщают операции конъюнкции и дизъюнкции на случай бесконечных областей.

 

25. Понятие формулы логики предикатов. Значение формулы логики предикатов. Равносильные формулы логики предикатов. Основные равносильности логики предикатов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6.  Никакая другая строка символов формулой не является.

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

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

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

Пример 1. Какие из следующих выражений являются формулами логики предикатов? В каждой формуле выделите свободные и связанные переменные.

1) ;

2) ;

3) ;

4) ;

5) ;

6) .

Решение. Выражения 1), 2), 4), 6) являются формулами, так как записаны в соответствии с определением формулы логики предикатов. Выражения 3) и 5) не являются формулами. В выражении 3) операция конъюнкции применена к формулам P(x) и ; в первой из них переменная х свободна, а во второй связана квантором общности, что противоречит определению формулы. В выражении 5) квантор существования по переменной у навешен на формулу , в которой переменная у связана квантором общности, что также противоречит определению формулы.

В формуле 1) переменная у свободна, а переменные х и z связаны. В формуле 2) нет предметных переменных. В формуле 4) переменная х связана, а переменная у свободна.

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

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

а)  переменных высказываний;
б)  свободных предметных переменных из множества М;
в)  предикатных переменных.

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

Пример 2. Дана формула , где предикаты Р(x), Q(x) и R(x) определены на множестве N. Найти ее значение, если

1)  Р(x): «число х делится на 3», Q(x): «число х делится на 4», R(x): «число х делится на 2»;

2)  Р(x): «число х делится на 3», Q(x): «число х делится на 4», R(x): «число х делится на 5».

Решение. В обоих случаях конъюнкция Р(x)&Q(x) есть утверждение, что число х делится на 12. Но тогда при всех х, если число х делится на 12, то оно делится и на 2, и, значит, в случае 1) формула истинна.

Так как из делимости числа х на 12 не при всех х следует делимость числа х на 5, то в случае 2) формула ложна.

Пример 3. Вычислить значение формулы , если предикат Р(х,у) имеет значение Р⁰(х,у) – «числох меньше числа у» и определен на множестве М = N × N.

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

Равносильные формулы логики предикатов

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

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

Ясно, что все равносильности алгебры высказываний будут верны, если в них вместо переменных высказываний подставить формулы логики предикатов. Но, кроме того, имеют место равносильности самой логики предикатов. Рассмотримосновные из этих равносильностей. Пусть А(х) и В(х) – переменные предикаты, а С – переменное высказывание. Тогда

ОСНОВНЫЕ РАВНОСИЛЬНОСТИ:

1. ,

2. ,

3. ,

4. ,

5. ,

6.  ,

7. ,

 

8.  ,

 

9. ,

 

10. ,

 

11. ,

 

12. ,

 

13. ,

 

14. ,

 

15. ,

Равносильность 1 означает тот простой факт, что, если не для всех х истинно  А(х), то существует х, при котором будет истиной   .

Равносильность 2 означает тот простой факт, что, если не существует х, при котором истинно А(х),  то для всех х будет истиной  .

Равносильности 3 и 4 получаются из равносильностей 1 и 2 соответственно, если от обеих их частей взять отрицания и воспользоваться законом двойного отрицания.

Эти равносильности широко используются в логике предикатов при равносильных преобразованиях, если приходится иметь дело с выражениями, содержащими операцию отрицания.

Пример 4. Найти отрицание формулы  .

Решение.

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

Пример 5. Доказать равносильность .

Решение. Для доказательства равносильности достаточно рассмотреть два случая:

1. Пусть предикаты A(х) и В(х) тождественно ложны.  Тогда будет тождественно ложным и предикат . При этом будут ложными высказывания   и .

2. Пусть теперь хотя бы один из предикатов (например, А(х)) не тождественно ложный. Тогда будет не тождественно ложным и предикат . При этом будут истинными высказывания  и , а, значит, будут истинными и исходные формулы. Следовательно,   .

В заключение отметим, что формула  не равносильна формуле , а формула  не равносильна формуле . Однако, справедливы равносильности

,



.