Какой логической операции соответствует операция симметрическая разность

x₂) = 0.

В заключение отметим, что симметрическая разность имеет несколько названий: строгая дизъюнкция, исключающая альтернатива, сумма по модулю два. Эту операцию можно передать словами — «либо А, либо В», т.е. это логическая связка «или», но без включенной в нее связки «и».

18. Операции разности и импликации.

Разностью множеств A и B, это множество, которое вошло в A, но не вошло в B:

Дополнение к разности называется импликацией

— импликация

Для данных операций можно записать:

19. Операции симметрической разности и эквивалентности.

Симметрическая разность двух множеств А и В – это объединение следующих двух разностей, то есть

Д ополнительной к данной операции является операция эквивалентности, которая определяется теми же элементами множества А и В, которые являются для них общими, при этом элементы не входящие ни в А ни в В также являются эквивалентными.

Симметричная разность Эквивалентность

Симметричную разность имеет другие названия: строгая дизъюнкция, исключительная альтернатива, сложение по модулю.

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

20. Формы представления булевых функций (сднф, скнф, спнф).

Любую булеву функцию y=f(a,b) можно представить как комбинацию областей:

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

Такая форма представления называется СДНФ (совершенно-дизъюнктивная нормальная форма)

В ней констинтуенты – коньюнты соединяются с помощью дизъюнкции.

В логике Буля действует принцип двойственности, который говорит, если одновременно заменить все конъюнкции на дизъюнкции, или наоборот (все ^ на v), замене символов (конъюнкция на дизъюнкцию и 0 на 1), то все логические равенства остаются в силе.

Такая форма представления логических функций называется СКНФ (совершенная коньюктивная нормальная форма). В ней констинтуенты – дизъюнкты, соединяются с помощью конъюнкции.

Существует также третья форма представления логических функций СПНФ – совершенная полиномиальная нормальная форма. Ее можно получить из СДНФ путем следующей замены:

Бинарные операции над упорядоченными множествами

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

I. Пересечение упорядоченных множеств

Пересечение двух упорядоченных множеств A и B — это множество только с теми элементами A и B, которые одновременно принадлежат обоим множествам, без дублей. Сложность алгоритма O(m+n), где m и n — длины входных множеств A и B соответственно.

Сделал небольшую анимацию, чтобы показать как работает алгоритм.

Пример реализации на javascript:

Обращение к функции:

II. Разность упорядоченных множеств

Разность двух упорядоченных множеств A и B — это множество с элементами A, не совпадающими с элементами B, без дублей. Сложность алгоритма O(m+n), где m и n — длины входных упорядоченных множеств A и B соответственно.

III. Объединение упорядоченных множеств

Объединение двух упорядоченных множеств A и B — это множество с элементами A и элементы множества B, без дублей. Сложность алгоритма O(m+n), где m и n — длины входных упорядоченных множеств A и B соответственно.

IV. Симметрическая разность упорядоченных множеств

Симметрическая разность двух упорядоченных множеств A и B — это такое множество, куда входят все те элементы первого упорядоченного множества, которые не входят во второе упорядоченное множество, а также те элементы второго упорядоченного множества, которые не входят в первое упорядоченное множество. Сложность алгоритма O(2(m+n)), где m и n — длины входных упорядоченных множеств A и B соответственно.

По сути это вычитание множеств, сначала A из B, затем B из A.

04. Основные операции над множествами

Суммой или Объединением двух или произвольного (даже бесконечного) числа заданных множеств называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из заданных множеств. Эта операция над множествами обозначается знаком .

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

Два множества называются Непересекающимися (или расчлененными) если . Практический интерес представляют разбиения множества на взаимно непересекающиеся подмножества (эту задачу иногда называются Классификацией). Разбиением множества называется такая расчлененная система непустых подмножеств множества , что каждый элемент множества является элементом некоторого единственного множества этой системы. Возможность разбиения множества на непересекающиеся подмножества зависит от признака, по которому производится разбиение.

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

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

Симметрической разностью множеств и называется множество :

.

Обозначается симметрическая разность: или .

Для подмножеств данного множества выполняются следующие законы:

· Закон коммутативности (переместительный закон):

; ;

· Закон ассоциативности (сочетательный закон) для любой тройки множеств , и :

;

;

· Закон дистрибутивности (распределительный закон) для любой тройки множеств , и :

;

;

· ; ;

· ;;

· ; ;

· ;

· ;

· ; ;

· ; ;

· ; ;

· ; .

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

Свойства фигурируют попарно таким образом, что каждое получается из соседнего заменой на , на и наоборот. Такие выражения называются Двойственными друг другу.

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

Очевидно, что операция Разность не обладает свойствами коммутативности и ассоциативности, в то же время операция Симметрическая разность и коммутативна, и ассоциативна.

Большое значение в современной математике имеет множественная операция Декартово произведение. Если заданы два множества и , то из их элементов можно составить упорядоченные пары, взяв сначала какой-либо элемент первого множества, а затем – элемент второго множества. Декартовым произведением двух исходных множеств и называется множество , составленное из упорядоченных пар (). Декартово произведение множеств и обозначается .

Очевидно, что и ‑ различные множества, т. е. операция декартова произведения не коммутативна, но, в то же время, она обладает свойством ассоциативности.