Нақты сандар облысында нольдің мынадай қасиеті бар екенін білеміз, ноль мен кез
жүктеу/скачать 1,67 Mb. Pdf көрінісі
|
| &
t (x 1 v x 2 v …. v x n ) , бейнелеу арқылы алынған дизъюнктив қалыпты форма F(x 1 , x 2 , …. , x n ) функцияны толығымен іске асырады, мунда α i = σ j , i=1,2, …, t; j= 1,2, … , n . Дәлелдеу. Мұнда A 1 v A 2 v … v A l = 0 теңдік кез келген i (i=1,2, …, l ) үшін текқана A i =0 болғандаға орындалатындығын көру қиын емес. Сондықтан, егер ά i = ( α 1 , α 2 , …., α n ), α j {0,1}, i=1,2, … , t; жиналымдар жиыны ( 1) теңдеулер жүйесінің шешімі болса, онда ол FF(x 1 , x 2 , …. , x n ) = j=1 V t (x 1 & x 2 & …. &x n ) = 1 мұнда γ i = α i , γ i { 0,1} , x , егер γ =1 болса, x γ = ┐x, егер γ = 0 болса, теңдеудіңда шешімі болады, яғни F( ά i ) = 0 , FF (ά i ) = 1 . Осыдан ┐FF (ά i ) = 0 екендігі айқын және кез келген α E n 2 үшін F (x 1 ,x 2 ,…,x n ) = ┐FF(x 1 ,x 2 ,…,x n ) теңдік ақиқат. Сондықтан ┐FF = ┐(V(x 1 & x 2 &…& x n )) = &(x 1 v…vx n ), мұнда σ j i = ά j = ά j . Теорема дәлелденді. Айталық логикалық теңдеулер жиыны кезектегі түрде берілген болсын: A 1 (x 1 ,x 2 ,…,x n ) = α 1 A 2 (x 1 ,x 2 ,…,x n ) = α 2 - - - - - - - - - - - - - - A e (x 1 ,x 2 ,…,x n ) = α e мунда α 1 = α 2 =…= α e = 1, {x 1 ,x 2 ,…,x n } {0,1} = E 2 Онда кемел дизъюнктив қалыпты форманың қасиетіне сәйкес F(x 1 ,x 2 ,…,x n ) = V( x 1 x 2 …x n ) болатындығын көру қиын емес. Сондықтан кемел дизъюнктив қалыпты форма кемель конъюнктивті қалыпты формаға екіленген болғандықтан бұл қойылған екі мәселенің түп мағынасы логикалық алгебраның бір мәселесіне алып келеді. Ал ол кезі келгенде біреуі екіншісін толықтырғандықтан олардың сипатталу күрделік бағаларыда бірдей болады. Сонымен екі жағдайдада олардың күрделік бағалары L к (F) ≤ 2 n-1 болады. Бұл курделік баға кез келген кемел д.қ.ф. және кемел к.қ.ф. лар үшін өз сипатын сақтайды. Логикалық формулаларда кез келген функциялар қатысқан базистен D 1 = {x , x 1 & x 2 , x 1 v x 2 } немесе D 2 = {0,1, x 1 & x 2 , x 1 x 2 } базистерге ауыстыруда үлкен қиындықтар туады. Себебі әр бір формуланы ауыстырғанда олардың негізгі сипатын D 1 немесе D 2 базисте бейнелеу үшін көптеген амалдар орындалады. Сондықтан, ауыстырудың жалпы формулаларын қолдану өте тиімді нәтижелер береді. Кезектегі қарастырылатын теориялық жұмыстар D 2 базиске өту заңдылықтарына арналған. Кезектегідей белгілеулер енгіземіз: {A i } m - m реттік тізбекті эквиваленция амалы ; {A i } m - m реттік дизъюнкция амалы ~ 167 ~ {A i } m - m реттік mod 2 бойынша қосу амалы ; {A i } → m - m реттік импликация амалы; {A i } & m - m реттік конъюнкция амалы; {A i } // m - m реттік реттік Шеффер функциясы. Айталық {A i } o m = A 1 ◦ A 2 ◦ … ◦A m болсын, мұнда “о” белгісі жоғарыда көрсетілген функциялардың кез келгенін белгілейді. {A i } o1 m ≡ {A j *} o2 m1 көріністегі теңдік о 1 логикалық амалдан о 2 логикалық тізбекке ауыстыруды сипаттайды, мұнда i=1,2,…,m; j=1,2,…,m 1 ; m 1 = K o2 o1 (m) -теңдіктің оң жағындағы тізбекке қатысатын қарапайым конъюнкциялар (қ.к) саны; L o2 o1 (m) – {A j *} o2 m1 формуладағы барлық A i өрнектегі қатысатын айнымалылар саны; A i , A j * - қ.к.лар, о 1 және о 2 логикалық амалдар белгілері. Анықтама. {x i1 σ1 ∙ x i2 σ2 ∙…∙ x ie σℓ } реттегі э.к.лар жиынын іспеттес деп айтамыз, егер σ it = 1, σ jk = 0 , t = 1,2,…,q; k = q+1, q+2,…,ℓ болса, мұнда x ijk терістемелі айнымалылар деп айтылады, ал ℓ санын осы қ.к.ның рангі деп айтуға келісеміз. D 2 базиске ауыстыру критерийлері. жүктеу/скачать 1,67 Mb. Достарыңызбен бөлісу:
|