Игошин Математическая логика и теория алгоритмов (1019110), страница 39
Текст из файла (страница 39)
При чтении высказывания (ЗхНР(х)) слова в квадратных скобках могут опускаться. Высказывание (ЗхНР(х)) называется экзистенциальным высказыванием для предиката Р(х). Символ 3 происходит от первой буквы англ. ех1вг — «существовать». Сам символ Зх также называют квантором существования по переменной х. Например, рассмотрим два одноместных предиката, определенных на множестве Ф: «х = х+ 1» и «х]30». Первый предикат тождественно ложный, поэтому применение к нему операции связывания квантором существования дает ложное высказывание: (ЗхНх = х+ 1) — «существует натуральное число, равное себе плюс 1», Второй предикат выполним, поэтому операция связывания квантором существования, примененная к нему, дает истинное высказывание: (ЗхНх]30) — «существует натуральное число, делящее число 30». Подобно выражению (АКР(х)), в выражении (ЗхНР(х)) переменная х также перестает быть переменной в обычном смысле слова: это — связанная переменная.
Если одноместный предикат Р(х) задан на конечном множестве М = [ан а„..., а„), то высказывание (ЗхНР(х)) эквивалентно (имеет то же логическое значение) дизъюнкции Р(а,) м Р(а~) ч ... ~ Р(а„). В самом деле, по определению 20.3 ложность высказывания (ЗхНР(х)) означает, что предикат Р(х) тождественно ложен, т.е. каждое из высказываний Р(а,), Р(ат), ..., Р(а„), в которые данный предикат может превратиться, ложно. Последнее равносильно ложности дизъюнкции Р(а,) ~~ Р(а2) ~ ...
ч Р(а„). Значит, для предикатов, заданных на конечном множестве, операция связывания квантором существования может быть выражена через дизъюнкцию. Для предикатов, заданных на бесконечном множестве, такого сделать нельзя, и в этом случае операция связывания квантором существования является существенно новой. Наконец рассмотрим вопрос о применении операции связывания квантором существования к предикатам с любым числом предметных переменных. Определение 20.4. Операцией связывания квантором существования по переменной х, называется правило, по которому каждому п-местному (п > 2) предикату Р(хн хь ..., х„), определенному на множествах М„Мь ..., М„, ставится в соответствие новый (и — 1)-местный предикат, обозначаемый (Зх1 НР(х„х„..., х„)) (чи- 160 тается: «существует такой х„что Р(х„хн, х„), который для любых предметов аг е Мн ..., а„е М„превращается в высказывание (Зх,КР(хн аь ..., а,)), ложное в том и только в том случае, когда одноместный предикат Р(хо ан ..., а„), определенный на множестве Мо тождественно ложен, и истинное в противном случае, т.е.
О, если Р(хьа„..., а„) — тождественно Ц(Зх,)(Р(хн ан ..., а„)) ] = ложный предикат от х„ 1, если Р(хп ан ..., а,) — выполнимый предикат отх,. Например, рассмотрим двухместный предикат «у < х», определенный на А2. Применим к нему квантор существования по переменной х. Получим одноместный предикат (ЗхКу < х), зависящий от переменной у. Этот предикат всегда превращается в истинное высказывание, если вместо у подставлять конкретные числа, т.е.
он является тождественно истинным предикатом. В другом примере двухместный предикат «х'+ у' < 0», определенный на А', тождественно ложен. Поэтому применение к нему квантора существования по любой переменной, например по х, дает одноместный (по у) предикат, который будет тождественно ложным: (ЗхКхз + у' < 0). Заметим в заключение, что к (п — 1)-местному предикату (Зх,КР(х„хн ..., х„)), зависящему от переменных хн ..., х„, можно снова применить одну из операций квантификации — квантор общности или квантор существования по одной из свободных переменных. В результате получим (л- 2)-местные предикаты, например (ЪхгКЗх|КР(хн хн ..., х„)) и (ЗхтКЗх1КР(хь хн ..., х„)). Так, применив к тождественно истинному одноместному предикату (ЗхКу < х), заданному на Ф, квантор общности, получим истинное высказывание: (ЪуКЗхКу < х) — «Для всякого натурального числа существует большее него натуральное число».
Применив к тому же одноместному предикату квантор существования„получим также истинное высказывание: (ЗуКЗхКу < х)— «Существуют два натуральных числа, из которых одно не превосходит другое». Далее, применив к выполнимому одноместному предикату (чхКу < х), заданному на Ф, квантор существования, получим истинное высказывание (ЗуКъхКу < х) — «Существует наименьшее натуральное число».
Наконец, применив квантор сушествования к одноместному тождественно ложному предикату (ЗхКх'+ у~ < 0), получим ложное высказывание: (ЗуКЗхКх'+ у2 < 0). Численные кваиторы. В математике часто встречаются выражения вида «по меньшей мере л» («хотя бы л»), «не более чем л», «л и только л» («ровно л», «точно л»), где и — натуральное число. Эти выражения называют численными кванторами. Они имеют Иош « 161 чисто логический смысл, потому что их можно выразить без числительных на языке кванторов общности и существования, без логических операций над предикатами и знака =, обозначающего тождество (совпадение) объектов. Рассмотрим ряд случаев. 1) и = 1.
Предложение «По меньшей мере один объект обладает свойством Р» имеет тот же смысл, что и предложение «Существует объект, обладающий свойством Р», т.е. (Лх) (Р (х)). Далее, предложение «Не более чем один объект обладает свойством Р» равнозначно по смыслу предложению «Если есть объекты, обладающие свойством Р, то они совпадают», т.е. ('Фх)(Чу)[(Р(х) л Р(у)) -э х = у]. (2) Наконец, предложение «Один и только один объект обладает свойством Р» равнозначно конъюнкции высказываний (1) и (2): (Лх)(Р(х)) л ('Фх)('Фу)[(Р(х) л Р(у)) -+ х = у].
(3) Сопоставление одноместному предикату Р(х) высказывания (3) носит название операции связывания нвантором существования и единственности, а само высказывание (3) иногда обозначают так: (31х)(Р(х)). (4) Символ 31х называют нвантором существования и единственности по переменной х. Например, используя этот квантор, запишем высказывание: «Всякая сходящаяся последовательность имеет точно один предел»: ('Ф(а„))((Ла)(а = 1пп а„) -+ (Л! а)(а = 1пп а„)). 2) и = 2.
Предложение «По меньшей мере два объекта обладают свойством Р» означает то же, что и предложение «Существуют два различных объекта, обладающих свойством Р», т.е. (Зх)(Лу)(Р(х) л Р(у) л х ~ у). (5) Далее, предложение «Не более чем два объекта обладают свойством Р» равнозначно по смыслу предложению «Каковы бы ни были объекты х, у, г, если все они обладают свойством Р, то по меньшей мере два из них совпадают», которое символически записывается так: (чх)(Ву)(Ъу)[(Р(х) л Р(у) л Р(г)) -+ (х = у ч х = г ч у= г]. (6) Наконец, предложение «Два и только два объекта обладают свойством Р» совпадает по смыслу с конъюнкцией высказываний (5) и (6).
162 Совершенно аналогично выражаются через обычные кванторы и логические операции численные кванторы при и > 2. Рекомендуется самостоятельно записать соответствующие выражения для я=3. Ограниченные кванторы. Нередки в математической практике обороты следующего вида: «Всякий объект, обладающий свойством Р, обладает также и свойством Ц» и «Среди объектов, обладающих свойством Р, существует объект, обладающий также и свойством О».
Первое высказывание равнозначно по смыслу высказыванию «Всякий объект, если он обладает свойством Р, то он обладает и свойством Д», которое на языке логики предикатов записывается так: ('с~х)(Р(х) — э Ц(х)). (7) Сопоставление двум данным одноместным предикатам Р(х) и О(х) высказывания (7) носит название операции связывания ограниченным кваятором общности, а само высказывание (7) иногда обозначают (ЧР(х))(Д(х)). (8) Символ МР(х) также называют ограниченным квантором общности.
Например, высказывание «Для всякого х > 1 справедливо 1и х > О» на языке логики предикатов записывается как (Ъх)(х > 1 — »!и х > О), а с использованием ограниченного квантора общности записывается в виде (Чх> 1)(1п х > О). Второе из приведенных в начале настоящего пункта высказываний равнозначно по смыслу высказыванию «Существует объект, обладающий свойством Р и обладающий свойством Д», которое на языке логики предикатов записывается так: (Лх)(Р(х) л Д(х)). (9) Сопоставление двум данным одноместным предикатам Р(х) и 0(х) высказывания (9) носит название операции связывания ограничелным хвантором существования, а само высказывание (9) иногда обозначается (10) (ЛР(х))(Д(х)).
Символ ЭР(х) также называют ограниченным квантором суШествования. Например, (ложное) высказывание «Существует действительное число, квадрат которого равен — 1» на языке логики предикатов запишется так: (Вх)(х в А л х2 = -1), или с использованием ограниченного квантора существования запишется в виде (Лх в А)(х2 = — 1). 1бЗ Логический квадрат. Кванторные операции (или операции квантификации) над предикатами — важнейший принципиальный шаг, отличающий теорию предикатов от теории высказываний. Систему взаимоотношений между универсальными и экзистенциальными высказываниями, возникающими при определении операций взятия квантора общности и квантора существования, схематично представляют в виде следующего так называемого «логического квадрата»: (»х)(Р(х)) (и'х)( Р(х)) (Эх) (Р(х) ) (Эх)( Р(х)) Универсальные высказывания ('с~х)(Р(х)) и ('Фх)(- Р(х)), стоящие в двух верхних вершинах квадрата, не могут быть (ни для какого предиката Р(х)) одновременно истинными (хотя конечно же могут быть одновременно ложными).
Говорят, что эти высказывания являются противньиии или контрарными. Экзистенциальные высказывания (Эх)(Р(х)) и (Бх)( — Р(х))„стоящие в двух нижних вершинах квадрата, наоборот, не могут быть (ни для какого предиката Р(х)) одновременно ложными (хотя конечно же могут быть одновременно истинными). Говорят, что эти высказывания субпротивны (или субконтрарны). Высказывания, стоящие в вершинах каждой диагонали квадрата, противоречат одно другому, т.е. одно является отрицанием другого.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
