- •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.11 Операции с кванторами
Приведем основные свойства высказываний, полученных с использованием кванторов:
свойства отрицания:
, ;
одинаковые кванторы можно менять местами:
, ;
разные кванторы нельзя менять местами:
, ;
квантор всеобщности можно выносить за скобки из выражения с операцией конъюнкции, но нельзя – из выражения с операцией дизъюнкции:
,
квантор существования можно выносить за скобки из выражения с операцией дизъюнкции, но нельзя – из выражения с операцией конъюнкции:
,
;
квантор можно выносить за скобки из выражения, часть которого не зависит от переменной, стоящей под знаком квантора:
,
,
,
,
где C – некоторая формула, не зависящая от переменной x.
Приведем несколько простых примеров, иллюстрирующих некоторые из этих свойств.
Пример 5.14 – Дан предикат P(x, y): «человек по фамилии x родился в день y». Найти, истинны или ложны высказывания: xyP(x, y), yxP(x, y).
Высказывание xyP(x, y) в данной задаче читается как «для любого человека существует день рождения». Это высказывание – истинное. Высказывание yxP(x, y) означает, что «существует день, который является днем рождения для любого человека». Это высказывание – ложное.
Этот пример иллюстрирует приведенное выше утверждение о том, что разные кванторы нельзя менять местами (или, другими словами, от порядка кванторов зависит смысл высказывания, а значит – и его истинность или ложность).
Пример 5.15 – Даны предикаты P(x): «x – страна в Европе», Q(x): «x – страна в Азии». Переменная x принимает значения на множестве M = {Польша, Чехия, Индия, Китай}. Приведем примеры высказываний, полученных из этих предикатов с использованием кванторов, а также логических операций:
= Л
Высказывание ложно, так как ложны высказывания (все страны из множестваM находятся в Европе) и (все страны из множестваM находятся в Азии). Таким образом, = Л Л = Л.
= И
Высказывание истинно: все страны во множестве M находятся или в Европе, или в Азии.
= И
Высказывание истинно, так как истинны высказывания (во множествеM есть хотя бы одна страна, находящаяся в Европе) и (во множествеM есть хотя бы одна страна, находящаяся в Азии). Таким образом, = И & И = И.
= Л
Высказывание ложно: во множестве M нет стран, которые находились бы и в Европе, и в Азии.
Этот пример иллюстрирует приведенное выше утверждение о том, что квантор всеобщности нельзя выносить за скобки из выражения с операцией дизъюнкции, а квантор существования – из выражения с операцией конъюнкции.