Әож 378(075. 8): 51 Логикалық формулаларда минимизациялау амалдарын орындаудың ондық сандар тәсілі Байжұманов А. А

Булдік функцияларды тиімді қысқарту (минилизациялау) мәселелері барлық уақытта актуал болып келген [1,2,3]. Бірақ логикалық өрнектерді қысқартуда қандай әдіс қолданған жөн? Қарастырылып жатқан жұмыста осы мәселеге ондық сандар тұрғысынан зерттеу жүргізілген.

Кез келген D ондық санды (1) қосынды ретінде жазып алу мүмкін. Мұнда және нің қалдық мүшесі. Ал ондық санның екілік жиындағы мәні.

(1) қосындыны ретінде белгілейміз. Бұл жерде және болған сан, мұнда

Айталық, және ондық сандар болсын, мұнда.

Анықтама:санды және ондық сандарының қиылысы деп айтылады, егер болса

Анықтама: кестені базистік кесте деп айтамыз, егер ге дейін болған барлық ондық сандардың қиылысы алдын ала берілген болса.

Ал, кестенің элементтері р-мәнді сандар деп айтылады. арқылы кестенің элементтерін белгілейміз (). Осы базистік кесте көмегімен р санға дейін болған, ондық сандардың қиылысу мәндері оңай табылады. Тағы да барлық уақыт екендігі айқын.

Кезектегі кестеде

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 8 8 8 8 8 8 8 8

1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 9 0 1 0 1 0 1 0 1 8 9 8 9 8 9 8 9

2 0 0 2 2 0 0 2 2 0 0 2 2 0 0 2 2 10 0 0 2 2 0 0 2 2 8 8 10 10 8 8 10 10

3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 11 0 1 2 3 0 1 2 3 8 9 10 11 8 9 10 11

4 0 0 0 0 4 4 4 4 0 0 0 0 4 4 4 4 12 0 0 0 0 4 4 4 4 8 8 8 8 12 12 12 12

5 0 1 0 1 4 5 4 5 0 1 0 1 4 5 4 5 13 0 1 0 1 4 5 4 5 8 9 8 9 12 13 12 13

6 0 0 2 2 4 4 6 6 0 0 2 2 4 4 6 6 14 0 0 2 2 4 4 6 6 8 8 10 10 12 12 14 14

7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Енді ,,

Мұнда сандарда қарастырамыз және - лар D₁ және D₂ сандарының р санына біртіндеп бөлінгенінен қалған қалдық мүшелер. Осы жерден әрбір қалдық мүшеге, қашан болғанда р-мәнді базистік кестенің қиылысуы сәйкес келеді, яғни _Vq

Сол секілді санның болған қиылысулар жиынын табу мүмкін.

Егер П (D₁, D₂) арқылы D₁ және D₂ ондық сандардың қиылысуын белгілесек, онда С саны кезектегі формула арқылы табылады:

Мұнда базистік кестенің өлшемі П (D₁, D₂) санның табылуына әсер етпейді. Сондықтан р-санды өз қалауымызша алуымыз мүмкін. Бірақта кестенің үлкеюі қосынды дәрежесі m нің азаюына алып келеді. Тағыда базистік кестелер диагональ бойынша симметриялы екендігін атап өткен жөн, яғни П (D_1, D₂)=П (D₂, D₁).

Енді х айнымалыға байланысты болған Х жиынынан алынған К элементар конюнкцияны қарастытырамыз (мұнда Х логикалық алгебраның барлық элементар коньюнкциялар жиыны).

Бұл жерде ǿ, ǿ ǿ екендігі айқын.

Осы жерден W айнымалылар жиынына тиісті болған әрбір топты

ретінде Бінар вектор көмегімен кезектегідей белгілеп алуымыз мүмкін:

Осы жердегі векторының бірлер санының мөлшер деп атаймыз және оны арқылы белгілейміз. Егер -ді екілік сан ретінде берілген деп қабылдасақ, онда оны өте оңай ондық санға өткізуге болады: r(W)=

Айталық, a=r(W ),b=r(W ) және c=r(W)болсын. Осы жерден екендігі айқын.

Тағыда а,в,с сандар К-элементар конъюнкцияны бір мәнді анықтайды. Сонымен бірге (а,в), (а,с),(в,с) жуптықтар К-элементар конъюнкцияға сәйкес келеді.

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

Айталық (а_1,в₁,с₁) және (а₂,в₂,с₂) сандар К₁ және К₂ элементар коньюнкцияларға сәйкес ондық сандар коды болсын.

1. К₁ және К₂ э.к.–лар ортогонал болмаған, яғни К_1* К₂≠0 болған элементар коньюнкиялар болса, онда П(b₁,c₂)=П(b₂,c₁)=0 шарт орындалады.

2. К₁ элементар конъюнкция К₂ элементар конъюнкцияны жұтады, егер және теңдіктер орынды болса.

3. К_1, К₂ элементар конъюнкциялар желімденеді, егер:

орындалса, мұнда бүтін оң сан, -набордың мөлшері.

Айталық, және болсын, онда коньюнкцияға сәйкес келетін ондық үштік сан кезектегідей табылады:

4.К₁ және К₂ э.к.үшін жалпы түрдегі желімдеу амалы қолданылады, егер

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

5. К₁ және К₂ элементар конъюнкциялары көрінісінде бейнеленеді, егер немесе болса.