Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 16
Текст из файла (страница 16)
д.) имеют довольно прозрачный логнческвй смысл, Однако, работая с этими объектами, мы практически не обращались к их логическому содержанию и обходились теоретико-множестаенной или алгебраической иитернретапией, рассматривая их как функции на двоичных векторах или как элементы алгебр.
Этот подход оказался эффективным во многом благодаря тому, что области определенна функций алгебры логинн конечны и имеют довольно простую струитуру. Кроме того, 40-летний опыт првложений алгебры логики показал, что функционально-алгебраическая интерпретация операций над двоичными объектами оказывается не менее содержательной и плодотворной, чем логическая интерпретация. С предикатами дело обстоит иначея'значение логики предикатов, которая как частный случай включает и логику высказываний, заключается не столько в ее собственных конкретных нрилозкениях (хотя таковые имеются), сколько в том, что она образует основу логического языка математики.
С ее помощью удается формализовать и точно исследовать основные методы построения математических теорий\ Логика преднкатов является важным средством построения развитых логических языков н формальных систем. Поэтому логическая интерпретация предикатов является основной, н мы ее будем в дальнейшем придержвваться. Выражение Р(ап ..., а,) (и другие, более сложные выражения логики предикатов), где аы „., а„енМ, будем поцнмать как высказывание «Р(ап „., а„)=1» илн в соответствии с логической интерпретацией как «Р(а„ ..., а„) истинно», аГвыражение Р(хь ..., х„), где х, „, х — переменные, как переменное высказывание, истинность которого определяется подстановкой элементов М вместо хп ..., хя.
При этом Р(х„ ..., хч) — это логическая (двоичная) переменная, а х„ ..., х„ — нелогические переменные. Поскольку предикаты принимают два значения и интерпретируются как высказывания, из них можно образовывать выражения логики высказываний, т. е. формулы вида Рг (хп хз) ч/ (Рз (хз, х,) й ЬР,(хж х,). Эта формула может рассматриваться и как составная булева формула, описывающая функцию алгебры логики от трех логических переменных Рг (хь хз), Р~ (хж х,), 6 — 750 81 Р»(хм х4) [Р,(хь хз) н Р,(х,, х4) — разные логические переменные, так как предикат Р, в этих выражениях зависит от разных переменных), и как составной четырехместный предикат, значение которого определяется четырьмя предметными переменными хь х,, х„х4.
В дальнейшем, если это не вызовет разночтений, будем употреблять одинаковые обозначения для отношений и соответствующих им предикатов; при этом, помимо функциональных обозначений вида Р(х), Р(хь ха), для двухместных предикатов будем пользоваться обозначениями вида х,Рхь которые уже употреблялись в гл.
1 для бинарных отношений. : Пример 3.11, а. Предикат х,>х, — это двухместный предикат, предметной областью которого могут служить любые множества действительных чисел. Высказывание 6>5 истинно, а высказывания 7= 7 и 3 10 ложны.
Различные подстановки чисел вместо одной предметной переменной дают различные одноместные предикаты: х~>5, х,>0, 7 >х, и т. д. б. Великая теорема Ферма, не доказанная до сих пор, утверждает, что для любого целого п>2 не существует натуральных чисел х, у, г, удовлетворяющих равенству х"+ +у =х", Если этому равенству поставить в соответствие предикат Рх(х, у, х, и), истинный тогда и только тогда, когда оно выполняется, а через 1У(х) обозначить предикат «х — натуральное число», то теорема Ферма равносильна утверждению «выражение М(х)ЬМ(д)ЙУ(г)ЙУ(п)й Ь(п >2) — Рг(х, у, х, и) верно для любых чисел х, у, г, и».
в. В описаниях вычислительных процедур и, в частности, в языках программирования часто встречаются указания типа «повторять цикл до тех пор, пока переменные х н у не станут равными, либо прекратить вычисление цикла после 100 повторений».
Если обозначить через 1 счетчик повторений, то описанное здесь условие описывается выражением (х=у) ~/(1>100), а указание в целом принимает вид: «повторять, если (х у) ~7 (1> 100)». Кванторы, Пусть Р(х) — предикат, определенный на'М. Высказывание «для всех х из М Р (х) истинно» обозначается мхР(х) (множество М не входит в обозначение и должно быть ясно из контекста). Знак ух называется квантором общности; другое его обозначение (х). Высказывание «существует такой х из М, что Р(х) истинно» обозначается ИхР(х), Знак цх называется квантором существования; другое его обозначение (Ех).
Переход от Р(х) к ухР(х) или к нхР(х) называется связыванием переменной х, а так- же навешиванием квантора на переменную х (нли на пре- днкат Р), иногда — квантификацией переменной х. Пере- менная, на которую навешен квантор, называетсд связан- нойг несвязанная переменная называется свободной. Смысл связанных и свободных переменных в предикат- ных выражениях различен. Свободная переменная — это обычная переменная, которая может принимать различные значения из Л1; выражение Р(х) — переменное высказыва- ние, зависящее от значения х, Выражение ЧхР(х) не зави- сит от переменной х и при фйксированных Р и М имеет вполне определенное значение. Это, в частности, означает, что переименование связанной переменной, т.
е. переход от ухР(х) к ууР(у), не меняет истинности выражения, Пе- ременные, являющиеся по ществу связанными, встреча- !О ются не только в логике. Например, в выражениях '~ !(х) «=а ь или ) !(х)Ых переменная х связана; прн фиксированной ! а .первое выражение равно определенному числу, а второе становится функцией от а и Ь. Навешивать кванторы можно и на многоместные преди- каты, и вообще на любые логические выражения, которые прн этом заключаются в скобки.,Выражение, на которое навешивается квантор чх или их, называется областью действия квантора! все вхождения переменной х в это выра'- жение являются связанными.у Навешнвание квантора на многоместный предикат уменьшает в нем число свободных переменных и превращает его в предикат от меньшего чис- ла переменных.
Пример 3.12. а. Пусть Р (х) — преднкат «х — четное число», Тогда высказывание ухР(х) истинно на любом множестве четных чисел и ложно, если М содержит хотя бы одно нечетное число; высказывание зхР(х) истинно на лю- бом множестве, содержащем хотя бы одно четное число, и ложно на любом множестве нечетных чисел. б.
Теорема Ферма (см. пример 3.11, б) формулируется следующим образом: ухчуигип(М(х) й У(у) й !т'(г)й у(п) й(п > 2) + -»-Рг(х, у, г, п)), в. Рассмотрим двухместный предикат х у на множе- 6' 83 ствах М с отношением нестрогого порядка и различные квантифнкации его переменных. ух(х)у) — одноместный предикат от у; если М вЂ” множество неотрицательных чисел, то этот предикат истинеи в единственной точке: у=О. чхуу(х)у) — высказывание, истинное на множестве, состоящем из одного элемента, и ложное на любом другом множестве, пхну(х)у) истинно на любом непустом множестве. Высказывание их чу(х)у) («существует х, такой, что для любого у х у») утверждает, что в М имеется единственный максимальный элемент.
Оно истинно на любом конечном множестве целых чисел, ио ложно на множестве (1/2, 2/3, 3/4, ..., и/(и+1)...) или на множестве двоичных векторов, из которого удален вектор, состоящий из одних единиц. Высказывание уунх(х)у) утверждает, что для любого элемента у существует элемент х не меньший, чем йн оно истинно на любом непустом множестве ввиду рефлексивности отношения - .
Последние два высказывания говорят о том, что перестановка кванторов существования и общности меняет смысл высказывания и условия его истинности. Истинные формулы и эквивалентные соотношения. При логической (истинностной) интерпретации формул логики преднкатов возможны три основные ситуации. 1. Если в области М для формулы Р существует такая подстановка констант вместо всех переменных, что Г становится истинным высказыванием, то формула Р называется выполнимой в области М. Если существует область М, где Р выполнима, то Г называется просто выполнимой.
Пример выполнимой формулы: 3 хР(х, у)- ухР(х, у). 2. Если формула Р выполнима в М при любых подстановках констант, то она называется тождественно истинной в М. Формула, тождественно истинная в любых М,называется тождественно истинной или общезначимой. Например, формула ЗхР(х, у) — «ухР(х, у) тождественно истинна для всех М, состоящих из одного элемента, а формула ух(Р(х)~/Р(х)) тождественно истинна. 3. Если формула Г невыполнима в М, она называется тождественно ложной в М.
Если Р невыполнима ни в каких М, она называется тождественно ложной, или противоречивой, Например, формула Р,(х, п)г«Р~(х, г)ЬР,(х)ЬЙР»(п)МР»(х) тождественно ложна на любой области М, если )М)(2 (предлагаем читателю это проверить). Формула нх(Р(х)ЬР(х)) тождественно ложна. В4 Формулы называются эквивалентными, если при любых подстановках констант они принимают одинаковые значения. В частности, все тождественно истинные формулы (и все ложные формулы) эквивалентны.
Отметим, что если Р, и Р, эквивалентны в соответствии с этим определением, то формула Р,-Рз тождественно истинна. Множество истинных формул логики предикатов входит в любую теорию, и, следовательно, его исследование явля.ется важнейшей целью логики предикатов. В частности, как следует из сделанного ранее замечания, в нем содержатся все эквивалентные соотношения логики предикатов. В этом исследовании прежде всего возникают две проблемы: получение истинных формул и проверка формулы на истинность.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
