Рассмотренные операции над множествами подчинены некоторым законам, которые напоминают известные элементарные законы алгебры чисел. Этим определяется название алгебра множеств , которую часто называют булевой алгеброй множеств, что связано с именем английского математика Джона Буля, который положил в основу своих логических исследований идею аналогии между алгеброй и логикой.

Для произвольных множеств А, В, и С справедливы следующие тождества (табл. 3.1):

Таблица 3.1

Законы алгебры множеств по отношению к операциям пересечения () и объединения () подчинены принципу двойственности: если в каком-либо законе все знаки пересечения заменить знаками объединения, а все знаки объединения – знаками пересечения, знак универсума (U) заменить знаком пустого множества (Ø), а знак пустого – знаком универсума, то получим снова верное тождество. Например (в силу этого принципа), из следует и т. п.

3.1. Проверка истинности тождеств при помощи диаграмм Эйлера-Венна

Все законы алгебры множеств можно наглядно представить и доказать, используя диаграммы Эйлера-Венна. Для этого необходимо:

Начертить соответствующую диаграмму и заштриховать все множества, стоящие в левой части равенства.

Начертить другую диаграмму и сделать то же для правой части равенства.

Данное тождество истинно тогда и только тогда, когда на обеих диаграммах заштрихована одна и та же область.

Замечание 3.1. Два пересекающихся круга делят всё универсальное множество на четыре области (см. рис.3.1)

Замечание 3.2. Три пересекающихся круга делят всё универсальное множество на восемь областей (см. рис.3.2):

Замечание 3.2. При записи условий различных примеров часто используются обозначения:

 - из … следует…;

 - тогда и только тогда, когда… .

Задача 3.1 . Упростить выражения алгебры множеств:

Решение.

Задача 3 .2 . Доказать тождества:

(АВ)\В = А\В;

А(ВС) = А\(А\В)(А\С).

Решение.

Задача 3.3 . Доказать следующие соотношения двумя способами: с помощью диаграмм и с помощью определения равенства множеств.

Решение.

2. Доказательство с помощью определения равенства множеств.

По определению, множества Х и Y равны, если одновременно выполнены соотношения: XY и YX.

Сначала покажем, что
. Пустьх – произвольный элемент множества
, то естьх 
. Это означает, чтох U и х 
. Отсюда вытекает, чтох А или х В. Если х А, то тогда х Ā, а значит,
. Если жех В, то
, а значит,
. Таким образом, всякий элемент множества.
. есть также элементом множества
То есть

Теперь докажем обратное, то есть, что
. Пусть
. Еслих Ā, то х U и х А, а значит, х АВ. Отсюда следует, что
. Если же
, тох U и х В. Значит, х АВ, то есть
. Отсюда следует, что всякий элемент множества
является также элементом множества
, то есть
.

Значит,
, что и требовалось доказать.

A(BC) = (AB)(AC);

1. Доказательство с помощью диаграммы:

Пусть х А(ВС). Тогда х А и х ВС. Если х В, то х АВ, что не противоречит сказанному, а значит, х (АВ)(АС). Если же х С, то х АС. Следовательно, х (AB)(AC). Итак, доказано, что A(BC)  (AB)(AC.

Пусть теперь х  (AB)(AC). Если х АВ, то х А и х В. Отсюда следует, что х А и х ВС, то есть х А(ВС). Если же х АС, то х А и х С. Отсюда вытекает, что х А и х ВС, то есть х А(ВС). Таким образом, (AB)(AC) A(BC). Следовательно, A(BC) = (AB)(AC). Что и требовалось доказать.

При доказательстве достаточности мы получили, что АВ=. Очевидно, что С, поэтому соотношение доказано. При доказательстве был рассмотрен самый общий случай. Однако здесь возможны ещё некоторые варианты при построении диаграмм. Например, случай равенства АВ=С либо
, случай пустых множества и так далее. Очевидно, что все возможные варианты учесть бывает затруднительно. Поэтому считается, что доказательство соотношений с помощью диаграмм не всегда является корректным.

2. Доказательство с помощью определения равенства множеств.

Необходимость. Пусть АВС и элемент х А. Покажем, что в этом случае элемент множества А будет являться также и элементом множества
.

Рассмотрим два случая: х В или
.

Если х В, то х АВС, то есть х С, и, как следствие этого,
.

Если же
, то и
. Необходимость доказана.

Пусть теперь
их АВ. Покажем, что элемент х также будет элементом множества С.

Если х АВ, тогда х А и х В. Поскольку
, значитх С. Достаточность доказана.

1. Доказательство с помощью диаграммы:

2. Доказательство с помощью определения равенства множеств.

Пусть АВ. Рассмотрим элемент х В (или
). Аналогично:х А (или х Ā). То есть всякий элемент множества есть также элементом множества Ā. А это может быть в случае, если
. Что и требовалось доказать.

Задача 3.4. Выразить символически указанные области и упростить полученные выражения.

Решение.

Искомая область состоит из двух изолированных частей. Условно назовём их верхней и нижней. Множество, которое они изображают, можно описать так:

М = {x  x A и х В и х С или х С и х А и х В}.

Из определения операций над множествами получим:

М = ((АВ)\С)(С\А\В).

Запишем это выражение с помощью основных операций – дополнения, объединения и пересечения:

Упростить это выражения нельзя, поскольку имеем по одному вхождению каждого символа. Это и есть простейший вид данной формулы.

Данную область можно рассматривать как объединение множеств А\В\С и АВС. По определению M = {x  x A и x В и х С или х А и х В и х С}. Упростим:

Задачи для самостоятельного решения.

1. Упростить:

2. Доказать с помощью диаграмм, законов алгебры множеств и определения равенства множеств:

(АВ)\В = А\В;

А(ВС) = А\(А\В)(А\С);

АВ = АВ  А=В;

А\В =   АВ = А.

3. Выяснить, существует ли множество Х, удовлетворяющее при любом А равенству:

АХ = А; (ответ );

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

В дальнейшем считается, что все рассматриваемые нечеткие множества являются подмножествами одного и того же множества Y .

П2-1. Законы де Моргана для нечетких множеств

Как известно, законами же Моргана называются следующие тождества алгебры множеств

Теорема 1. Для нечетких множеств справедливы тождества

(3)

Доказательство теоремы 1 состоит в непосредственной проверке справедливости соотношений (2) и (3) путем вычисления значений функций принадлежности участвующих в этих соотношениях нечетких множеств на основе определений, данных в главе 8.

Тождества (2) и (3) назовем законами де Моргана для нечетких множеств . В отличие от классического случая соотношений (1), они состоят из четырех тождеств, одна пара которых относится к операциям объединения и пересечения, а вторая - к операциям произведения и суммы. Как и соотношение (1) в алгебре множеств, законы де Моргана в алгебре нечетких множеств позволяют преобразовывать выражения и формулы, в состав которых входят операции отрицания.

П2-2. Дистрибутивный закон для нечетких множеств

Некоторые свойства операций над множествами не выполнены для нечетких множеств. Так, за исключением случая, когда А - "четкое" множество (т.е. функция принадлежности принимает только значения 0 и 1).

Верен ли дистрибутивный закон для нечетких множеств? В литературе иногда расплывчато утверждается, что "не всегда". Внесем полную ясность.

Теорема 2. Для любых нечетких множеств А, В и С

В то же время равенство

справедливо тогда и только тогда, когда при всех

Доказательство . Фиксируем произвольный элемент . Для сокращения записи обозначим Для доказательства тождества (4) необходимо показать, что

Рассмотрим различные упорядочения трех чисел a, b, c. Пусть сначала Тогда левая часть соотношения (6) есть а правая т.е. равенство (6) справедливо.

Пусть Тогда в соотношении (6) слева стоит а справа т.е. соотношение (6) опять является равенством.

Если то в соотношении (6) слева стоит а справа т.е. обе части снова совпадают.

Три остальные упорядочения чисел a, b, c разбирать нет необходимости, поскольку в соотношение (6) числа b и c входят симметрично. Тождество (4) доказано.

Второе утверждение теоремы 2 вытекает из того, что в соответствии с определениями операций над нечеткими множествами (см. главу 8)

Эти два выражения совпадают тогда и только тогда, когда, когда что и требовалось доказать.

Определение 1. Носителем нечеткого множества А называется совокупность всех точек , для которых

Следствие теоремы 2. Если носители нечетких множеств В и С совпадают с У, то равенство (5) имеет место тогда и только тогда, когда А - "четкое" (т.е. обычное, классическое, не нечеткое) множество.

Доказательство. По условию при всех . Тогда из теоремы 2 следует, что т.е. или , что и означает, что А - четкое множество.

П2-3. Нечеткие множества как проекции случайных множеств

С самого начала появления современной теории нечеткости в 1960-е годы началось обсуждение ее взаимоотношений с теорией вероятностей. Дело в том, что функция принадлежности нечеткого множества напоминает распределение вероятностей. Отличие только в том, что сумма вероятностей по всем возможным значениям случайной величины (или интеграл, если множество возможных значений несчетно) всегда равна 1, а сумма S значений функции принадлежности (в непрерывном случае - интеграл от функции принадлежности) может быть любым неотрицательным числом. Возникает искушение пронормировать функцию принадлежности, т.е. разделить все ее значения на S (при S 0), чтобы свести ее к распределению вероятностей (или к плотности вероятности). Однако специалисты по нечеткости справедливо возражают против такого "примитивного" сведения", поскольку оно проводится отдельно для каждой размытости (нечеткого множества), и определения обычных операций над нечеткими множествами с ним согласовать нельзя. Последнее утверждение означает следующее. Пусть указанным образом преобразованы функции принадлежности нечетких множеств А и В . Как при этом преобразуются функции принадлежности ? Установить это невозможно в принципе. Последнее утверждение становится совершенно ясным после рассмотрения нескольких примеров пар нечетких множеств с одними и теми же суммами значений функций принадлежности, но различными результатами теоретико-множественных операций над ними, причем и суммы значений соответствующих функций принадлежности для этих результатов теоретико-множественных операций, например, для пересечений множеств, также различны.

В работах по нечетким множествам довольно часто утверждается, что теория нечеткости является самостоятельным разделом прикладной математики и не имеет отношения к теории вероятностей (см., например, обзор литературы в монографиях ). Авторы, сравнивавшие теорию нечеткости и теорию вероятностей, обычно подчеркивали различие между этими областями теоретических и прикладных исследований. Обычно сравнивают аксиоматику и сравнивают области приложений. Надо сразу отметить, что аргументы при втором типе сравнений не имеют доказательной силы, поскольку по поводу границ применимости даже такой давно выделившейся научной области, как вероятностно-статистические методы, имеются различные мнения. Напомним, что итог рассуждений одного из наиболее известных французских математиков Анри Лебега по поводу границ применимости арифметики таков: "Арифметика применима тогда, когда она применима" (см. его монографию ).

При сравнении различных аксиоматик теории нечеткости и теории вероятностей нетрудно увидеть, что списки аксиом различаются. Из этого, однако, отнюдь не следует, что между указанными теориями нельзя установить связь, типа известного сведения евклидовой геометрии на плоскости к арифметике (точнее к теории числовой системы - см., например, монографию ). Напомним, что эти две аксиоматики - евклидовой геометрии и арифметики - на первый взгляд весьма сильно различаются.

Можно понять желание энтузиастов нового направления подчеркнуть принципиальную новизну своего научного аппарата. Однако не менее важно установить связи нового подхода с ранее известными.

Как оказалось, теория нечетких множеств тесно связана с теорией случайных множеств. Еще в 1974 г. в работе было показано, что нечеткие множества естественно рассматривать как "проекции" случайных множеств. Рассмотрим этот метод сведения теории нечетких множеств к теории случайных множеств.

Определение 2. Пусть - случайное подмножество конечного множества У. Нечеткое множество В, определенное на У, называется проекцией А и обозначается Proj A, если

(7)

при всех

Очевидно, каждому случайному множеству А можно поставить в соответствие с помощью формулы (7) нечеткое множество В = Proj A. Оказывается, верно и обратное.

Теорема 3. Для любого нечеткого подмножества В конечного множества У существует случайное подмножество А множества У такое, что В = Proj A.

Доказательство. Достаточно задать распределение случайного множества А . Пусть У 1 - носитель В (см. определение 1 выше). Без ограничения общности можно считать, что при некотором m и элементы У 1 занумерованы в таком порядке, что

Введем множества

Для всех остальных подмножеств Х множества У положим Р(А=Х)=0 . Поскольку элемент y t входит во множества Y(1), Y(2),…, Y(t) и не входит во множества Y(t+1),…, Y(m), то из приведенных выше формул следует, что Если то, очевидно, Теорема 3 доказана.

Распределение случайного множества с независимыми элементами, как следует из рассмотрений главы 8, полностью определяется его проекцией. Для конечного случайного множества общего вида это не так. Для уточнения сказанного понадобится следующая теорема.

Теорема 4. Для случайного подмножества А множества У из конечного числа элементов наборы чисел и выражаются один через другой.

Доказательство. Второй набор выражается через первый следующим образом:



Элементы первого набора выразить через второй можно с помощью формулы включений и исключений из формальной логики, в соответствии с которой

В этой формуле в первой сумме у пробегает все элементы множества Y\X, во второй сумме переменные суммирования у 1 и у 2 не совпадают и также пробегают это множество, и т.д. Ссылка на формулу включений и исключений завершает доказательство теоремы 4.

В соответствии с теоремой 4 случайное множество А можно характеризовать не только распределением, но и набором чисел В этом наборе а других связей типа равенств нет. В этот набор входят числа следовательно, фиксация проекции случайного множества эквивалентна фиксации k = Card(Y) параметров из (2 k -1) параметров, задающих распределение случайного множества А в общем случае.

Будет полезна следующая теорема.

Теорема 5 . Если Proj A = B , то

Для доказательства достаточно воспользоваться тождеством из теории случайных множеств формулой для вероятности накрытия из главы 8, определением отрицания нечеткого множества и тем, что сумма всех P(A=X) равна 1.

П2-4. Пересечения и произведения нечетких и случайных множеств

Выясним, как операции над случайными множествами соотносятся с операциями над их проекциями. В силу законов де Моргана (теорема 1) и теоремы 5 достаточно рассмотреть операцию пересечения случайных множеств.

Теорема 6. Если случайные подмножества А 1 и А 2 конечного множества У независимы, то нечеткое множество является произведением нечетких множеств Proj A 1 и Proj A 2 .

Доказательство. Надо показать, что для любого

По формуле для вероятности накрытия точки случайным множеством (глава 8)

Как известно, распределение пересечения случайных множеств можно выразить через их совместное распределение следующим образом:

Из соотношений (9) и (10) следует, что вероятность накрытия для пересечения случайных множеств можно представить в виде двойной суммы

Заметим теперь, что правую часть формулы (11) можно переписать следующим образом:

(12)

Действительно, формула (11) отличается от формулы (12) лишь тем, что в ней сгруппированы члены, в которых пересечение переменных суммирования принимает постоянное значение. Воспользовавшись определением независимости случайных множеств и правилом перемножения сумм, получаем, что из (11) и (12) вытекает равенство

Для завершения доказательства теоремы 6 достаточно еще раз сослаться на формулу для вероятности накрытия точки случайным множеством (глава 8).

Определение 3. Носителем случайного множества С называется совокупность всех тех элементов для которых

Теорема 7. Равенство

верно тогда и только тогда, когда пересечение носителей случайных множеств и пусто.

Доказательство. Необходимо выяснить условия, при которых

Тогда равенство (13) сводится к условию

Ясно, что соотношение (14) выполнено тогда и только тогда, когда р 2 р 3 =0 при всех т.е. не существует ни одного элемента такого, что одновременно и , а это эквивалентно пустоте пересечения носителей случайных множеств и . Теорема 7 доказана.

П2-5. Сведение последовательности операций над нечеткими множествами

к последовательности операций над случайными множествами

Выше получены некоторые связи между нечеткими и случайными множествами. Стоит отметить, что изучение этих связей в работе (эта работа выполнена в 1974 г. и доложена на семинаре "Многомерный статистический анализ и вероятностное моделирование реальных процессов" 18 декабря 1974 г. - см. ) началось с введения случайных множеств с целью развития и обобщения аппарата нечетких множеств Л. Заде. Дело в том, что математический аппарат нечетких множеств не позволяет в должной мере учитывать различные варианты зависимости между понятиями (объектами), моделируемыми с его помощью, не является достаточно гибким. Так, для описания "общей части" двух нечетких множеств есть лишь две операции - произведение и пересечение. Если применяется первая из них, то фактически предполагается, что множества ведут себя как проекции независимых случайных множеств (см. выше теорему 6). Операция пересечения также накладывает вполне определенные ограничения на вид зависимости между множествами (см. выше теорему 7), причем в этом случае найдены даже необходимые и достаточные условия. Желательно иметь более широкие возможности для моделирования зависимости между множествами (понятиями, объектами). Использование математического аппарата случайных множеств предоставляет такие возможности.

Цель сведения нечетких множеств к случайным состоит в том, чтобы за любой конструкцией из нечетких множеств видеть конструкцию из случайных множеств, определяющую свойства первой, аналогично тому, как плотностью распределения вероятностей мы видим случайную величину. В настоящем пункте приводим результаты по сведению алгебры нечетких множеств к алгебре случайных множеств.

Определение 4. Вероятностное пространство { W , G, P} назовем делимым, если для любого измеримого множества Х G и любого положительного числа , меньшего Р(Х), можно указать измеримое множество такое, что

Пример. Пусть - единичный куб конечномерного линейного пространства, G есть сигма-алгебра борелевских множеств, а P - мера Лебега. Тогда { W , G, P} - делимое вероятностное пространство.

Таким образом, делимое вероятностное пространство - это не экзотика. Обычный куб является примером такого пространства.

Доказательство сформулированного в примере утверждения проводится стандартными математическими приемами, основанными на том, что измеримое множество можно сколь угодно точно приблизить открытыми множествами, последние представляются в виде суммы не более чем счетного числа открытых шаров, а для шаров делимость проверяется непосредственно (от шара Х тело объема отделяется соответствующей плоскостью).

Теорема 8. Пусть даны случайное множество А на делимом вероятностном пространстве { W , G, P} со значениями во множестве всех подмножеств множества У из конечного числа элементов, и нечеткое множество D на У. Тогда существуют случайные множества С 1 , С 2 , С 3 , С 4 на том же вероятностном пространстве такие, что

где B = Proj A.

Доказательство. В силу справедливости законов де Моргана для нечетких (см. теорему 1 выше) и для случайных множеств, а также теоремы 5 выше (об отрицаниях) достаточно доказать существование случайных множеств С 1 и С 2 .

Рассмотрим распределение вероятностей во множестве всех подмножеств множества У , соответствующее случайному множеству С такому, что Proj C = D (оно существует в силу теоремы 3). Построим случайное множество С 2 Исключим элемент только для того же множества У такие, что

и, кроме того, результаты теоретико-множественных операций связаны аналогичными соотношениями

где знак означает, что на рассматриваемом месте стоит символ пересечения случайных множеств, если в определении B m стоит символ пересечения или символ произведения нечетких множеств, и соответственно символ объединения случайных множеств, если в B m стоит символ объединения или символ суммы нечетких множеств.

Ассоциативность

х 1 (х 2 х 3) = (х 1 х 2)х 3 ;

х 1 Ú (х 2 Ú х 3) = (х 1 Ú х 2) Ú х 3 .

Коммутативность

х 1 х 2 = х 2 х 1

х 1 Ú х 2 = х 2 Ú х 1

Дистрибутивность конъюнкции относительно дизъюнкции

х 1 (х 2 Ú х 3) = х 1 х 2 Ú х 1 х 3 .

Дистрибутивность дизъюнкции относительно конъюнкции

х 1 Ú(х 2 × х 3) = (х 1 Úх 2) × (х 1 Úх 3). *

Идемпотентность (тавтология)

Двойное отрицание

Свойства констант

x & 1 = x; (законы универсального множества)

x & 0 = 0; (законы нулевого множества)

Правила (законы) де Моргана





Закон противоречия (дополнительности)

Закон исключения третьего (дополнительности)

Доказательства всех этих формул тривиальны. Один из вариантов –построение таблиц истинности левой и правой частей и их сравнение.

Правила склеивания

Правило склеивания для элементарных конъюнкций следует из распределительного закона, закона дополнительности и закона универсального множества: дизъюнкцию двух соседних конъюнкций можно заменитьодной элементарной конъюнкцией, являющейся общей частьюисходных конъюнкций .

Правило склеивания для элементарных сумм следует из распределительного закона второго рода, закона дополнительности и закона нулевого множества: конъюнкцию двух соседних дизъюнкций можно заменить одной элементарной дизъюнкцией, являющейся общей частьюисходных дизъюнкций .

Правило поглощения

Правило поглощения для суммы двух элементарных произведений следует из распределительного закона первого рода и законов универсального множества: дизъюнкцию двух элементарных конъюнкций, из которых одна является составной частью другой, можно заменить конъюнкцией, имеющейменьшее количество операндов .

Правило поглощения для произведения элементарных сумм следует из распределительного закона второго рода и законов нулевого множества: конъюнкцию двух элементарных дизъюнкций, из которых одна является составной частью другой, можно заменить элементарной дизъюнкцией, имеющей меньшее количество операндов.

Правило развертывания

Это правило определяет действие обратное склеиванию.

Правило развертывания элементарного произведения в логическую сумму элементарных произведений большего ранга (в пределе до r = n, т.е. до конституент единицы, как и будет рассмотрено ниже) следует из законов универсального множества, распределительного закона первого рода и производится в три этапа:

В развертываемое элементарное произведение ранга r вводится в качестве сомножителей n-r единиц, где n- ранг конституенты единицы;

Каждая единица заменяется логической суммой некоторой, не имеющейся в исходном элементарном произведении переменной и ее отрицания: x i v `x i = 1;

Производится раскрытие всех скобок на основе распределительного закона первого рода, что приводит к развертыванию исходного элементарного произведения ранга r в логическую сумму 2 n-r конституент единицы.

Правило развертывания элементарного произведения используется для минимизации функций алгебры логики (ФАЛ).

Правило развертывания элементарной суммы ранга r до произведения элементарных сумм ранга n (конституент нуля) следует их законов нулевого множества (6) и распределительного закона второго рода (14) и производится в три этапа:

В развертываемую сумму ранга r в качестве слагаемых вводится n-r нулей;

Каждый нуль представляется в виде логического произведения некоторой, не имеющейся в исходной сумме переменной и ее отрицания: x i ·`x i = 0;

Получившееся выражение преобразуется на основе распределительного закона второго рода (14) таким образом, чтобы исходная сумма ранга r развернулась в логическое произведение 2 n-r конституент нуля.

16.Понятие полной системы. Примеры полных систем (с доказательством)

Определение. Множество функций алгебры логики A называется полной системой (в P2), если любую функцию алгебры логики можно выразить формулой над A.

Система функций A={ f 1 , f 1 ,…, f m }, являющаяся полной, называется базисом .

Минимальным базисом называется такой базис, для которого удаление хотя бы одной функции f 1 , образующей этот базис, превращает систему функций (f 1 , f 1 ,…, f m) в неполную.

Теорема. Система A = {∨, &, } является полной.

Доказательство. Если функция алгебры логики f отлична от тождественного нуля, то f выражается в виде совершенной дизъюнктивной нормальной формы, в которую входят лишь дизъюнкция, конъюнкция и отрицание. Если же f ≡ 0, то f = x & x . Теорема доказана.

Лемма. Если система A - полная, и любая функция системы A может быть выражена формулой над некоторой другой системой B, то B - также полная система.

Доказательство. Рассмотрим произвольную функцию алгебры логики f (x 1 , …, x n) и две системы функций: A = {g 1 , g 2 , …} и B = {h 1 , h 2 , …}. В силу того, что система A полна, функция f может быть выражена в виде формулы над ней:

f (x 1 , …, x n) = ℑ

где g i = ℜ i

то есть функция f представляется в виде

f (x 1 , …, x n)=ℑ[ℜ1,ℜ2,...]

иначе говоря, может быть представлена формулой над B. Перебирая таким образом все функции алгебры логики, получим, что система B также полна. Лемма доказана.

Теорема. Следующие системы являются полными в P 2:

4) {&, ⊕ , 1}базис Жегалкина.

Доказательство.

1) Известно (теорема 3), что система A = {&, V, } полна. Покажем, что полна система B = { V, . Действительно, из закона де Моргана (x& y) = (x ∨ y) получаем, что x & y = (x ∨ y) , то есть конъюнкция выражается через дизъюнкцию и отрицание, и все функции системы A выражаются формулами над системой B. Согласно лемме система B полна.

2) Аналогично пункту 1: (x ∨ y) = x & y ⇔ x ∨ y =(x & y) и из леммы 2 следует истинность утверждения пункта 2.

3) x | y=(x&y), x | x = x ; x & y = (x | y) = (x | y) | (x | y) и согласно лемме 2 система полна.

4) x = x ⊕1 и согласно лемме 2 система полна.

Теорема доказана.

17.Алгебра Жегалкина. Свойства операций и полнота

Множество булевых функций, заданных в базисе Жегалкина S4={⊕,&,1} называется алгеброй Жегалкина .

Основные свойства.

1. коммутативность

h1⊕h2=h2⊕h1 h1&h2=h2&h1

2. ассоциативность

h1⊕(h2⊕h3)=(h1⊕h2)⊕h3 h1&(h2&h3)=(h1&h2)&h3

3. дистрибутивность

h1&(h2⊕h3)=(h1&h2)⊕(h1&h3)

4. свойства констант

5. h⊕h=0 h&h=h
Утверждение . Через операции алгебры Жегалкина можно выразить все другие булевы функции:

x→y=1⊕x⊕xy

x↓y=1⊕x⊕y⊕xy

18.Полином Жегалкина. Способы построения. Пример.

Полиномом Жегалкина (полиномом по модулю 2) от n переменных x 1 ,x 2 ... x n называется выражение вида:

c 0 ⊕c 1 x 1 ⊕c 2 x 2 ⊕ ... ⊕c n x n ⊕c 12 x 1 x 2 ⊕ ... ⊕c 12 ... n x 1 x 2 ... x n ,

где постоянные C k могут принимать значения 0 ли 1.

Если полином Жегалкина не содержит произведений отдельных переменных, то он называется линейным (линейная функция).

Например, f=x⊕yz⊕xyz и f 1 =1⊕x⊕y⊕z - полиномы, причем вторая является линейной функцией.

Теорема . Каждая булева функция представляется в виде полинома Жегалкина единственным образом.

Приведем основные методы построения полиномов Жегалкина от заданной функции.

1. Метод неопределенных коэффициентов. Пусть P(x 1 ,x 2 ... x n) - искомый полином Жегалкина, реализующий заданную функцию f(x 1 ,x 2 ... x n). Запишем его в виде

P=c 0 ⊕c 1 x 1 ⊕c 2 x 2 ⊕ ... ⊕c n x n ⊕c 12 x 1 x 2 ⊕ ... ⊕c 12 ... n x 1 x 2 ... x n

Найдем коэффициенты C k . Для этого последовательно придадим переменным x 1 ,x 2 ... x n значения из каждой строки таблицы истинности. В итоге получим систему из 2 n уравнений с 2 n неизвестными, имеющую единственное решение. Решив ее, находим коэффициенты полинома P(X 1 ,X 2 ... X n).

2. Метод, основанный на преобразовании формул над множеством связок {,&}. Строят некоторую формулу F над множеством связок {,&}, реализующую данную функцию f(X 1 ,X 2 ... X n). Затем заменяют всюду подформулы вида A на A⊕1, раскрывают скобки, пользуясь дистрибутивным законом (см. свойство 3), а затем применяют свойства 4 и 5.

Пример . Построить полином Жегалкина функции f(X,Y)=X→Y

Решение .
1. (метод неопределенных коэффициентов). Запишем искомый полином в виде:

P=c 0 ⊕c 1 x⊕c 2 y⊕c 12 xy

Пользуясь таблицей истинности импликации получаем, что

f(0,0)=P(0,0)=C 0 =1

f(0,1)=P(0,1)=C 0 ⊕C 2 =1

f(1,0)=P(1,0)=C 0 ⊕C 1 =0

f(1,1)=P(1,1)=C 0 ⊕C 1 ⊕C 2 ⊕C 12 =1

Откуда последовательно находим, C 0 =1, C 1 =1, C 2 =0, C 12 =1

Следовательно: x→y=1⊕X⊕XY.

2. (Метод преобразования формул.). Имеем: x→y=xvy=(xy)=(x(y⊕1)) ⊕1=1⊕x⊕xy
Заметим, что преимущество алгебры Жегалкина (по сравнению с другими алгебрами) состоит в арифметизации логики, что позволяет выполнять преобразования булевых функций довольно просто. Ее недостатком по сравнению с булевой алгеброй является громоздкость формул.




Похожая информация.




Теорема поглощения записывается в двух формах - дизъюнктивной и

конъюнктивной, соответственно:

А +АВ =А (16)

А(А + В)=А (17)

Докажем первую теорему. Вынесем за скобки букву А:

А + АВ= А(1 + В)

Согласно теореме (3) 1 + В = 1, следовательно

А(1 + В) = А 1 = А

Чтобы доказать вторую теорему, раскроем скобки:

А(А + В) = А А + АВ = А + АВ

Получилось выражение, только что доказанное.

Рассмотрим несколько примеров на применение теоремы поглощения при

упрощении булевых формул.

Теорема склеивания также имеет две формы - дизъюнктивную и

конъюнктивную:

Докажем первую теорему:

поскольку согласно теоремам (5) и (4)



Для доказательства второй теоремы раскроем скобки:



Согласно теореме (6) следовательно:

По теореме поглощения (16) А+АВ = А

Теорема поглощения, как и теорема склеивания, применяется при упрощении

булевых формул, например:



Теорема де Моргана связывает все три основные операции булевой алгебры

Дизъюнкцию, конъюнкцию и инверсию:

Первая теорема читается так: инверсия конъюнкции есть дизъюнкция

инверсий. Вторая: инверсия дизъюнкции есть конъюнкция инверсий. Доказать теоремы Моргана можно с помощью таблиц истинности для левой и правой частей.

Теорема де Моргана применима и к большему числу переменных:

Лекция 5

Инвертирование сложных выражений

Теорема де Моргана применима не только к отдельным конъюнкциям

или дизъюнкциям, но и к более сложным выражениям.

Найдем инверсию выражения АВ + CD , представленного в виде дизъюнкции конъюнкций. Инвертирование будем считать законченным, если знаки отрицания стоят только над переменными. Введем обозначения: АВ = Х;

CD = Y, тогда

Найдем и подставим в выражение (22):



Таким образом:

Рассмотрим выражение, представленное в конъюнктивной форме:

(А + В)(С + D)

Найдем его инверсию в виде



Введем обозначения: А + В = X; С + D =Y, тогда

Найдем и подставим их в выражение

Таким образом:

При инвертировании сложных выражений можно пользоваться следующим правилом. Чтобы найти инверсию, необходимо знаки конъюнкции заменить знаками дизъюнкции, а знаки дизъюнкции - знаками конъюнкции и поставить инверсии над каждой переменной:

Понятие булевой функции

В общем случае функция (лат. functio - исполнение, соответствие,

отображение) - это некоторое правило (закон), согласно которому каждому элементу множества X, представляющего собой область значений независимого переменного х, ставится в соответствие определенный элемент множества F,

под которым понимается область значений зависимого переменного f . В случае булевых функций X = F = {0,1}. Правилом, при помощи которого задается функция, может служить любая булева формула, например:



Символом f здесь обозначена функция, которая является, как и аргументы А, В, С, двоичной переменной.

Аргументы - это независимые переменные, они могут принимать любые значения - либо 0, либо 1. Функция же f - зависимая переменная. Ее значение полностью определяется значениями переменных и логическими связями между ними.

Главная особенность функции: чтобы определить ее значение, в общем случае необходимо знать значения всех аргументов, от которых она зависит. Например, приведенная выше функция зависит от трех аргументов А, В, С. Если принять А = 1, то получим



т. е. получилось новое выражение, не равное ни нулю, ни

единице. Пусть теперь В = 1. Тогда



т. е. и в этом случае неизвестно, чему равна функция, нулю или единице.

Примем, наконец, С = 0. Тогда получим: f = 0. Таким образом, если в исходном выражении принять А = 1, В = 1, С= 0, то функция примет нулевое значение: f = 0.

Рассмотрим понятие набора значений переменных .

Если всем аргументам, от которых зависит функция, присвоены некоторые значения, то говорят о наборе значений аргументов, который можно

называть просто набором. Набор значений аргументов - это последовательность нулей и единиц, например, 110, где первая цифра соответствует первому аргументу, вторая - второму и третья - третьему. Очевидно, что необходимо заранее договориться, что такое первый, второй или, допустим, пятый аргумент. Для этого удобно пользоваться алфавитным расположением букв.

Например, если

то согласно латинскому алфавиту первым является аргумент Р, вторым -

Q, третьим - X, четвертым - У. Тогда по набору значений аргументов легко

найти значение функции. Пусть, например, дан набор 1001. Согласно его

записи т. е. на наборе 1001 заданная функция равна единице.

Еще раз отметим, что набор значений аргументов - это совокупность

нулей и единиц. Двоичные числа также являются наборами нулей и единиц.

Отсюда возникает вопрос - нельзя ли наборы рассматривать как двоичные

числа? Можно, и во многих случаях это очень удобно, особенно если двоичное

число перевести в десятичную систему. Например, если

А = 0, В = 1, С = 1, D= 0,

0 * 2 3 +1 * 2 2 +1 * 2 1 +0 * 2 0 = 4+2 = 6

т. е. заданный набор имеет номер 6 в десятичной системе.

Если по десятичному номеру требуется найти значения аргументов, то

поступаем в обратной последовательности: сначала десятичное число переводим в двоичное, затем слева дописываем столько нулей, чтобы общее число разрядов равнялось числу аргументов, после чего находим значения аргументов.

Пусть, например, требуется найти значения аргументов А, В, С, D, Е, F по набору с номером 23. Переводим число 23 в двоичную систему методом

деления на два:

В результате получаем 23 10 = 10111 2 . Это число пятизначное, а всего

аргументов шесть, следовательно, слева необходимо записать один нуль:

23 10 = 010111 2 . Отсюда находим:

А = 0, В = 1, С = 0, D = 1, Е = 1, F = 1.

Сколько всего существует наборов, если известно число п аргументов? Очевидно, столько же, сколько существует n-разрядных двоичных чисел, т. е. 2 n

Лекция 6

Задание булевой функции

Один способ мы уже знаем. Это аналитический, т. е. в виде математического выражения с использованием двоичных переменных и логических операций. Кроме него существуют и другие способы, важнейшим из которых является табличный. В таблице перечисляются все возможные наборы значений аргументов и для каждого набора указывается значение функции. Такую таблицу называют таблицей соответствия (истинности).

На примере функции



выясним, как построить для нее таблицу соответствия.

Функция зависит от трех аргументов А, В, С. Следовательно, в таблице

предусматриваем три колонки для аргументов A,B,C и одну колонку для значений функции f. Слева от колонки А полезно разместить еще одну колонку. В ней будем записывать десятичные числа, которые соответствуют наборам, если их рассматривать как трехразрядные двоичные номера. Эта десятичная

колонка вводится для удобства работы с таблицей, поэтому, в принципе,

ею можно пренебречь.



Заполняем таблицу. В строке с номером ООО записано:

А = В = С = 0.

Определим значение функции на этом наборе:

В колонке f записываем нуль в строке с набором 000.

Следующий набор: 001, т. е. А = В = 0, С = 1. Находим значение функции

на этом наборе:

На наборе 001 функция равна 1, следовательно, в колонке f в строке с

номером 001 записываем единицу.

Аналогично вычисляем значения функций на всех остальных наборах и

заполняем всю таблицу.

 


---




Читайте:
Царица Мария Ильинична, урождённая Милославская Арапов александр николаевич биография Смирение – христианская добродетель Слонимская духовная семинария регент при поступлении Водородная энергетика. Хранение водорода. Водород - это что за вещество? Химические и физические свойства водорода Атомный номер водорода Инфразвуковой излучатель для шумных соседей