.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
  • upbringing.bystrickaya.ru/ledohod-na-reke-pechora-ozhidaetsya-na-uchastke-sherdino-ust-shugor-komi-informacionnoe-agentstvo-regnum-24042012.html
  • testyi.bystrickaya.ru/8-zak-3368-garris-rukovodstvo-k-vedeniyu.html
  • kontrolnaya.bystrickaya.ru/programma-teoreticheskogo-seminara-motivacionnij-menedzhment-v-praktike-uchitelya.html
  • prepodavatel.bystrickaya.ru/t-rislov-audani-kmdgn-blm-blmne-arasti-zhalpi-blm-beretn-mektepterde-11-sinip-oushilarini-oritindi-memlekettk-attestattaua-zhne-bt-ge-dajindi-degejn-zerdeleu-anitamasi.html
  • exchangerate.bystrickaya.ru/lichnost-i-kollektiv-kak-obekti-upravleniya.html
  • tests.bystrickaya.ru/materiali-s-bolshim-udelnim-soprotivleniem-1-harakteristika-kristallicheskih-reshetok.html
  • bystrickaya.ru/zaochnaya-forma-uchastiya-v-rabote-konferencii-vserossijskaya-nauchno-prakticheskaya-konferenciya-strategiya-gimnazicheskogo-obrazovaniya.html
  • thesis.bystrickaya.ru/programma-laboratornih-zanyatij-3-kurs-6-sem-64-ch-dif-zachet-starshij-prepodavatel-feofanov-aleksandr-vladimirovich-assistent-abrukovskij-aleksej-aleksandrovich.html
  • college.bystrickaya.ru/1-vvedenie-internet-tehnologii-v-teatre-sajt-sverdlovskogo-gosudarstvennogo-akademicheskogo-teatra-muzikalnoj-komedii.html
  • nauka.bystrickaya.ru/v-n-zemcov-chernaya-kniga-karmartena-to-nemnogoe-chto-mi-o-nej-znaem-materiali-k-speckursu-ekaterinburg-2007.html
  • education.bystrickaya.ru/04042011-permskij-krajna-subsidirovanie-malogo-i-srednego-biznesa-v-permskom-krae-budet-napravleno-20-mln-rublej.html
  • laboratory.bystrickaya.ru/vozniknovenie-klassicheskoj-shkoli-upetti-predmet-istorii-ekonomicheskih-uchenij-2.html
  • ucheba.bystrickaya.ru/programma-po-discipline-mirovaya-ekonomika-dlya-studentov-2-kursa-dnevnogo-otdeleniya-fakulteta-stranica-3.html
  • ekzamen.bystrickaya.ru/skazka-pro-slavnogo-carya-goroha.html
  • books.bystrickaya.ru/biologicheskie-nauki-stranica-8.html
  • lecture.bystrickaya.ru/a-a-shiyan-ekonomicheskaya-kibernetika.html
  • lesson.bystrickaya.ru/test-po-obshestvoznaniyu-1.html
  • school.bystrickaya.ru/geografiya-meksiki.html
  • esse.bystrickaya.ru/publichnij-otchet-mou-srednyaya-obsheobrazovatelnaya-shkola-18.html
  • credit.bystrickaya.ru/ou-badarlamasini-zhalpi-sipattamasi.html
  • school.bystrickaya.ru/konstitucionnij-sud-avstrii.html
  • uchebnik.bystrickaya.ru/uchebno-metodicheskij-kompleks-po-discipline-formi-i-zhanri-publicistiki-dlya-specialnosti-050504-zhurnalistika-shifr-specialnost-ust-kamenogorsk-2005-g.html
  • spur.bystrickaya.ru/laboratornaya-rabota-6-tema-potokovij-vvod-vivod-v-yazike-s.html
  • desk.bystrickaya.ru/orlova-e-b-urok-igra-puteshestvie-v-stranu-chitaliyu-mou-sosh-179.html
  • pisat.bystrickaya.ru/tretij-variant-o-v-zikovu-uvazhaemij-oleg-vladimirovich.html
  • report.bystrickaya.ru/kalendarno-tematicheskoe-planirovanie-urokov-literaturi-v-5-klasse-stranica-2.html
  • abstract.bystrickaya.ru/-kommunikacii-vne-organizacii-.html
  • universitet.bystrickaya.ru/strukturnie-aspekti-teorii-avtomaticheskogo-upravleniya.html
  • ekzamen.bystrickaya.ru/selektivnie-voltmetri-chastotno-selektivnie-voltmetri-ili-voltmetri-nesushej-chastoti.html
  • uchitel.bystrickaya.ru/pyataya-sessiya-zheneva-26-30-aprelya-2010-g-proekt-otcheta-stranica-7.html
  • turn.bystrickaya.ru/plavilnogo-kotla.html
  • lektsiya.bystrickaya.ru/prikaz-ot-2010g-rabochaya-programma-po-russkomu-yaziku-dlya-kursa.html
  • education.bystrickaya.ru/32-rasporyazhenie-isklyuchitelnim-pravom-na-izobretenie-poleznuyu-model-ili-promishlennij-obrazec.html
  • institut.bystrickaya.ru/tematicheskoe-planirovanie-s-opredeleniem-osnovnih-vidov-uchebnoj-deyatelnosti-obuchayushihsya-po-obucheniyu-gramote-v-1-klasse-stranica-15.html
  • znaniya.bystrickaya.ru/razdel-4-ekspertnie-zaklyucheniya-recenzii-otzivi-na-uchebniki-monografii-dissertacii-avtoreferati-oficialnoe-opponirovanie.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.