Нақты сандар облысында нольдің мынадай қасиеті бар екенін білеміз, ноль мен кез
жүктеу/скачать 1,67 Mb. Pdf көрінісі
|
| & &(¬а
ij v ¬ε i v ¬ε j ) = 1 . ( 4) i=1 j=1 Осы теңдеуден a ij =0 болғанда ¬ а ij v ¬ε i v ¬ε j = 1 теңдіктің барлық уақыт орындалуын байқаймыз, ал а ij =1 болғанда ¬а ij v ¬ε i v ¬ε j = ¬ε i v ¬ε j ақиқат. Сондықтан (4) шартты мынадай жазуға болады: & ( ¬ε i v ¬ε j ) = 1 aij=1 немесе F(Y 1 ,…,Y n ) = & ( ¬Ү i v ¬Ү j ), а ij =1 F( ε 1 ,…,ε n ) = 1. ( 5) Сонымен біз төмендегі тұжырымның ақиқат екендігін көрсеттік. Тұжырым: U V жиынның іштен тұрақты болуы үшін <ε 1 ,…,ε n > бағалар ( 1) шартты қанағаттандырғанда (5) теңдеудің орындалуы қажет және жеткілікті. D бграф төбелерінің максимал іштен тұрақты жиынын табу үшін төмендегідей амалдар орындалады: 1) F логикалық формуланы & және v үшін дистрибутивтік заңдар негізінде д.қ.ф.да бейнелейміз; 2) Осы д.қ.ф. да төмендегі теңдіктер негізінде мүмкін болғанша қысқарту амалдарын орындаймыз: Av(A&B)=A, AvA=A, A&A=A, ( 6) ABvA¬B=A, (AvB)&(AvC)&…&(AvD)=AV(B&C&…&D), бұл жерде A,B,C,…,D-логикалық алгебраның кез келген формуласы. 3) Табылған д.қ.ф. дағы әр бір ¬Үi 1 &¬Үi 2 &…&¬Үi k мүшеге максимал іштен тұрақты V \ {υ i1 , υ i2 ,…,υ ik } жиынды сәйкес қоямыз. Сонда –{j 1 ,…,j l }={1,2,…,n}\{i 1 ,…,i k }, k+l=n, U={υ j1 , υ j2 ,…,υ jl }. Сонымен Магу әдісі арқылы табылған кез келген жиын D бграф төбелерінің максимал іштен тұрақты жиыны болады және ол барлық максимал іштен тұрақты жиынды бейнелейді. |