18.04.2024 / Предикаты и кванторы

Предикаты

Предикаты - это часть предложения, которая выражает действие или состояние субъекта.

• Предикат (логическая функция): утверждение, содержащее переменные.

• Предикат-свойство: от одной переменной.

  • Примеры:

    • P(N) = "В городе N живут более 2 млн человек"

    • Простое(x) = "x – простое число"

    • Спит(x) = "x всегда спит на уроке"

• Предикат-отношение: от нескольких переменных.

  • Примеры:

    • Больше(x, y) = "x > y"

    • Живет(x, y) = "x живет в городе y"

    • Любит(x, y) = "x любит y"

Кванторы

Кванторы - слова или символы, указывающие на количество элементов в логическом выражении.

• Квантор: знак, обозначающий количество.

• Какой квантор использовать?

  • Примеры:

    • "Все моря соленые" - всеобщий квантор.

    • "Некоторые кошки серые" - существенный квантор.

    • "Все числа чётные" - всеобщий квантор.

    • "Некоторые окуни – рыбы" - существенный квантор.

    • "Все прямоугольники – квадраты" - всеобщий квантор.

    • "Некоторые квадраты – прямоугольники" - существенный квантор.

Высказывания

• Истинно ли высказывание?

• Дано:

  • A = "Все люди смертны" = 1

  • B = "Сократ – человек" = 1

• Доказать:

  • C = "Сократ смертен" = 1

• Доказательство:

  • P(x) = "x – человек"

  • Q(x) = "x – смертен"

  • A = 1: при x = Сократ

  • B = 1: по свойствам импликации

Кванторы и переменные

• Один квантор связывает одну переменную:

  • ∀x P(x, y) – предикат от переменной у

  • ∃y P(x, y) – предикат от переменной х

• Два квантора связывают две переменных:

  • ∀x ∃y P(x, y) - для любого х существует у, при котором P(х,у)=1

  • ∃x ∀y P(x, y) – существует х, такой что при любом у верно P(x,y)=1

Сравнение высказываний

• Отрицание кванторов:

  • НЕ "для любого x выполняется P(x)" ⟺ "существует x, при котором не выполняется P(x)"

  • НЕ "существует x, при котором выполняется P(x)" ⟺ "для любого x не выполняется P(x)"