Кванторы

^{Решение задач}

Пусть P ( x ) - предикат, определённый на множестве M .

1) Выражение ( ∀ x ) P(x) означает высказывание, истинное только в том случае, когда предикат P(x) истинен для всех переменных из множества M . Выражение ( ∀ x ) P (x) читается « для всякого x, P (x)», здесь символ ∀ - квантор общности.

2) Выражение ( ∃ x ) P(x) означает высказывание, истинное только в том случае, когда предикат P(x) истинен хотя бы для одной переменной из множества M . Выражение ( ∃ x ) P(x) читается «сущестует x, что P(x)», здесь символ ∃ - квантор существования.

Определение. Переход от P(x) к ( ∀ x) P(x) или ( ∃ x ) P(x) называется связыванием переменной x или навешиванием квантора на переменную x или кван- тификацией переменной x .

Определение. Квантор общности – это оператор, приводящий в соот- ветствие каждому заданному предикату y = P(x) такую двузначную логическую переменную z , которая принимает значение 1 тогда и только тогда, когда y 1 при всех значениях x .

Определение. Квантор существования - это оператор, приводящий в со- ответствие каждому одноместному предикату y = P(x) такую двузначную логи- ческую переменную z , которая принимает значение 0 тогда и только тогда, когда y 0 при всех значениях x .

Определение. Областью действия квантора называется выражение, на которое навешен квантор.

Задача 4.1. Рассмотреть все варианты навешивания кванторов на предикат P(X,Y) "x ≤ y", определённый на множестве натуральных чисел N . Определить истинность полученных высказываний.

Решение.

∀x (x ≤ y) одноместный предикат от y : «любое число не больше y »; ∀xP(x, y) = 0;

∀y (x ≤ y) одноместный предикат от x : «любое число из M не меньше x»; ∀yP( x,y ) = 0;

∃x (x ≤ y) - одноместный предикат от y : «существует число в M , которое не больше y »; ∃xP(x, y) = 1;

∃y (x ≤ y) одноместный предикат от x : «существует число в M , которое не меньше x»; ∃yP(x,y) = 1;

∀x∀y (x ≤ y) - двуместный предикат: «для любых x и y выполняется x ≤ y»; ∀x∀yP(x,y) = 0;

∀y∀x (x ≤ y) двуместный предикат: «для любых x и y выполняется x ≤ y»; ∀y∀xP(x,y) = 0;

∃x∃y (x ≤ y) двуместный предикат: «существуют такие x и y , что выполняется x ≤ y»; ∃x∃yP(x,y) = 1;

∃y∃x (x ≤ y) двуместный предикат: «существуют такие x и y , что выполняется x ≤ y»; ∃y∃xP(x,y) = 1;

∀x∀y (x ≤ y) двуместный предикат: «для любого числа x существует число y, не меньшее, чем x»; ∀x∀yP(x,y) = 1;

∀y∀x (x ≤ y) двуместный предикат: «для любого числа y существует число x, не большее, чем y»; ∀y∀xP(x,y) = 1;

∃x∀y (x ≤ y) двуместный предикат: «существует x такой, что он не больше любого y »; ∃x∀yP(x, y) = 1 , так как во множестве N есть единственный минимальный элемент 1;

∃y∀x (x ≤ y) двуместный предикат: «существует y такой, что для любого x x≤y»; ∃y∀xP(x,y) = 0,так как во множестве N нетединственного максимального элемента.

Задачи для самостоятельного решения

Рассмотреть все варианты навешивания кванторов на предикат P(X,Y), определённый на некотором множестве. Определить истинность полученных высказываний.

Предикат P ( X, Y ) = "X, Y делятся на 3"определён на множестве натуральных чисел N .
Предикат P ( X, Y ) = "X, Y - нечётные числа” определён на множестве натуральных чисел N .
Предикат P ( X ,Y ) " X > Y " определён на множестве натуральных чисел N .
Предикат P ( X, Y) "X является делителем Y" определён на множестве натуральных чисел N .
Предикат P ( X ,Y ) = " X + Y = 0" определён на множестве действительных чисел Q.
Предикат P( X ,Y ) = " X² + Y² = 0" определён на множестве рациональных чисел R .
Предикат P ( X, Y ) = "X моложе Y" определён на множестве всех людеи.
Предикат P (X, Y) = "X сын Y" определён на множестве всех людеи.
Предикат P ( X ,Y ) = " X брат Y " определён на множестве всех людей.
P (X, Y ) = "X и Y имеют один и тот же остаток от деления на 3" определён на множестве натуральных чисел N .