21. Алгебра предикатов: операции отрицания, конъюнкции и дизъюнкции.

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

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

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

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

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

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

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

========================================================================

22. Алгебра предикатов: операции импликации и эквивалентности.

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

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

!!!!!!!«Эквивалентность – не нашел!»!!!!!!!

23. Понятие квантора. Двойственность кванторов.

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

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

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

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

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

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

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

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

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