Законы де моргана для множеств

Множества Содержание 1 Определения 2 Способы задания множеств 2.1 Перечисление 2.2 Описание 3 Отношения между множествами 3.1 Включение 3.2 Равенство

Законы де моргана для множеств

Множества

Содержание

  • 1 Определения
  • 2 Способы задания множеств
    • 2.1 Перечисление
    • 2.2 Описание
  • 3 Отношения между множествами
    • 3.1 Включение
    • 3.2 Равенство
    • 3.3 Общие элементы
  • 4 Специальные множества
  • 5 Операции над множествами
    • 5.1 Бинарные операции над множествами
    • 5.2 Унарные операции над множествами
  • 6 Теорема де Моргана

Определения [ править ]

Определение:
Множество — первичное математическое понятие, которому не дано строгое математическое определение. Представляет собой набор, совокупность каких-либо объектов, объединенных общим свойством.
Определение:
Объекты, из которых состоит множество, называют элементами этого множества. Если [math]a[/math] — элемент множества [math]A[/math] , то записывают [math]a in A[/math] (« [math]a[/math] принадлежит [math]A[/math] »). Если [math]a[/math] не является элементом множества [math]A[/math] , то записывают [math]a notin A[/math] (« [math]a[/math] не принадлежит [math]A[/math] »). В отличие от мультимножества каждый элемент множества уникален, и во множестве не может быть двух идентичных элементов.

Способы задания множеств [ править ]

Существуют два основных способа задания множеств: перечисление и описание.

Перечисление [ править ]

Первый способ состоит в том, что задаётся и перечисляется полный список элементов, входящих в множество.

Описание [ править ]

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

[math] A = [/math] , где [math]P[/math] — определенное свойство элемента [math]a[/math] .

Отношения между множествами [ править ]

Два множества [math]A[/math] и [math]B[/math] могут вступать друг с другом в различные отношения.

Включение [ править ]

  • [math]A[/math] включено в [math]B[/math] , если каждый элемент множества [math]A[/math] принадлежит также и множеству [math]B[/math] : [math]displaystyle Asubseteq BLeftrightarrow forall ain A colon ain B[/math]
  • [math]A[/math] включает [math]B[/math] , если [math]B[/math] включено в [math]A[/math] : [math][/math]
  • [math]A[/math] строго включено в [math]B[/math] , если [math]A[/math] включено в [math]B[/math] , но не равно ему: [math][/math]

Равенство [ править ]

  • [math]A[/math] равно [math]B[/math] , если [math]A[/math] и [math]B[/math] включены друг в друга: [math][/math]

Общие элементы [ править ]

  • [math]A[/math] и [math]B[/math] не пересекаются, если у них нет общих элементов: [math]A[/math] и [math]B[/math] не пересекаются [math][/math]

Специальные множества [ править ]

Определение:
Пустое множество — множество, не содержащее ни одного элемента. Обычно пустое множество обозначают как [math]varnothing[/math] .
Определение:
Универсальное множество — множество, содержащее все объекты и все множества. В тех аксиоматиках, в которых универсальное множество существует, оно единственно. Обычно универсальное множество обозначают как [math] displaystyle mathbb [/math] .

Операции над множествами [ править ]

Бинарные операции над множествами [ править ]

  • Пересечение [math]A[/math] и [math]B[/math] . [math]>[/math]
  • Объединение [math]A[/math] и [math]B[/math] . [math]>[/math]
  • Разность [math]A[/math] и [math]B[/math] . [math]>=>[/math]
  • Симметрическая разность [math]A[/math] и [math]B[/math] . [math] [/math]

Унарные операции над множествами [ править ]

  • Дополнение определяется следующим образом: [math]equiv A^=>=Usetminus A>[/math] .

Теорема де Моргана [ править ]

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

Сначала докажем, что [math] displaystyle overline displaystyle subseteq bigcaplimits_alpha overline[/math] .

Пусть [math]x in left ( overline right )[/math] . Значит, [math]nexists alpha_i[/math] такого, что [math]x in A_[/math] . Следовательно, [math]forall alpha : x in overline Rightarrow x in left (bigcaplimits_alpha overline right )[/math] . В силу выбора [math]x[/math] (любой элемент множества [math]overline[/math] ) следует искомое включение.

Теперь докажем, что [math] displaystyle bigcaplimits_alpha overline subseteq overline[/math]

Пусть [math]x in left ( bigcaplimits_alpha overline right )[/math] . Тогда [math]forall alpha : x in overline Rightarrow x notin A_alpha[/math] . Поскольку [math]x[/math] не входит ни в одно объединяемое множество, то [math]x notin bigcuplimits_alpha A_alpha Rightarrow x in overline A_alpha>[/math]

Теорема де Моргана устанавливает двойственность понятий объединения и пересечения множеств. То есть, имея некоторое верное равенство, содержащее объединения и пересечения, можно переписать его, заменив пересечения на объединения и наоборот. Например, из равенства

[math](A cup B) cap C = (A cap C) cup (B cap C) Rightarrow (A cap B) cup C = (A cup C) cap (B cup C)[/math]

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

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

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

Определение

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

not (P and Q) = (not P) or (not Q) not (P or Q) = (not P) and (not Q)

Обычная запись этих законов в формальной логике:

Если существует операция логического умножения двух и более элементов, операция «и» — (A&B), то для того, чтобы найти обратное от всего суждения

(A&B), необходимо найти обратное от каждого элемента и объединить их операцией логического сложения, операцией «или» — (

B). Закон работает аналогично в обратном направлении:

История

  • «Противоречащая противоположность дизъюнктивного суждения — конъюнктивное суждение, составленное из противоречащих противоположностей частей дизъюнктивного суждения (The contradictory opposite of a disjunctive proposition is a conjunctive proposition composed of the contradictories of the parts of the disjunctive proposition)» (Уильям Оккам, Summa Logicae).

Ссылки

  • Weisstein, Eric W.Законы де Моргана (англ.) на сайте Wolfram MathWorld.

Wikimedia Foundation . 2010 .

  • Жук-олень
  • Эгер (река)

Смотреть что такое «Законы де Моргана» в других словарях:

ЗАКОНЫ ДЕ МОРГАНА — законы логики высказываний, связывающие отрицание с операциями конъюнкции и дизъюнкции, соответствующими логич. союзам и и неразделительному или естеств. языка. З. де М. в словесной формулировке были известны еще схоластич. логикам. В математич.… … Философская энциклопедия

Законы Моргана — * законы Моргана * Morgan’s Laws … Генетика. Энциклопедический словарь

Моргана законы — * Моргана законы * Morgan’s Laws or M. rules основные положения хромосомной теории наследственности, разработанные Т. Морганом и сотр. в 1911 1915 гг. Сводятся к следующему: 1) гены находятся в хромосомах и в пределах одной хромосомы образуют… … Генетика. Энциклопедический словарь

Моргана единица морганида М — Моргана единица, морганида, М * Моргана адзінка, марганіда, М * Morgan’s unit or M относительное расстояние между двумя генами на хромосоме, или частота рекомбинации () между двумя генетическими маркерами. Одна морганида соответствует 100%… … Генетика. Энциклопедический словарь

МОРГАНА ЗАКОНЫ — Предусматривают, что: гены находятся в хромосомах, и в пределах одной хромосомы образуют одну группу сцепления; гены в хромосомах расположены линейно; между гомологичными хромосомами в мейозе может происходить кроссинговер, частота которого пропо … Термины и определения, используемые в селекции, генетике и воспроизводстве сельскохозяйственных животных

законы Моргана — Ряд закономерностей наследования, иногда объединяемых в общую группу З.М.: вхождение генов в хромосомы, представляющие собой группы сцепления, линейное расположение генов в хромосомах и наличие между гомологичными хромосомами мейотической… … Справочник технического переводчика

Законы Хаммурапи — Свод законов Хаммурапи (или Кодекс Хаммурапи), созданный приблизительно в 1780 г. до н. э., является одним из древнейших законодательных памятников. Найден археологической экспедицией Жака де Моргана в ходе раскопок в 1901 1902 годах в Сузах… … Википедия

Законы Хамураппи — Свод законов Хаммурапи (или Кодекс Хаммурапи), созданный приблизительно в 1780 г. до н. э., является одним из древнейших законодательных памятников. Найден археологической экспедицией Жака де Моргана в ходе раскопок в 1901 1902 годах в Сузах… … Википедия

Законы царя Хамураппи — Свод законов Хаммурапи (или Кодекс Хаммурапи), созданный приблизительно в 1780 г. до н. э., является одним из древнейших законодательных памятников. Найден археологической экспедицией Жака де Моргана в ходе раскопок в 1901 1902 годах в Сузах… … Википедия

законы Моргана — Morgan rules законы Моргана. Pяд закономерностей наследования, иногда объединяемых в общую группу З.М.: вхождение генов в хромосомы, представляющие собой группы сцепления, линейное расположение генов в хромосомах и наличие между гомологичными… … Молекулярная биология и генетика. Толковый словарь.

Логические формулы де Моргана

Краткая историческая справка

Огастес, или же Август де Морган жил в середине XIX века в Шотландии. Он был первым президентом Лондонского математического общества, но прославился в основном благодаря своим работам в сфере логики.

Ему принадлежит множество научных трудов. Среди них работы по теме пропозиционной логики и логики классов. А также, разумеется, формулирование всемирно известной формулы де Моргана, названной в его честь. В дополнение ко всему этому Август де Морган написал множество статей и книг, в том числе «Логика – это ничто», которую, к сожалению, так и не перевели на русский язык.

Суть логической науки

В самом начале необходимо разобраться в том, как построены и на чем основаны логические формулы. Лишь потом можно переходить к изучению одного из самых известных постулатов. В наиболее простых формулах существует две переменные, а между ними ряд знаков. В отличие от того, что знакомо и привычно для среднестатистического человека по математическим и физическим задачам, в логике переменные чаще всего имеют буквенное, а не численное обозначение и представляют собой какое-либо событие. Например, переменная «a» может означать «завтра грянет гром» или «девушка говорит неправду», а под переменной «b» будут иметь в виду, что «завтра будет солнечно» или «парень говорит правду».

В пример можно привести одну из самых простых логических формул. Переменная «a» означает то, что «девушка говорит неправду», а под переменной «b» имеется в виду, что «парень говорит правду».

А вот и сама формула: a = b. Она означает, что тот факт, что девушка говорит неправду равносилен тому, что парень говорит правду. Можно сказать, что она говорит неправду только в том случае, если он говорит правду.

Суть формул де Моргана

На самом деле все довольно очевидно. Формула закона де Моргана записывается вот так:

Не (а и b) = (не а) или (не b)

Если переводить эту формулу на слова, то отсутствие и «a», и «b» означает либо отсутствие «a», либо отсутствие «b». Если говорить на более простом языке, то если нет и «a», и «b», значит нет «a» или нет «b».

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

(Не а) или (не b) = Не (а и b)

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

Конъюнкция – это операция, которую в сфере логики связывают с союзом «и».

Дизъюнкция – это операция, которую в сфере логики связывают с союзом «или». Например, «или одно, или второе, или оба сразу».

Простейшие примеры из жизни

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

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

Нельзя сказать, что учащийся знаком с физикой и химией в том случае, если он не знает физики или не знает химии.

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

Зачем было искать доказательства и формулировать законы?

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

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

И напоследок

Без логики невозможно представить себе человеческое общество. На ней основывается большинство современных технических наук. А формулы де Моргана неоспоримо являются неотъемлемой частью логики.

Законы де моргана для множеств

Что такое творческие кладовые по дискретной математике
портала «Русский след»?

Поэзия всей сути чисел
Сравнима с россыпью светил,
Прекрасна как алмазный бисер
Родоначальница мерил. (Ю.Н. Пиллигримов)

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

З аконы двойственности или , другими словами, закон ы Де – Моргана , открытые шотландским
логиком Огаснесом де Морганом в девятнадцатом веке нашли широко применение в исчислении
высказываний, в теории множеств, в теории автоматов, в теории алгоритмов и других областях науки
и техники. Они относятся к одним из широко применяемых инструментов при оптимизации
алгоритмов, систем автоматики, при проектировании радиорелейных системах и в других
практических применениях.

Первый закон де Моргана гласит: «Отрицание конъюнкции высказываний равнозначно
дизъюнкции отрицаний этих высказываний», что выражается следующей формулой:

≡ `A ú`B ; Здесь знак ù обозначает союз «и», символизирует операцию «конъюнкция», а знак ú обозначает союз «или», символизирует знак «дизъюнкция», черта сверху буквы — знак отрицание, знак ≡ означает равнозначность.

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

Если истинное высказывание обозначить цифрой 1, а ложное цифрой 0, то таблица истинного значения конъюнкции будет выглядеть так:

А В А ù В

Если сравнить конъюнкцию (логическое умножение) с арифметическим умножением, то результат произведения АВ сходен с результатом в арифметике 1 х 1 = 1. 1 х 0 = 0, 0 х 1 = 0, 0 х 0 = 0. Общее отрицание конъюнкции, которое обозначается чертой сверху свидетельствует о том, что имеет место одно из трёх сочетаний в вышеприведённой таблицы, где фигурирует хоть один 0.

Если конъюнкцию отрицать, а отрицание обозначается чертой сверху, то в результате мы получим следующее преобразование: ( ) ≡ ( `A ú`B ), где знак ú означает слово «или», черта сверху формулы — отрицание всей формулы, черта над `A — отрицание А, то есть, не-А, `B — не-В . Это преобразование и есть, в сущности, первый закон де Моргана , который доказывается методом рассуждений на базе принятой аксиоматике в исчислении высказываний. А, именно, «какое бы конкретное содержание не вкладывалось в А, всегда А и отрицание `A (не-А), вместе не могут быть истинными. Это положение называется логическим законом противоречия, который формулируется так: » не могут быть одновременно истинными два противоречащих высказывания об одном и том же предмете в одно и тоже время и одном и том же отношении». Гильберт и Аккерман при доказательстве 1-ой теоремы де Моргана, так это поясняют: Если А означает утверждение » треугольник ∆ прямоугольный», а В — » треугольник ∆ равнобедренный», конъюнкции А ù В, тогда соответствует высказывание » треугольник ∆ прямоугольный и треугольник ∆ равнобедренный», а этого не может быть, Отрицание этого является утверждение «треугольник ∆ не прямоугольный или треугольник ∆ не равнобедренный», а это высказывание и выражается формулой ` ( A ú`B ). Откуда следует справедливость первой теоремы де Моргана.

Графически конъюнкцию можно представить двумя наложенными областями, г де элементы в о второй области принадлежат и множеству А и множеству В. Отрицание принадлежности элементов в этой области, возможно тогда и только тогда, когда этих элементов нет или в области А, или в области В, или в обеих областях одновременно, что записывается `A ú`B .

В торой закон де Моргана, = `A ù `B говорит, что отрицание дизъюнкции равнозначно конъюнкции отрицаний этих высказываний.

Доказательство 2-го закона де Моргана () может быть таким :

Пусть x î , т огда из утверждения x î U (где U — универсальное множество) и x ï A ú B следует x ï A и x ï B x î`A и х î `B х î `A ù `B í `A ù `B ;

Пусть x î `A ù `B , тогда х î `A и х î `B x î U и ï A и x ï B x ï А ú В, то есть

x î `A ù `B í .

В силу справедливости того и другого справедливо и доказываемое утверждение.

Нечеткие и случайные множества

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

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

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

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

(1)

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

(2)

(3)

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

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

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

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

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

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

(4)

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

(5)

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

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

(6)

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

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

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

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

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

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

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

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

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

Елена Фомина/ автор статьи

Приветствую! Я являюсь руководителем данного проекта и занимаюсь его наполнением. Здесь я стараюсь собирать и публиковать максимально полный и интересный контент на темы связанные с юридическим оформлением документов. Уверена вы найдете для себя немало полезной информации. С уважением, Елена Фомина.

Понравилась статья? Поделиться с друзьями:
News-nnovgorod.ru
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: