Мүлтіксіз конъюнктивті қалыпты форма (мкқф).

Анықтама. Айталық, А формуласы < > айнымалыдан тәуелді болсын. Егер төмендегі шарттар орналаса А- берілген айнымалылар тізімінде мұлтіксіз конъюнктивті қалыпты формада делінеді.

1. А-конъюнктивті қалыпты формада

2. А-ң әрбір мұшесі к мүшелі дизъюнкция және бұл дизъюнкцияның - ші орнында ( ) не айнымалысының не өзі, не оның терістеуі тұрса.

3. А- ның барлық конъюнктивті мүшелері өзара әр түрлі.

Мысалдар. - МДҚФ

- МДҚФ емес.

Берілген формулаға эквивалентті МДҚФ, МКҚФ табу есептерін шешу үшін , алдымен буль функциясы үшін Шеннон жіктеуін қарастырамыз.

Шеннон жіктелулері.

Кез келген Буль функциясы Шеннон жіктелуі түрінде өрнектеледі. Мысалы, 000, 010, 011 құрамаларында 1-ге тең болсын. Олай болса, жіктелуі: = ; Осыған ұқсас 0-ге тең емес функциялары төмендегідей болып жіктеледі:

Бұл формулалардан төмендегі теореманы келтіруге болады.

Теорема. Кез келген Буль функциясын өрнектейтін формула табылады Егер

болса оны МДҚФ түрінде өрнектейтін жалғыз ғана формула бар.

Егер болса оны МКҚФ түрінде өрнектейтін жалғыз ғана формула бар.

Мысалы, ақиқаттық кестемен берілген функциясының МДҚФ, МКҚФ табу керек. Функцияның толықтығы туралы теорема бойынша

x 0 0 0 0 1 1 1 1 y 0 0 1 1 0 0 1 1 z 0 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1

-МДҚФ; -МКҚФ

Сонымен МДҚФ , МКҚФ - белгілері.

1. дизъюнкцияның (конъюнкцияның ) мүшелері әр түрлі

2. конъюнктердің (дизъюнктердің ) мүшелері әр түрлі

3. бір де бірі конъюнкте (дизъюнкте)айнымалының әрі өзі ,әрі оның терістеуі бірге болмайды.

4. Әрбір конъюнктің (дизъюнктің ) құрамында формулаға енетін барлық айнымалылар болуы керек, яғни х₁^ х₂^...  х₃^ мұндағы х_і^ не өзі , не .

Мысалы, -өрнегі формуласының – дизъюнктивті қалыпты формаларының бірі. Бұл МДҚФ-ң алдыңғы үш талабын қанағаттандырады, ал төртіншісін қанағаттандырмайды. Сондықтан оған түрлендірулер жүргіземіз ( көбейтміз).

Кез келген F (х₁,х₂...х_n ) формуласын МДҚФ (МКҚФ ) түріне келтіру үшін мына ережені қолдануға болады.

1. F (х₁,х₂...х_n ) формуласын қандайда бір дизъюнктивті (конъюнктивті) қалыпты формаға түрлендіру.

2. Егер конъюнктке қандай да бір айнымалы өзінің терістеуімен бірге кірсе оны ДҚФ- тан жою керек. (х   0)

3. Егер конъюнктке бір литер х^ бірнеше рет кірсе, олардың біреуін ғана қалдырып калғандарын қысқарту керек. (х  х х)

4. Егер конъюнктердің біріне ( ) y айнымалыc кірмей тұрса, онда бүл конъюнктті оған эквивалентті формуламен алмастырамыз да, дистрибутивті заңды (x (yz)) = xy  xz қолданып ДҚФ түріне келтіреміз. Егер толық емес конъюнкт бірнешеу болса олардың әрқайысысы үшін сәйкес формуласын қосамыз.

5. Алынған ДҚФ- да бірдей бірнеше конъюнктер болса олардың ( х х) біреуін ғана қалдырамыз.Нәтижесінде МДҚФ шығады.

Мысалы, ДҚФ –ны МДҚФ-қа түрлендіру керек.

КҚФ-ны МКҚФ түрлендірудің алгоритмі де осындай. Мысал арқылы көрейік. формуланы МКҚФ ға келтіру керек болсын.

1. Формуланы қандайда бір конъюнктивті қалыпты формаға (КҚФ) келтіреміз.

2). Бірдейлерін жоямыз. Айнымалының терістеуімен бірге қатысып тұрған конъюнкция мүшесі, 3 қайталанып тұрған конъюнкция мүшесі 1 мен 4.

9-дәрістің тақырыбы: Предикаттар алгебрасы

Жаспары:

1.Предикат ұғымы. Квантор ұғымы.

2. Предикаттар алгебрасының формулалары.

3. Еркін және байланған айнымалылар

4. Тұйық формулалар. Предикаттар алгебрасының заңдары. Қалыптаспаған нормалдық форма.

Предикаттар. Негізгі түсініктер.

Предикат түсінігі пікірлер түсінігінің жалпылауы болып табылады. Математикада анықталған тұжырымның ақиқат немесе жалған екендігі оның құрамындағы айнымалыға тәуелді болатын сөйлемдер тжиі кездеседі.

Мысалы: 1) «х+2=5» , х Z

2) «n-жай сан»

3) «х өзені Байкал көліне құяды»

осы пікірлердің әрқайсысы, айнымалының орнына қандай-да бір нақты мәнді қойғаннан ақиқат немесе жалған пікірге айналады.

1 анықтама. М₁,…,М_n жиындарында анықталған n орынды предикат деп, құрамында х₁,…,х_n айнымалылардың орнына сәйкес М₁,…,М_n жиындарынан кез келген нақты мәндерді қойғаннан пікірге айналатын сөйлемді айтады.

Белгіленуі Р(х₁,…,х_n).

х₁,…,х_n – заттық айнымалылар, М₁,…,М_n жиындаының элементтері – нақты айнымалылар деп аталады.

М₁,…,М_n жиындарында анықтылған n орынды Р(х₁,…,х_n) предикат n аргументті функция болып табылады. Предикат – функция-пікір деп те аталады.

Мысалы: «х²+у²≤9» - екі орынды предикат. RxR жиынында берілген.

(2;1) «2²+1²≤9» - ақиқат

(3;3) «3²+3²≤9» - жалған.

Предикаттар классификациясы

2 анықтама. М₁,…,М_n жиындарында анықталған Р(х₁,…,х_n) предикат:

1. егер х₁,…,х_n айнымалылардың орнына М₁,…,М_n жиындарынан сәйкес а₁,…,а_n нақты айнымалыларды қойғаннан Р (а₁,…,а_n) ақиқат пікірге айналса, онда ақиқат предикат деп аталады;

2. Р (а₁,…,а_n) жалған пікірге айналса, жалған предикат деп талады;

3. Орындалатын предикат (жалған да, ақиқат та)болса; Мысалдар.

1) R жиыныда анықталған бір орынды предикат «sin²x+cos²x=1», -ақиқат.

2) R- жиыныда анықталған «х²+у²<0»-екі орынды предикат жалған.

3) «х өзені Байкал көліне құяды» - бір орынды предикат - орындалатын, себебі берілген предикатты ақиқат пікірге айналдыратын басқа да, өзен (Баргузин) бар және жоққа шығарылатын, себебі «Ангара» жалған пікірге айналдырады.

Анықтама: М₁,…,М_n жиындарында анықталған Р (х₁,…,х_n) предикаттың ақиқиттық жиыны деп берілген предикат х₁=a_1, х₂=a_2,…, х_n=a_n мәндерінің орнына қойғанда Р (х₁,…,х_n) пікірі ақиқат болатындай реттелген (а₁,…,а_n) n-жүйелер жиынтығы аталады. Мұндағы, а₁ М₁, …, а_n М_n. Бұл жиын Р⁺ деп белгіленеді.

Мысалдар:

1) R жиынында берілген екі орынды S (х,у): «х²+у²=9» предикаттың ақиқаттық жиыны, центрі координаталар бас нүктесінде орналасқан және радиусы 3-ке тең шеңбер бойында орналасқан жазықтықтағы нақты сандардың қостар жиыны.

2) А (х): « »-R гі бір өлшемді предикат.

А⁺=

М₁,…,М_n жиындарында берілген Р (х₁,…,х_n) n- орынды предикат:

1. ақиқат

2. жалған Ø

3. орындалатын Р⁺ Ø

4. жоққа шығарылатын

Предикаттарға қолданылатын кванторлық операциялар

Предикаттарға пікірлерге қолданылатын ( ) амалдардан басқа, олардан өзгеше басқа амалдар қолдануға болады.

Бұл – предикаттарға қолданылатын екі квантолық операциялар: жалпылау кванторы және табылу кванторы.

Бір орынды предикаттан пікір алу үшін, оның айнымалысының орнына предикаттың берілген облысынан бір мәнді қою керек.

Осылайша айналдырудың тағы бір тәсілі бар – бұл предикатқа жалпылау кванторымен және табылу кванторымен байланыстыру операциясын қолдану.

Бұл операциялардың әрқайсысы бір орынды предикатқа, берілген предикатқа тәуелді ақиқат немесе жалған мән қабылдайтын пікірді сәйкестендіреді (яғни бір орынды предикат нөлдік предикатқа айналады).

Анықтама: Жалпылау кванторымен байланыстыру операциясы деп, М жиынында анықталған әрбір бір орынды Р (х) предикатқа деп белгіленетін пікірді сәйкестендіретін ережені атайды. ( «барлық х үшін Р (х) орындалады» деп оқылады),

Бұл пікірлердің логикалық мәндері келесі формула бойынша анықталады:

Мысал. - ақиқат предикат

N сандар жиыныда –жоққа шығарылатын предикат

жалпылау кванторымен байланыстыратын операция, бірінші жағдайда ақиқат пікір, ал екінші жағдайда жалған пікірге айналады.

Қорытынды: егер берілген предикат М жиынының барлық элеметтеріне ақиқат болса, онда жалпылау кванторымен байланыстырғаннан:

р (х) оны ақиқат пікірге айналдырады.

Бұл жерде х айнымалысы «байланысты» болады, кәдімгі мағынадағы айнымалы болмайды.

Анықтама: Табылу кванторымен байланыстыру операциясы деп, М жиыныда анықталған әрбір бір орынды Р (х) предикатқа ( х)(Р(х)) деп белгіленетін пікірді сәйкестендіретін ережені атайды. ( «Р(х) орындалатындай, х табылады» деп оқылады), Бұл пікірлердің логикалық мәндері келесі формула бойынша анықталады:

Мысал: Р (х): «х=х+1» - жалған предикат

- орындалатын предикат

табылу кванторымен байланыстыратын операция, бірінші жағдайда жалған пікір, ал екінші жағдайда орындалатын пікірге айналады.

Қорытынды: егер берілген предикат М жиынының кем дегенде х М бір элементі үшін ақиқат болса, онда табылу кванторымен байланыстырғаннан: р (х) оны ақиқат пікірге айналдырады.

Бұл амалдардың ерекшеліктері.

а) логикалық операциялар бір немесе бірнеше предикаттарға жаңа предикаттар сәйкестендірді, ал квантолық операциялар бір орынды предикатқа пікірді сәйкестендіреді.

б) егер бірорынды Р(х) предикат М={a₁,…,а_k} ақырлы жиында берілсе, онда пікірі

Р (а₁) … Р (а _k) конъюнкцияға эквивалентті

( х)(Р(х)) пікірі

Р (а₁) … Р (а _k) дизъюнкцияға эквивалентті

10-дәрістің тақырыбы: Модель ұғымы.

Жаспары:

1. Формуланы мәндеу. Орындалатын, ақиқат және жалған фориулалар.

2. Кванторлы эквивлент формулалар. Квантролы формулалар үшін де Морган заңдары.

3. Предикаттар алгебрасының математикалық теорияларда қолдануы.

4. Формалды теория ұғымы. Қорыту және оның қасиеттері

Ақиқат кесте бойынша берілген Буль функциясына формула құру әдісі.

Буль функцияларының түйіндестік принципі. (1сағ).

Тұжырымдар логикасының әрбір формуласына ақиқат кесте құруға болатынын білеміз. Керісінше қалай? Керісінше де яғни ақиқат кесте бойынша формула құруға болатынын көреміз.

Айталық n айнымалыдан тәуелді буль функциясы ақиқат кестемен берілсін. Буль функциясының кесте түрінен формулаға көшудің алгоритмі. 1.Кестеден функцияны 1-ге айналдыратын аргументтерге сәйкес құрамалар алынады (асты сызылады).

2. Осы құрамаларға сәйкес конъюнкция жазамыз. Егер х_і аргументінің құрамадағы мәні 1-ге тең болса ол конъюнкцияға өзгеріссіз енеді,ал х_і=0, болса конъюнкцияға оның терістеуі алынады.

3. Алынған барлық конъюнкциялардың дизъюнкциясы іздеген формула болады және ол құрылған функцияның МДҚФ-ы болады.

Мысалы, f (x₁ ,x₂,x₃ )= (3,4,6) f (x₁ ,x₂,x₃ )= (0,2,5,7)

3,4,6-құрамалардың нөмірлері 0,2,5,7- құрамалардың нөмірлері

1 2 3 f (x1 ,x2,x3) 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 F=( )

x1 x2 x3 f(x1 ,x2,x3) 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 F=( )

Ақиқаттық кесте бойынша МКҚФ құрудың алгоритмі. Алгоритмді f (x₁ ,x₂,x₃ )= (0,3,7)

функциясына МКҚФ құруға қолданайық.

1.Кестеден функцияны 0-ге айналдыратын аргументтерге сәйкес құрамалар алынады(асты сызылады). 2. Осы құрамаларға сәйкес дизъюнкция жазамыз. Егер хі аргументінің құрамадағы мәні 0-ге тең болса ол конъюнкцияға өзгеріссіз енеді, ал хі=1, болса конъюнкцияға оның терістеуі алынады. 3. Алынған барлық дизъюнкциялар конъюнкциямен жалғастырылады.

x1 x2 x3 f(x1 ,x2,x3) 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0

Анықтама Егер f^* (x₁,x₂,…,x_n) = онда f*(x₁,x₂,…,x_n) функциясы f(x₁,x₂,…,x_n) функциясына түйіндес функция деп аталады. f(x₁,x₂,…,x_n) функциясына түйіндес функцияны анықтау үшін, барлық айнымалылар және функцияның өзін оның қарама-қарсы мәндеріне ауыстыру керек.

мысал. Үш айнымалыдан тәуелді функциясын буль формуласы яғни МДҚФ- түрінде өрнектеу керек.

0	0	0	1	0	0	0	1
0	0	1	1	0	1	0	1
0	1	0	0	1	0	0	0
0	1	1	0	1	1	1	1
1	0	0	1	1	1	0	0
1	0	1	1	1	1	0	0
1	1	0	0	0	1	1	1
1	1	1	0	0	1	1	1

Іздеп отырған МДҚФ =

Түйіндестік принципі: Егер f функциясын өрнектейтін F формуласындағы барлық операция белгілерін түйіндес функцияның операция белгілеріне алмастырғаннан алынған F* формуласы берілген f функциясының түйіндес функциясын өрнектейтін болады.

Тек , , а, ж символдарымен ғана байланысқан формулаларды қарастырамыз. , , а, ж символдары бір біріне түйіндес деп аталады.

Мысалдар: ақиқат– формуласының түйіндесі - жалған;

1: х  ж; : х  а;

f2 : х  ж  ж; : х а  а;

3 = ;

; ;

Егер f₁, f₂ функциялары тең болса, онда оларға сәйкес түйіндес формулалар да тең болады. онда . Түйіндестік принцип дизъюнкция, конъюнкция, терістеу арқылы байланысқан формулалармен берілген функциялардың түйіндестерін табу үшін ыңғайлы. Бұл жағдайда берілген формулада конъюнкция дизъюнкцияға, дизюнкция конъюнкцияға ауысады. Сөйтіп ДҚФ – КҚФ, КҚФ- ДҚФ, МДҚФ – МКҚФ немесе керісінше.

Мысалы: (

Егер  формуласы  - ге эквивалент болса:    онда оларға сәйкес түйіндес формулалар да эквивалентті болады ,яғни *  * болады.Егер f* (x₁,x₂,…,x_n) = f(x₁,x₂,…,x_n) онда f(x₁,x₂,…,x_n) функциясы өзіне-өзі түйіндес функция деп аталады.Мысалы,   xy  xz  yz функциясы өзіне өзі түйіндес функцияны кескіндейді. Оған (б₁,б₂,б₃) және (1-б₁, 1-б₂ , 1-б₃) жиынтықтарының қарама-қарсы мәндерінде функция да қарама қарсы мән қабылдайтындығына көз жеткізуге болады. Ол үшін ақиқаттық кесте құрып:

X	0	0	0	0	1	1	1	1
Y	0	0	1	1	0	0	1	1
Z	0	1	0	1	0	1	0	1
	0	0	0	0	0	1	1	1

= ; ;

; ;

екендігін көреміз.

Мысал: Түйідестік принципіне сүйене отыра, буль алгебрасындағы түйідестік принципінің дұрыстығын дәлелдеу керек. Буль алгебрасында үш амал бар: ;

Буль алгебрасының әр бір амалына түйіндес амалдарды анықтайық.

а) Айталық, болсын. Олай болса ;

б) Айталық, ; Олай болса ;

в) Айталық, ; Олай болса ;

Сонымен конъюнкция дизъюнкцияға, дизъюнкция конъюнкцияға түйіндес, ал терістеу өзіне өзі түйіндес.

Негізгі әдебиет: 1[49-54]; 2[192-197].

Қосымша әдебиет: 7[50-80] .

Бақылау сұрақтары:

1. Қандай функциялар бір-біріне түйіндес деп аталады? Мысал келтіріңіз.

2. Ақикаттық кесте бойынша формула құру ережелері

Предикаттық алгебрасының негізгі формулалары.

1. Предикаттар алгебрасының негізгі теңмағыналылық (НТМ)

2. Немесе негізгі жалпы мәнділілік(НЖМ) формулалары.

3. Негізгі теңмағыналылық (НТМ) формулаларының тізімі.

4. ІІ. Кванторлады коньюнция мен диэьюнкциялар арқылы көшіру заңдары.

5. ІІІ. Кванторларды имплакация арқылы көшіру заңдары

Квантор амалы жбір орынды предикаттар үшін қашанда орындалатынын теорема ретінде дәлелдеуге болатын төмендегі предикаттық формулалар тізімін предикаттар алгебрасының негізгі заңдары немесе предикаттың негізгі теңмағыналылық немее жалпымәнділілік формулалары деп атайды.

Негізгі теңмағыналылық (НТМ) формулаларының тізімі.

І. Кванторларды терістеу заңдары

ІІ. Кванторлады коньюнция мен диэьюнкциялар арқылы көшіру заңдары.

Мұндағы Q – нөл орынды предикат

немесе пікірлік айнымалы

ІІІ. Кванторларды имплакация арқылы көшіру заңдары

Мұндағы Q – нөл орынды предикат

ІV. Жалпылық кванторын шеткерілеу бармыстық

кванторын енгізу заңдары.