- •5 Элементы математической логики
- •5.1 Основные понятия математической логики
- •5.2 Логические переменные и логические функции. Алгебра логики
- •5.3 Основные равносильности алгебры логики
- •5.4 Функционально полные системы операций
- •5.5 Совершенные дизъюнктивные и конъюнктивные нормальные формы
- •5.5.1 Совершенные дизъюнктивные нормальные формы
- •5.5.2 Совершенные конъюнктивные нормальные формы
- •5.6 Минимизация формул алгебры логики
- •5.6.1 Минимальные днф
- •5.6.2 Минимальные кнф
- •5.8Основные понятия логики предикатов
- •5.9 Операции над предикатами
- •5.10 Кванторы
- •5.11 Операции с кванторами
5.10 Кванторы
Пусть P(x) – некоторый предикат. Тогда высказывание, утверждающее, что предикат P(x) принимает значение «истина» для любого значения переменной x, записывается как xP(x), где - квантор существования. Высказывание, утверждающее, что предикатP(x) принимает значение «истина» хотя бы для одного значения переменной x, записывается как xP(x). Здесь - квантор существования.
Следует еще раз обратить внимание, что xP(x) и xP(x) – не предикаты, а высказывания.
Пример 5.12 – Дан предикат P(x): «x - четное число». Переменная x принимает значения из множества M = {4, 7, 12}. Найти, истинны или ложны высказывания xP(x) и xP(x).
Высказывание xP(x) – ложно, так как не все числа во множестве M четны. А высказывание xP(x) – истинно, так как во множестве M есть четные числа.
Если предикат n-местный (т.е. содержит n переменных), то применение квантора к одной из переменных делает его (n-1)-местным, причем не зависящим от переменной, к которой применен квантор. Если кванторы применяются к двум переменным, то предикат становится (n-2)-местным, и т.д. Если кванторы применяются ко всем переменным, то предикат превращается в высказывание.
Пример 5.13 – Дан предикат P(x, y): «x делится на y». Переменная x принимает значения из множества M = {10, 12, 18}, а y – из множества N = {2, 4, 6, 7}. Приведем примеры применения кванторов к этому предикату.
Предикат P(x, y) – двухместный. Он задан в таблице 5.13.
Таблица 5.13 – Двуместный предикат из примера 5.13
x |
y | |||
2 |
4 |
6 |
7 | |
10 |
И |
Л |
Л |
Л |
12 |
И |
И |
И |
Л |
18 |
И |
Л |
И |
Л |
Предикат xP(x, y) – одноместный, читается как «любое число x из множества M делится на y», или «любое из чисел {10, 12, 18} делится на y». Этот предикат зависит от переменной y. Он задан в таблице 4.7.
Предикат xP(x, y) – одноместный, читается как «во множестве M есть число, которое делится на y», или «хотя бы одно из чисел {10, 12, 18} делится на y». Этот предикат также зависит от переменной y. Он задан в таблице 4.8.
Таблица 5.14 – Предикат xP(x, y) из примера 5.13 |
Таблица 5.15 – Предикат xP(x, y) из примера 5.13 | |||||||||
y |
2 |
4 |
6 |
7 |
|
y |
2 |
4 |
6 |
7 |
xP(x, y) |
И |
Л |
Л |
Л |
|
xP(x, y) |
И |
И |
И |
Л |
Здесь, например, при y=2 предикат xP(x, y) превращается в истинное высказывание, так как все числа во множестве M делятся на 2. При y=4 этот предикат превращается в ложное высказывание, так как не все числа во множестве M делятся на 4.
Рассмотрим примеры для предиката xP(x, y). Например, при y=4 он превращается в истинное высказывание, так как во множестве M есть число, которое делится на 4 (это число 12). При y=7 он превращается в ложное высказывание, так как ни одно число во множестве M не делится на 7.
Предикат yP(x, y) – одноместный, читается как «число x делится на любое число из множества N», или «число x делится на любое из чисел {2, 4, 6, 7}». Этот предикат зависит от переменной x. Он задан в таблице 5.16.
Предикат yP(x, y) – одноместный, читается как «число x делится хотя бы на одно из чисел множества N», или «число x делится хотя бы на одно из чисел {2, 4, 6, 7}». Этот предикат также зависит от переменной x. Он задан в таблице 5.17.
Таблица 5.16 – Предикат yP(x, y) из примера 5.13 |
Таблица 5.17 – Предикат yP(x, y) из примера 5.13 | |||||||
x |
10 |
12 |
18 |
|
x |
10 |
12 |
18 |
yP(x, y) |
Л |
Л |
Л |
|
yP(x, y) |
И |
И |
И |
Здесь, например, при x=10 предикат yP(x, y) превращается в ложное высказывание, так как число 10 делится не на все числа во множестве N. Предикат yP(x, y) при x=10 превращается в истинное высказывание, так как во множестве N есть хотя бы одно число, на которое делится число 10 (это число 2).
Если кванторы применяются к обеим переменным, то предикат P(x, y) превращается в высказывание. Например, xyP(x, y) – высказывание, которое можно прочитать так: «любое число из множества {10, 12, 18} делится без остатка на любое число из множества {2, 4, 6, 7}». Видно, что это высказывание - ложное. Высказывание xyP(x, y) читается как «любое число из множества {10, 12, 18} делится без остатка хотя бы на какое-то число из множества {2, 4, 6, 7}»; это высказывание – истинное.