 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Рk(х1, х2, ..., хk): Мk → {1,0}
|
|
Например, если Х — множество действительных чисел, то х2 > 1 — одноместный предикат.
Если X, У — множества действительных чисел, то ху = 5 — двуместный предикат.
Предикат называется разрешимым, если существуют такие кортежи, компоненты которых обращают предикат в истинное высказывание.
Если предикат при подстановке любых конкретных элементов из соответствующих множеств обращается в истинное высказывание, он называется тождественно истинным.
Если предикат при подстановке любых конкретных элементов из соответствующих множеств обращается в ложное высказывание, он называется тождественно ложным.
К предикатам, определенным на одном и том же множестве, можно применять операции алгебры высказываний: конъюнкцию, дизъюнкцию, импликацию, эквивалентность, отрицание и получать новые предикаты.
Например, если к предикатам «х = y» и «х < у» — обозначим их соответственно Р(х, у) и Q(x, у) — применить операцию конъюнкции, то получим новый предикат Р(х, у) 
Q(x, у).
Язык логики предикатов.
Символами X, Y, Z, Xi, Yi,... в логике предикатов принято обозначать предметные переменные, т.е. отдельные предметы — имена. Они могут быть простыми и сложными. Если такие предметы (имена) не содержат дополнительной информации о себе, то они называются собственными (простыми), например «земля», «студент» и др. Если такое имя содержит наряду с самим предметом его отдельные свойства, то оно является сложным, например «автор романа «Анна Каренина», «перпендикулярные прямые», «взаимно-однозначное соответствие» и др.
Символами а, b, с, ai bi... принято обозначать константы или предметные постоянные, т. е. конкретные значения имен предметов из указанной предметной области. Высказывательные формы, входящие в предикаты, называют также препозиционными функциями, или предикаторами.
Любое непустое множество содержит два подмножества: само себя и пустое. Это свойство автоматически выделяет из области определения два случая.
Тождественно-истинным называется предикат, истинный всюду на области определения: Т(Р) = D(P).
Тождественно-ложным называется предикат, множество истинности которого пусто: Т(Р) = 0.
Два предиката в одной и той же области определения различны в том и только в том случае, если их множества истинности не совпадают. Это определение совпадает с отрицанием обычного определения равенства функций.
Логические операции (связки) над предикатами
Связки, аналогичные связкам булевой алгебры и исчисления высказываний, соответствуют логическим операциям над предикатами. Операции над n -местными предикатами вводятся аналогично одноместным.
Пусть, например, Р(х,...) и Q(x,...) — предикаты, которые
определены на множестве D, причем Т(Р) и T(Q) — их множества истинности.
Отрицанием предиката Р(х,.. .) называется предикат Р(х), также определенный на множестве D и истинный при тех значениях переменной х, при которых Р(х,. ..) ложен, т.е. Т(Р) = D\T(P) (рис. 5.1).
Рассмотрим примеры.
1. Для предикатов Р(х): «х — четное число» и Q(x): «х кратно 7» конъюнкцией Р(х) л Q(x) служит предикат «х — четное и кратное 7 число» или «х — число, кратное 14».
Рис. 5.1. Множество истинности Рис. 5.2. Множество истинности
предиката Р(х) конъюнкции предикатов
Пример.
Предикат Р(х): «х — простое число» определен на множестве D = Z целых чисел, а его областью истинности являются только простые числа, т. е. числа, имеющие два делителя: х и 1. Тогда предикат «х — составное (целое) число», также определенный на Z, будет отрицанием предиката Р(х), т.е. 
, а его областью истинности будет множество всех ц елых составных чисел (имеющих три и более делителей): 
\T(P).
Аналогично вводятся и остальные операции.
Конъюнкция предикатов Р(х,...) и Q(x,...) есть новый предикат 
, определенный на множестве D и истинный при тех значениях переменной х, при которых истинны одновременно оба предиката Р(х, ...) и Q(x,. ..), поэтому 
(рис. 5.2).
Пример.
Для предикатов P(x): «x – четное число» и Q(x): «x – кратное 7» конъюнкцией служит предикат «x – четное и кратное 7 число» или «x –число, кратное 14»
Пример.
Решить систему неравенств 
означает: решить первое неравенство, т.е. определить Т(Р1), решить второе неравенство — определить Т(Р2): ,<=> 
. Определить, при каких х верны и первое, и второе неравенства. В данном случае система означает конъюнкцию высказываний 
<=> 5 < х =< 8, а ответ является пересечением Т(Р1) и T(Р2) (рис. 5.3), т. е. интервалом 5 < х < 8.
Рис. 5.3. Графическое решение системы неравенств 
Обратите внимание, что в итоговый ответ вошла конъюнкция высказываний, эквивалентных данным в условии, а не самих исходных.
Дизъюнкцией предикатов Р(х,...) и Q(x,...) называется предикат Р(х)vQ(x), определенный на множестве D и истинный при тех значениях переменной х, при которых истинен хотя бы один из предикатов Р(х) или Q(x).
Поэтому 
(рис. 5.4).
Рис. 5.4. Множество истинности дизъюнкции предикатов 
Пример.
Для предикатов Р(х): «х— число, кратное 3» и Q(x): «х — число, оканчивающееся на 3», определенных на N, дизъюнкцией Р(х)vQ(x) служит предикат: «х — число или кратное 3, или оканчивающееся цифрой 3».
Так, при решении уравнений (неравенств), левая часть которых есть произведение нескольких множителей, а правая — нуль, они разбиваются на совокупность уравнений (неравенств).
Пример.
х2 - 8х - 20 = 0 <=> (х - 10)(х + 2) = 0 <=> х - 10 = 0 (Р1) или х + 2 = 0 (Р2). Таким образом, нужно найти T(P1) = {10}, T(Р1) = {-2} и их объединение: Т(Р) = {-2, 10}.
Импликацией предиката Р(х,...) в Q(x, ...) называется предикат Р(х) → Q(x), определенный на множестве D и ложный только при тех значениях переменной х, при которой предикат Р(х,...) истинен, а предикат Q(x,...) ложен. В полном соответствии с формулой алгебры логики 
имеем: 
и 
(рис. 5.5).
Рис. 5.5. Множество истинности импликации предикатов 
Пример.
Импликацией предикатов Р(х): «х — нечетное число» и Q(x): «х кратно 5», определенных на 
, служит предикат Р(х) → Q(x): «Если х — нечетное число, то х кратно 5».
Здесь Т(Р) = {y|(ymod2) = 1} = {1, 3, 5,...};
T(Q) = {y|(ymod5) = 0}= {0, 5, 10,...}.
Тогда D/T(Р) = {у| (ymod2) = 0} ={0, 2, 4,...};
Импликация верна, если число кратно двум или пяти.
Замечание. Поскольку в данном нами алфавите связка → является основной, a 
и - дополнительными, то дадим введение конъюнкции и дизъюнкции через 
и 
:
,
.
Эквиваленцией предикатов Р(х,...) и Q(x,...) называется предикат Р(х) в Q(x), определенный на множестве D и истинный при тех значениях переменной х, при которых либо оба предиката истинны, либо оба предиката ложны.
Поэтому 
.
В силу законов Де Моргана 
. Если Т(Р) = T(Q), то Т(Р = Q) = D.
Пример.
Эквивалентны предикаты Р(х): «х — натуральное число, кратное 3» и Q{x): «х — натуральное число, сумма цифр которого делится на 3».
Кванторы
Помимо операций алгебры высказываний, в логике предикатов есть две операции, которые связаны с природой предикатов. Пусть дан предикат Р(х), зависящий от одной переменной и определенный на поле М.
а) Выражение (
х)Р(х) означает высказывание, истинное только в том случае, когда предикат Р(х) истинен для всех предметов из поля М. Выражение ( х)Р(х) читается «для всякого х, Р(х)», здесь символ — квантор общности.
б) Выражение (
х)Р(х) означает высказывание, истинное только в том случае, когда предикат Р(х) истинен хотя бы для одного предмета из поля М. Выражение ( х)Р(х) читается «существует х, что Р(х) », символ — квантор существования.
Рассмотрим примеры применения операций квантирования к предикатам. Пусть даны предикаты над полем натуральных чисел:
1) х2 = х х, тогда ( х) (х2 = х х) — истинное высказывание;
2) х + 2 = 7, тогда ( х) (х+2 = 7) — ложное высказывание; а ( х) (х + 2 = 7) — истинное высказывание;
3) х + 2 = х, тогда ( х) (х + 2 = х) — ложное высказывание.
| Название | Прочтение | Обозначение |
| Квантор общности | «все», «всякий», «каждый», «любой» |
|
| Квантор существования | «Хотя бы один», «найдется», «существует» |
|
Квантор общности — это оператор, приводящий в соответствии любому заданному предикату у = Р(х) такую двузначную логическую переменную z, которая принимает значение 1 тогда и только тогда, когда у = 1 при всех значениях х.
Квантор существования — это оператор, приводящий в соответствии любому одноместному предикату у = Р(х) такую двузначную логическую переменную z, которая принимает значение 0 тогда и только тогда, когда у = 0 при всех значениях х.
Рассмотрим некоторые общие свойства введенных операторов. В соответствии с определениями кванторов логическая переменная z в выражениях
z = ( х)Р(х)
z = ( х)Р(х)
уже не является функцией предметной переменной х.
Для того чтобы отметить отсутствие функциональной зависимости z от х, предметную переменную х в таких случаях называют связанной. Несвязанные переменные называют свободными.
Например, в предикате
( х) A(х,y) ( z) B(z,v)
переменные х и z — связанные, а у и v — свободные.
Если квантор общности или квантор существования применяется не к одноместному предикату, а к какому-нибудь k -местному предикату, то в результате этого получается снова предикат, но за счет связывания одной предметной переменной получаемый предикат будет ( k-1)-местным.
Кванторы.
Для количественных характеристик обычно используют понятия «все», «некоторые», «существуют» и др., которые называют кванторами (от лат. quantum — сколько). Мы часто пользовались символами и , заменяющими слова «любой» и «существует». Покажем действие этих кванторов в высказывательных формах. Часть формулы, на которую распространяется действие квантора, называется областью действия этого квантора. Вхождение переменной в формулу может быть связанным, если переменная расположена либо непосредственно после знака квантора, либо в области действий квантора, после которого стоит переменная. Все прочие вхождения — свободные. Например, в выражении 
переменная х связывает свойство предиката и квантор общности. Грубо говоря, от этой переменной, ее конкретного вида и имени, ничего не зависит, т.е. и 
суть одно и то же. Так, можно произвольно называть индекс суммирования в рядах и переменную интегрирования в определенных интегралах. В частности, в определении множества как совокупности всех объектов, удовлетворяющих характеристическому свойству, использовалась запись G = {х\Р(х)}. Очевидно, что в предикате со связанной переменной ее так же легко можно заменить на любую другую. При этом множество все равно будет совокупностью тех же элементов, удовлетворяющих свойству Р. Переменная, не являющаяся связанной, называется свободной, если после подстановки вместо нее имени некоторых конкретных объектов предикат превращается в осмысленное предложение.
Между кванторами и и логическими операциями существует тесная связь. Пусть предикат Р(х) определен на конечном множестве D= {a1, а2,...,аn}. Тогда высказывание 
будет истинным только в том случае, если истинны одновременно все высказывания Р(а1), Р(а2),..., Р(ап), т.е. если истинна их конъюнкция: 
. Аналогично высказывание 
означает, что оно истинно, когда истинно хотя бы одно из высказываний Р(а1), Р(а2),…, Р(ап). Тогда должна быть истинной дизъюнкция высказываний 
. Поэтому для конечной области определения выполняются равносильности: 
и 
.
Таким образом, кванторы общности и существования являются дополнениями и аналогами соответственно логических операций конъюнкции и дизъюнкции.
Поскольку конъюнкцию можно выразить через отрицание и дизъюнкцию, то, вообще говоря, символ можно было не включать в число основных символов, так как квантор существования 
по сути является сокращенной записью формулы 
, выражающей так называемую двойственность.
Пример.
Записать с помощью формул логики предикатов следующее утверждение: «Для лечения любого известного компьютерного вируса имеются программы. Существуют новые (неизвестные) компьютерные вирусы, для лечения которых программы еще не разработаны»
Решение.
Введем обозначения элементарных формул:
A(x) – известен компьютерный вирус x;
B(x) – для лечения вируса x существует программа ;
Тогда с помощью логических связок и кванторов получим формулы:
- против вируса x нет программы;
- любой вирус известен;
- существуют новые (неизвестные) вирусы;
- если вирус давно известен, то имеется программа для его лечения;
- существуют (появились) новые вирусы, для лечения которых программы еще не разработаны.
Тогда формализованное исходное утверждение примет вид:
Отношение следования и равносильности между высказывательными формами связаны с тождественно-истинными импликацией и эквиваленцией, следовательно, их можно записать с помощью кванторов общности:
тождественно 
тождественно 
Пример.
Запись х2 - 5х = 0 <=> х(х - 5) = 0 является не формулой, а истинным высказыванием о равносильности двух формул, представленных в виде уравнений. В то же время справедлива запись 
(х2 - 5х = 0) ≡ (х(х - 5) = 0), выражающая истинное высказывание, которое включает операцию эквиваленции в качестве составляющей.
Поэтому логическое следование можно определить через импликацию, а равносильность через эквиваленцию. Так, для эквиваленции справедливо: «Две высказывательные формы Q1 и Q2 истинны или ложны (Q1 <=> Q2) одновременно с высказыванием », что и было ранее введено.
Существует различие в употреблении знаков и «
»,«», «
» и «
».
Знаки «», «» обозначают логические операции импликации и равносильности и входят составной частью в формулы.
Знаки «» и «» обозначают определенные отношения между высказывательными формами, не входя в них в качестве составной части.
Квантификация многоместных высказывательных форм
Пусть Q(x1, х2,..., хn) — n -местная высказывательная форма. Ее замену на высказывательную форму xi Q(x1, х2,..., хn) либо на xi Q(x1, х2,..., хn) называют квантификацией высказывательной формы Q(x1, х2,..., хn) по переменной xi.
В процессе такой квантификации эта i -я переменная связывается одним из кванторов, а n -местная высказывательная форма превращается в (п- 1) -местную.
Это аналогично тому, что если функцию f(x1, х2, …, хn) проинтегрировать от а до b по переменной xi, то полученный результат будет функцией от п -1 переменной и не будет зависеть от хi: I(х1,…, хi-1, xi+1, …, хn) = 
Так, интеграл от функции одной (п = 1) переменной является константой и вообще ни от чего не зависит.
Пусть дана двухместная высказывательная форма х - у < 0, определенная на 
. Произведем квантификацию по переменной у («навесим» квантор общности). Получим одноместную высказывательную форму 
со свободной переменной х. Если для фиксированного х = х0 будет выполнено 
, то эта высказывательная форма превращается в истинное высказывание, например, при х = -2, а при х = 3 — в ложное.
Если в одноместной высказывательной форме связать квантором и вторую переменную х, то можно получить высказывание: либо 
— истинное высказывание; 
— ложное высказывание.
При «навешивании» кванторов на двухместную высказывательную форму Q(x,у) можно получить одну из восьми комбинаций:
1) 
— «для любого х и любого у Q(x,у)»;
2) 
— «для любого у и любого х Q(x,у)»;
3) 
) — «существует х и существует у, такие, что Q(x,у)»;
4) 
— «существует у и существует х, такие, что Q(x,у))»;
5) 
— «существует х, такой, что для любого у Q(x,у)»;
6) 
— «для всякого х существует у, такой, что Q(x,у)»;
7) 
— «существует у, такой, что для любого х Q(x, у)»;
8) 
— «для всякого у существует х, такой, что Q(x, у)».
Очевидно, что первое и второе высказывания, а также третье и четвертое тождественны между собой, их значения истинности совпадают. Между остальными полученными высказываниями нельзя установить тождественности: если истинно высказывание 5, то истинным будет и высказывание 8, причем обратное неверно. Аналогично, если истинно высказывание 7, то истинно и высказывание 6, но не наоборот. То есть, если кванторы одноименны (1 — 4), то их порядок не играет роли и полученные высказывания эквивалентны. Если кванторы разноименные (5 — 8), то их порядок в полученном высказывании принципиально важен.
Например, для двухместного предиката «Город х находится в стране у» высказывание 
имеет вид 0 -местного предиката и читается «В каждой стране у есть некоторый город х». Оно будет истинным, в то время как высказывание 
читается «Существует город х, находящийся во всех странах у» будет ложным.
Пусть даны х, у — две различные переменные, F(x), Ф(х) и Q(x,у) — любые формулы логики предикатов и М — формула, не содержащая свободных вхождений х. Тогда справедливы равносильности, представленные с учетом двойственности кванторов и в табл. 5.5.
Таблица 5.5
Следствия и равносильности логики предикатов
Дата публикования: 2014-11-04; Прочитано: 941 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
