Игошин Математическая логика и теория алгоритмов (1019110), страница 46
Текст из файла (страница 46)
Такое сведение осуществляется на основе следующей теоремы и следствия из нее. Теорема 23.2. Если формула логики предикатов, содержащая только одноместные предикатные переменные, выполнима, то она выполнима на конечном множестве, содержащем не более 2" элементов, где и — число различных предикатных переменных, входящих в рассматриваемую формулу. Д о к а з а т е л ь с т в о. Заметим сначала, что если 6(хь ..., хг)— открытая формула логики предикатов, в которой хь ..., хг — все ее свободные предметные переменные, то выполнимость такой формулы равносильна выполнимости следующей замкнутой формулы: (Зх,) ...
(Зх„) (6(хь ..., хг)). (Продумайте это утверждение.) По- 188 этому доказательство теоремы лостаточно провести для замкнутой формулы в предваренной нормальной форме. Пусть Г = (Кх,) ... (К,х„)(Н(Р,(х,), ..., Р„(х„))) (1) такая формула, где каждый К; есть один из кванторов 'Ф или В(1= = 1, ..., п), Р;(х;) — одноместные предикатные переменные (1 = = 1, ..., и), а формула Н не содержит кванторов. Предположим, что формула Г выполняется на некотором множестве М. Это означает, что существуют конкретные одноместные предикаты А,(х,), ..., А„(х„), определенные на М, такие, что высказывание Е(А,(х,), ..., А„(х„)) = (К,х,) ...
(К„х„)(Н(А,(х,), ..., А„(х„))) (2) истинно. Рассмотрим конечную последовательность «„»„..., »„, в которой каждое»; есть 0 или 1, и выберем все такие элементы а из множества М, для которых ЦА,(а)) = «и ЦАг(а)) = »г, ..., Л(А„(а)) = »„. Подмножество множества М„составленное из всех таких элементов, обозначим М, (где а — десятичная запись двоичного числа «1»г ...
»„). Итак, М, = (а в М: Л(А,(а)) = «„ЦАг(а)) = »,, ..., Л(А„(а)) = »„). В частности, для некоторой последовательности «н»г, ..., »„ требуемых элементов а в множестве М может не найтись. Тогда такое М, = И. Но ясно, что М„~ Мв — — кг, если а~ !3 . Сколько же всего образуется подмножеств М,? Ровно столько, сколько существует конечных последовательностей длины п, составленных из нулей и единиц, т.е.
2" (см. доказательство теоремы 10.3). Но некоторые подмножества, как было отмечено, могут быть пустыми. Поэтому число т непустых подмножеств М не превосходит числа 2", Другими словами, набор непустых подмножеств М„образует разбиение множества М на непересекающиеся подмножества. Обозначим через М множество, элементами которого являются все непустые подмножества М,: М = (М,„: М,„~ Я, и = 1, ..., т; т < 2") (число элементов в М равно т < 2" ). Определим на множестве М п одноместных предикатов А,'(х,), ..., А„'(х„) по следующему правилу: каждый предикат А (х,) таков, что логическое значение ЦА,г(М,)) высказывания А (М,), получающегося из этого предиката в результате подстановки вместо предметной переменной х; элемента М, множества М, совпадает с логическим значением ЦА;(а)) высказывания А,(а), !89 получающегося из предиката А;(х;) подстановкой элемента а вместо переменной хь где а в М,.
(Отметим, что определение корректно, т. е. не зависит от выбора а в множестве М„потому что для всех а из М, ЦА;(а)) = ~ь) Итак, по определению имеем (3) Х(Аг(М,)) = 7~(А,(а)) () = 1, ..., и) для О е Ма. Докажем теперь, что формула Г(Р„...„Р„) выполнима на т-элементном множестве М, а именно, что она превращается при подстановке в нее вместо предикатных переменных Р,(х,), ..., Р„(х„) конкретных предикатов А;(х,), ..., А„'(х„) соответственно в выполнимый предикат Г(А;(х,), ..., А„'(х„)) (фактически истинное высказывание).
Доказательство этого утверждения проведем индукцией по числу кванторов в предваренной нормальной форме формулы Г. Сформулируем еще раз полностью то утверждение, которое будем доказывать по индукции: если некоторая формула Г(Рь ..., Р„) выполняется на множестве Мдля предикатов А,(х,), ..., А„(х„) и предметов ап ..., а„в М, то она выполняется и на т-элементном множестве М для предикатов А;(х,), ..., А„'(х„) и предметов Мео ..., М,, таких, что а, в М„, ..., а, в М„(эти предикаты определены в предыдущем абзаце).
Причем некоторые (или все) предметы могут отсутствовать, если соответствующие переменные связаны. Пусть сначала формула Р(Рь ..., Р„) не имеет кванторов вовсе, т.е. Г(Рь ..., Р„) га Н(Р,(х,), ..., Р„(х„)). Тогда выполнимость ее на множестве Мдля предикатов А,(х,), ..., А„(х„) и предметов аь ..., а„а М означает, что предикат Н(А,(х,), ..., А„(х„)) выполним, причем ЦН(А,(а,), ..., А„(а„))] = 1. Формула Н не содержит кванторов и, следовательно, является формулой алгебры высказываний. Поэтому логическое значение составного высказывания Н(А,(а,), ..., А„(а„)) может быть найдено на основании теоремы 2.2, в результате чего последнее равенство примет вид (4) Н()~(А,(а,)), ..., Х(А„(а„))) = 1.
Для элементов ап ..., а„множества М выберем такие подмножества М„, ..., М, этого множества, что а, в М„, ..., а„в М, . Тогда, по определению предикатов АЯх;) (см. (3)), Х(А;(а;)) = = ).(АЯ М„)), 1 = 1, ..., и. Подставим эти значения в (4). Получим Н(Х(А1'(М„)), ..., Х(А„'(М,„))) = 1, 190 откуда, на основании теоремы 2,2, заключаем, что ЦН(А,'( М„), ..., А„'( М,„))1 = 1.
Последнее означает выполнимость предиката Н(А;(х,), ..., А„'(х„)) на т-элементном множестве М для предметов М„, .„, М, и, значит, выполнимость формулы Н(Р,(х,), ..., Р„(х„)), т.е. формулы Г(Р„..., Р„) на этом же множестве для тех же предметов. Предположим теперь, что для всякой формулы Г(Р„..., Р„) с числом кванторов < х из выполнимости ее на множестве Мдля предикатов А,(х,), ..., А„(х„) и предметов аь ..., а„в М следует выполнимость ее на множестве М для предикатов А (х,), ..., А„'(х„) и предметов М„, ..., М,, таких, что а, в М„, ..., а, в М,„.
Наконец рассмотрим произвольную формулу Г(Рь ..., Р„) с числом кванторов Й ~ и, т.е. Г(Р„..., Р„) и (К,х,) ... (Кьхь)(Н(Рь ..., Р„)). (5) Допустим, что формула (5) выполняется на множестве М для предикатов А,(х,), ..., А„(х„) и предметов аь„, ..., а„в М. Учитывая предположение индукции, покажем, что она выполняется на т-элементном множестве М для предикатов А,'(х,), ..., А„'(х„) и предметов М„„...,М, таких, что а, в М„, ..., а„е М, .
Здесь нужно рассмотреть две возможности для квантора К,хь а) Квантор Кх, есть ~хь Тогда выполнимость формулы (5) для предикатов А~(х,), ..., А„(х„) и предметов аь, и ..., а„в М означает, что при соответствующей подстановке она превращается в выполнимый предикат (Ъх,)(Кзх,) ... (К„хь)(Н(А,(х,), Аз(хз), ..., А„(х„))), причем Х[(Ъх,)(Кзхз) ... (К~х~)(Н(А,(х,), ..., А (х~), А~,,(а„,,), ..., А„(а„)))1=1.
Далее, по определению 20.1 квантора общности, из последнего соотношения следует, что для любого а в М Ц(Кгхг) ... (Кх,)(Н(А,(а), Аг(хг), ..., АКх~), А~,,(а~,,), ..., А„(а„)))1 = 1. (6) Равенство (6) означает, что формула (7) (Кзхз) —. (КМ(Н(Рь Рз - Р )) выполнима на множестве Мдля предикатов А,(х,), Аз(хз), ..., А„(х„) и предметов а, а~, ь ..., а„в М. Но формула (7) имеет /с — 1 кван- торов. Поэтому на основании предположения индукции заключаем, что она выполняется на множестве М для предикатов А,'(х,), Аг'(х,), ..., А„'(х„) и предметов М„М,„„, ..., М„, таких, что а а М„ Ц(Кзхз) ...
(Кдх~НН(А,'(М,), Аз'(хз), ..., Ак'(х„), Ад,~(М„,), ...,А„(М, )))) = 1. 191 Соотношение (6) выполняется для любого а е М, поэтому соотношение (8) будет выполняться лля любого М„е М. Последнее означает, по определению квантора общности, что Х[(вх,)(Кзхз) ... (К„х„)(Н(А1'(х~), Аз'(хз), ..., Аь'(хя), Ая„,( М ен ), ..., А„'( М, )))[ = 1. Это равенство говорит о том, что формула (ых1)(Кзх,) ... (Кьхя)(Н(Рь Р,, ..., Р„)) выполнима на множестве М для предикатов А,'(х,), ..., А„'(х.) и предметов М„„..., М, е М.
б ) Квантор К,х, есть Лхь Тогда выполнимость формулы (5) для предикатов А,(х,), ...„А„(х„) и предметов аь, „..., а. в М означает, что при соответствующей подстановке она превращается в выполнимый предикат (Эх,)(К,х,) ... (К„х~)(Н(А,(х,), Аз(х,), ..., А„(х„))), причем Х[(Лх,)(Кзхз) ... (Кьх~)(Н(А,(х,), ..., Ая(хь), Ая,,(аь,,), ..., А„(а„)))[ = 1. Далее, по определению 20.3 квантора существования, из последнего соотношения получим, что Х[(Кзхз) ...
(КьхьНН(А~(а), Аз(хз), ..., Аь(хь), Аь,(а*,,), ..., А„(а„)))[ = 1 для некоторого а а М. Полученное равенство означает, что формула (7) выполнима на множестве М для предикатов А,(х,), А,(х,), ..., А„(х„) и предметов а, ая, „..., а„в М. Но формула (7) имеет /с- 1 кванторов, поэтому на основании предположения индукции заключаем, что она выполняется на множестве М для предикатов А,'(х,), А,'(хз), ..., А„'(х„) и предметов М„, М,„„..., М, в М, тасоотношение (8). По определению квантора существования, оно приводит к равенству Ц(Лх,НК,хз) ... (Кяхь)(Н(АЯх,), Аз'(хз), ..., А„'(хя), А~„( М,„, ), ..., А„( М, )))[ = 1, показывающему, что формула (Эх~НКзхз) ... (КяхяйН(Рн Ри ..., Р„)) выполнима на множестве М для предикатов А,'(х,), А,'(х,), ..., А„'(х„) и предметов Итак, какое бы количество кванторов ни имела формула Г, она будет выполняться на т-элементном множестве М, где т < 2".
Теорема доказана. П Следствие 23.3. Если замкнутая формула Р(ЄЄ..., Р„'), в которую входят только одноместные предикатные переменные Ро Р„..., Р„, тождественно истинна на множестве из 2" элементов, то она общезначима. Доказательство. Допустим, что рассматриваемая формула Р(Рь Р„..., Р„) не общезначима. Тогда ее отрицание -Г(Рн Рп ..., Р„) есть выполнимая формула.
Следовательно, по доказанной теореме, эта формула выполнима на конечном множестве из т элементов, причем т < 2". Отсюда, на основании теоремы 23.1, заключаем, что она выполнима на множестве из 2" элементов. Значит, на таком множестве исходная формула Г(Рн Р,, ..., Р„) не 192 тождественно истинна, что противоречит условию. Следствие доказано. П Таким образом, задача об общезначимости формулы, содержащей лишь одноместные предикатные переменные, сводится к задаче о тождественной истинности этой формулы на конечном множестве. В свою очередь, во втором пункте настоящего параграфа показано, как последняя задача решается путем сведения ее к задаче о тождественной истинности некоторой формулы алгебры высказываний, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
