Игошин Математическая логика и теория алгоритмов (1019110), страница 44
Текст из файла (страница 44)
теоремы 21.9 и 4.4, р, с). Итак, если Гесть —,Г, и Г, обладает приведенной формой Г,", то мы сможем найти приведенную форму и для Г. Далее, пусть Г есть (Г, — г Гг). Тогда на основании теоремы 4.4, у формула Гравносильна формуле ( Г, ч Гг). Заменив формулы Гг и Г, на равносильные им приведенные формы Г,* и Гг* соответственно, получим равносильную формулу ( Г,* ч Г;), которая, вообще говоря, не является приведенной. Но, на основании предыдущего абзаца, можно найти для формулы -Г,* приведенную форму Г,**.
Тогда ясно, что формула (Г,** ~~ Гг*) имеет приведенный вид и равносильна исходной формуле Г Наконец, если Г есть (Гг с-> Г,), то на основании равносильности теоремы 4.4, ч Г равносильна формуле ((Гг -э Гг) г (Гг -г Г,)). В предыдущем абзаце было показано, как найти приведенные формы (Гг** г Г,*) и (Гг*" ч Гг*) для формул (Г, -+ Г,) и (Г, — > Г,) соответственно. Тогда ясно, что формула (Г,"' г Г,*) л (Г;* г Гг') имеет приведенный вид и равносильна исходной формуле Е Итак, в любом случае формула Г обладает приведенной формой.
Теорема доказана. (З Разберите пример Хо 9.51, л из Задачника. Предваренная нормальная форма для формул логики предикатов. Еще одним удобным видом формулы, к которому ее можно привести равносильными преобразованиями, является предваренная нормальная форма. 180 Определение 22.4. Предваренной нормальной формой для формулы логики предикатов называется такая ее приведенная форма, в которой все кванторы стоят в ее начале, а область действия каждого из них распространяется до конца формулы, т, е. это формула вила (К~х~)...(К х ) (р(хо ..., х„)), где К; есть один из кванторов ~у или 3 (1 = 1, ..., и), и < и, причем формула Г не солержит кванторов и является приведенной формулой.
(Заметим, что кван- торы в формуле могут отсутствовать вовсе.) Теорема 22.5.,йля каждой формулы логики предикатов существует предваренная нормальная форма. Доказательство. Проведем доказательство по индукции, следуя правилу построения формул логики предикатов (определение 21.1). Если формула атомарна, то она сама представляет собой пред- варенную нормальную форму. Поскольку каждая формула г" равносильна формуле, полученной из более простых формул с, и Гз с помощью операций —, г,, ~, зз', 3 (операции -+ и <-+ выражаются через —, л и г ), то теперь остается научиться находить предваренные нормальные формы для формул — Гь (Г, л гз), (Г, ы ч гз), (зубр~), (З~НГ,), если известны предваренные нормальные формы Р7 и гз* формул с1 и сз соответственно.
Пусть, например, г7 имеет вид (Ч»,Н'охзНЗ»з)...(З»„НП,(»н ..., х„)), а Г,* имеет вид (Зу,Н'Фуз)...(Чу„Нбз(уь ..., у„)). Рассмотрим формулу Ри Поскольку Г, в г7, то Г, =- Г,*. Но формула — с"1*, в свою очередь, равносильна„на основании законов де Моргана для кванторов (теорема 21.9), формуле (Зх,НЗ»зН'ч'хз) ...
(зз»„Н- б,(хп ..., х„)). Остается по законам де Моргана для конъюнкции и дизъюнкции (теорема 4.4, р, с) пронести знак отрицания до предикатных переменных: — б, в 6,*. Тогда — с", будет иметь предваренную нормальную форму (З»,НЗ»зН'ухз) - (зу» Нг»1 (»1 " х~)). Далее, покажем, как отыскивается предваренная нормальная форма для с', если Г есть (г", л гз).
Поскольку при переименовании связанной переменной формула, очевидно, переходит в равносильную, то можно считать, что переменные хн ..., х„не вхолят в формулу гз', а переменные у„..., у не входят в с,*. Ясно, что Р; л г, в г7 л Г,*, но последняя формула еще не представляет собой предваренной нормальной формы. Покажем, как ее можно преобразовать к такой форме. На основании равносильности (получаемой из тавтологии) теоремы 21.11, а формула (с7 л сз*) равносильна формуле (Ч»,)((зУ»зНЗ»з) ... (З»„Нб,(хп ..., х„)) л л (Зу1Н~Фуз) ". (Фу )(Пз(уь ", у ))зз. 181 Теперь можно производить равносильные преобразования под знаком квантора чх, в квадратных скобках, потому что в результате связывания квантором по одной и той же переменной х, двух равносильных формул мы снова получим равносильные формулы, Тогда, на основании той же равносильности, последняя формула равносильна формуле ( гх! Н ч хг) 1(З хг) (ЗОН 61 (х1 х~у)) л л (Зу~Н'слуг)" (~гу Нбг(у~ - у ))].
И так далее. Наконец, на основании равносильности (получаемой из тавтологии) теоремы 21.!1, г последняя формула равносильна формуле (Чх,НЧхгНЗхг) ... (Зх„)((6,(хн ..., х„)) л л (Зу1Нс'уг) — (С~у Нбг(ун ..., у ))]. Таким же образом кванторы, стоящие перед формулой 6,, выносятся за квадратные скобки. В результате получим формулу (с~х~Нс~хгНЗхг) ... (Зх„) (ЗУ~Н~Ууг) ...
... (Чу ) [6,(хн ..., х.) л 6г(у„..., у )], равносильную формуле (Г, л Гг) и являющуюся предваренной нормальной формой этой формулы. Аналогичным образом при помощи равносильностей (получаемых из тавтологий) теоремы 21.11, б можно построить предваренную нормальную форму для формулы (Р, ~ Гг), исходя из пред- варенных нормальных форм Г,* и Гг' формул Г, и Рг соответственно.
Наконец, нетрудно понять, что формула (ЧсНР1*) равносильна формуле (Ч~НУ;) и является ее предваренной нормальной формой. Аналогично, (ЗсНГ;) — предваренная нормальная форма лля формулы (ЗР)(Г,). Итак, в каждом случае Г обладает предваренной нормальной формой. Теорема доказана. П Разберите пример М 9.52, м из Задачника.
Логическое следование формул логики предикатов. Понятие логического следования для формул логики предикатов соответствует понятию логического следования для формул алгебры высказываний. Формула блогики предикатов называется логическим следствием формулы Г, если при всякой интерпретации, при которой Г превращается в тождественно истинный предикат, формула 6 также превращается в тождественно истинный предикат.
Запись: 6. Как и в алгебре высказываний, Г~ 6<=г ~ à — г 6. Также две формулы равносильны тогда и только тогда, когда каждая из них является логическим следствием другой. Поэтому здесь целесооб- 182 азно еще раз обратить внимание на такие тавтологии, имеющие >орму импликации, лля которых обратные импликации тавтоогиями не являются. Так, закон о перестановке разноименных ванторов (теорема 21.!4, в) приводит к логическому следоваию: (ЭуН««хНР(х, у)) ~ (««хНЛуНР(х, у)), причем обратное слеование не выполняется. Аналогичные примеры логических следований дают тавтолоии, связанные с пронесением кванторов через знаки логических пераций, которые мы обсуждали в предыдущем параграфе: (БхНР(х) н Д(х)) ~ (ЛхНР(х)) н (ЗхНД(х)); ('«ГхНР(х)) ч (ЧхНО(х)) («УхНР(х) ч Д(х)); (ЛхНР(х)) -э (ЧхН(г(х)) ~ (««хНР(х) -+ Ц(х)); (««'хНР(х) — э Д(х)) ~ ('««хНР(х)) — ь ('ФхНО(х)); («««хНР(х) -э Д(х)) ~ (ЗхНР(х)) -+ (ЛхНД(х)).
Наконец обратим внимание на тавтологии теоремы 2!.13, выажающие законы удаления квантора общности и введения кванора существования ~ («««хНР(х)) -+ Р(у), ~ Р(у) -+ (3хНР(х)) «ри условии, что предметная переменная у не входит свободно в !«ормулу Р(х). Из этих тавтологий получаются следующие логи«еские следования: (««хНР(х)) ~ Р(у) — правило удаления квантора общности или правило универсальной конкретизации); Р(у) ~ (БхНР(х)) — правило введения квантора существова«ия (или правило экзистенциального обобщения).
Эти правила можно представить также в следующих видах: Г, Р(х) 6 Г Р(х) Г (чх)(Р(х)) Г,(ЗхНР(х)) «з «ри условии, что ни в одну формулу из совокупности Г и в форлулу «з предметная переменная х не входит свободно. Обоснуем, например, первое из этих правил (второе обоснуйе самостоятельно). По условию Г ~ Р(х), т.е. формула Р(х) пре«ращается в тождественно истинный предикат при всякой такой «нтерпретации, при которой в тождественно истинные предикагы превращаются все формулы из совокупности Г.
Пусть мы име:м такую интерпретацию и при ней формула Р(х) превращается в гождественно истинный предикат Рь(х, ун ..., у„) от переменных т, у«, ..., у,. Тогда, по определению квантора общности, предикат ;«Ух)(рь(х, у„..., у„)) от переменных ун ..., у„также будет тожде-твенно истинным. Это и означает, что Г («««хНР(х)). 183 ф 23. Проблемы разрешения для общезначимости и выполнимости формул Постановка проблемы и ее неразрешимость в общем виде. В алгебре высказываний было установлено, что существует четкий алгоритм, позволяющий для каждой формулы алгебры высказываний ответить на вопрос, будет ли данная формула выполнима, тождественно истинна или тождественно ложна. Для этого нужно составить таблицу истинности формулы и посмотреть на распределение нулей и единиц в ее последнем столбце.
Аналогичная проблема возникает и для формул логики предикатов: существует ли единый алгоритм, позволяющий для каждой формулы логики предикатов определить, будет ли она выполнимой или общезначимой? Ответ отрицательный: общего такого алгоритма яе существует. Это было доказано в 1936 г. американским математиком А.
Черчем. Тем не менее для некоторых частных видов формул данная проблема допускает решение. В настоящем параграфе покажем, как решается проблема разрешения для некоторых типов формул. Решение проблемы для формул на конечных множествах. Если формула логики предикатов рассматривается на конечном множестве, то вместо ее предикатных переменных могут подставляться конкретные предикаты, определенные на этом конечном множестве. Ввиду того что операции квантификации на конечном множестве сводятся к конъюнкции и дизъюнкции (см. 5 20), задача о выполнимости и общезначимости формулы логики предикатов на конечном множестве сводится к задаче о выполнимости или общезначимости некоторой формулы алгебры высказываний.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
