- •Логика предикатов
- •§ 1. Основные понятия
- •§ 2. Классификация предикатов
- •Примеры:
- •§ 3. Множество истинности предиката
- •Примеры:
- •Утверждения:
- •Примеры:
- •§ 4. Равносильность предикатов
- •Пример 1
- •§ 5. Логические операции над предикатами Отрицание предиката
- •Примеры:
- •Пример 3
- •Предикат от n переменных и квантор общности
- •Квантор существования
- •Замечание
- •Предикат от n переменных и квантор существования
- •Замечание
- •Примечание
- •§ 7. Численные кванторы
- •Ограниченные кванторы
- •§ 8. Формулы логики предикатов
- •Определение формулы логики предикатов (по индукции)
- •§ 9. Классификация формул логики предикатов
- •Классификационные определения для формул логики предикатов
- •Значение формулы логики предикатов
- •§ 10. Тавтологии (равносильности) логики предикатов
- •Доказательство
- •§ 11. Равносильные преобразования формул
- •Пример неравносильных формул
- •§ 12. Общезначимость и выполнимость
- •Из определений следует:
- •Связь между общезначимостью и выполнимостью формул логики предикатов.
- •Проблема разрешения для общезначимости и выполнимости формул.
- •Решение проблемы для формул на конечных множествах.
- •Алгоритм распознавания общезначимости формул в частных случаях
- •Теорема 1
- •Следствие
- •Решение проблемы для -формул и-формул.
- •§ 13. Примеры и задачи
- •§ 14. Решение примеров
- •Решение
- •Решение
- •Решение
- •Решение примеров:
- •Литература
- •Содержание
Примеры:
S (x,y): S+ R
A(x):
Утверждения:
n-местный предикат , заданный на множествах будет:
Тождественно-истинным тогда и только тогда, когда ;
Тождественно-ложным тогда и только тогда, когда ;
Выполнимым, тогда и только тогда, когда ;
Опровержимым, тогда и только тогда, когда
Примеры:
P(x): “x – простое число” определен на множестве N (натуральных чисел), а множество – множество всех простых чисел.
Q(x): определен на множествеR, множество истинности
F(x): «диагонали параллелограмма x перпендикулярны» определен на множестве всех параллелограммов, множество истинности – множество всех ромбов.
§ 4. Равносильность предикатов
Определение. Два n-местных предиката , и заданных над одними и теми же множествами называютсяравносильными тогда и только тогда, когда их множества истинности совпадают:
Равносильность предикатов P и Q будем обозначать P↔Q.
Переход от предиката к равносильномуназываетсяравносильным преобразованием.
Определение. Предикат , заданный на множествахназываетсяследствием предиката , заданного над теми же множествами тогда и только тогда, когда P+ Q+.
Q – следствие P записываем так: P Q.
Теорема. Каждые два тождественно истинных предиката, заданных на одних и тех же множествах, равносильны.
Обратно, всякий предикат, равносильный тождественно истинному предикату, сам является тождественно истинным предикатом.
Пример 1
–одноместный предикат P(x), P+={-4}.
При выполняется равенство. Не является предикатом, это – ложное высказывание.
. Предложение является одноместным предикатом P(x), P+={1}.
Существует такое число x, что . Не является предикатом. Истинное высказывание.
–P(x), P+= (3, +∞).
Однозначное число x кратно 3 – P(x), P+={0, 3, 6 , 9}.
–не предикат.
–P(x, y) – двухместный предикат, P+= {(0; 0)}
Пример 2. Какие предикаты тождественно истинные:
при не тождественно истинный.
§ 5. Логические операции над предикатами Отрицание предиката
Определение. Отрицанием предиката P(x) называется новый предикат , который принимает значение «истина» при всех значениях , при которых предикат P(x) принимает значение «ложь» и принимает значение «ложь» при тех значениях , при которых предикат P(x) принимает значение «истина».
Из этого определения следует, что .
Определение. Отрицанием n-местного предиката , определенного на множествахназываетсяn-местный предикат, определенный на тех же множествах, обозначаемый , который превращается в истинное высказывание при всех тех значениях предметных переменных, при которых исходный предикат превращается в ложное высказывание.
То есть, предикат таков, что для любыхвыказываниеявляется отрицанием высказывания.
Примеры:
, отрицанием одноместного предиката является , определенного на множествеR.
, .
Теорема. Для n-местного предиката , определенного на множествах, множество истинности его отрицаниясовпадает с дополнением множества истинности данного предиката:. Дополнение рассматривается в множествах, то есть.
Доказательство
Согласно определению:
Следствие. Отрицание предиката будет тождественно истинным тогда и только тогда, когда исходный предикат будет тождественно ложным.
Доказательство
–тождественно истинный предикат, определен на множествах , тогда.
По теореме имеем:
.
Отсюда .
Так как если , то, значит предикаттождественно ложен.
Примеры:
есть любой из равносильных ( ) предикатов:
–тождественнно истинный предикат, задан на множестве R.
Отрицание предиката также определенного наR:
и т.д.
Конъюнкция двух предикатов
Определение. Конъюнкцией двух предикатов P(x) и Q(x) называется новый предикат P(x)&Q(x), который принимает значение истина при тех и только тех значениях , при которых каждый из предикатов принимает значение «истина» и принимает значение «ложь» во всех остальных случаях.
Пример 1. Конъюнкцией двух одноместных предикатов иопределенных наR, будет одноместный предикат , который может быть записан:, который равносилен предикату
Пример 2. Конъюнкция двух одноместных предикатов и, заданных наR, является двухместный предикат , заданный наR, равносилен предикату , определенному наR.
Теорема. Для n-местных предикатов и, определенных на множествах, множество истинности конъюнкциисовпадает с пересечением множеств истинности исходных предикатов:
Доказательство:
Следствие. Конъюнкция двух предикатов тождественно истинна тогда и только тогда, когда оба данных предиката тождественно истинны.