Лекция Логикалық функциялардың қасиеттері. Екіленген ( қосалқы) функциялар. Буль функцияларын айнымалылар бойынша жіктеу. КдқФ және ккқФ лар
жүктеу/скачать 38,22 Kb.
|
4-лек.МЛДМ
- Бұл бет үшін навигация:
- 3. КДҚФ және ККҚФ лар 1. Екіленген (қосалқы) функциялар Анықтама
- 2. Буль функцияларын айнымалылар бойынша жіктеу
|
4-лекция Логикалық функциялардың қасиеттері. 1. Екіленген ( қосалқы) функциялар. 2. Буль функцияларын айнымалылар бойынша жіктеу . 3. КДҚФ және ККҚФ лар 1. Екіленген (қосалқы) функциялар Анықтама. формулаға тең болған функция функциясына екіленген деп айтылады. Бұл жерде болғаны себебінен функциясы функциясының бейнелеуін анықтайды. Сонда болады. Анықтамадан жиын үшін төмендегілерді көру қиын емес, яғни: 0 функциясы 1 дің екіленген функциясы, 1 функциясы 0 дің екіленген функциясы, х функциясы х тің екіленген функциясы, ¬х функциясы ¬х тің екіленген функциясы, х1 & х2 функциясы х1 v х2 дің екіленген функциясы, х1 v х2 функциясы х1 & х2 дің екіленген функциясы. Екіленгендік анықтамасынан f** = ( f* )* = f екендігі келіп шығады, яғни екі рет екіленген функция өзіне тең. Екіленгендік ұстанымы. Егер A = C[f1 , f2 , … , fs ] формула f(x1,x2,…,xn) функциясын іске асырса, онда А формула да f1 , f2 , … , fs функцияларды сәйкес f1* , f2* , … , fs* функцияларға ауыстыру жолымен алынған С[ f1* , f2* , … , fs* ] формула f* функциясын іске асырады. Осы формуланы А ға екіленген формула деп айтамыз және А* арқылы белгілейміз. Демек А* = C[f1* , f2* , … , fs* ] . Осымен D={ 0,1,x,¬x, х1 & х2 , х1 v х2 } жиынындағы формулалар үшін екіленгендік ұстанымын төмендегідей қорытындылау мүмкін: А формулаға екіленген А* формуланы алу үшін, А формулада төмендегідей ауыстыруларды орындау жеткілікті: 0 ді 1 ге, 1 ді 0 ге, & ны v ға, v ны & ға немесе , егер А = C[0,1,x,¬x, х1 & х2 , х1 v х2 ] болса, онда A* = C[ 1, 0, x,¬x, х1 v х2 , х1 & х2 ] болады. Мысал: 1) A1 (х1 , х2 ) = х1 & х2 , A1* (х1 , х2 ) = х1 v х2 ; 2) A2 (х1 , х2 ) = х1х2 v ¬х1¬х2 , A2* (х1,х2 ) = (х1vх2 )(¬х1v¬х2 ). Анықтама: Егер f(x1,x2,…,xn) функция өзінің екіленген функциясына тең, яғни f(x1 ,x2,…,xn) = f*(x1,x2,…,xn) = ¬f(¬x1,¬x2,…,¬xn) болса, онда ол өздік екіленген функция деп айтылады. Өздік екіленген функцияларға мысалдар: x, ¬x, xy v xz v yz . Тағыда екіленгендік үстанымынан төмендегілер келіп шығады: Егер А(x1,x2,…,xn ) = B(x1,x2,…,xn ) болса, онда А*(x1,x2,…,xn ) = B*(x1,x2,…,xn ) болады. Мысалдар : 1) А(x1,x2,…,x5 ) = х1 x2 x3 v ¬ x1 ¬ x2 x3 v ( х1 x5 → x3 ¬ x4 ) v ¬ x3 ¬ x5 A(x1,x2,…,x5 ) = х1 x2 x3 v ¬ x1 ¬ x2 x3 v ¬(х1 x5 ) v x3 ¬ x4 ) v ¬ x3 ¬ x5 = = х1 x2 x3 v ¬ x1 ¬ x2 x3 v ¬х1 v ¬ x5 v x3 ¬ x4 v ¬ x3 ¬ x5 = х1 x2 x3 v ¬x1 v ¬ x5 v x3 ¬ x4 . Екіленгендік ұстанымына сәйкес : А* =( х1 v x2 v x3)¬x1¬ x5 (x3 v ¬x4 ) = ¬х1x3 ¬x5 v ¬x1 x3 x4¬ x5 = ¬х1x3 ¬x5 . A = ¬(х1 →х2 ) = ¬( ¬х1 v х2 ) = х1 ¬х2 ; A* = ¬¬(¬х1 →¬х2 ) = ¬х1 →¬х2 ) = х1v¬х2 . 3) A = х1 →¬х2 ~ х1 = х1 х2 ; A* = ¬(¬х1 →¬¬х2 ~ ¬х1 ) = х1 v х2 . 2. Буль функцияларын айнымалылар бойынша жіктеу Барлық логикалық алгебраның функциялары формулалар ретінде жазылуы мүмкінба? Осы мәселені шешуге әрекет жасаймыз. Белгілеу еңгіземіз: хσ = xσ v ¬x¬σ, σ = {0,1}. Бұл жерден ¬ х , егер σ = 0 болса, хσ = х , егер σ = 1 болса екендігі немесе текқана x=σ болғанда xσ = 1 екендігі келіп шығады. Теорема (Функцияларды айнымалылар бойынша жіктеу тұралы). Кез келген m(1 ≤ m ≤ n) үшін логикалық алгебраның барлық функцияларын төмендегідей түрде жазу мүмкін: f(x1,…,xm,xm+1,…,xn) = V x1σ1 &…& xmσm f(σ1,…, σm , xm+1,…,xn), (σ1,…,σm) бұл жерде дизъюнкция x1,…,xm айнымалылардың мүмкін болған барлық жиналымдары бойынша алынған. Бұл формула функцияны x1,x2,…,xm айнымалылар бойынша жіктеу деп айтылады. 1-салдар. Бір айнымалы бойынша жіктеу: f(x1,…,xn-1,хn) = xn& f(x1,…,xn-1,1) v ¬xn & f(x1,…,xn-1,0). Бұл жерде f(x1,…,xn-1,0) және f(x1,…,xn-1,1) функциялар жіктеу мушелері деп айтылaды. Мысал: 1)(((x1x2)+x1)+x2)=x2f(x1,1)v¬x2f(x1,0)=x2(x1+x1+1)v¬x2(x1+0)= x2vx1¬x2 ; 2) ¬{x1v[(x2 → x3)(x3 → x2)]} = ¬x1 & [¬(x2 → x3 ) v ¬(x3 → x2)] = = x3f(x1,x2,1) v x3f(x1,x2,0) = x3(¬x1 &¬(1→x2)) v ¬x3(¬x1 &¬(x2 →0)). Бұл формула {001,010} жиналымдарда ақиқат. 2-салдар. Барлық n айнымалылар бойынша жіктеу. f(x1,x2,…,xn) = V x1σ1 &…& xnσn f(σ1,…,σn) , (σ1,…,σn) f(x1,…,xn) ≠ 0 болғанда V x1σ1 &…& xnσn f(σ1,…,σn) = V x1σ1 &…& xnσn . (σ1,…,σn) (σ1,…,σn), f (σ1,…,σn)=1 Нәтижеде f(x1,x2,…,xn) = V x1σ1 &…& xnσn . (σ1,…,σn) f (σ1,…,σn)=1 Осылай жіктеу буль функциясының кемел дизъюнктивті қалыпты формасы(к.д.қ.ф.) деп айтылады. Мысал: ¬{x1v[(x2 → x3)(x3→x2)]} = ¬x1¬x2 x3 v ¬x1x2 ¬x3. 3 – теорема. Логикалық алгебраның барлық функцияларын кері функция, конъюнкция және дизъюнкция арқылы формулалар ретінде жазу мүмкін. Дәлелдеу: 1) Егер f(x1,x2,…,xn) ≡ 0 болса f(x1,x2,…,xn) ≡ x1 &¬ x1 деп жазу мүмкін. 2) Егер f(x1,x2,…,xn) ≠ 0 болса, онда f(x1,x2,…,xn) = V x1σ1 &…& xnσn (σ1,…,σn) f (σ1,…,σn)=1 болады. Теорема дәлелденді. Кез келген жуйеде берілген логикалық формуладан кемел дизъюнктивті қалыпты форманы құру үшін: 1) f(x1,x2,…,xn) функцияны немесе формуланың ақиқаттық кестесі құрылады; 2) кестеден f(σ1, σ2,…, σn) = 1 болған барлық (σ1, σ2,…, σn) жиналымдар жиыны белгілеп алынады; 3) белгілеп алынған жиналымдар үшін x1σ1 &…& xnσn логикалық көбейтулер, яғни қарапайым конъюнкциялар жазылады; 4) қарапайым конъюнкцияларды логикалық қосу (дизъюнкция) арқылы біріктіріп шығылады. Алынған формула f(x1,x2,…,xn) функцияның кемел дизъюнктивті қалыпты формасы болады. Бүл жерде x1σ1 &…& xnσn элементар конъюнкциялардың логикалық қосындысы v& типтегі өрнек кемел д.қ.ф.. болды. Ал кез келген логикалық фукнция &v типте жазылуы мүмкінба? Осының f ≠ 1 болғанда мүмкіндігін дәлелдейміз. Айталық f*≠ 0 және f*(x1,x2,…,xn) = V (x1σ1 &…& xnσn) болсын. σ1,…,σn) f* (σ1,…,σn)=1 Онда екіленгендік формуласына сайкес f**(x1,x2,…,xn) = & (x1σ1v…v xnσn) болады. (σ1,…,σn) f * (σ1,…,σn)=1 Екіленгендік принципі бойынша теңдіктің сол жағы f(x1,x2,…,xn) ке тең. Ал оң жағы & (x1σ1 v…v xnσn) = & (x1σ1 v…v xnσn) = & (x1¬σ1 v…v xn¬σn ) = (σ1,…,σn) (σ1,…,σn) (σ1,…,σn) f * (σ1,…,σn)=1 f * (¬σ1,…,¬σn)=0 f * (σ1,…,σn)=0 = f(x1,x2,…,xn). f(x1,x2,…,xn) = & (x1¬σ1 v…v xn¬σn ). (σ1,…,σn) f * (σ1,…,σn)=0 Бұл өрнек буль функциясының кемел конъюнктивті қалыпты формасы(к.к.қ.ф..) деп айтылады. Демек, буль фукнцияларының берілуін кестеден басқа, {¬,v,&} функциялар жиынындағы формулалар арқылыда оңай сипаттау мүмкін екен. жүктеу/скачать 38,22 Kb. Достарыңызбен бөлісу:
|