.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
  • zanyatie.bystrickaya.ru/tipologicheskoe-modelirovanie-knigotorgovogo-assortimenta.html
  • doklad.bystrickaya.ru/uchebno-metodicheskij-kompleks-specialnost-080401-tovarovedenie-i-ekspertiza-tovarov-moskva-2009-stranica-4.html
  • pisat.bystrickaya.ru/uchastkovaya-izbiratelnaya-komissiya-327-uchastkovaya-izbiratelnaya-komissiya-301.html
  • vospitanie.bystrickaya.ru/zakonodatelstvo-rossijskoj-federacii.html
  • desk.bystrickaya.ru/otodvigayut-sebya-eleni-fajgl-ute-erhardt-gute-madchen-kommen-in-den-himmel-bose-uberall-hin-warum-bravsein-uns.html
  • znanie.bystrickaya.ru/aizozulya--ponyatie-novih-religioznih-organizacij-v-socialno-psihologicheskom-izuchenii.html
  • otsenki.bystrickaya.ru/restoran-czin-yue-otel-astrus-centralnij-dom-turista-moskva-leninskij-pr-t-146-holodnie-zakuski.html
  • essay.bystrickaya.ru/dvizhenie-kollivadov.html
  • nauka.bystrickaya.ru/uchebno-metodicheskij-kompleks-rabochaya-uchebnaya-programma-dlya-studentov-020200-62-napravleniya-biologiya.html
  • upbringing.bystrickaya.ru/konkurs-detskogo-tvorchestva-yunie-talanti-starogo-goroda-v-ramkah-goda-istorii-rossii-v-ramkah-programmi-istoriya-gosudarstva-rossijskogo-mb-mibs.html
  • literature.bystrickaya.ru/chast-v-edinaya-teoriya-v-xxi-veke-brajana-grina-elegantnaya-vselennaya.html
  • crib.bystrickaya.ru/izbrannie-raboti-ktajner-monografiya-taganrog.html
  • tasks.bystrickaya.ru/-municipalitet-vozrozhdaet-narodnij-kontrol-informacionnij-byulleten-mestnogo-samoupravleniya-izdaetsya-asdg.html
  • school.bystrickaya.ru/gosudarstvennoe-i-municipalnoe-upravlenie-4.html
  • institut.bystrickaya.ru/stilistika-kultura-rechi-teoriya-rechevoj-kommunikacii-uchebnij-slovar-terminov-stranica-6.html
  • credit.bystrickaya.ru/olimpiada-vedomosti-avtor-ne-ukazan-03072008-121-str-a3-gosduma-rf-monitoring-smi-3-iyulya-2008-g.html
  • reading.bystrickaya.ru/metodicheskie-rekomendacii-po-izucheniyu-teoreticheskogo-materiala-dlya-studentov-specialnostej.html
  • lecture.bystrickaya.ru/62-osnovnie-faktori-vliyayushie-na-uroven-cen-na-mezhdunarodnom-rinke-cenoobrazovanie-uchebnoe-posobie.html
  • education.bystrickaya.ru/23-marta-2010-goda-10-chasov-30-minut-stranica-4.html
  • klass.bystrickaya.ru/a-1-osimshasi.html
  • control.bystrickaya.ru/bibliya-v-dokumentah-istorii.html
  • shpargalka.bystrickaya.ru/uchebno-metodicheskij-kompleks-rabochaya-programma-dlya-studentov-napravleniya-031700-62-istoriya.html
  • shkola.bystrickaya.ru/raschyot-ekonomicheskoj-effektivnosti-ot-vnedreniya-novoj-tehniki.html
  • report.bystrickaya.ru/kafedra-ekonomicheskoj-teorii.html
  • spur.bystrickaya.ru/mesyac-svyatogo-ogyusta-zodchego.html
  • kontrolnaya.bystrickaya.ru/rajona-primorskogo-kraya-postanovleni-e.html
  • lesson.bystrickaya.ru/prilozhenie-7-utverzhden-ukazom-prezidenta.html
  • tests.bystrickaya.ru/kommunikativnaya-kompetenciya-v-professionalnoj-kulture-gossluzhashego.html
  • literatura.bystrickaya.ru/socialnaya-zashita-na-stranicah-periodicheskoj-pechati.html
  • letter.bystrickaya.ru/n-d-ugrinovich-invariantnaya-sostavlyayushaya-traektorij-obucheniya-v-8-klasse-1-chas-v-nedelyu.html
  • literatura.bystrickaya.ru/socialnaya-relevantnost-i-socialnaya-nisha-psihologii-stranica-7.html
  • nauka.bystrickaya.ru/unit-5-personnel-administration-staffing-and-training-the-agencya-vocabulary.html
  • tetrad.bystrickaya.ru/uchebno-metodicheskij-kompleks-ekonomicheskaya-teoriya-visshee-professionalnoe-obrazovanie-specialnost-080507-65-menedzhment-organizacii-moskva-2011-stranica-7.html
  • zanyatie.bystrickaya.ru/raketnie-vojska-strategicheskogo-naznacheniya.html
  • institut.bystrickaya.ru/tema-13-kriminalisticheskaya-registraciya-informacionno-spravochnie-sistemi-ekzamen-viisemestr-dlya-ochnoj-formi-obucheniya.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.