Пример 3

множество истинности предиката , определенного наR:

.

Пример 4

P(x) = «x – четное число»,

Q(x) = «x – кратно 3»,

P()&Q() = «x – четное число и x кратно 3» = «x делится на 6».

Дизъюнкция двух предикатов

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

Пример 5

Даны два одноместных предиката , определенные на R. Дизъюнкция двух одноместных предикатов: – двухместный предикат, равносилен предикатунаR.

Теорема

Для n-местных предикатов и, определенных на множествах, множество истинности дизъюнкциисовпадает с объединением множеств истинности исходных предикатов:

Следствие

Дизъюнкция двух предикатов есть выполнимый предикат тогда и только тогда, когда по меньшей мере один из данных предикатов выполним.

Следствие

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

Примеры:

1. Найти множество истинности предиката , определенного наR.

2. Дизъюнкция двух двухместных предикатов, определенных на R:

есть выполнимый предикат, т.е. выполним один из них: xy=0.

Импликация двух предикатов

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

§ 6. Кванторные операции над предикатами

Квантор общности.

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

Символ – квантор общности по переменнойx.

Примеры:

Рассмотрим одноместные предикаты на множестве N: и.

Первый предикат – тождественно истинный, следовательно - истинное высказывание.

Второй предикат – опровержимый, следовательно    – ложное высказывание.

В выражении вместоx нельзя ничего подставлять. Говорят, что переменная x – связанная.

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

Связанные переменные в следующих выражениях:

Любое из этих выражений не зависит от связанных переменных.

Замечание. Если одноместный предикат P(x) задан на конечном множестве ,тогда высказывание эквивалентно конъюнкции .

Предикат от n переменных и квантор общности

Определение. Операцией связывания квантором общности по переменной называется правило, по которому любому n-местному предикату , определенному на множествах, сопоставляется новый (n-1)-местный предикат, обозначаемый , который для любых предметов, превращается в высказывание, истинное в том и только том случае, когда одноместный предикат, определенный на множестветождественно истинен и ложное в противоположном случае, то есть:

Пример. Рассмотрим двухместный предикат , определенный на множествеN. Применим к нему квантор общности по переменной x. Получим одноместный предикат , зависящий от переменнойy. Этот предикат может превратиться в истинное высказывание при y=1 и в ложное – при y ≠ 1.

Замечание. К (n-1)-местному предикату , зависящему от переменных, можно снова применить операцию связывания квантором общности по любой свободной переменной. В результате получится (n-2)-местный предикат.

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

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