Понятие отношений. Свойства отношений.

Бинарные отношения связывают два объекта, бывают: <, >, ║, ≤, ≥, ≠, ┴, =, <быть сверстниками>, родство, дружба, любовь, <жить в одном доме>, равносильность, следование:

xRy - объект x находится в отношении R с объектом y.

Свойства бинарных отношений:

1) Рефлексивность - xRx (= ,=> , ║, ≤, ≥, ≡, родство, любовь, <друг>)

2) Симметричность - (xRy) (yRx) (║, =, ┴, ≠, ≤, ≥, дружба, родство, <быть одноклассниками>, <быть тезками>)

3) Транзитивность - (xRy) (yRz) => (xRz) (>, <, ≥, ≤, =, ║, кровное родство)

4) Антирефлексивность - (<, >, ≠, ┴)

5) Антисимметричность - ((xRy) (yRz)) => ( ) (<, >, <жить этажом выше>)

6) Связанность - (x≠y) => ((xRy) (yRx)) (>, <, ≤, ≥)

Вопросы для контроля:

1. Понятие предиката. Способы задания.

2. Понятие множества истинности предиката.

3. Отношения логического следования и логической истинности высказывательных форм

4. Понятие отношений, свойства отношений.

Раздел 8. Исчисление предикатов

Кванторы общности и существования

- квантор общности, используется вместо слов: <для любого>, <для каждого>, <для всех>.

(x² + y + 1 > 0) - <для всех x верно, что x² + y + 1 > 0>

- квантор существования, используется вместо слов: <существует>, <найдется>.

(5 + x =5) - <существует такое x, что 5 + x = 5>

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

Квантификация многоместной высказывательной формы.

Квантификация - переход от высказывательной формы к истинному высказыванию.

Рассмотрим двуместную высказывательную форму и всевозможные варианты её квантификации:

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(1) ≡ (2)

(3) ≡ (4)

Одноименные кванторы можно менять местами

(6) => (5)

(8) => (7)

Если высказывательная форма зависит от n переменных, то при квантификации высказывательной формы по x_i переменной, x_i переменная становится связанной (связана квантором), при этом все остальные называются свободными.

Чтобы перейти от высказывательной формы к истинному высказыванию нужно проквантифицировать её n раз по каждой переменной.

Отрицание предложений кванторами.

Рассмотрим такой пример: (отрицание предложения необходимо начинать со слов <неверно, что:>) - <неверно, что все ученики отличники>. Попытаемся перефразировать: <среди учеников есть хотя бы неотличник> или , т. е. ≡ . Ещё один пример: ≡ .

Правила построения отрицания предложения с кванторами:

- каждый квантор меняем на противоположный;

- отрицание переносим на высказывательную форму.

Пример: Предложение: <в каждой стране найдётся город, у всех жителей которого глаза одинакового цвета>.

Запись кванторами: (глаза одинакового цвета)

Отрицание кванторами: (неверно, что глаза одинакового цвета)

Отрицание предложение: <существует страна, в каждом городе которой найдётся житель с глазами разного цвета>.

Численные кванторы

а) Не менее n

б) Не более n

в) Ровно n

1) n = 1

a) - кубическое уравнение имеет не менее одного корня.

б) - две прямые пересекаются не более чем в одной точке

в) - линейное уравнение имеет один корень

2) n = 2

а) - в треугольнике находится не менее двух острых углов

б) - квадратное уравнение имеет не более двух действительных корней

в) - в прямоугольном треугольнике ровно два острых угла.

Аналогичным образом можно сделать и для n = 3, 4 и так далее.

Символическая запись определений и теорем.

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

Пример: число A называется пределом числовой последовательности тогда и только тогда, когда для любого E больше <0> существует такое число N, что для любого n, где n больше либо равно N, выполняется условие, что модуль разности числа A и любого числа последовательности меньше E.

Вопросы для контроля:

1. Кванторы общности и существования.

2. Квантификация многоместных высказывательных форм.

3. Отрицание предложений с кванторами.

4. Численные кванторы.

5. Символическая запись определений и теорем.

Раздел 9. Алгоритмы. Свойства алгоритмов.

Не нашли, что искали? Воспользуйтесь поиском по сайту: