ЛЕКЦИЯ 1.2.

Свойства операций над множествами

Пусть Каковы бы ни были заданные подмножества универсума U, справедливы соотношения

1. Идемпотентность.

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

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

Дистрибутивность.

2. Законы поглощения.

3. Свойства нуля.

4. Свойства единицы.

5. Инволютивность.

6. Законы де Моргана.

10. Свойства дополнения.

Доказательство этих равенств большей частью совершенно элементарно. Построим доказательства одного из законов дистрибутивности и одного из законов де Моргана.

Утверждение. .

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

.

Пусть Þ

.

.

Утверждение. .

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

, .

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

Запишем обобщение законов дистрибутивности и де Моргана

Доказательство проводится, например, методом математической индукции.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Для студента самое главное не сдать экзамен, а вовремя вспомнить про него. 10073 — | 7514 — или читать все.

78.85.5.224 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)
очень нужно

Законы де Мо́ргана (правила де Мо́ргана) — логические правила, связывающие пары логических операций при помощи логического отрицания. Названы в честь шотландского математика Огастеса де Моргана. В краткой форме звучат так:

Отрицание конъюнкции есть дизъюнкция отрицаний. Отрицание дизъюнкции есть конъюнкция отрицаний.

Содержание

Определение [ править | править код ]

Огастес де Морган первоначально заметил, что в классической пропозициональной логике справедливы следующие соотношения:

не (a и b) = (не a) или (не b) не (a или b) = (не a) и (не b)

В математике это выглядит так:

¬ ( a ∧ b ) = ¬ a ∨ ¬ b ¬ ( a ∨ b ) = ¬ a ∧ ¬ b <displaystyle <egin
eg <(awedge b)>=
eg vee
eg \
eg <(avee b)>=
eg wedge
eg end>> 000 или по-другому: 000 ( a ∧ b ) ¯ = a ¯ ∨ b ¯ ( a ∨ b ) ¯ = a ¯ ∧ b ¯ <displaystyle <egin<overline <(awedge b)>>=<overline >vee <overline >\<overline <(avee b)>>=<overline >wedge <overline >end>>

A ∩ B ¯ = A ¯ ∪ B ¯ A ∪ B ¯ = A ¯ ∩ B ¯ <displaystyle <egin<overline >=<overline >cup <overline >\<overline >=<overline >cap <overline >end>> 000 или по-другому: 000 ( A ∩ B ) C = A C ∪ B C , ( A ∪ B ) C = A C ∩ B C . <displaystyle <egin(Acap B)^=A^cup B^,\(Acup B)^=A^cap B^.end>>

Эти правила также действительны для множества элементов (семейств):

⋂ i ∈ I A i ¯ = ⋃ i ∈ I A i ¯ <displaystyle <overline <igcap _A_>>=igcup _<overline >>> 00000 и 00000 ⋃ i ∈ I A i ¯ = ⋂ i ∈ I A i ¯ <displaystyle <overline <igcup _A_>>=igcap _<overline >>> .

¬ ∀ x P ( x ) ≡ ∃ x ¬ P ( x ) , <displaystyle
eg forall x,P(x)equiv exists x,
eg P(x),> ¬ ∃ x P ( x ) ≡ ∀ x ¬ P ( x ) . <displaystyle
eg exists x,P(x)equiv forall x,
eg P(x).>

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

a ∧ b = ¬ ( ¬ a ∨ ¬ b ) <displaystyle awedge b=
eg (
eg vee
eg )> a ∨ b = ¬ ( ¬ a ∧ ¬ b ) <displaystyle avee b=
eg (
eg wedge
eg )>

Если существует суждение, выраженное операцией логического умножения двух или более элементов, т. е. операцией «и»: ( A ∧ B ) <displaystyle <(Awedge B)>> , то для того, чтобы найти обратное ¬ ( A ∧ B ) <displaystyle <
eg (Awedge B)>> от всего суждения, необходимо найти обратное от каждого элемента и объединить их операцией логического сложения, т. е. операцией «или»: ( ¬ A ∨ ¬ B ) <displaystyle (
eg vee
eg )> . Закон работает аналогично в обратном направлении: ¬ ( A ∨ B ) = ( ¬ A ∧ ¬ B ) <displaystyle
eg (Avee B)=(
eg wedge
eg )> .

Применение [ править | править код ]

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

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

Рассмотрим выражение в левой части :

Если хМ, то значит, что хС и одновременноА илиВ

Когда хА, х(АС), а когда хВ х(ВС)

Объединение этих выражений даёт правую часть.

Возьмем правую часть равенства. Согласно закону ассоциативности

раскроем скобки и получим:

(АС)(ВС)=АВСВАССС=АВС (упростили используя

закон поглощения ). Из записи закона ассоциативности и закона

дистрибутивности видно, что один закон можно получить из другого,

заменив знаки “” и “”, следовательно, законы двойственны.

Если А содержится в В, то АB=В.

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

Исходя из определения операции пересечения ясно, что АМ содержится в А.В итоге получаем А.

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

Законы де Моргана.

Эти законы позволяют выразить законы объединения и пересечения друг через друга с использованием операции дополнения :

а) АВ=

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

Обозначим через М: М=АВ и =. Если теперь объединение М идаст единичное множество, то закон будет доказан.

М  = А  В  = А(В )(В ). Используя определение дополнения получим :

М  =АВ=1В=1=I

б) АВ=

Обозначим через М: М=АВ и =. Если теперь объединение М идаст единичное множество, то закон будет доказан.

М  = А  В  =( А)  (В )= В=1 =1=I

Законы де Моргана так же являются двойственными.

ВЫВОДЫ ПО РАЗДЕЛУ.

Если АВ и ВА, то А=В

Если АВ и ВС, то АС

Если АВ, то АВ=В, АВ=А

А  = I

A  =

=I

=

= A

Если АВ, то

( ) =

( ) =

Минимизация функционального представления

Определим функцию от фрагментов, являющихся множествами. Функцией будем называть взаимооднозначное отображение элементов группы множеств Аiв элементы множества С. Если каждому элементу С соответствует некоторый элемент Аi, такую функцию называют всюду значимой

f – функция переводит элементыAiво множество С.

Если пересечение множеств обозначать как функциональную операцию Р , то

На единичном множестве 1 заданы множества А,В,С. В этом случае с помощью известной операции над множествами переводим исходное множество в какое-либо другое.

f (А,В,С) = АВС  АС  В  АВ  AС  С  В;

Записанное выражение назовем формулой. Определим сложность формулы, как количество, содержащихся в ней исходных множеств. Для приведенного примера сложность =20. При аналазе формул первым вопросом является: «Можно ли уменьшить сложность формулы?» Сделаем это на примере применяя законы дистрибутивности и поглощения

f(А,В,С) = АВС  А В  А(В  С)  (В  С) =

= АВС  А B  В  С = В А С =

=  В  С ==1

f(А,В,С) = АС  С  ВС  АВС  АВ В = АС  С  В  АВ =

=В  АС  С;

F(А,В,С) = АС  С  ВС  АВС  АВ В = АС  С  ВС  АВ  В = АС  С  ВС  В = С  В

Как видно из примеров минимизация одних и тех же функций может дать разные результаты при применении одних и тех же законов.