§ 5.10: Булева алгебра и теория множеств - Приднестровский государственный университет им. Т. Г. Шевченко инженерно-технический...
.RU

§ 5.10: Булева алгебра и теория множеств - Приднестровский государственный университет им. Т. Г. Шевченко инженерно-технический...


^ § 5.10: Булева алгебра и теория множеств

Определение 5.23: Всякая алгебра типа (2, 2, 1) называется булевой алгеброй, если ее операции удовлетворяют соотношениям (5.4)- (5.13)

В алгебре множеств элементарными являются подмножества универсального множества U (обозначим систему всех подмножеств U через, В(U)), операции & соответствует ,  соответствует ,  соответствует , единицей является само множество, а нулем - .

Булева алгебра на множестве Bn определяется следующим образом. Для любых векторов  = (1,.., n) и  = (1,..n).

   = (1  1,..., n  n)

 &  = (1 & 1,.., n & n)



Т.к. компоненты i и i векторов  и  принимают значение 0 и 1, то указанные операции - это просто логические операции над двоичными переменными; операции над векторами называются покомпонентными (поразрядными) логическими операциями над двоичными векторами. Такие операции входят в систему команд любой современной ЭВМ.

Например:  = (01011)  = (11010)

   = 01010

Теорема 5.9: Если |U| = n, то булева алгебра изоморфна булевой алгебре .

Эта теорема позволяет заменить теоретико-множественные операции над системой подмножеств подразрядными логическими операциями над двоичными векторами. Такая замена часто используется в программировании.

Рассмотрим теперь множество Р2 (m) всех логических функций m переменных х1,.., хm. Оно замкнуто относительно операций &    (результат их применения к функциям из Р2 (m) снова дает функцию из Р2 (m) и следовательно образует конечную булеву алгебру <Р2 (m), &    >, являющуюся подалгеброй булевой алгебры логических функций.

Теорема 5.10: Если |U| = 2m, то алгебра множеств изоморфна булевой алгебре функций <Р2 (m), &,,  >.

Эти алгебры равномощны и содержат элементов.

Рассмотренные теоремы указывают на связь между множествами и логическими функциями и позволяют переходить от операций над множествами к операциям над логическими функциями и обратно. Они дают возможность непосредственно производить операции над функциями, заданными не формулами, а таблицами или единичными множествами. Булевы операции над формулами, заданными таблицами, сводятся к подразрядным логическим операциям над столбцами значений функций (табл.5.7).


Пример:

Табл.5.7.



^ § 5.11: ДНФ. Интервалы и покрытия

Теоретико - множественная интерпретация булевой алгебры функций оказывается очень удобным языком для изучения дизъюнктивных нормальных форм ДНФ и методов их упрощения.

Если функция f (х1,.., хm) представляет собой элементарную конъюнкцию всех m переменных, то Mf содержит один элемент множества Bm (т.е. это двоичный вектор длины m, на котором функция f принимает значение 1). Если же f - элементарная конъюнкция k переменных, k < m, то Mf содержит 2m - k двоичных наборов (т.к. m - k переменных, не вошедших в эту конъюнкцию, несущественны для f и могут принимать любые 2m - k значений, не изменяя f). Множество Мf такой функции f называется интервалом.

Например: m = 4, f (x1, x2, x3, x4) = x2

Mf = {0100, 0110, 1100, 1110} |Mf| = 24 - 2 = 4

В этом случае говорят, что конъюнкция х2 (а точнее интервал ) покрывает множество Мf ( и все его подмножества).

Если f  g  1, то Mf  Mg (Mf - множество единичных наборов функции f). Из определения импликации следует, что ни для какого набора  не может быть одновременно f () = 1 и g () = 0. Поэтому, если f () = g () = 1, т.е. если   Mf то   Mg и, следовательно, Mf  Mg. Говорят, что функция f имплицирует функцию g. Если f - элементарная конъюнкция, то f называется импликантом g, и если после удаления буквы (вхождения переменной) из f, f перестает быть импликантом g, то f называется простым импликантом g.

Например, для функции x(yz) xy и xz - простые импликанты, x,y,z- импликант, но не простой.

Любая конъюнкция любой ДНФ является импликантом этой функции.

Представление f в виде ДНФ соответствует представлению ее единичного множества в виде объединения интервалов. В совокупности все конъюнкции ДНФ покрывают все единичное множество f. Верно и обратное: если Mk  Mf то существует ДНФ функции f, содержащая конъюнкцию k. В частности СДНФ функции f соответствует просто перечислению элементов Mf. Отношение покрытия между конъюнкциями ДНФ и элементами Mf наглядно задается таблицей покрытия (табл.5.8), строки которой соответствуют конъюнкциям, т.е. интервалам, столбцы - элементам Mf, а на их пересечении 1, если i - ая конъюнкция покрывает (поглощает) j -ый элемент Mf.

Например: ДНФ F = xz  yz  xy.

Табл.5.8.

y xz xy xyz




Интервал Mxy покрывается Mxz  Myz. Поэтому исключение xy из формулы F не изменит единичного множества данной функции: xxy=x. Интервал Mxy всегда покрывается Мх. Этот закон в терминах ДНФ можно сформулировать: любой импликант в ДНФ, не являющийся простым, можно заменить простым импликантом k0, покрывающим k; импликант k0 получается из k вычеркиванием нескольких букв.

Т.о. для любой функции f существует ДНФ F, состоящая из простых импликантов ДНФ F  k, где k - простой импликант f, не содержащийся в F, также представляет f. Поэтому дизъюнкция всех простых импликантов f, называется сокращенной ДНФ, и также представляет f.

Методы упрощения ДНФ состоят из 2-х этапов:

1) получают список всех простых импликантов, т.е. сокращенную ДНФ

2) используя таблицу покрытия, удаляют импликанты, покрываемые другими импликантами. ДНФ, из которой нельзя удалить ни одного импликанта, называется тупиковой.

110000-selskoe-i-ribnoe-hozyajstvo-perechen-uchebnih-izdanij-dlya-obrazovatelnih-uchrezhdenij-realizuyushih-obrazovatelnie.html
11092008-g-s-17-tema-stroitelstvo-stroitelen-kontrol.html
111-slozhenie-chisel-s-raznimi-znakami-1-prikaz-po-shkole-ot-2009-g.html
112-kodeks-rossijskoj-federacii-ob-administrativnih-pravonarusheniyah-ot-30122001-n-195-fz.html
112-primernij-perechen-plan-meropriyatij-po-perehodu-federalnih-obrazovatelnih-uchrezhdenij-v-au.html
112osnovnaya-obrazovatelnaya-programma24020265-himicheskaya-tehnologiya-i-oborudovanie-otdelochnogo-proizvodstva.html
  • thesis.bystrickaya.ru/porfirii-klinicheskaya-himiya-v-diagnostike-i-lechenii.html
  • knigi.bystrickaya.ru/ris1-sistema-kriteriev-dlya-ocenki-rezultatov-sinteza-sostava-smesi-holodilnih-agentov.html
  • thescience.bystrickaya.ru/i-skuchno-i-grustno-i-nekomu-ruku-podat-kozhu-dlya-nih-dayut.html
  • pisat.bystrickaya.ru/trebovaniya-k-znaniyam-i-umeniyam-studentov-uchebno-metodicheskij-kompleks-po-discipline-metodika-prepodavaniya-matematiki.html
  • otsenki.bystrickaya.ru/rekomendacii-po-podgotovke-dissertacii-k-zashite-chasto-zadavaemie-voprosi.html
  • spur.bystrickaya.ru/kogda-teryaesh-golovu-skazka-o-kvartirnom-voprose-65.html
  • crib.bystrickaya.ru/iakolesnik-predsedatel-belorusskogo-profsoyuza-metallistov-uvazhaemie-delegati-uchastniki-kongressa.html
  • education.bystrickaya.ru/1061-gornoe-pravo-gosudarstvennij-rubrikator-nauchno-tehnicheskoj-informacii-grnti.html
  • uchit.bystrickaya.ru/uchebnij-plan-povisheniya-kvalifikacii-po-napravleniyu-ocenka-sobstvennosti-dlya-specializacii-ocenka-stoimosti-predpriyatiya-biznesa-perechen-disciplin.html
  • laboratornaya.bystrickaya.ru/razdel-iv-upravlenie-shkoloj-i-obshaya-harakteristika-obrazovatelnogo-uchrezhdeniya-istoricheskaya-spravka-o-shkole.html
  • zanyatie.bystrickaya.ru/proishozhdenie-osnovnie-etapi-razvitiya-i-sovremennie-opredeleniya-termina-bibliografiya-chast-2.html
  • znanie.bystrickaya.ru/7-arhitekturno-stroitelnie-resheniya-tehnicheskoe-zadanie.html
  • knigi.bystrickaya.ru/referatov-po-discipline-osnovi-bezopasnosti-zhiznedeyatelnosti.html
  • kolledzh.bystrickaya.ru/aleks-zeltin-promivka-mozgov-stranica-20.html
  • bukva.bystrickaya.ru/opera-petro-maskani-selskaya-chest-cavalleria-rusticana.html
  • shkola.bystrickaya.ru/tema-3-sistema-institutov-korrekcionnoj-pomoshi-v-rossii-uchebno-metodicheskij-kompleks-disciplini-bijsk.html
  • university.bystrickaya.ru/glava-2-priobretenie-chelovekom-individualnogo-opita-v-obrazovatelnom-processe.html
  • tasks.bystrickaya.ru/14-gadanie-na-kofejnoj-gushe-fedor-berezin.html
  • assessments.bystrickaya.ru/dinamika-trudovih-resursov-zanyatih-v-osnovnih-otraslyah-ivanovskoj-oblasti.html
  • teacher.bystrickaya.ru/glava-mchs-chinil-rozetki-bashin-pil-sake-komsomolskaya-pravda-gazeta-aleksandr-katerusha15-01-2009.html
  • uchitel.bystrickaya.ru/programma-predprofilnogo-elektivnogo-kursa-po-biologii-dlya-9-klassa-poyasnitelnaya-zapiska.html
  • tasks.bystrickaya.ru/0bra30va-vii-mezhdunarodnaya-nauchnaya-konferenciya-novie-informacionni-tehnologii-i-menedzhmen-stranica-4.html
  • lecture.bystrickaya.ru/averyanov-l-ya.html
  • klass.bystrickaya.ru/432-finansovie-vlozheniya-emitenta-ezhekvartalnijotche-t-otkritogo-akcionernogo-obshestva-gazavtomatika-otkritogo.html
  • shpora.bystrickaya.ru/zayavka-na-uchastie-v-aukcione-stranica-8.html
  • knowledge.bystrickaya.ru/nachala-russkoj-istorii-izbrannoe-otv-red-yu-g-alekseev-sankt-peterburg-gos-un-t-m-izdat-dom-parad-2001-975-s-1-l-portr.html
  • letter.bystrickaya.ru/minimum-trebovanij-dlya-provedeniya-letnej-universiadi-2015-g-noyabr-2008-stranica-6.html
  • spur.bystrickaya.ru/konkurs-izdanij-publikacij-video-i-radiomaterialov-v-rajonnih-okruzhnih-gorodskih-federalnih-smi-k-pamyatnim-datam-istorii-otechestva-polozhenie.html
  • pisat.bystrickaya.ru/sto-velikih-mifov-i-legend-stranica-44.html
  • credit.bystrickaya.ru/plan-meropriyatij-po-perehodu-na-mezhvedomstvennoe-i-mezhurovnevoe-vzaimodejstvie-pri-predostavlenii-municipalnih-uslug-v-alikovskom-rajone.html
  • notebook.bystrickaya.ru/ideya-gubernatora-yugri-podderzhana-polpredom-ugra-newsru-14072011-centralnaya-pressa.html
  • textbook.bystrickaya.ru/kalendarno-tematicheskoe-planirovanie-.html
  • lecture.bystrickaya.ru/6-tehnologicheskaya-karta-po-discipline-logistika.html
  • vospitanie.bystrickaya.ru/zasedanie-magistrov-scena-pervaya.html
  • obrazovanie.bystrickaya.ru/problemi-koordinacii-struktura-v-kulake-sozdanie-effektivnoj-organizacii.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.