.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/prilozheniya-prilozhenie-i-metodicheskie-ukazaniya-k-kursovomu-proektirovaniyu-po-discipline-proektirovanie-avtomatizirovannih.html
  • uchebnik.bystrickaya.ru/uchebno-metodicheskij-kompleks-osnovnoj-obrazovatelnoj-programmi-po-napravleniyu-podgotovki-bakalavrov-sistemnij-analiz-i-upravlenie-sankt-peterburg-2009-g.html
  • textbook.bystrickaya.ru/informacionnij-byulleten-administracii-sankt-peterburga-26-777-ot-16-iyulya-2012-g-stranica-9.html
  • letter.bystrickaya.ru/n-n-yumanova-bankovskaya-politika.html
  • doklad.bystrickaya.ru/v-rezultate-izucheniya-obshestvoznaniya-na-profilnom-urovne-uchenik-dolzhen.html
  • nauka.bystrickaya.ru/vospominaniya-grigoriya-ivanovicha-filipsona-stranica-10.html
  • teacher.bystrickaya.ru/fgbu-rossijskij-selskohozyajstvennij-centr-filial-fgbu-rossijskij-selskohozyajstvennij-centr-po-novgorodskoj-oblasti-stranica-4.html
  • znaniya.bystrickaya.ru/promezhutochnij-otchyot-ob-itogah-realizacii-pedagogicheskogo-proekta-za-20102011-uchebnij-god.html
  • institut.bystrickaya.ru/tematicheskij-plan-izucheniya-disciplini-rabochaya-programma-uchebnoj-disciplini-kreditnij-rinok-dlya-studentov-3-kursa.html
  • holiday.bystrickaya.ru/neispolzovanie-tovarnogo-znaka-kak-osnovanie-dlya-prekrasheniya-ego-ohrani.html
  • holiday.bystrickaya.ru/metodicheskie-ukazaniya-i-kontrolnie-zadaniya-s-programmoj-dlya-studentov-zaochnikov-inzhenerno-tehnicheskih-specialnostej-visshih-uchebnih-zavedenij-pod-redakciej-yu-s-arutyunova-izdanie-trete-stranica-2.html
  • uchitel.bystrickaya.ru/programma-tura-den-karakas-pribitie-v-karakas-vstrecha-v-aeroportu-transfer-v-otel-alba-caracas-4.html
  • letter.bystrickaya.ru/mezhpravitelstvennij-komitet-po-intellektualnoj-sobstvennosti-geneticheskim-resursam-tradicionnim-znaniyam-i-folkloru.html
  • books.bystrickaya.ru/blagodarim-vas-za-otcheti-prislannie-v-vologodskuyu-oblastnuyu-yunosheskuyu-biblioteku-im-v-f-tendryakova-na-osnove-kotorih-sostavlen-ocherednoj-informacionnij-byull.html
  • zanyatie.bystrickaya.ru/reklama-mobilizaciya-resursov.html
  • shkola.bystrickaya.ru/strategiya-perioda-v-v-do-nashej-eri-xx-v-nashej-eri-stranica-25.html
  • uchebnik.bystrickaya.ru/voprosi-ocenki-effektivnosti-proizvodstva-i-realizacii-produkcii-energeticheskogo-mashinostroeniya-chast-3.html
  • institut.bystrickaya.ru/tematicheskij-plan-po-predmetu-risunok-plan-uroka-prilozhenie.html
  • learn.bystrickaya.ru/glava-13-biznis-udk-82.html
  • literatura.bystrickaya.ru/skazka-kak-lekarstvo-stranica-18.html
  • composition.bystrickaya.ru/patrioticheskoe-vospitanie-rabota-so-starshimi-doshkolnikami.html
  • studies.bystrickaya.ru/diplom-demidov-d-a.html
  • crib.bystrickaya.ru/karies-zubov-spravochnik-putevoditel-prakt-vracha.html
  • turn.bystrickaya.ru/poisk-i-sozdanie-novih-socialnih-form-ih-vzaimodejstvie-mezhdu-soboj-i-sociokulturnoj-sredoj-obespechivayushih-formirovanie-vnutrennej-motivacii-k-samorazvitiyu-subektov-shkolnogo-soobshestva.html
  • notebook.bystrickaya.ru/gosdumu-napugali-rossijskoj-armiej-pervij-kanal-novosti-13-11-2008-pankratova-yuliya-15-00-10.html
  • lektsiya.bystrickaya.ru/programma-kursa-dlya-uchashihsya-srednej-shkoli-poyasnitelnaya-zapiska.html
  • textbook.bystrickaya.ru/kak-sostavit-konspekt-uroka-russkogo-yazika-konspekt-uroka-stranica-6.html
  • laboratornaya.bystrickaya.ru/provesti-konkurs-luchshij-sajt-obrazovatelnogo-uchrezhdeniya-2012-v-obsheobrazovatelnih-uchrezhdeniyah-prohladnenskogo-municipalnogo-rajona-v-period-s-01-aprelya-po-30-maya-2012-goda.html
  • bukva.bystrickaya.ru/o-razlichenii-ponyatij-bogosluzhebnogo-peniya-i-muziki-na-rusi.html
  • zadachi.bystrickaya.ru/osobennosti-psihologicheskoj-harakteristiki-lichnosti-prestupnika-chast-3.html
  • lesson.bystrickaya.ru/nravstvennoe-vospitanie-mladshih-shkolnikov-v-uchebno-vospitatelnom-processe.html
  • testyi.bystrickaya.ru/8-primernaya-tematika-kursovih-proektov-rabot-ne-predusmotreno-primernaya-programma-naimenovanie-disciplini.html
  • uchit.bystrickaya.ru/svedeniya-ob-uchastii-komitetov-oblastnoj-dumi-v-zakonotvorcheskom-processe-za-i-polugodie-2010-goda.html
  • essay.bystrickaya.ru/chast-nalichnogo-vhoda-nadeyus-takoe-dovolno-gruboe-opredelenie-ne-pokazhetsya.html
  • literature.bystrickaya.ru/biznes-inkubatori-mehanizm-upravleniya-innovaciyami.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.