Основы дискретной математики В.А. Осипова (552659), страница 13
Текст из файла (страница 13)
Тогда под выражением (Чх)Р(х) будем подразумевать высказывание истинное, когда Р(х) истинно для каждого элемента х из множества М, и ложное — в противном случае. Читается это выражение так: «для всех х Р(х)». Это высказывание уже не зависит от х. Символ ех называется квантором общности. Квантор существования. Пусть Р(х) — некоторый предикат. Под выражением (Зх)Р(х) будем понимать высказывание истинное, когда существует элемент множества М, для которого Р(х) истинно, и ложное — в противном случае. Читается это выражение так: «существует х такое, что Р(х)» или «существует х, для которого Р(х)».
Символ Зх называется квантором существования. Операцию связывания квантором можно применять и к предикатам от большего числа переменных (подробнее об этом будет сказано позже). Пример 2.17. Для предикатов, приведенных в примере 2.16, имеем': (Вх) (Р11) (х)ВЯ(1) (х)) — истинное высказывание; (гх) (Р11) (х) ЙЯ 6) (х)) — ложное высказывание. На языке предикатов можно составить гораздо более слож- ные предложения, чем на языке логики высказываний. Определим понятие формулы логики предикатов. Алфавит логики предикатов содержит следующие символы: 1) символы предметных переменных: х1, хг, ..., х„, ...; 2) символы предикатов: АИ)1, Ай)г, ..., Ай)ь, ..., где 1 =0,1,2, ...; 3) логические символы: -, й, Ч, ~, 4) символы кванторов: В, Ч; 5) скобки и запятую: ), (.
Во избежание нагромождения индексов часто символы пред- метных переменных будем обозначать через х, у, л, а символы предикатов — через Р, Я, Я, В и т. д. Слово в алфавите логики предикатов называется формулой, если оно удовлетворяет следующему индуктивному определе- нию (одновременно определяется понятие свободной и связан- ной переменной формулы): 1. Если А — символ предиката, х;„х;„..., х;, — символы 6) предметных переменных, не обязательно различные, то А (х«„ 6) хе, ..., х;,) — формула. Такая формула называется атомарной.
Все предметные переменные атомарных формул свободные, связанньж переменных нет. 2. Пусть А — формула. Тогда А тоже формула. Свободные : и связанные переменные формулы . А — это соответственно . свободные и связанные переменные формулы А. 3. Пусть А и  — формулы, причем нет таких предметных переменных, которые были бы связаны в одной формуле и свободны — в другой.
Тогда (АчВ), (АйВ), (А~ В), (А - В) (2.3) 'есть формулы, в которых свободные переменные формул А и В ' остаются свободными, а связанные переменные формул А и В остаются связанными. 72 Глава 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ 4. Пусть А — формула, содержащая свободную переменную х. Тогда (Чх)А, (Зх)А (2.4) тоже формулы. Переменная х в них связана. Остальные же переменные, которые в формуле А свободны, остаются свободными и в формулах (2.4).
Переменные, которые в формуле А связаны, остаются связанными и в формулах (2.4). В первой из формул (2.4) формула А называется областью действия квантора дУх, а во второй — областью действия квантора Зх. 5. Слово в алфавите логики предикатов 1 — 5 является формулой только в том случае, если это следует из правил 1 — 4. Заметим, что по определению формулы никакая переменная не может быть одновременно свободной и связанной. Оставим в силе принятое в равд. 2.1.1 соглашение об опускании скобок. Пример 2.18. 1. Следующие выражения являются формулами логики пре(з) дикатов: Аз (хд, хз, хд) — атомарная формула, в которой хд, хз, хд — свободные переменные; (дед)(Зхз)Ад (хд, хз, хз) Э (ддхд)Ад (хд, х4) — формула, в которой хд, хз — связанные переменные, а хз, х4— свободные переменные.
2. Выражение (Зхд)(ехз)Ад (хд, хз)аеА2 (хд, хз) не является (2) (2) формулой. Значение формулы определено лишь тогда, когда задана какая-нибудь интерпретация входящих в нее символов. Под интерпретацией понимают систему 9Л =< М, 7" >, состоящую из непустого множества М и соответствия 7, сопоставляющего каждому предикатному символу А(. ) определенный (д) .д г-местньдй предикат (будем обозначать предикаты, поставленные в соответствие предикатным символам, теми же символами).
При заданной интерпретации считают, что предметные переменные пробегают множество М, а символы —, М, й, З, и символы кванторов имеют свой обычный смысл. Для данной интерпретации каждая формула без свободных переменных представляет собой высказывание, которое истинно или ложно, а всякая формула со свободными переменными выражает 2.3. Логика предикагов некоторый предикат на множестве М, который истинен при одних значениях переменных из этого множества и ложен при других. Определим значение формулы в данной интерпретации, следуя индуктивным шагам определения формулы. Значение формулы Г на наборе < ад, аз, ..., а„>, а; Е М, своих свободных переменных х,„х;„..., х;„обозначим символом Г ~<апаа,...,а„>. 1.
Формула à — атомарная формула А (х;„х;„..., х;,). (д) Пусть х;„х;„..., х;, — все различные свободные переменные этой формулы, выписанные в определенном порядке. Значением формулы Г на наборе < ад, аз, ..., а, >, а; Е М, называется значение г-местного предиката, сопоставленного символу А. (д) при соответствующем замещении его переменных элементами ад, аз, ..., а,. 2. Формула Г имеет вид А. Пусть значение формулы А на наборе < ад, аз, ..., а„>, а, Е М, есть е.
Тогда Г ~<аьаа,...,а > 3. Формула Г имеет вид А М В, АоеВ, А З В или А В. Значение формулы Г на наборе < ад, аз, ..., а„>, а; е М, есть соответственно ед Мез, едгеез, ед З ез, ед ез, где ед — значение формулы А, а ез — значение формулы В на этом наборе. 4. Формула Г имеет вид (ддх)А. Если х;„х;„..., х;„ совокупность всех свободных переменных формулы Г, то х, х;„х,„..., х;„— все свободные переменные формулы А. Значение (ддх)А ~<„ь„,„> — — И тогда и только тогда, когда для любого а Е М А(<а,ад „, а„> = И. 5. Формула Г имеет вид Ях)А.
Если х;„х;„..., х, совокупность всех свободных переменных формулы Г, то х, х;„х;„..., х;„— все свободные переменные формулы А. Значение (Бх)А (<„ , ,„> = И тогда и только тогда, когда для некоторого а Е М А (<а,ад,а,,...,а > = И Пример 2.19. Рассмотрим три формулы: 1) А, (хд, хз); 2) (ехз)А (хд, хз); 3) (Зхз)(Чхд)Ад~ (хз, хд). Возьмем в качестве области интерпретации множество целых положительных чисел и интерпретируем Ад (х, у) как х < у. (2) Тогда первая формула — это предикат хд < хз, который прини- 75 2.3.
Логика предикатоа (Чх)А(х) = (Зх) А(х); — (Бх)А(х) = (ддх)- А(х). (2. 5) (2.б) 74 Глава 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ мает истинное значение для всех пар а, Ь целых положительных чисел таких, что а < Ь. Вторая формула выражает свойство: «для каждого целого положительного числа р: х < р», которое выполняется только при х = 1. Наконец, третья формула— это истинное высказывание о существовании наименьшего целого положительного числа.
Если бы в качестве области интерпретации мы рассматривали множество целых чисел, то третья формула была бы ложным высказыванием. Пример 2.20. Пусть 9Л =< И, ~ >, где 1ч — множество натуральных чисел, 7" — соответствие, сопоставляющее предикатным символам Фз~(х, р, з), Р(з1(х, р, з) следующие преди,; ~(з)(х, р,,); + „= -.; Р(з)(х, „, -); Запишем формулы, истинные в М тогда и только тогда, когда выполнены следующие условия: а) х = 0; б) х = 1; в) х — четное число; г) х — простое число; д) х = р; е) х < р; ж) х делит р; з) коммутативность сложения. Ответы: а) Рд(х) = (Чр)Я(зд(х, р, р), так как х + р = р для любого р тогда и только тогда, когда х = 0; б) Р~(х) = (е'р)Р(з1(х, р, р); в) Рз(х) = (Зр)51 ~(р, р, х); г) Р«(х) = Рд(х)бз(Чр)(»г)(Рд д(р, л, х) З (Рз(р) Ч Рз(з))), где Рд, Рз — формулы, определенные в пп. «а» и «б»; д) Рз(х) = (Чг)(»и)(о(з1(х, з, и) з Я1зд(р, з, и)); е) Ре(х, р) = (Зл)ЯОО(х, х, р); ж) Рт(х~ р) (Зз) Р( ~(х, л, р); з) (ех)(рр)(р )(~(з)(х р з) одз)(р Пример 2.21.
Пусть Т" (х) — произвольная фиксированная функция, заданная на отрезке [а, 6]. 1. Рассмотрим интерпретацию 9Л =< М, Тд >, где М— множество Действительных чисел; 1д — соответствие, сопоставляющее предикатным символам Р(х, б), фх, е) и Л(е) предикаты Р(х, б): ]х — хе[ < 6, Я(х, е): [д(х) — А[ < е, В(е): е > О.
Здесь хо — фиксированный элемент отрезка [а, 6]; А — некоторое фиксированное действительное число. Тогда утверждение о том, что число А — предел функции д" (х) при х — ~ хо, записывается формулой (»е)(Зб)(»х)((Л(е)беР(х, б)) з Я(х, е)). 2. Рассмотрим интерпретацию 9Л =< М, дз >, где М— множество действительных чисел; 72 — соответствие, сопостав- ляющее предикатным символам Р(х, б), Рд(е), Я(х, е) предикаты Р(х, б): [х — хо] < б, В(е): е > О, Я(х, е): [Дх) — ~(хе)] < е. Здесь хо — произвольный фиксированный элемент отрезка [а, Ь]. Тогда утверждение о том, что функция Т'(х) непрерывна в точке хе, записывается формулой (~е)(Зб)(ах)((Я(е)беР(х, д)) З Я(х, е)). 3. Рассмотрим интерпретацию 9Л =< М, дз >, где М— множество Действительных чисел; 1з — соответствие, сопоставляющее предикатным символам Рд(х, хд, б), В(е), Яд(х, хд, .е),.
Р(х) предикаты Рд(х, хд, б): ]х — хд] < б, В(е): е > О, Яд(х, хд, е): ~Дх) — Дхд)] < е, Р(х): х Е [а, 6]. Тогда утверждение о том, что функция ~(х) непрерывна на отрезке [а, 6], записывается формулой (»хд)(»е)(Зб)(лх)((Р(хд)ЙР»(е)беРд(х, хд, б)) з од(х, хд, е)). 2.3.2. Равносильность формул Пусть формулы Р и С имеют одно и то же множество свободных переменных (в частности, пустое). Формулы Р и С равносильны в данной интерпретации, если на любом наборе значений свободных переменных они принимают одинаковые значения (т.
е. если формулы выражают в данной интерпретации один и тот же предикат). Формулы Р и С равносильнъс в логике предикатов, если они равносильны во всех интерпретациях (тогда будем писать Р: — С). Укажем несколько правил перехода от одних формул к другим, им равносильным (во всех интерпретациях). Очевидно, что для формул логики предикатов сохран»ддотся все равносильности и правила равносильных преобразований логики высказываний.
Кроме того, можно доказать следующие правила: 1. Перенос квантора через отрицание. Пусть А — формула, содержащая свободную переменную х. Тогда справедливы следующие равносильности: 77 2.3. Логика предикатов Отсюда по определению (Зх) 1А(х) ) <аы аг, ..., а > (ЗхПА(х)ЙВ) ив е (Ях)А(х)7еВ; (Чх)(А(х)йВ) = (Мх)А(х)7еВ; (Зх)(А(х) Ч В) = (Бх)А(х) у В; (вх)(А(х) у В) = (Чх)А(х) Ч В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
