Второй закон де моргана доказательство

Второй закон де моргана доказательство

ЛЕКЦИЯ 1.2.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

Пусть Þ

.

.

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

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

, .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  Как сохранить текст на картинке в ворде

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

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

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

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

а) АВ=

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

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

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

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

б) АВ=

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

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

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

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

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

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

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

А  = I

A  =

=I

=

= A

Если АВ, то

( ) =

( ) =

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

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

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

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

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

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

Читайте также:  Установленная мощность принтера квт

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

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

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

=  В  С ==1

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

=В  АС  С;

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

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

Зависит от того, что разрешено. Например, для
!(A v B) = !A & !B
пойдем таким путем
!(A v B) & (A v B) = !A & !B & (A v B)
Слева ноль. Раскроем справа по дистрибутивности
(!A & !B & A) v (!A & !B &B) = 0 v 0 = 0

Для второго все аналогично, добавляем с двух сторон коньюнкцией (A&B)

Ссылка на основную публикацию
Во время записи произошла неопознанная ошибка obs
Если вы хотите начать потоковую передачу своим бесчисленным неиспользованным и в настоящее время неизвестным поклонникам по всему миру, Open Broadcast...
В ворде маленький лист что делать
открываю ворд, а у меня почему то листок слево. как в настройках сделать , чтобы он был по средине? 19...
В кореле не двигаются объекты
Теперь, после этого отступления, рассмотрим процедуру удаления. Удалить объект очень просто. Выделите объект или несколько объектов, которые вы хотите удалить....
Возобновить работу системы или удалить данные
После включения, через некоторое время появляется надпись на экране: Загрузчик возобновления Windows Последняя попытка возобновления работы системы из прежнего места...
Adblock detector