Өлшемі: px

Әсерді келесі беттен бастау:

транскрипт

1 Дәріс 2. Функционалдық элементтердің (ФЭҚ) кейбір негіздегі схемалары. Схеманың күрделілігі мен тереңдігі. Мысалдар. DNF арқылы SFE синтезі әдісі. Дәріс беруші – доцент Светлана Н.Селезнева Дискретті математикадан дәрістер 2. 1 курс, 141 топ Ломоносов сайтындағы дәрістер

2 Функционалдық элементтерден алынған схемалар Функционалдық элементтерден алынған тізбектерді қандай да бір негізде анықтайық. Логикалық функциялардың кейбір жиынын берейік B = (g 1 (x 1,..., x n1),..., g s (x 1,..., x ns)) P 2, мұндағы n 1, .. ., n s 0. Бұл жиынды базис деп атаймыз. Назар аударыңыз, бұл базис ұғымы логика алгебрасында қарастырылған P 2 базис ұғымымен ешқандай байланысы жоқ. Әдетте, стандартты B 0 = (x&y, xy, x) негізін қарастырамыз.

3 Функционалдық элементтер тізбегінің анықтамасы В 0 = (x&y, x y, x) негізіндегі функционалдық элементтер тізбегі (SFE) 1) бағытталған ациклдік граф G = (V, E), оның әрбір шыңы v V d (v ) екіден (d (v) 2) аспайтын дәрежесі бар; 2) дәрежесі 0 (d (v) = 0) тең әрбір v шыңы кіріс (немесе тізбек кірісі) деп аталады және оған кейбір логикалық x i айнымалысы тағайындалады; 3) барлық басқа төбелер (кірістерден басқа) тізбектің ішкі шыңдары деп аталады;

4 Функционалдық элементтерден тізбекті анықтау (жалғасы) 4) дәрежесі 1 (d (v) = 1) тең әрбір v шыңына (функционалдық) терістеу элементі тағайындалады; мұндай шыңдардың барлығы инверторлар деп аталады; 5) дәрежесі 2 (d (v) = 2) тең әрбір v шыңына не (функционалдық) конъюнкция элементі & немесе (функционалдық) ажырату элементі тағайындалады; конъюнктураның элементтері тағайындалған барлық төбелер конъюнкторлар деп аталады, дизъюнкция элементтері тағайындалған барлық төбелер ажыратқыштар деп аталады;

5 Функционалдық элементтерден схеманың анықтамасы (жалғасы) 6) сонымен қатар кейбір шыңдарға жұптық әр түрлі шығыс айнымалылары y 1,..., y m тағайындалады. Егер кірістері тек x 1,..., x n айнымалылары тағайындалған және y 1,..., y m шығыс айнымалыларымен берілген CFE S берілсе, онда бұл CFE-ді S(x 1,) арқылы белгілейміз. .., x n ;y 1,..., ym).

6 SFE мысалы 1-мысал. SFE S(x 1, x 2, x 3 ; y 1, y 2, y 3):

7 SFE мысалы 1-мысал. Әдетте, SFE келесідей бейнеленген S(x 1, x 2, x 3; y 1, y 2, y 3):

8 CFE күрделілігін анықтау CFE S күрделілігі L(S) осы CFE ішкі шыңдарының саны болып табылады, яғни. SFE SFE-дегі функционалдық элементтердің саны.

9 SPE күрделілігі 2-мысал. SPE S күрделілігі:

10 CFE төбесінің тереңдігін анықтау Индукция арқылы CFE S ішіндегі v шыңының d(v) тереңдігін анықтаймыз. 1. Индукция негізі. SPS әрбір v кірісінің 0-ге тең тереңдігі бар: d(v) = Индуктивті өту. 1) Егер v 1 төбесінен доға инверторға v CFE S апарса, онда d(v) = d(v 1)) v 1 және v 2 төбелерінен доғалар конъюнкторға немесе v CFE S ажыратқышына апарса, онда d (v) = max(d(v 1), d(v 2)) + 1. CFE S тереңдігі D(S) оның шыңдарының тереңдіктерінің максимумы.

11 SPE тереңдігі 3-мысал. SPE шыңының тереңдігі S және SPE тереңдігі S:

12 SFE қызметін анықтау SFE әрбір шыңында белгілі логикалық функция орындалады (немесе есептеледі). Индукция арқылы біз CFE S төбесінде орындалатын логикалық функцияны анықтаймыз. 1) Егер v кіріс шыңы болса және оған x i айнымалысы тағайындалған болса, онда f v = x i функциясы v шыңында жүзеге асырылады. . 2) Егер v 1 төбесінен доға v инверторға апарса, және f v1 функциясы v 1 шыңында жүзеге асса, онда f v = f v1 функциясы v шыңында жүзеге асады. 3) Егер v 1 және v 2 төбелерінен доғалар конъюнкторға (немесе дизъюнкторға) v әкелсе және f v1 және f v2 функциялары сәйкесінше v 1 және v 2 төбелерінде орындалса, онда f v = f v1 &f функциясы v2 v шыңында жүзеге асырылады (тиісінше f v = f v1 f v2).

13 МКҚК қызметі SFE S(x 1,..., x n ; y 1,..., y m) өзінің шығыс шыңдарында y іске асырылған логикалық функциялар жүйесін F S = (f 1,..., f m ) жүзеге асырады деп есептеледі. 1,..., ym.

14 SFE функциясының жұмысы 4-мысал. SFE S төбелерінде орындалатын логикалық функциялар: F S = (x 3, x 1 x 2, x 1 x 2 x 3 ).

15 Сызықтық бағдарлама B 0 = (x&y, xy, x) негізіндегі x 1,..., x n кірістері бар сызықтық бағдарлама z 1, z 2,..., z t тізбегі болып табылады, онда әрбір j саны үшін , j = 1,..., t, 1) не z j = x i ; 2) k үшін не z j = z k< j; 3) либо z j = z k &z l при k, l < j; 4) либо z j = z k z l при k, l < j. Линейная программа последовательно вычисляет значения z 1,..., z t как функции булевых переменных x 1,..., x n.

16 CFE және сызықтық бағдарламалар CFE-дегі есептеуді сызықтық бағдарлама түрінде қайта жазуға болатыны анық. Және керісінше, әрбір сызықтық бағдарлама белгілі бір CFE ретінде ұсынылуы мүмкін.

17 SFE және сызықтық бағдарламалар 5-мысал. SFE S z 1 = x 1 &x 2, z 2 = x 3, z 3 = z 1 z 2 сызықтық бағдарламасына сәйкес келеді.

18 SFE және олардың сипаттамалары Функционалдық элементтердің схемалары есептеу моделі болып табылады. Біз енгізген SPE сипаттамалары есептеу тиімділігінің әртүрлі аспектілерін көрсетеді. SFE күрделілігі дәйекті есептеу уақытына сәйкес келеді. SPE тереңдігі параллельді есептеу уақытына сәйкес келеді. CFE-де бірдей тереңдіктегі шыңдардың максималды саны параллельді есептеудегі процессорлар санына сәйкес келеді.

19 Мысал: екі бит қосындысы 6-мысал. Екі х және у биттерінің қосындысын жүзеге асыратын (есептейтін) стандартты негізде SFE құрыңыз. Шешім. Екі х және у биттерінің қосындысының кестесін жазайық. Бұл қосынды екі екілік цифры бар сан болуы мүмкін, сондықтан x + y = 2z 1 + z 0 болатындай екі логикалық z 0, z 1 айнымалысын енгіземіз: x y z 1 z

20 Мысал: екі бит қосындысы Шешімі (жалғасы). Сонда z 0 = x y, z 1 = xy болады. x y = (x y) (x y) екенін ескере отырып, біз CFE аламыз: L(S 1) = 3, және D(S 1) = 3 екені анық.

21 ерікті негізде CFE Сол сияқты, еркін негіздегі CFE түсінігі B P 2 енгізілген.

22 Мысал: үш биттің қосындысы 7-мысал. Үш x, y және z биттерінің қосындысын жүзеге асыратын (есептейтін) P2 2 (яғни екі айнымалыға байланысты барлық логикалық функциялардан) негізінде SFE құрыңыз.

23 Мысал: үш бит қосындысы Шешімі. 6-мысал сияқты, үш бит x, y және z қосындысының кестесін жазамыз. Бұл қосынды екі екілік цифры бар сан да болуы мүмкін, сондықтан x + y + z = 2u 1 + u 0 болатындай u 0, u 1 екі логикалық айнымалысын енгіземіз: x y z u 1 u

24 Мысал: үш бит қосындысы Шешімі (жалғасы). Сонда u 0 = x y z, u 1 = xy xz yz. xy xz yz = xy z(x y) екенін ескере отырып, біз CFE аламыз: L(S) = 5, ал D(S) = 3 екенін көреміз.

25 CFE логикалық функциясын жүзеге асыру B 0 = (x&y, x y, x) негізінде CFE еркін логикалық функциясын (немесе логикалық функциялар жүйесін) жүзеге асыру мүмкін бе? мүмкін. Мұны қалай ақтауға болады? Мысалы, иә. Өйткені (x&y, x y, x) P 2 жүйесінде толық жүйе, ерікті логикалық f функциясын тек конъюнкция, дизъюнкция және терістеу арқылы формуламен көрсетуге болады. Мысалы, мінсіз DNF түрінде, егер f 0 болса және x & x түрінде, егер f = 0 болса. Содан кейін осы DNF (формула) көмегімен сәйкес CFE құрастырыңыз. Бульдік функциялар үшін SFE құрудың бұл әдісі DNF синтез әдісі деп аталады.

26 DNF арқылы CFE синтезі n айнымалыға байланысты логикалық функция f (x 1,..., x n) үшін DNF бойынша CFE S қандай күрделілікте болады? f функциясы үшін тамаша DNF ең көбі 2 n элементар конъюнктураны қамтиды. Әрбір элементар конъюнктура n айнымалының конъюнкциясы немесе олардың терістеулері болып табылады.

27 DNF арқылы SFE синтезі Сондықтан схемада: x 1,..., x n айнымалылардың барлық терістеулерін жүзеге асыру үшін n инверторлар болады; (n 1) конъюнктор арқылы мінсіз DNF-де ең көбі 2 n элементар қосылыстардың әрқайсысын жүзеге асыру үшін; DNF элементар конъюнкцияларының дизъюнкциясын жүзеге асыруға арналған ең көбі (2 n 1) дизъюнктор. L(S) n + (n 1) 2 n + (2 n 1) n 2 n + n болатынын аламыз.

28 Логикалық функцияның күрделілігі CFE класындағы f (x 1,..., x n) логикалық функциясының L(f) күрделілігі f функциясын жүзеге асыратын барлық CFE арасындағы ең аз күрделілік болып табылады. Осылайша, біз теореманы дәлелдедік: Теорема 1. Ерікті функция үшін f (x 1,..., x n) P 2, L(f) n 2 n + n ақиқат.

29 Тапсырма тәуелсіз шешім 1. Логикалық функциясы үшін f (x 1, x 2, x 3) = () стандартты күрделілік негізінде CFE құру. Буль функциясы үшін f (x 1, x 2, x 3) = () CFE-ді стандартты күрделілік негізі функциялары f (x 1, x 2, x 3, x 4) = x 1 x 2 x 3 x 4 стандартты тереңдік негізінде SFE құру Стандартты негізде L(x y) = 4 екенін дәлелдеңіз.

30 4-дәріске арналған әдебиеттер 1. Яблонский С.В. Дискретті математикаға кіріспе. М .: Жоғары мектеп, V бөлім, ch. 2, Гаврилов Г.П., Сапоженко А.А. Дискретті математикадағы тапсырмалар мен жаттығулар. Мәскеу: Физматлит, Ч. X 1.1, 1.5, 1.7, 1.17, 1.18.

31 Дәрістің соңы 4

Дәріс: Кешіктірілген функционалдық элементтердің сұлбалары (КЭЖ), оларды бейнелеудің автоматизмі. ҚАВ АЭА өкілдігі. CAV жеңілдетулері. CAV күйлерінің ерекшелігі және ажыратылмауы. Мур теоремасы

Дәріс: n өлшемді кубты тізбектерге бөлу туралы Ансель теоремасы. Логика алгебрасының монотонды функцияларының саны туралы теорема. Логика алгебрасының монотонды функцияларын ашу туралы теорема. Дәріс беруші – доцент Селезнева Светлана

Дәріс: Шығарылатын ақырлы автоматтар (КАВ). Автоматтың функциялары, оларды тағайындау әдістері. Периодтық тізбектерді автоматтық функциялар арқылы түрлендіру туралы теорема. Дәріс беруші – доцент Светлана Николаевна Селезнева

Дәріс: Жартылай реттелген жиынтықтар (POS). CHUM диаграммасы. Ең үлкен, ең кіші, ең үлкен және ең кіші элементтер. Шынжырлар мен қарсы шынжырлар, оба соңының ұзындығы мен ені. ПЛ-ны антитізбектерге бөлу теоремасы.

Дәріс 2. Биномдық коэффициенттердің қасиеттері. Қорытындылау және функцияларды құру әдісі (соңғы жағдай). Көпмүшелік коэффициенттер. Биномдық және көпмүшелік коэффициенттерді бағалау. Бағалау сомасы

Дәріс: П к-та толықтықты тану алгоритмі. жабық сабақтар. Жиындарды сақтайтын және бөлімдерді сақтайтын функциялар кластары, олардың тұйықтығы. Кузнецовтың функционалдық толықтық туралы теоремасы. Сабақтарды алдын ала аяқтау.

Дәріс 2. Комбинаторика. Биномдық коэффициенттердің қасиеттері. Қосындыларды санау және функцияларды құру әдісі. Көпмүшелік коэффициенттер. Биномдық және көпмүшелік коэффициенттерді бағалау. Асимптотикалық

Дәріс: Ақырлы мәнді функциялар. Элементар к-мәнді функциялар. k-мәнді функцияларды көрсету жолдары: кестелер, формулалар, 1-ші және 2-ші формалар, көпмүшелер. Толықтық. Пост жүйесінің толықтығы туралы теорема. Webb функциясы.

Дәріс 3. Қайталанатын қатынастар арқылы анықталатын тізбектер. Біртекті және біртекті емес сызықтық қайталанатын теңдеулер (LORU және LNRU). Жалпы шешімдер LORA және LNRU. Дәріс беруші – доцент Селезнева Светлана

Дәріс 15. Ақырғы мәнді логикалардың функциялары. k-мәнді логиканың элементар функциялары. k-мәнді логикалық функцияларды көрсету әдістері: кестелер, формулалар, I және II пішіндер, көпмүшелер. Толықтық. Дәріс беруші – доцент Селезнева

Дәріс: Ақырғы шамалар логикасының функциялары. k-мәнді логиканың элементар функциялары. k-мәнді логикалық функцияларды көрсету әдістері: кестелер, формулалар, I және II пішіндер, көпмүшелер. Толықтық. Дәріс беруші – доцент Селезнева Светлана

Дәріс: CCM-дегі Мобиус функциясы. n-өлшемді текшедегі Мобиус функциясы. Мобиус инверсия формуласы. Қосу-шығару принципі. Орын ауыстыру-бұзылыстар санын санау мәселесі. Дәріс беруші – доцент Селезнева Светлана

Дәріс 2. Биномдық коэффициенттердің қасиеттері. Функцияларды генерациялау әдісі, қосындыларды есептеу және сәйкестендіруді дәлелдеу. Көпмүшелік коэффициенттер. Қосу-шығару принципі. Дәріс беруші – доцент Селезнева Светлана

Дәріс: Маңызды функциялар. Маңызды функциялар туралы үш лемма. Яблонскийдің толықтық критерийі. Слупецкий толықтық критерийі. Шеффер функциялары. Оқытушы доцент Светлана Николаевна Селезнева [электрондық пошта қорғалған]

Дәріс: Негізгі комбинаторлық сандар. Комбинаторлық сандарды бағалау және асимптотика. Оқытушы – доцент Светлана Николаевна Селезнева, М.В. Ломоносов http://mk.cs.msu.su сайтындағы дәрістер

Дәріс: Биномдық коэффициенттердің қасиеттері. Қорытындылау және функцияларды құру әдісі (соңғы жағдай). Көпмүшелік коэффициенттер. Биномдық және көпмүшелік коэффициенттерді бағалау. Биномдық қосындыларды бағалау

Дәріс: Шығарылатын соңғы автоматтар. Шығарылатын соңғы автоматтар арқылы периодтық тізбектерді түрлендіру. Шығарылымы бар ақырлы автоматтардағы күйлердің айырмашылығы. Машиналарды жеңілдету. Оқытушы Селезнева

Дәріс: Мұқаба мен матрицалық қақпақ. Градиентті қамту. Градиентті жабу леммасы. n-өлшемді текшенің көлеңкелеу жиынының күрделілігіне арналған бағалаулар. Функциялардың көпмүшелік қалыпты формаларының ұзындығын бағалау

Дәріс 5. Жабдық және матрицалық қақпақ. Градиентті қамту. Градиентті жабу леммасы. Буль текшесінің көлеңкелеу жиынының негізгілік көрсеткіштері. Көпмүшелік логикалық қалыпты пішіндердің ұзындығын бағалау

Дәріс 3. Қайталанатын қатынастар арқылы анықталатын тізбектер. Біртекті және біртекті емес сызықтық қайталанатын теңдеулер (LORU және LNRU). LORU және LNRU ортақ шешімдері. Мысалдар Оқытушы – доцент Селезнева

Дәріс 3. Жиындардағы қатынастар. Қасиеттер. Қосу-шығару формуласы. Эквиваленттік қатынас. Жартылай реттілік қатынасы. Дәріс беруші – доцент Светлана Н. Селезнева Дискретті модельдер бойынша дәрістер.

Дәріс 4. Көп мәнді логиканың ерекшеліктері. Жабық сынып, жабық сыныптың негізі. Янов пен Мучниктің көп мәнді логикадағы негізі жоқ жабық сыныптардың және есептелетін жабық кластардың болуы туралы теоремалары.

Дәріс. Табиғи аргументтің функциялары (тізбегі). Біртекті және біртекті емес сызықтық қайталанатын теңдеулер (LORU және LNRU). LORU және LNRU ортақ шешімдері. Мысалдар Оқытушы – доцент Светлана Селезнева

Дәріс: Графиктің хроматикалық саны. Екі түсті графиктің критерийі. Графиктің хроматикалық санының жоғарғы және төменгі шекаралары туралы теоремалар. Дәріс беруші – доцент Светлана Н. Селезнева Дискретті модельдер бойынша дәрістер.

Дәріс: Графиктер және желілер. q шеттері бар псевдографтар санының болжамы. q шеттері бар ағаштар санының болжамы. Жазық графиктер. Жазық графиктерге арналған Эйлер формуласы. Жазық графиктердегі шеттердің ең көп саны. жоспарлы емес

Дәріс 1. Комбинаторика. Орналастырулар, ауыстырулар, қайталанулары бар орналастырулар, комбинациялар, қайталанулары бар комбинациялар. Олардың саны. Оқытушы – доцент Светлана Н.Селезнева Математикалық кибернетика кафедрасы

Дәріс: Тізбектер. Біртекті және біртекті емес сызықтық қайталанатын теңдеулер. Сызықтық қайталанатын біртекті және біртекті емес теңдеулердің жалпы шешімдері. Дәріс беруші – доцент Светлана Николаевна Селезнева

Дәріс 8. Бояу беттері. Топқа қатысты бояулардың теңдігі. Функцияларды құру. Фигуралар үшін санау қатары және функциялар үшін санау қатары. Поя теоремасы. Дәріс беруші Селезнева Светлана Николаевна

Дәріс: Бояу. Пермутация тобына қатысты бояулардың баламалылығы. Поля теоремасы (ерекше жағдай). Функцияларды құру. Фигуралар үшін санау қатары және функциялар үшін санау қатары. Теорема

Дәріс 2. Жалғау қалыпты формалар. Имплицент, функцияның жай имплиценті. Логика алгебрасының қысқартылған CNF функциялары. Қысқартылған CNF құру әдістері. Дәріс беруші Селезнева Светлана Николаевна [электрондық пошта қорғалған]

Математикалық модельдер және VLSI логикалық синтез әдістері Күз 2015 Дәріс 4 Дәріс жоспары Комбинациялық логикалық оңтайландыру логикалық схемалар Әртүрлі жолдарлогика алгебрасының функцияларын ұсыну (FAL)

Дәріс: Шығарылымсыз детерминирленген емес ақырлы автоматтар (NFA). Шекті детерминирленген және ақырлы детерминирленген емес автоматтар рұқсат еткен сөздер жиынының класстарының сәйкестігі туралы теорема. Процедура

Дәріс 1. Таңдамалар. Орналастырулар, ауыстырулар, қайталанулары бар орналастырулар, комбинациялар, қайталанулары бар комбинациялар, олардың саны. Мысалдар. Дәріс беруші – доцент Светлана Николаевна Селезнева Дискретті курс бойынша лекциялар

Дәріс 1. Комбинаторлық объектілер: таңдаулар, орналастырулар, ауыстырулар, қайталанулары бар орналастырулар, комбинациялар, қайталанулары бар комбинациялар, олардың саны. Комбинаторлық сандар: факторлық, кемімелі факторлық, биномдық

4-ДӘРІС ФУНКЦИОНАЛДЫҚ ЭЛЕМЕНТТЕРДЕН АЛЫНҒАН СҰЛБАЛАР 1. Негізгі анықтамалар Ең алдымен композицияны қарастыру қажет. Функция кірісі мен шығысы бар «қара жәшік» ретінде ұсынылуы мүмкін. Болсын

Дәріс 2. П к-та толықтықты тану алгоритмі. Кузнецов теоремасы. жабық сабақтар. Жиынды сақтайтын функциялар кластары. Бөлімді сақтайтын функциялар кластары. Сабақтарды алдын ала аяқтау. Лектор Селезнева

Дәріс 3. Жегалкин көпмүшесі. Жегалкин функциясының көпмүшелігін құру әдістері. Сызықтық имплицентті функция. Сызықтық конъюнктивтік қалыпты форма (LCNF). Барлық сызықтық имплицентті функцияларды табу. Емтихан

Дәріс 2. Генераторлық функциялар: комбинаторлық қосындыларды санау және сәйкестендірулерді дәлелдеу, комбинаторлық объектілерді тізімдеу. Қосу-шығару принципі. Орын ауыстыру-бұзылыстар санын санау. Лектор -

Дәріс 5. Графиктер. Графикалық бояу парақтары. Графиктің хроматикалық саны. Графиктің бихроматтық критерийі. Графиктің хроматикалық санының жоғарғы шекаралары. Лектор Селезнева Светлана Николаевна [электрондық пошта қорғалған]Дәрістер

Дәріс: Шығармасыз ақырлы автоматтар (ҚА) (шекті автоматтар-танғыштар). Өтпелі диаграммалар. Автомат жинақтары (тілдер). Автомат жиындарының қасиеттері туралы лемма. Автоматты емес жиынтықтың мысалы. Лектор

Дәріс 1. Ақырлы мәнді функциялар. Элементар k-мәнді функциялар. k-мәнді функцияларды көрсету жолдары: кестелер, формулалар, 1-ші және 2-ші формалар, көпмүшелер. Толықтық. Пост жүйесінің толықтығы туралы теорема. Webb функциясы.

Дәріс 7 Ұшуды бөлу тапсырмасының графикалық моделі. Графиктің хроматикалық саны. Графиктің екі түсті болу шарты.

01.02.09.01 мамандық студенттеріне арналған «Кибернетика негіздері» курсы (математикалық және бағдарламалық қамтамасыз етукомпьютерлер) 1. жалпы ақпарат(оқу жүктемесі, бақылау нысандары және т.б.). Курс

Дәріс 6. Графиктер. Графиктердің тұқым қуалайтын қасиеттері. Тұқым қуалаушылық қасиеті бар графиктердегі жиектер санын бағалау. Экстремалды графиктер. Берілгені бар жазық және үшбұрышсыз графиктердегі шеттердің ең көп саны

Math-Net.Ru Бүкілресейлік математикалық порталы Д.С.Романов, Тұрақты ұзындықтағы бірліктерді тексеру сынақтарын рұқсат ететін оңай тексерілетін схемаларды құрастыру әдісі, Diskr. Мат., 2014, 26 том, 2 шығарылым,

Дәріс: Шығарусыз, детерминирленген және детерминирленген емес ақырлы автоматтар. Шекті детерминирленген және детерминирленген емес автоматтар рұқсат ететін сөздер жиынының класстарының сәйкестігі туралы теорема. Процедура

Практикалық жұмыс 2 Логикалық функцияның қалыпты формаларын құру Жұмыстың мақсаты: Логикалық функцияның конъюнктивтік, дизъюнктивтік, толық қалыпты формаларын құруды үйрену Жұмыстың мазмұны: Негізгі

Логикалық функциялардың күрделілігі бойынша семинар Дәріс 1: Кіріспе А. Куликов POMI информатика клубы http://compsciclub.ru 09/25/2011 09/25/2011 1 / 26 Дәріс жоспары 1 Бульдік функциялар 2 Буль схемалары 3 Дерлік

Практикалық жұмыс 1 Логикалық және релелік басқару жүйелерін талдау және синтездеу

Дәріс: Тұрақты өрнектержәне тұрақты жиынтықтар. Автомат жиындары мен тұрақты жиындардың класстарының сәйкестігі туралы Клин теоремасы. Дәріс беруші – доцент Светлана Николаевна Селезнева Дискретті математикадан дәрістер

Дәріс 3 Буль алгебралары және логикалық функциялар Буль алгебралары Алгебралық жүйелер туралы түсінік Алгебралық жүйенемесе алгебралық құрылым, берілгені бар кейбір алфавиттің (тасымалдаушының) таңбалар жиынтығы

Дәріс 5. Графиктер. Графиктерді қолдану мысалдары. тасымалдау міндеті. Желідегі ағын, желідегі максималды ағынның мәні туралы Форд және Фулкерсон теоремасы. Желідегі максималды ағынды құру алгоритмі. Лектор

Дәріс: Графиктер. Графиктерді қолдану мысалдары. тасымалдау міндеті. Желідегі ағын, желідегі максималды ағынның мәні туралы Форд және Фулкерсон теоремасы. Желідегі максималды ағынды құру алгоритмі. Лектор -

8-сабақ Ерікті A және B жиындары үшін A B = (x x A және x B) жиындары бар екенін еске түсірейік; (А және В қиылысы) A B = (x x A немесе x B); (А және В бірігуі) A \ B = (x x A және x / B) (A және B айырмашылығы).

Дәріс 7. Рэмси сандары. Рэмси санының жоғарғы шегі. Рэмси санының төменгі шегі. Дәріс беруші Селезнева Светлана Николаевна [электрондық пошта қорғалған]М.В. атындағы Мәскеу мемлекеттік университетінің ЦМК профессорлық-оқытушылық құрамы. Ломоносов http://mk.cs.msu.ru сайтындағы дәрістер

Дәріс: Графиктер. Негізгі ұғымдар. Қосылған графиктер. Ағаштар. Негізгі ағаш. Ағаштағы ілулі шыңдардың саны. Дәріс беруші – доцент Светлана Н. Селезнева Дискретті модельдер бойынша дәрістер. магистратура,

Дәріс 11. Бульдік схемалар. Дискретті математика, HSE, информатика факультеті (2014 жылдың күзі, көктемі 2015 ж.) x 1,..., x n айнымалылардағы буль тізбегі — g логикалық функцияларының тізбегі

бойынша проректор БЕКІТІЛДІ академиялық жұмысЮ.А.Самарский 10 маусым 2008 ж. ДИСКРЕТТІК ҚҰРЫЛЫМДАР курсының БАҒДАРЛАМАСЫ МЕН ТАПСЫРМАЛАРЫ 010600 Жоғары температура және деректерді талдау институтының факультеті Деректерді талдау курсы II семестр 4 Екі

Мәскеу Мемлекеттік университетіЛомоносов атындағы М.В. Есептік математика және кибернетика факультеті С.А.Ложкин ДИСКРЕТТІ БАСҚАРУ ЖҮЙЕЛЕРІНІҢ СИНТЕЗІ ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТТЕРІ Мәскеу 2016 Мазмұны

Дәріс: Графиктердің тұқым қуалаушылық қасиеттері. Экстремалды графиктер. Рэмси сандары. Оқытушы – доцент Светлана Николаевна Селезнева, М.В. Ломоносов http://mk.cs.msu.su сайтындағы лекциялар Тұқым қуалаушылық

Дәріс: Ақырлы автоматтар жиындарына амалдар. Автомат жиынтықтарының толықтырылуы, бірігуі, қиылысуы, туындысы және қайталануы, олардың автоматизмі. Дәріс беруші – доцент Светлана Николаевна Селезнева Дәрістер

министрлігі Ресей ФедерациясыБайланыс және ақпараттандыру Еділ мемлекеттік телекоммуникациялар және информатика академиясы Жоғары математика кафедрасы PGATI Әдістемелік кеңесімен бекітілген 29 наурыз 2002 ж.

Дәріс 5. Графиктердің шеттерін бояу. Графиктің хроматикалық көрсеткіші. Екі жақты графиктердің хроматикалық көрсеткіші. Графиктің хроматикалық индексінің жоғарғы және төменгі шекаралары. Дәріс беруші Селезнева Светлана Николаевна [электрондық пошта қорғалған]

Math-Net.Ru Бүкілресейлік математикалық порталы Н.П.Редькин, Бірыңғай диагностикалық қысқа сынақтарды қабылдайтын тізбектерде, Diskr. Мат., 1989, 1 том, 3 шығарылым, 71 76 Бүкілресейлік

МАТЕМАТИКАЛЫҚ ЛОГИКА(1) Тапсырмалар практикалық оқыту 1. Мәлімдемелердің алгебрасы Мәлімдеме екі мәнді қабылдай алатын мән: ақиқат және жалған. Мәлімдемелер бас әріптермен белгіленеді

Дәріс 2

(SFE) кейбір негізде. Күрделілігі мен тереңдігі

схема. Мысалдар. DNF арқылы SFE синтезі әдісі.

Дәріс беруші – доцент Светлана Николаевна Селезнева

«Дискретті математика 2» бойынша дәрістер.

1 курс, 141 топ,

М.В. атындағы Мәскеу мемлекеттік университетінің ЦМК профессорлық-оқытушылық құрамы. Ломоносов

http://mk.cs.msu.su сайтындағы дәрістер

SPE мысалдары DNP-дан SPE синтезі

Функционалдық элементтерден жасалған схемалар

Функционалдық элементтердің схемаларын қандай да бір негізде анықтайық.

B = (g1 (x1,..., xn1),..., gs (x1,..., xns)) P2, мұндағы n1,..., ns 0 логикалық функциялардың кейбір жиынын берейік.

Осы жиынды негіз деп атаймыз.

Бұл базис концепциясы логика алгебрасында қарастырылған Р2 базис ұғымымен ешқандай байланысы жоқ екенін ескеріңіз.

Ереже бойынша стандартты B0 = (x&y, xy, x ) негізін қарастырамыз.

SFE мысалдары DNF-тен SFE синтезі Функционалдық элементтерден тізбектің анықтамасы

1) G = (V, E) бағытталған ациклдік графы, оның әрбір v V шыңы екіден (d (v) 2) аспайтын d (v) дәрежесіне ие;

2) 0 (d (v) = 0) дәрежесіне тең әрбір v шыңы кіріс (немесе тізбек кірісі) деп аталады және оған кейбір логикалық айнымалы xi тағайындалады;

3) барлық басқа төбелер (кірістерден басқа) тізбектің ішкі шыңдары деп аталады;

4) дәрежесі 1 (d (v) = 1) тең әрбір v шыңына (функционалдық) терістеу элементі тағайындалады; мұндай шыңдардың барлығы инверторлар деп аталады;

5) дәрежесі 2 (d (v) = 2) тең әрбір v шыңына не (функционалдық) конъюнкция элементі & немесе (функционалдық) ажырату элементі тағайындалады; конъюнктураның элементтері тағайындалған барлық төбелер конъюнкторлар деп аталады, дизъюнкция элементтері тағайындалған барлық төбелер ажыратқыштар деп аталады;

CFE мысалдары DNF-тен CFE синтезі Функционалдық элементтерден тізбектің анықтамасы (жалғасы)

6) сонымен қатар кейбір шыңдарға жұптық әр түрлі шығыс айнымалылары y1,..., ym тағайындалады.

Кірістері тек x1,..., xn айнымалылары тағайындалған және y1,..., ym шығыс айнымалылары бар CFE S берілсе, онда бұл CFE-ді S(x1,...,) деп белгілейміз. xn ;y1,.. ., ym).

SPE мысалдары DNP-дан SPE синтезі

–  –  –

CFE төбесінің тереңдігін анықтау Индукция арқылы CFE S-дегі v шыңының d(v) тереңдігін анықтаймыз.

1. Индукцияның негізі. SPE S әрбір v кірісінің 0-ге тең тереңдігі бар: d(v) = 0.

–  –  –

SFE және олардың сипаттамалары Функционалдық элементтердің схемалары есептеу моделі болып табылады.

Біз енгізген SPE сипаттамалары есептеу тиімділігінің әртүрлі аспектілерін көрсетеді.

SFE күрделілігі дәйекті есептеу уақытына сәйкес келеді.

SPE тереңдігі параллельді есептеу уақытына сәйкес келеді.

CFE-де бірдей тереңдіктегі шыңдардың максималды саны параллельді есептеудегі процессорлар санына сәйкес келеді.

CFE мысалдары DNF-тен CFE синтезі Мысал: үш бит қосындысы Шешім. 6-мысал сияқты, үш бит x, y және z қосындысының кестесін жазамыз. Бұл қосынды екі екілік цифры бар сан да болуы мүмкін, сондықтан біз екі логикалық айнымалыны енгіземіз

x + y + z = 2u1 + u0 болатындай u0, u1:

–  –  –

Дәріске арналған әдебиеттер 4

1. Яблонский С.В. Дискретті математикаға кіріспе. М.:

Жоғары мектеп, 2001. V бөлім, Ч. 2, б. 336-355.

2. Гаврилов Г.П., Сапоженко А.А. Дискретті математикадағы тапсырмалар мен жаттығулар. М.: Физматлит, 2004. Ч. X 1.1, 1.5, 1.7, 1.17, 1.18.

SPE мысалдары DNP-дан SPE синтезі

Бульдік функцияларды формулалар арқылы көрсетуге келесі «инженерлік-конструктивті» мағына беруге болады. Біз «қара жәшік» ретінде кейбір ерікті бекітілген жиынның үстінен формуланы қарастырамыз, оның кірісіне айнымалы мәндердің барлық мүмкін жиындары және формуламен берілген функция мәндері беріледі. шығысында пайда болады (6.22-сурет).

«Қара жәшік» қалай жұмыс істейтінін түсіну үшін біз ішкі формулалардан формула құру процесін талдауымыз керек. «Негізгі» ішкі формулаларға жету, яғни. жиынтықтың элементтері , біз «кірпішке» келеміз, «қара жәшік» құрастырылған құрылымдық элементтер, ол функцияны есептейді . «Негіздің» әрбір функциясы біздің «қара жәшіктің» ең кіші құрылымдық бірлігі ретінде қарастырылатын сәйкес «түйінмен» есептеледі және оның ішкі құрылымыенді талданбайды.

6.22-мысал.Жиын ретінде стандартты негізді таңдайық. Содан кейін функцияны (эквивалентті) білдіретін стандартты негіздегі формула келесі түрде құрастырылады:

Осы формула бойынша есептеуді (және оны стандартты негіздің элементтерінен құрастыру процесі) суретте көрсетілгендей схемалық түрде бейнелеуге болады. 6.23.

Айнымалы (дәлірек айтқанда, осы айнымалының мәні) кіріске беріледі құрылымдық элемент, түрлендіргіш деп аталады (6.24, а-сурет) және терістеуді есептеу. Инвертордың шығысынан алынған терістеу, яғни. функциясы , конъюнктордың кірістерінің біріне беріледі (6.24.5-сурет), оның екінші кірісі айнымалымен қамтамасыз етіледі. Функция конъюнктордың шығысында пайда болады. Функцияның есептелуі де дәл осылай қадағаланады. Бұл функциялардың екеуі де ажыратқыштың кірістеріне беріледі (6.24, в-сурет), оның шығысынан функция жойылады (бұл 2 модулінің қосындысынан басқа ештеңе емес:). Ақырында, бұл функция инвертордың кірісіне беріледі, оның шығысында функция (эквиваленттілік) алынған.

Осылайша біз «схема» идеясына келеміз - математикалық модельЛогикалық функция калькуляторы, кейбір формуламен ұсынылған, құрылымдық элементтерден жинақталған, олардың әрқайсысы «негізгі» логикалық функциялардың бірін есептейді. Жалпы жағдайда «схема» логикалық операторды есептейді және осы оператордың әрбір координаталық функциясы схеманың шығыстарының бірінен алынады.

Математикалық тұрғыдан «сұлба» төбелері де, доғалары да кейбір белгілермен қамтамасыз етілген бағытталған графтың ерекше түрі ретінде анықталады.

Белгілеуді енгізейік: егер логикалық функциялардың кейбір жиыны болса, онда біз айнымалылардың барлық функцияларынан тұратын ішкі жиынмен белгілейміз.

Анықтама 6.14. Жиындар: (Логикалық функциялар) және (Логикалық айнымалылар) бекітілген болсын.

Функционалдық элементтердің базис үстіндегі тізбегі (CFE) немесе жай базис үстіндегі схема, сондай-ақ (F, X) - схемасы - контурсыз бағытталған график (яғни желі), оның әрбір төбесі белгіленеді. мыналар ақиқат болатындай жиынның элементтерінің бірі: талаптар:

1) желінің әрбір кірісі не -дан қандай да бір айнымалымен, не -ден кейбір тұрақтымен белгіленеді;

2) егер желінің v шыңы айнымалылар функциясымен белгіленсе (яғни ), онда оның кіру жарты дәрежесі -ге тең және төбеге кіретін доғалар жиынында (бірден-бірге) нөмірлеу беріледі. , онда әрбір доға 1-ден -ге дейінгі санды алады.

Тізбектерді бейнелеу кезінде кірістер шеңберлермен, ал кіріс болып табылмайтын шыңдар үшбұрыштармен белгіленеді, олардың ішінде берілген шыңды белгілейтін функцияның белгіленуі жазылады. Шығулар «шығыс» көрсеткілерімен белгіленеді. Суретте. 6.25 негізінде SFE көрсетеді.

Егер негіз тұспалданса, онда біз жай ғана «схема» деп айтамыз. Сонымен қатар, егер айнымалылар жиыны «бір рет және біржола» бекітілген болса және қарастыру кезінде әртүрлі схемаларбіз тек функциялар жиынын өзгертеміз, содан кейін формула және берілген негіз бойынша суперпозиция ұғымдарын енгізе отырып, біз әр жолы бір рет бекітілген айнымалылар жиынын білдіреді деп есептей отырып, негіз бойынша SFE туралы сөйлесеміз, бұл ( егер бұл дәлдікке зиян келтірмесе) айтылмайды.

Енді индукция арқылы тізбек төбесімен есептелетін логикалық функция ұғымын анықтайық.

Анықтама 6.15. төбелерінің жиыны болатын базис үстінде SFE берілсін.

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

2. Егер төбе функциямен белгіленсе, оған кіретін саны бар доға функцияны есептейтін шыңнан келеді, содан кейін v шыңы суперпозицияны есептейді.

Осылайша, егер CFE үстіндегі әрбір төбесі қандай да бір функцияны есептесе, онда орындалатын функциялардың тізімделу реті функцияның айнымалылары, жалпы жағдайда маңызды. Айнымалылардың логикалық функциясын ауыспалы деп атау заңды, егер ол айнымалылардың ерікті ауыстырылуы кезінде өз мәнін сақтайтын болса. Бұл жағдайда біз осындай функциямен белгіленген тізбек шыңына кіретін доғалардың нөмірленуіне мән бермеуіміз мүмкін.

6.23-мысал.Суреттегі SFE-ді қарастырайық. 6.25. Төбелері мен SFE кірістері болып табылады. Бұл шыңдар сәйкесінше және функцияларын есептейді. Содан кейін шыңы , сонымен қатар шыңы 6.15 анықтамасына сәйкес функцияны есептейді (Шеффер инсульт), ал шыңы (желі шығысы) функцияны есептейді, ол белгілі болғандай конъюнктураға тең .

SFE суретте көрсетілген. 6.26 екі шығысы бар, есептеу функциялары және .

Анықтама 6.16. логикалық функция, базис бойынша SFE есептеген, оның кез келген шығыстары арқылы есептелген функция.

Осылайша, SFE шығыстары бар логикалық функцияларды дәл есептейді. SFE сур. 6.25 бір функцияны есептейді, ал SFE күріш. 6,26 - екі.

Жалпы жағдайда, егер m шығысы бар базис үстіндегі тізбектің кірістері үшін белгілер ретінде қызмет ететін барлық айнымалылар жиыны болса, CFE логикалық текшені логикалық текшеге салыстыруды анықтайды, яғни. логикалық оператор.

Ескерту 6.10.Кейбір жағдайларда берілген CFE арқылы есептелетін функция таңдалған CFE шыңдарының ішкі жиынынан кез келген шыңы арқылы есептелетін функция деп есептесек, басқаша анықталады. Атап айтқанда, бұл шығу болуы мүмкін. Қалай болғанда да, схеманың таңдалған (жаңа көрсетілген мағынада) шыңдарынан «шығу» көрсеткісін салуға келістік.

Осылайша, функционалдық элементтердің әрбір тізбегі қандай да бір логикалық операторды есептейді, атап айтқанда, схеманың шығыстарының саны 1 болса, онда ол қандай да бір логикалық функцияны есептейді.

Керісінше де дәлелдеуге болады: кез келген логикалық оператор үшін SFE негізі негізінде құрастырылуы мүмкін, мұндағы осы операторды есептейтін толық жиынтық.

6.24-мысал.Кестені салыстыратын логикалық операторға орнатайық (6.9-кесте).

Кестеден оңай көруге болады (функция айнымалылардың көпшілік функциясынан басқа ештеңе емес және ол үшін ең аз DNF жоғарыда жазылған, 6.12 мысалды қараңыз). Функцияны Жегалкин негізінде көрсетейік. Де Морган заңдарын пайдалана отырып, біз аламыз

Соны ескерсек, бізде болады

Кестеде көрсетілген логикалық операторға арналған SFE. 6.9, Жегалкин негізіндегі суретте көрсетілген. 6.27.
SPV құрастырған кезде оның күрделілігі деп аталатын сандық параметрді есте ұстаған жөн.
SFE күрделілігі оның кіріс болып табылмайтын шыңдарының саны болып табылады.
Суретте көрсетілген. 6.27 Жегалкин негізіндегі CFE күрделілігі 5.

Енді стандартты негізде бір оператор үшін CFE-ді қарастырайық. Кестеге сәйкес (6.9 кестені қараңыз) функция үшін SDNF құрастырамыз

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

Бірақ сіз басқа жолмен жүре аласыз. Біз кестені қарастыра аламыз. 6.9 жартылай логикалық функцияны анықтайтын кесте ретінде. Суретте көрсетілген Карно картасына* сәйкес бұл функцияны азайту. 6.29, біз аламыз

*Бұл картада біз сәйкес ұяшықтарға нөлдерді қою арқылы функция 0 мәнін алатын жиындарды нақты белгіледік. Осылайша, біз нөлдерді сызықшалармен шатастырмау керек екеніне тағы да назар аударғымыз келеді: картаның ұяшығындағы сызықша ішінара функцияны анықтайтын бұл жиынтықфункцияның мәні анықталмаған, яғни. 0 де, 1 де емес.

Қарастырылып отырған логикалық оператор үшін стандартты негіздегі SFE суретте көрсетілген. 6.30. Бұл CFE күрделілігі 11. Функцияны бағалайтын түйін шығыс емес екенін ескеріңіз.

Бұл мысалда қарастырылған логикалық оператор бір таңбалы үш мүшенің екі таңбалы қосындысын (модуль 2) есептейді. Оны бірразрядты екілік қосқыш – көпразрядты екілік қосқыштың функционалды блогы – екі термин үшін де қарастыруға болады. Содан кейін r/1 функциясы ең маңызды битке «тасымалдау сигналы» ретінде түсіндіріледі. Суретте. 6.31 екі үш таңбалы санның қосындысын есептейтін үш SFE «қосылуын» көрсетеді (6.30-суретте көрсетілгендей). екілік сандар. Ең аз мәнді бит үшін қосқыштың үшінші кірісіне тұрақты 0 қолданылады, ал ең маңызды разрядтың «тасымалдау сигналы» жалпы жағдайда төрт таңбалы сан болатын қосындының ең маңызды биті болып табылады. .

31. Функционалдық элементтердің сұлбалары, құрылыс және пайдалану ережелері, sdnf және sknf негізіндегі sfe синтез әдісі.

Анықтама.Функционалдық элемент деп белгілі бір заңға сәйкес кірісте қабылдаған сигналдарды түрлендіргіштің шығысындағы сигналға түрлендіретін элементар дискретті түрлендіргіштің математикалық үлгісін айтады. Функционалдық элементтерден кейбір ережелердің көмегімен құрылымы мен жұмыс істеуі жағынан күрделірек модельдерді – функционалды элементтердің диаграммаларын құруға болады. Бұл модельдерде кіріс және шығыс сигналдары 0 және 1 символдарымен кодталады.

Құрылыс ережелері.Қарапайымдардан күрделі СПЕ алу үшін тізбектің кірісін немесе шығысын бөлу, тізбекке функционалды элементті қосу және функционалды элементті тізбектің кірісіне немесе шығысына қосу операциялары оларға дәйекті түрде қолданылады. Бұл операциялар суперпозицияны қолдану арқылы қарапайымдан күрделі формуланы алу ережелеріне ұқсайды.

SFE синтезі.Дизъюнкция, конъюнкция және терістеу формасынан бері толық жүйесыныпта Р 2 , содан кейін кез келген логикалық функциядан nаргументтер функционалдық элементтер тізбегі арқылы жүзеге асырылуы мүмкін - дизъюнкторлар, конъюнкторлар және инверторлар - бар nкіріс және бір шығыс. Ол үшін, мысалы, берілген логикалық функцияны SDNF немесе SKNF арқылы өрнектеп, содан кейін тізімде келтірілген бөлу, біріктіру және қосу операцияларын ретімен қолдана отырып, алынған формуланы функционалдық элементтер тізбегі түрінде «синтездеуге» болады. жоғарыда.

32. Әмбебап көпполюсті пайдалана отырып, барлық конъюнкцияларды ықшам жүзеге асыруға негізделген SPE синтез әдісі, алынған тізбектердің күрделілігі.

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

Логикалық функцияларды орнату үшін кестелерді, векторларды, формулаларды және графиктерді қолданамыз. Келесі белгілерді алайық: бұл барлық жиындардың жиыны, мұндағы.

Анықтама.Функционалдық элемент деп белгілі бір заңға сәйкес кірісте қабылдаған сигналдарды түрлендіргіштің шығысындағы сигналға түрлендіретін элементар дискретті түрлендіргіштің математикалық үлгісін айтады. Функционалдық элементтерден кейбір ережелердің көмегімен құрылымы мен жұмыс істеуі жағынан күрделірек модельдерді – функционалды элементтердің диаграммаларын құруға болады. Бұл модельдерде кіріс және шығыс сигналдары 0 және 1 символдарымен кодталады.

Әмбебап көп полюсті пайдалана отырып, барлық конъюнкцияларды ықшам іске асыруға негізделген SPE синтез әдісі. Бұл әдіс сонымен қатар функцияны SDNF түрінде көрсетуге негізделген, бірақ аз құрастыруға мүмкіндік береді күрделі схемаларжалғаулардың ықшам орындалуына байланысты. SDNF-де функцияның ыдырауы ортақ факторлары бар конъюнкцияларды қамтуы мүмкін. Егер осындай екі конъюнктура блоктағы бір ішкі схема арқылы орындалса, онда бұл үшін бірінші синтез әдісімен барлық конъюнкцияларды тәуелсіз орындау арқылы бұрынғы талап етілгеннен кем дегенде біреуі кем конъюнктор қажет болады. Ұзындықтың барлық мүмкін қосылыстарының жинақы орындалуы nиндуктивті түрде салынған әмбебап көп полюсті қолдану арқылы қол жеткізуге болады nкірістер және 2 n шығу, қайда n = 1,2,3,… Әдістің артықшылығы, әсіресе, бір тізбекті пайдаланып, бірнеше логикалық функциялар жүйесін жүзеге асыру қажет болғанда байқалады. Бұл жағдайда берілген жүйенің функцияларының SDNF құрамына кіретін конъюнкцияларға сәйкес келетін әмбебап көпполюстің сол шығыстарын бөлуге, содан кейін дизъюнкторлар арқылы өткізуге болады. Бұл берілген жүйенің әрбір функциясын өзінің ішкі схемасы дербес жүзеге асырғанға қарағанда, аз конъюнкторлармен жұмыс істеуге мүмкіндік береді.

Мұндай көп полюстің күрделілігі тең Л() =.

Функционалдық элементтердің тізбегі Σ дәл болса rфункционалдық элементтер болса, онда оның күрделілігі бар деп айтамыз rжәне оны теңдеу түрінде жазыңыз Л(Σ) = r.

Бульдік функцияларды формулалар арқылы көрсетуге келесі «инженерлік-конструктивті» мағына беруге болады. Ф(x 1 ,..., x n) формуласын F(x 1 ,..., x n) кейбір ерікті бекітілген F жиынына «қара жәшік» ретінде, кірісте айнымалы мәндердің барлық мүмкін жиынтықтарын қабылдайтын құрылғы түрін және мәндерді қарастырамыз. Осы жиындарға сәйкес келетін f функциясының шығуы Ф формуласымен берілген (6.22-сурет).

«Қара жәшік» қалай жұмыс істейтінін түсіну үшін біз ішкі формулалардан формула құру процесін талдауымыз керек. «Негізгі» ішкі формулаларға жету, яғни. F жиынының элементтері, біз «кірпіштерге», f функциясын есептейтін «қара жәшік» құрастырылған құрылымдық элементтерге келеміз. F «негізінің» әрбір функциясы біздің «қара жәшіктің» ең кіші құрылымдық бірлігі ретінде қарастырылатын сәйкес «түйін» арқылы есептеледі және оның ішкі құрылымы енді талданбайды.

6.22-мысал. F жиыны ретінде стандартты базисті таңдайық. Содан кейін ~ (эквиваленттік) функциясын білдіретін стандартты базис үстіндегі формула келесі түрде құрастырылады:

Осы формула бойынша есептеуді (және оны стандартты негіздің элементтерінен құрастыру процесі) суретте көрсетілгендей схемалық түрде бейнелеуге болады. 6.23.

Айнымалы x 1 (дәлірек айтқанда, осы айнымалының мәні) инвертор деп аталатын құрылымдық элементтің кірісіне беріледі (6.24-сурет, а) және есептелетін терістеу. Инвертордың шығысынан x 1 теріске шығару алынып тасталды, яғни. функциясы x 1, конъюнктордың кірістерінің біріне беріледі (6.24, б-сурет), оның екінші кірісі х 2 айнымалысымен қамтамасыз етіледі. Конъюнктордың шығысында x 1 x 2 функциясы пайда болады. Сол сияқты x 1 x 2 функциясының есебі қадағаланады.Бұл функциялардың екеуі де дизъюнктордың кірістеріне беріледі (6.24, в-сурет), оның шығысынан x 1 x 2 ∨ x 1 x 2 функциясы шығады. жойылады (бұл 2 модулі қосындысынан басқа ештеңе емес: x 1 ⊕ x 2). Ақырында, бұл функция инвертордың кірісіне беріледі, оның шығысында ~ функциясы (эквиваленттілік) алынған. #

Осылайша, біз «схема» идеясына келдік - бұл логикалық функция калькуляторының математикалық моделі, құрылымдық элементтерден жинақталған, кейбір формулалармен ұсынылған, олардың әрқайсысы «негізгі» логикалық функциялардың бірін есептейді. Жалпы жағдайда «схема» логикалық операторды есептейді және осы оператордың әрбір координаталық функциясы схеманың шығыстарының бірінен алынады.

Математикалық тұрғыдан «сұлба» төбелері де, доғалары да кейбір белгілермен қамтамасыз етілген бағытталған графтың ерекше түрі ретінде анықталады.

Белгілеуді енгізейік: егер F логикалық функциялардың кейбір жиыны болса, онда F (n) арқылы n айнымалының (n≥0) барлық функцияларынан тұратын F ішкі жиынын белгілейміз.

Анықтама 6.14.Жиындар бекітілген болсын: F (логикалық функциялар) және X (логикалық айнымалылар).

Базис бойынша функционалдық элементтердің схемасы F ∪ X (C F E), немесе жай ғана F ∪ X негізіндегі қысқарту, сондай-ақ (F,X) - схемасы контурсыз бағытталған график (яғни желі) деп аталады, оның әрбір төбесі элементтерінің бірімен белгіленеді. F U X параметрін келесі талаптарға сай етіп орнатыңыз:

1. желінің әрбір кірісі не X-тен қандай да бір айнымалымен немесе F (0) константасымен белгіленеді;
2. егер желінің v шыңы n айнымалының f функциясымен белгіленсе (яғни, f ∈ F (n)), онда оның дәрежесі n болады, ал v шыңына енетін доғалар жиынында ( әрбір доға 1-ден n-ге дейінгі сандарды алатындай нөмірлеу.

Егер негіз тұспалданса, онда біз жай ғана «схема» деп айтамыз. Сонымен қатар, егер айнымалылар жиыны «бір рет және мәңгілікке» бекітілген болса және әртүрлі схемаларды қарастырғанда, біз тек F функциялар жиынын өзгертеміз, онда формула мен суперпозиция ұғымдарын берілген негізге енгізген кездегідей, біз әр уақытты орнатудың F негізіндегі CFE туралы айтатын боламыз, бұл X айнымалыларының бір рет тіркелген жиынын білдіреді, ол (егер ол дәлдікке зиян келтірмесе) айтылмайды.

Енді ұғымды индукция арқылы анықтаймыз контур төбесімен есептелетін логикалық функция .

Анықтама 6.15. SFE берілсін С төбесінің жиыны V болатын F ∪ X негізінде.

1. Әрбір SFE кірісі таңбаланған логикалық функцияны есептейді деп болжанады (яғни, кейбір айнымалы немесе тұрақты).
2. Егер v ∈ V шыңы f ∈ F (n) функциясымен белгіленсе, оған енетін i (1≤i≤n) саны бар доға g i функциясын есептейтін u i ∈ V төбесінен келеді, онда v шыңы есептейді f(g 1 , ... ,gn) суперпозициясы.

Осылайша, егер F үстіндегі әрбір CFE шыңы қандай да бір функцияны есептейтін болса, онда f функциясының айнымалыларының орнына қойылған g 1 , ...,g n функцияларының тізімделу реті жалпы мәнді болады. n айнымалының f логикалық функциясын ауыспалы деп атау табиғи нәрсе, егер ол айнымалыларының ерікті ауыстырылуы кезінде өз мәнін сақтайтын болса. Бұл жағдайда біз осындай функциямен белгіленген тізбек төбесіне кіретін доғалардың нөмірленуіне мән бермеуіміз мүмкін.

6.23-мысал.Суреттегі SFE-ді қарастырайық. 6.25. v 1 және v 2 шыңдары SFE кірістері болып табылады. Бұл шыңдар сәйкесінше x және y функцияларын есептейді. Содан кейін v 3 шыңы, сондай-ақ v 4 шыңы 6.15 анықтамасына сәйкес x|y функциясын (Шеффер штрихы), ал v 5 шыңы (желі шығысы) (x|y)l( функциясын есептейді. x|y), ол x · y конъюнкциясына тең екені белгілі.

SFE суретте көрсетілген. 6.26, (x|x)|(y|y) = x ∨ y және (x|y)|(x|y) = x·y функцияларын есептейтін екі шығысы бар.

Анықтама 6.16. SFE арқылы есептелген логикалық функция F ∪ X негізінде, оның кез келген шығысымен есептелетін функция.

Осылайша, SFE дәл stmko логикалық функцияларды есептейді, оның қанша шығысы бар. SFE сур. 6.25 бір функцияны есептейді, ал SFE күріш. 6,26 - екі.

Жалпы, егер (x 1 ,..., x n ) - тізбек кірістері үшін белгілер ретінде қызмет ететін барлық айнымалылар жиыны С m шығысы бар F ∪ Х негізінде, CFE С логикалық текшені көрсетуді анықтайды Б n логикалық кубқа Бм, яғни. логикалық оператор.

Ескерту 6.10.Кейбір жағдайларда берілген CFE арқылы есептелетін функция таңдалған CFE шыңдарының ішкі жиынынан кез келген шыңы арқылы есептелетін функция деп есептесек, басқаша анықталады. Атап айтқанда, бұл шығу болуы мүмкін. Қалай болғанда да, схеманың таңдалған (жаңа көрсетілген мағынада) шыңдарынан «шығу» көрсеткісін салуға келістік. #

Осылайша, функционалдық элементтердің әрбір тізбегі қандай да бір логикалық операторды есептейді, атап айтқанда, схеманың шығыстарының саны 1 болса, онда ол қандай да бір логикалық функцияны есептейді.

Керісінше де дәлелдеуге болады: кез келген логикалық оператор үшін SFE F негізінде құрастырылуы мүмкін, мұндағы F берілген операторды бағалайтын толық жиынтық.

y 1 функциясын Жегалкин негізінде көрсетейік. Де Морган заңдарын пайдалана отырып, біз аламыз

(тең мүшелердің кез келген жұп санының 2 қосындысы 0 болатынын еске түсірейік).

y 1 \u003d x 1 x 2 ⊕ x 1 x 3 ⊕ x 2 x 3 \u003d x 1 x 2 ⊕ x 3 (x 1 ⊕ x 2).

Кестеде көрсетілген логикалық операторға арналған SFE. 6.9, Жегалкин негізіндегі суретте көрсетілген. 6.27.

SPV құрастырған кезде оның күрделілігі деп аталатын сандық параметрді есте ұстаған жөн.

SFE күрделілігі оның кіріс болып табылмайтын төбелерінің саны.

Суретте көрсетілген. 6.27 Жегалкин негізіндегі CFE күрделілігі 5.

Енді стандартты негізде бір оператор үшін CFE-ді қарастырайық.

Кестеге сәйкес (6.9 кестені қараңыз) y 2 функциясы үшін SDNF құрастырамыз:

y 2 \u003d x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3.

Бұл функция үшін Карно картасы суретте көрсетілген. 6.28 оны азайту мүмкін емес екенін көрсетеді (дәлірек айтқанда, жоғарыда жазылған SDNF бұл функция үшін ең аз DNF болып табылады). Бірақ сіз басқа жолмен жүре аласыз. Біз кестені қарастыра аламыз. 6.9 y 2 = y 2 (x 1 x 2 x 3 y 1) жартылай логикалық функцияны анықтайтын кесте ретінде. Бұл функцияны азайту арқылы

Карно картасы* суретте бейнеленген. 6.29, біз аламыз

* Бұл картада сәйкес ұяшықтарға нөлдерді қою арқылы функция 0 мәнін алатын жиындарды белгіледік. Осылайша, біз тағы бір рет нөлдерді сызықшалармен шатастырмау керек екеніне назар аударғымыз келеді: картаның ұяшығындағы жартылай функцияны анықтайтын сызықша функцияның мәні осы жиында анықталмағанын білдіреді, яғни. 0 де, 1 де емес.

y 2 \u003d x 1 x 2 x 3 ∨ y 1 (x 1 ∨ x 2 ∨ x 3).

Қарастырылып отырған логикалық оператор үшін стандартты негіздегі SFE суретте көрсетілген. 6.30. Бұл CFE күрделілігі 11. y 1 функциясын есептейтін түйін шығыс емес екенін ескеріңіз.

Бұл мысалда қарастырылған логикалық оператор бір таңбалы үш мүшенің екі таңбалы қосындысын (модуль 2) есептейді. Оны бірразрядты екілік қосқыш – көпразрядты екілік қосқыштың функционалды блогы – екі термин үшін де қарастыруға болады. Сонда y 1 функциясы жоғары ретке дейін «тасымалдау сигналы» ретінде түсіндіріледі. Суретте. 6.31-суретте екі үш таңбалы екілік сандардың қосындысын есептейтін үш SFE (6.30-суретте көрсетілгендей) «қосылуы» көрсетілген. Ең аз мәнді бит үшін қосқыштың үшінші кірісіне тұрақты 0 қолданылады, ал ең маңызды разрядтың «тасымалдау сигналы» жалпы жағдайда төрт таңбалы сан болатын қосындының ең маңызды биті болып табылады. .

Ескерту 6.11.Егер біз стандартты негізде SFE құрастыратын болсақ және оның күрделілігін азайтқымыз келсе, онда біз ең алдымен сәйкес минималды DNF құруымыз керек. Бұл жағдайда біз DNF-тің өзін азайтатын тағы бір критерийді - теріске шығарулар санын ескере аламыз. Барлық минималды (анықтама 6.6 мағынасында) DNF ішінен терістеу белгісінің астындағы айнымалылардың пайда болу саны ең аз болатынын таңдау керек. Минималды DNF негізінде құрылатын CFE күрделілігі тұрғысынан бұл «инверторлардың» санын азайтады - терістеу функциясымен белгіленген CFE шыңдары.

Мысалы, функция үшін, берілген картаКарно (6.32-сурет), x 1 x 2 x 4 және x 1 x 3 x 4 жай импликанттардан тұратын ядроға x 1 x 2 x 3 емес, қарапайым импликант x 2 x 3 x 4 қосу керек, өйткені оның құрамында негативтер жоқ.