Спирина, М.С. Дискретная математика

из указанной предметной области. Высказывательные формы, вхо­ дящие в предикаты, называют также препозиционными функция­ ми, или предикаторами. Рассмотрим двухместную высказывательную форму х > у + 2, где х определено на множестве Мх = {3, 5}, а у — на множестве Му = {1, 5, 8}. Этой форме соответствуют два предиката Р{ и Р2, определенные на множествах Мх х Л/,, и Му х Мх, которые образо­ ваны с помощью декартова произведения двух множеств. Срав­ ним предикаты Рх(х, у) и Р2(х, у) = Pt(y, х) по табл. 5.4. Видно, что двухместная высказывательная форма, вообще го­ воря, определяет два различных предиката. Для установления вза­ имно-однозначного соответствия между «-местной (« > 2) выска- зывательной формой и соответствующим предикатом принято устанавливать для этих переменных определенный порядок. Так, если для « переменных высказывательной формы Р(хи х2, ..., хп) установлен порядок (х,- ч xh ч, ..., ч х,я), а Л/,и Min ..., Min — множества значений этих переменных, то такая форма задает пре­ дикат на множестве, составляющем декартово произведение име­ ющихся множеств: М = Л/,, х Mh х ... х Min. Принято одноместный предикат называть предикатом-свойством, «-местный (для « > 1, л е N) — предикатом-отношением, 0-местный предикат — выска­ зыванием. Полный прообраз единицы (1) при Р назовем множеством истинности Т(Р) предиката Р (от англ, truth — истина): Т{Р) - = />-‘(1) = {х \ х е М \ Р(х) = 1}. В рассмотренном примере множество истинности Т(Р{) пре­ диката Р](х): х >у + 2 равно Т(РХ) = {(3, 1), (5, 1)}, а для предика­ та Р2(х) множество истинности Т(Р2) = {(5, 3), (8, 3), (8, 5)}. Как мы знаем из гл. 1, любое непустое множество содержит два подмножества: само себя и пустое. Это свойство автоматически выделяет из области определения два случая. Т а б л и ц а 5.4 Сравнение предикатов Р х( х , у ) и Р г( х , у) = Р х( у , х ) Мх X Му. (х, у) х>у + 2 Р\(х, у) М у х Мх: (у, х) у > х + 2 Pi(x, у) (3, 1) 3> 3 1 (1, 3) 1 > 5 0 (3, 5) 3 > 7 0 (1, 5) 1 > 7 0 (3, 8) 3 > 10 0 (5, 3) 5 > 5 1 (5, 1) 5 > 3 1 (5, 5) 5 > 7 0 (5, 5) 5 > 7 0 (8, 3) 8 > 3 1 (5, 8) 5> 10 0 (8, 5) 8 > 7 1 226