![]() Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
![]() Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
![]() |
Глава 5. Предикаты
В исчислении высказываний нет предметных переменных, то есть переменных, которые могут принимать нелогические значения, например, числовые. Для того чтобы в логические исчисления могли быть включены нелогические константы и переменные, вводится понятие предиката.
Определение. n-местным предикатом на множестве
Примеры. 1. Предикат 2. Предикат
Если Нульместный предикат представляет собой высказывание. Для каждого предиката
Примеры. 1. Для предиката 2. Для предиката
Поскольку множество значений любого предиката лежит во множестве 3. Коммутативность:
2. Ассоциативность:
3. Дистрибутивность:
4. Идемпотентность: 5. Закон двойного отрицания: 6. Закон исключения третьего: 7. Закон противоречия: 8. Законы де Моргана:
9. Свойства операций с логическими константами:
Здесь
В то же время, для предикатов определены операции специального вида, которые называются кванторами. Пусть дан
Пример. На множестве
Пусть дан
Пример. На множестве
Отметим, что запись Пусть дана запись Имеют место эквивалентности:
Отметим, что список переменных в предикате
Предикат называется тождественно истинным (тождественно ложным), если при всех возможных значениях переменных он принимает значение 1(0).
Теорема. Пусть Доказательство. Возьмем произвольный набор значений
Покажем, что это высказывание истинно. Возможны два случая. 1. 2. Соотношение выполнено при любых значениях
Следовательно, по свойству импликации получаем, что
Теорема. Пусть Доказательство аналогично доказательству предыдущей теоремы.
Предикат называется выполнимым, если при некоторых значениях переменных он принимает значение 1.
Пример. Найти значение высказывания Решение. Пусть
Предикаты могут быть выражены с помощью так называемых предикатных формул. Строгое определение формулы исчисления предикатов будет дано в следующей главе. Пока нужно учитывать, что формула становится предикатом, когда все переменные определены на некотором множестве, и определены все предикаты, входящие в формулу.
Справедливы эквивалентности:
Разноименные кванторы можно переставлять только следующим образом:
Обратные формулы неверны.
Пример. Очевидно, что высказывание
Выражения с кванторами можно преобразовывать следующим образом:
Докажем первую эквивалентность. Пусть предикаты Пусть теперь хотя бы один из предикатов (например, Таким образом, обе части эквивалентности одновременно истинны или ложны, и эквивалентность доказана.
Замечание. Формула Доказательство. Рассмотрим обе формулы на множестве
Тем не менее, справедливы эквивалентности:
Аналогично, формулы
Имеют место формулы:
Здесь
Определение. Предикатная формула находится в приведенной форме, если в ней использованы только кванторные операции, а также операции инверсии, конъюнкции, дизъюнкции, причем инверсия относится только к предикатным буквам. Определение. Предикатная формула находится в предваренной форме (предваренной нормальной форме), если она имеет вид
Пример. Записать формулу в предваренной нормальной форме. Решение. Полученная формула записана в приведенной форме. Для того чтобы квантор всеобщности можно было вынести за скобки, переобозначим переменные и выполним преобразования:
Рассмотрим предикат Если же хотя бы для одного элемента Таким образом, имеет место эквивалентность Справедлива и аналогичная эквивалентность
Пример. Найти предикат, логически эквивалентный предикату Решение.
С помощью предикатов можно записывать различные математические утверждения.
Пример. Покажем, как можно записать утверждение: “числовая последовательность Решение. Запишем данное утверждение с помощью кванторов и обозначим его
Запишем инверсию данного высказывания:
По известным формулам, инверсия импликации преобразуется следующим образом:
Отсюда получаем:
Утверждение
В Содержание.
|