Законы моргана алгебры логики

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

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

Содержание

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

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

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

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

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

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

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

Содержание

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

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

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

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

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

– общее название логических законов, связывающих с помощью отрицания конъюнкцию («и») и дизъюн­кцию («или»). Названы именем англ. логика XIX в. А. де Моргана.

Один из этих законов можно выразить так: отрицание конъюнк­ции эквивалентно дизъюнкции отрицаний. Напр.: «Неверно, что завтра будет холодно и завтра будет дождливо, тогда и только тогда, когда завтра не будет холодно или завтра не будет дождливо».

Другой закон: отрицание дизъюнкции эквивалентно конъюнк­ции отрицаний. Напр.: «Неверно, что ученик знает арифметику или знает геометрию, тогда и только тогда, когда он не знает ни арифметики, ни геометрии».

В терминах символики логической (р, q — некоторые высказыва­ния; & – конъюнкция; v – дизъюнкция;

— отрицание, «невер­но, что»; = — эквивалентность, «если и только если») данные два закона представляются формулами:

q), неверно, что р и q, если и только если неверно р и неверно q;

q), неверно, что или р, или q, если и только если неверно р и неверно q.

На основе этих законов, используя отрицание, связку «и» мож­но определить через «или», и наоборот: «р и q» означает «Невер­но, что не–р или не–q», «р или q» означает «Неверно, что не–р и не–q».

Напр., «Идет дождь и идет снег» означает «Неверно, что нет дождя или нет снега»; «Сегодня холодно или сыро» означает «Не­верно, что сегодня не холодно и не сыро».

Закон дистрибутивности(от англ. Distribution – распреде­ление, размещение)

– общее название группы логических законов сходной структуры. Эти законы позволяют распределить одну ло­гическую связь относительно другой.

Полный 3. д. конъюнкции относительно дизъюнкции с использо­ванием символики логической формулируется так (р, q, r — некото­рые высказывания; & – конъюнкция, «и»; v – дизъюнкция, «или»; = — эквивалентность, «если и только если»):

первое и (второе или третье), если и только если (первое и вто­рое) или (первое и третье). Напр.: «Сегодня идет дождь и завтра ясно или послезавтра ясно в том и только в том случае, когда сегодня идет дождь и завтра ясно или сегодня идет дождь и после­завтра ясно».

Полный 3. д. дизъюнкции относительно конъюнкции:

первое или (второе и третье), если и только если (первое или вто­рое) и (первое или тре’тье). Напр.: «Завтра будет солнечно или послезавтра будет мороз и снег тогда и только тогда, когда завтра будет солнечно или послезавтра будет мороз и завтра будет сол­нечно или послезавтра будет снег».

Закон самодистрибутивности импликации (->, «если, то») дает возможность распределять импликацию по импликации:

если (если первое, то (если второе, то третье)), то (если (если первое, то второе), то (если первое, то третье)). Этот закон верен для импликации материальной, но не имеет места для целого ряда иных импликаций, вводимых в современной логике.

Закон дунса скота

– закон логики классической, характери­зующий логическое противоречие и импликацию материальную. За­кон можно передать так: ложное высказывание влечет (имплици­рует) любое высказывание. Напр.: «Если дважды два не равно четырем, то, если дважды два четыре, вся математика ничего не значит».

Первое упоминание закона принадлежит средневековому фило­софу и логику Дунсу Скоту, прозванному «тонким доктором» схо­ластики. Амер. философ и логик К. И. Льюис (1883-1964), поло­живший начало исследованию модальной логики, отнес данный закон к парадоксальным положениям классической логики. В пред­ложенной самим К. И. Льюисом новой теории логического следо­вания — т. наз. теории строгой импликации — 3. Д. С. не­доказуем. Но в этой теории есть собственный аналогичный парадокс, говорящий уже о логической невозможности: логически невоз-

можное высказывание влечет любое высказывание. Напр.: «Если снег бел и вместе с тем не бел, трава бывает только черной».

С использованием символики логической (р, q — некоторые выска­зывания;

– отрицание, «неверно, что»; —> импликация, «если, то») 3. Д. С. выражается формулой:

если неверно, что p, то если р, то q; или эквивалентной ей в класси­ческой логике формулой:

Если принимаются высказывание и его отрицание, то, исполь­зуя данные формулы в качестве схем вывода, можно получить лю­бое высказывание. В подобного рода переходах есть элемент пара­доксальности. Особенно заметным он становится, когда в качестве следствия берется явно ложное и совершенно не связанное с по-сылками высказывание. Напр.: «Если Солнце и звезда, и не звезда, то Луна сделана из зеленого сыра».

3. Д. С. есть своего рода предостережение против принятия лож­ного высказывания: введение в научную теорию такого высказыва­ния ведет к тому, что в ней становится доказуемым все что угодно и она перестает выполнять свои функции. Однако предостережение не настолько очевидно, чтобы стать одним из правил логического следования. Не все современные описания следования принимают 3. Д. С. в качестве правомерного способа рассуждения. Уже построены теории логических связей, в которых этот и подобные ему способы рассуждения считаются недопустимыми.

Если 3. Д. С. не принимается, то появление противоречия в сис­теме утверждений становится допустимым. Такое более «терпи­мое» отношение к противоречию лежит в основе логических тео­рий, получивших название паранепротиворечивой логики.