Предикаттар жана алар боюнча операциялар
жүктеу/скачать 26,19 Kb.
|
Логика предикатов первого порядка
| Определение. Предикат W ( x 1 , …, xn ) называется конъ- юнкцией предикатов U ( x 1 , …, xn ) и V ( x 1 , …, xn ), заданных на множестве M , если для любых а 1 , …, an из М высказывание W ( a 1 , …, an ) есть конъюнкция высказываний U ( a 1 , …, an ) и V ( a 1 , …, an ).
Аныктама. W (x1, …, xn) предикаты M топтомунда аныкталган U (x1, …, xn) жана V (x1, …, xn) предикаттарынын коньюктурасы деп аталат, эгер каалаган а1, …, an М үчүн W (a 1, …, an) оператору U (a 1, …, an) жана V (a 1, …, an) айтуулардын конъюнциясы болуп саналат. Жогоруда айтылган башка операцияларга аналогия аркылуу аныктама берүү оңой. Биринчи даражадагы предикат логикасында эки жаңы операция киргизилет. Алар жалпы сандагычтын асылышы жана экзистенциалдык сандагычтын асылышы деп аталат. Биз алгач бул операцияларды мисалдар аркылуу карап чыгабыз. “х + у = 10 болгон x бар” туюнтмасы берилсин. Натурал сандардын жыйындысында бул сүйлөм бир орундуу P (y) предикатын аныктайт, ошондуктан P(2) жана P(9) чындык, P(11) жалган. Эгерде “ x + y = 10” предикатын S ( x , y ) менен белгилесек (жана бул эки орундуу предикат), анда P ( y ) төмөнкүчө жазылса болот: “ S ( x , y ).” Мында P ( y ) предикаты S ( x , y ) предикатынан хга экзистенциалдык кванторду туташтыруу менен алынган деп айтабыз жана P ( y ) =( x ) S ( x , y ) деп жазабыз. Дагы бир мисалды карап көрөлү. “Бардык x үчүн y – х 2 экени чын” деген туюнтма бүтүн сандардын жыйындысында Q ( y ) унардык предикатын аныктайт. Эгерде “ y – х 2 ” предикаты T (x, y) менен белгиленсе, анда Q (y) төмөнкүчө жазылса болот: “бардык х үчүн, T (x, y) туура”. Мында Q (у) предикаты Т (х, у) предикатынан х-ка жалпы квантордук туташтыруу аркылуу алынганын айтышат жана Q ( y ) = ( x ) T ( x , y ) деп жазышат. Бул мисалдардан кийин жалпы аныктама берүү кыйын эмес. Аныктама. P ( x 1 , …, xn ) M топтомунда аныкталган предикат, y өзгөрмө болсун. Анда “ар бир у P ( x 1, …, xn ) үчүн” туюнтмасы y өзгөрмөсүнө жалпы кванторду кошуу аркылуу Рден алынган предикат жана “Р ( x 1,…, xn ) болгон у бар. )” y өзгөрмөсүнө экзистенциалдык кванторду кошуу аркылуу Р-дан алынган предикат. Бул операциялар үчүн белги жогоруда киргизилген. Көңүл буруңуз, аныктама y өзгөрмөсүнүн x1, ..., xn өзгөрмөлөрүнүн бири болушун талап кылбайт, бирок төмөндө келтириле турган маанилүү мисалдарда квантор х 1, өзгөрмөлөрдүн бирине ыйгарылат. .., xn. Бул талап предикаттык логикалык формуланын аныктамасын татаалдаштырбоо үчүн аныктамада коюлбайт. Эгерде у х 1 , …, xn өзгөрмөлөрүнүн бири болсо, анда у өзгөрмөсүнө квантордук тиркегенден кийин жаңы предикат ( n –1)-локалдык болот, бирок y { x 1 , …, xn } болсо, анда жаңы предикаттын орду n . Эгерде W(x1, …, xn) предикаты U(x1, …, xn) жана V(x1, …, xn) предикаттарынан туташтыргычтар аркылуу алынса, анда W(a1, …, an) сүйлөмүнүн чындыгы. бул байланыштардын чындык таблицалары менен аныкталат. W(x1, …, xn)= ( y ) U(x1, …, xn, y) болсун. Анда W(a1, …, an) билдирүүсү туура болот, эгерде кандайдыр бир b M үчүн U(a1, …, an, b) билдирүүсү чын болсо жана анда гана. Эгерде W(x1, …, xn)= ( y ) U ( x 1 , …, xn , y ), анда W(a1, …, an) билдирүүсү b M болгондо гана туура болот. U(a1, …, an, b) туура. Предикат түшүнүгү өтө кеңири түшүнүк. Муну жогоруда келтирилген мисалдардан эле көрүүгө болот. Келгиле, n-жергиликтүү функцияны (n+1)-жергиликтүү предикат катары кароого болорун көрсөтүү менен мындай мисалдардын запасын кеңейтели. Чынында эле, M көптүгү боюнча аныкталган у = f(x1,..., xn) функциясын “y барабар f(x1,..., xn)” туюнтмасы менен байланыштырууга болот. Бул туюнтма кандайдыр бир предикат P(x1, …, xn, y). Мындан тышкары, эгерде b элементи функциянын (a1, …, a) чекитиндеги мааниси болсо, анда P(a1, …, an, b) билдирүүсү туура болот жана тескерисинче. (Биз жогоруда натурал сандарды кошуу үчүн функцияны предикатка окшош "трансформациялоону" буга чейин жасаганбыз.) Предикаттарды дагы расмий түрдө жана эки көз караштан кароого болот. Биринчиден, предикатты төмөнкүдөй катыш менен көрсөтүүгө болот. P(x1, …, xn) предикаты М көптүгү боюнча аныкталсын. Бул Mn = MM … M көптүгүнүн түз күчүн жана Mn көптүгүнүн теңдик менен аныкталган Dp ички топтомун карап көрөлү: жүктеу/скачать 26,19 Kb. Достарыңызбен бөлісу:
|