Правило де моргана примеры

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

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

Содержание

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

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

не (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 )> .

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

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

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

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

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

Покажем на примерах некоторые приемы и способы, применяемые при упрощении логических формул:

1. 
   (законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с её инверсией и правило операций с константами);
2. 
   (применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией);
3. 
   ( повторяется второй сомножитель , что разрешено законом идемпотенции; затем комбинируются два первых и два последних сомножителя и используется закон склеивания);
4. 
   ( вводится вспомогательный логический сомножитель ( ); затем комбинируются два крайних и два средних логических слагаемых и используется закон поглощения);
5. 
   (сначала добиваемся, чтобы знак отрицания стоял только перед отдельными переменными, а не перед их комбинациями, для этого дважды применяем правило де Моргана; затем используем закон двойного отрицания);
6. 
   (выносятся за скобки общие множители; применяется правило операций с константами);
7. 
   (к отрицаниям неэлементарных формул применяется правило де Моргана; используются законы двойного отрицания и склеивания);
8. 
   (общий множитель x выносится за скобки, комбинируются слагаемые в скобках – первое с третьим и второе с четвертым, к дизъюнкции применяется правило операции переменной с её инверсией);
9. 
   (используются распределительный закон для дизъюнкции, правило операции переменной с ее инверсией, правило операций с константами, переместительный закон и распределительный закон для конъюнкции);
10. 
    (используются правило де Моргана, закон двойного отрицания и закон поглощения).

Из этих примеров видно, что при упрощении логических формул не всегда очевидно, какой из законов алгебры логики следует применить на том или ином шаге.

Пример 1. Утверждение “Симпсон будет признан судом виновным тогда и только тогда, когда все 12 присяжных заседателей признают его виновным” может быть записано в виде формулы B≡(A1&A2&. &A12), где B означает виновность, а An – факт признания вины n-ым присяжным заседателем. Равносильная ей формула ךB≡ ך(A1&A2. &A12) по закону де Моргана может быть преобразована в формулу ךB≡(ךA1 V ךA2 &. ךA12), которую можно интерпретировать так: “Симпсон не будет признан судом виновным тогда и только тогда, когда хотя бы один из 12 присяжных заседателем не признает его вины”.

Пример 2. Рассмотрим следующую задачу. Имеется текстовый файл, который необходимо прочитать посимвольно до появления любого из трех символов: (%,#,EOF). Привести возможные варианты решения этой задачи. В первую очередь нас интересует построение условия для циклической конструкции, выполняющей чтение символов из файла. Обозначим факт появления первого символа как А, второго – как В и третьего – как С. Тогда условие, при котором читаются символы из файла будет записано в виде следующей формулы: (ךA)&(ךB)&(ךC) Однако для данной формулы имеется логически эквивалентная ей конструкция: ך(A V B V C) Поэтому можно предложить два варианта реализации цикла чтения содержимого файла на языке программирования С.

9. Законы логики.

Равносильности формул логики высказываний часто называют законами логики. Знание законов логики позволяет проверять правильность рассуждений и доказательств.

Закон тождества. Он сформулирован древнегреческим философом Аристотелем. Закон тождества утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует. (A = A)

Закон противоречия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием. (A&(ךA)) = ”Это яблоко спелое” и ”Это яблоко не спелое”.

Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно либо ложно. Третьего не дано. ”Сегодня я получу 5 либо не получу”. Истинно либо суждение, либо его отрицание. (AV(ךA)) =

Закон двойного отрицания. Отрицать отрицание какого-нибудь высказывания – то же, что утверждать это высказывание. ”Неверно, что 2×2 не равно 4” . (ך(ךA)) = A

Законы идемпотентности. В алгебре логики нет показателей степеней и коэффициентов. Конъюнкция одинаковых ”сомножителей” равносильна одному из них. (A&A) = A, (AVA) = A

Законы коммутативности и ассоциативности. Конъюнкция и дизъюнкция аналогичны одноименным знакам умножения и сложения чисел.

Коммутативность: (A&B) = (B&A), (AVB) = (B VA)

Ассоциативность: (A&B)&C = A&(B&C) (AVB)VC = AV(B VC)

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

Законы де Моргана: (ך(A&B)) = ((ךA)V(ךB)) – отрицание логического произведения эквивалентно логической сумме отрицаний множителей; (ך(AVB)) = ((ךA)&(ךB)) – отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых.

Законы поглощения A&(A V B) = A; AV(A&B) = A

Законы склеивания (AVB)&((ךA)VB) = B; (A&B)V((ךA)&B) = B

10. Понятие теоремы. Основная теорема логического вывода и ее доказательство.

· Формула G теории L называется теоремой теории L, если существует вывод в L, в котором последней формулой является G. Вообще говоря, может не существовать алгоритма, позволяющего по формуле определить существование ее вывода. Теория, для которой такой алгоритм существует, называется разрешимой, в противном случае – неразрешимой.

Доказать теорему означает построить вывод в данной Формальной Теории.

· Лемма: формула, которая используется в процессе вывода и сама имеет вывод в данной формальной теории.

Построение вывода для заданной формулы является непростой задачей. Ещё более сложной задачей может быть ответ на вопрос: А существует ли данный вывод?

Одной из важнейших задач современной науки является:

1) Построение алгоритмов, определяющих существует доказательство алгоритмов или нет. Если такой алгоритм удается построить для теории, то теория называется разрешимой.

2) Построение методов алгоритмического доказательства теоремы.

Дата добавления: 2015-05-05 ; просмотров: 1 | Нарушение авторских прав