Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

предикаты с помощью операций &, v, =. Например, А(х)&В(х) обозначает предикат, который при фиксированном х=Ь превращается в сложное высказы­ вание A(b)&B(b), образованное из высказываний А(Ь) и В(Ь) соединением их связкой &. Точно так же будем образовывать новые предикаты из произволь­ ных многоместных предикатов. Например, A(x,y)^>C(x,y,z) обозначает преди­ кат, который при фиксированных переменных: х =а, у= Ь, z =c (a,b,cE !М) пре­ вращается в высказывание A (a,b)^^(a,b ,c), образованное из двух высказыва­ ний и С(а,Ь,с) соединением их связкой Множество всех х из !М, при которых Р(х) =И, называется областью истин­ ности предиката Р(х). Это множество обозначают через 1р или через Р. Очевид­ но, что область истинности для —Р(х) равна дополнению множества 1р. Области истинности для P(x)&Q(x) и Р(х) vQ(x) равны IPDIQ И Ipulg, соответственно. В дальнейшем, особенно в логическом программировании, предикат вида <а - человек» записывается в виде: человек(х). Аналогично, <а является родителем для j^ » записывается в виде: родитель(х,з^). Предикат <а больше, чем j^ » записывается в виде: больше(х,з^). § 2. Кванторы Введем специальные обозначения. Пусть !М - множество, Р(х) - определенный на Ж одноместный предикат. Тогда выра­ жение VxP(x) читается: "для всех х Р(х)" или "для всех х выполняется Р(х)", или "для любого X Р(х)", или "для каждого х Р(х)". Под выражением " VxP(x)" будем подразуме­ вать высказывание истинное, когда Р(х) истинно для каждого х из 5Ц, и ложное - в противном случае. Символ называется квантором всеобщности. Выражение ЗхР(х) читается: "существует х такое, что Р(х)" или "хотя бы для одного X Р(х)", или "для некоторого (некоторых) х Р(х)". Под выражением "ЗсР(х)" будем подразумевать высказывание, которое истинно, если Р(х) при­ нимает значение И хотя бы для одного значения переменной ХЕ !М, и ложно, если Р(х) для всех значений переменной х принимает значение Л. Символ Зх называется квантором существования. Квантор Зх считается двойственным к квантору td, и наоборот. В литературе применяются и другие обозначения. Так, вместо VxP(x) пи­ шут ЛхР(х) или ЛхР (х), а вместо ЗхР(х) пишут VxP(x) или VxP (x), или ЕхР(х). Введенные обозначения позволяют записывать предложения в символиче­ ской форме, которая оказывается более удобной для анализа и логических дей­ ствий над этими предложениями. При символизации языка требуется опреде­ 29