Игошин Математическая логика и теория алгоритмов (1019110), страница 41
Текст из файла (страница 41)
Посмотрим, в какие высказывания может превращаться данный предикат при подстановке вместо его переменных х и у конкретных предметов (чисел) из )у. Нетрудно понять, что двухместный предикат (Лг)(х у= г -» х+ у= г) превращается в истинное 167 высказывание при любой подстановке вместо его предметных переменных х и у натуральных чисел.
В самом деле, для натуральных т и и получаем высказывание (Лг)(т и = 7 -+ т + и = 7), Одноместный предикат (зависит от г) т . и = г -+ т + и = г, стоящий под знаком квантора Зг, выполним, потому что всегда можно найти такое натуральное число и, что т . и в и и т+ и в й, т.е. высказывания т и = /с и т+ и = lс будут ложны, а значит, высказывание т . и = и -~ т+ п = )с — истинно. А раз так, то высказывание (Зг)(т и = г — ~ т+ и = г) истинно. Поэтому высказывание (Лг)(т . и = г -+ т+ и = г) — > 2 = 4, в которое превращается данный предикат, ложно.
Итак, исходная открытая формула логики предикатов превращена в тождественно ложный предикат. Нетрудно понять, что если вместо предикатных переменных Р(х, у, г) и Ц(х, у, г) подставить только что рассмотренные предикаты, а вместо нульместной предикатной переменной Л— любое истинное высказывание, то исходная формула превратится в тождественно истинный предикат. Сформулируем классификационные определения для формул логики предикатов. Определение 21.4.
Формула логики предикатов называется выполнимой (опровержимой) на множестве М, если при некоторой подстановке вместо предикатных переменных конкретных предикатов, заданных на этом множестве, она превращается в выполнимый (опровержимый) предикат. Другими словами, формула выполнима (опровержима) на М, если существует истинная (ложная) ее интерпретация на М. Формула из примера 21.2 является как выполнимой, так и опровержимой. Еще один пример такой формулы приведен в Задачнике, № 9.35, л.
А в задаче № 9.54 подробно разбирается пример формулы, выполнимой на множестве из трех элементов и невыполнимой ни на каком множестве из двух элементов. Определение 21.5. Формула логики предикатов называется тождественно истинной (тождественно ложной) на множестве М, если при всякой подстановке вместо предикатных переменных любых конкретных предикатов, заданных на этом множестве, она превращается в тождественно истинный (тождественно ложный) предикат. В задачах № 9.53, 9.58 Задачника приводятся примеры формул, тождественно истинных на одних множествах, но не являющихся таковыми на других множествах.
Определение 21.б. Формула логики предикатов называется общезначшиой, или тавтологией (тождественно ложной или противоречием), если при всякой подстановке вместо предикатных переменных любых конкретных предикатов, заданных на каких угодно 168 множествах, она превращается в тождественно истинный (тождественно ложный) предикат. (Тот факт, что формула Г является тавтологией, обозначается, как и в алгебре высказываний, Е) Так, формула из примера 21.3 не является тавтологией, потому что хотя при одной подстановке она и превратилась в тождественно истинный предикат, при другой она оказалась превращенной в предикат тождественно ложный.
Поэтому данная формула не является и противоречием. Пример 21.7. Покажем, что формула —,Р(х) л (Чу)(Р(у)) является противоречием, т.е. тождественно ложной. В самом деле, допустим противное: на некотором множестве М имеется конкретный предикат А(х), такой, что данная формула превращается в выполнимый предикат (от х) -А(х) л ('-"у)(А(у)). Последнее означает: найдется предмет а в М, такой, что высказывание 4(а) л (чу)(А(у)) истинно. Истинность конъюнкции дает истинность высказываний -А(а) и (чу)(А(у)).
Из истинности первого следует, что высказывание А(а) ложно, а из истинности второго — что предикат А(у) тождественно истинный и, значит, для любого предмета из М, в том числе и для а е М, высказьгвание А(а) истинно. Получаем противоречие, исключающее предположение о непротиворечивости исходной формулы. Следовательно, она тождественно ложна. Нахождение тавтологий является одной из важнейших задач логики предикатов, как и алгебры высказываний. Но если в алгебре высказываний имеется общий метод определения, является или нет данная формула тавтологией (это — метод составления таблицы истинности для формулы), то в логике предикатов такого общего метода не существует.
Каждая формула подлежит изучению индивидуальным методом на тождественную истинность. Дело здесь в том, что каждое высказывание имеет только одно из двух логических значений: «истина» или «ложь», тогда как значение предиката зависит от выбора значений его предметных переменных, который, вообще говоря„можно сделать бесконечным числом способов. Мы вернемся к этой проблеме в Э 23 при рассмотрении ее лля формул некоторых частных видов. Тавтологии логики предикатов. Рассмотрим наиболее важные тавтологии логики предикатов. О значении тавтологий алгебры высказываний подробно говорилось в 5 3. Все сказанное там сохраняет свое значение и для тавтологий логики предикатов.
Но, как уже отмечалось, язык логики предикатов более тонок, а поэтому тавтологии логики предикатов более тонко отражают процессы логических умозаключений. Рассмотрение тавтологий логики предикатов начнем с установления того, что простейшие ее тавтологии получаются из тавтологий алгебры высказываний, а тавтологии алгебры высказываний образуют часть тавтологий логики предикатов. 169 Теорема 21.8. Всякая формула, получающаяся из тавтологии алгебры высказываний заменой входящих в нее пропозициональных переменных произвольными предикатными переменными, является тавтологией логики предикатов, Доказательство. Пусть Г(Х„Хь ..., Х„) — тавтология алгебры высказываний и Р~(хь х,, ..., х„,), Рг(уь уг* ", У и),, Р.(гь гь ..., г „) — предикатные переменные. Подставим их в данную формулу вместо пропозициональных переменных Хо Хг, ..., Х„соответственно.
Получим формулу логики предикатов: Р(Р,(х„„,,х,), Р„(гь ..., г )) . Если теперь вместо предикатных переменных подставить произвольные конкретные предикаты А,(х„хг, ...,х,), ..., А„(гн гг, ...,г ), то формула превратится в конкретный предикат Г(А,(хь ..., х,), ..., А„(г„...,г )). Этот предикат тождественно истинный, потому что подстановка вместо предметных переменных хь ..., х„,, ..., г„..., г любых конкретных предметов а„..., а „..., с„...,с из соответствующих множеств превращает данный предикат в высказывание Г(А,(хь ..., х„,), ..., А„(г, „, г„)), которое может быть получено также в результате подстановки в исходную тавтологию Р(Хь Хг, ..., Х) алгебры высказываний вместо пропозициональных переменных Хь Хг, ..., Х„конкретных высказываний А,(аь ..., а,), ..., А„(с„...,с ) соответственно и потому истинно.
Следовательно, формула Г(ЄЄ..., Р„) логики предикатов также является тавтологией. Теорема доказана. О В последующих теоремах приводятся наиболее важные тавтологии логики предикатов, не сводящиеся к тавтологиям алгебры высказываний. Все такие тавтологии содержат кванторы. Теорема 21.9 (законы де Моргана для кванторов). Следующие формулы логики предикатов являются тавтологиями: а) -(чхНР(х)) +-» (ЛхН-Р(х)); б) -(Лх)(Р(х)) +-» (чх)(- Р(х)). До ка з а тел ь с т в о.
Докажем тождественную истинность формулы а). (Тождественную истинность формулы б) предлагается проверить самостоятельно.) Данная формула замкнута, т.е. не имеет свободных предметных переменных. Поэтому, подставив в эту формулу вместо предикатной переменной Р(х) любой конкретный одноместный предикат А(х), определенный на некотором множестве М, получим высказывание — (чх)(А(х)) с-ь (Лх)( 4(х)). (1) Для доказательства его истинности нужно убедиться, что обе части эквивалентности одновременно истинны или одновременно ложны.
В самом деле, высказывание (Чх)(А(х)) истинно тогда и только тогда, когда высказывание ('Фх)(А(х)) ложно, что возможно на основании определения 20.1 тогда и только тогда, когда предикат А(х) опровержим. Далее, опровержимость предиката 170 А(х) означает выполнимость его отрицания -А(х) (обдумайте это!), что равносильно на основании определения 20.3 истинности высказывания (ЗхН-А(х)). Итак, высказывание (ехНА(х)) истинно тогда и только тогда, когда истинно высказывание (ЗхН 4(х)). Следовательно, высказывание (1) истинно, что и доказывает тождественную истинность формулы а). С! Непосредственно из этой теоремы и закона двойного отрицания (теорема 3.1, в) вытекает следствие. Следствие 21.10 (выражение кванторов одного через другой).
Следующие формулы логики лредикатов являются тавтологиями: а) (ехНР(х)) <-+ -(ЗхН- Р(х)); б) (ЗхНР(х)) <-+ — ('сгхН- Р(х)). Заметим, что законы де Моргана для кванторов напоминают аналогичные законы для конъюнкции и дизъюнкции в алгебре высказываний. Можно считать„что эти законы для кванторов представляют собой обобщения соответствующих законов для коньюнкции и дизъюнкции, подобно тому как сами операции квантификации являются обобщениями операций конъюнкции и дизьюнкции, что отмечалось в э 20. Теорема 21.11 (законы пронесения кванторов через конъюнкцию и дизъюнкцию). Следующие формулы логики лредикатов являются тавтологиями: а) (ехНР(х) л (г(х)) <-+ (вхНР(х)) а (ЧхНО(х)); б) (ЗхНР(х) ~ (г(х)) с-+ (ЗхНР(х)) ~~ (ЗхН(2(х)); в) (ЧхНР(х) ч Ц) е-> ('с'хНР(х)) ч Д; г) (ЗхНР(х) а О) с-+ (ЗхНР(х)) а (г.
Доказательство. а) Подставим вместо предикатных переменных Р(х) и (г(х) конкретные предикаты А(х) и В(х), определенные на некотором множестве М. Формула превратится в высказывание (чхНА(х) а В(х)) <-~ ('ехНА(х)) л (чхНВ(х)). (1) Докажем его истинность. На основании определения 20.1 высказывание (ехНА(х) а В(х)) истинно тогда и только тогда, когда предикат А(х) а В(х) тождественно истинен, что на основании следствия 19.7 возможно в том и только в том случае, когда оба предиката А(х) и В(х) тождественно истинны.