Дискретная математика (1). Лекция Составные высказывания
 Скачать 2.15 Mb.
|
Операции над предикатами.Над предикатами выполняются те же операции, что и над высказываниями. 1) Отрицание.  - предикат, множеством истинности которого является множество, для которого предикат Р – ложный. Рис. 1. Область истинности отрицания предиката 2) Конъюнкция Р (х)  Q(х) – это предикат, область истинности которого равна М ∩ М . Рис. 2. Область истинности конъюнкция предикатов Дизъюнкция Р (х)  Q(х) – предикат, область истинности которого равна М  М . Рис. 3. Область истинности дизъюнкции предикатов Импликация Р (х)  Q(х) – предикат, у которого область истинности совпадает с дополнением разности М и М , т.е. равна ( ). Рис. 3. Область истинности импликаци предикатов Эквиваленция Р (х)  Q(х) – предикат, область истинности которого совпадает с объединением пересечения М с М и дополнения к их объединению, т.е. равна - М ∩М  . Рис. 4. Область истинности эквиваленции предикатовКванторы.Рассмотрим предложения: В любой треугольник можно вписать окружность. Всякое число, оканчивающееся на четную цифру, делится на 2. В этих предложениях встречаются слова «любой», «всякое». Эти слова заменяют специальным символом. Значок  называется квантором всеобщности. - всякий, любой, каждый.( х) Р (х), где х U – запись, говорящая о том, что любой х из предметной области U обладает свойством Р.Например. Пусть Р (х) предикат, выражающий для х N свойство быть простым числом. Тогда ( х) (х N) Р (х) - ложное высказывание «любое натуральное число является простым».Наряду с квантором всеобщности в логике предикатов рассматривается квантор существования: Его значок  .( х) Р (х) – существует такой х, который обладает свойством Р.Например. Пусть Р (х) предикат, выражающий для х N свойство быть простым числом. Тогда, ( х) (х N) Р (х) - истинное высказывание «существует натуральное число, которое является простым».Операция введения квантора называется операцией навешивания квантора. Навешивание квантора по какой-нибудь переменной понижает местность предиката. Переменная, по которой навешен квантор, называется связанной. Например. х<у - двухместный предикат. Навесим квантор: ( х) (х N) (х<у) предикат одноместный по переменной у.Таким образом, понизить местность предиката можно двумя способами. задать предметной переменной конкретное значение. навесить кванторы по одной или нескольким переменным. Квантор всеобщности можно рассматривать как обобщение конъюнкции для конечных и бесконечных множеств. Квантор существования можно рассматривать как обобщение дизъюнкции для конечных и бесконечных множеств. |