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

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

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

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

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

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

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

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

А

В

А  ù   В

1	1	1
1	0	0
0	1	0
0	0	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   í  .

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