La leĝoj de De Morgan
#000000
Sorbado / Maniero tollens /
#000002
En propozicia logiko kaj bulea algebro, la leĝoj de De Morgan [1] [2] [3] estas paro de transformreguloj kiuj estas ambaŭ validaj reguloj de inferenco.
Ili estas nomitaj laŭ Augustus De Morgan, 19-ajarcenta brita matematikisto.
La reguloj permesas la esprimon de konjunkcioj kaj dismetadoj sole laŭ unu la alian per negacio.
#000003
La reguloj povas esti esprimitaj en la angla kiel:
#000004
la negacio de konjunkcio estas la dismetado de la negacioj;
kaj la negacio de dismetado estas la konjunkcio de la negacioj;
#000005
la komplemento de la unio de du aroj estas la sama kiel la intersekciĝo de iliaj salutoj;
kaj la komplemento de la intersekciĝo de du aroj estas la sama kiel la unio de iliaj salutoj.
#000006
En aroteorio kaj bulea algebro, tiuj estas skribitaj formale kiel
#000007
En formala lingvo, la reguloj estas skribitaj kiel
#000009
P kaj Q estas proponoj,
#000010
Aplikoj de la reguloj inkludas simpligon de logikaj esprimoj en komputilaj programoj kaj ciferecaj cirkvitodezajnoj.
La leĝoj de De Morgan estas ekzemplo de pli ĝenerala koncepto de matematika dueco.
#000011
6 Etendaĵo al predikato kaj modala logiko
#000012
La negacio de konjunkcio regulo povas esti skribita en sekvent notacio:
#000013
La negacio de dismetad regulo povas esti skribita kiel:
#000015
kaj esprimita kiel ver-funkcia taŭtologio aŭ teoremo de propozicia logiko:
#000017
La leĝoj de De Morgan estas normale montritaj en la kompakta formo supraj, kun negacio de la produktaĵo maldekstre kaj negacio de la enigaĵoj dekstraflanke.
Pli klara formo por anstataŭigo povas esti deklarita kiel:
#000018
Tio emfazas la bezonon inversigi kaj la enigaĵojn kaj la produktaĵon, same kiel ŝanĝi la funkciigiston, dum farado de anstataŭigo.
#000019
En aroteorio kaj bulea algebro, ĝi ofte estas deklarita kiel "unio kaj intersekciĝo interŝanĝas sub suplementado", [4] kiel kiuj povas esti formale esprimitaj:
#000020
Estas la negacio de A, la trolinio estanta skribita super la esprimoj por esti neita,
∩ estas la intersekciĝ funkciigisto (KAJ),
∪ estas la sindikat funkciigisto (AŬ).
#000021
kie I estas iun, eventuale nenombreblan, indeksante aron.
#000022
En metita notacio, la leĝoj de De Morgan povas esti memoritaj utiligi la mnemonikon "rompas la linion, ŝanĝas la signon".
#000023
En elektra kaj komputilinĝenieristiko, la leĝoj de De Morgan estas ofte skribitaj kiel:
#000024
La leĝoj de De Morgan ofte validas por teksto priserĉanta uzanta-Bu-sonoblikvecfunkciigistojn KAJ, AŬ, kaj NE.
Pripensu aron de dokumentoj enhavantaj la vortojn "aŭtoj" kaj "kamionojn".
De la leĝoj de Morgan diras ke tiuj du serĉoj resendos la saman aron de dokumentoj:
#000026
La korpuso de dokumentoj enhavantaj "aŭtojn" aŭ "kamionojn" povas esti reprezentita per kvar dokumentoj:
#000028
Dokumento 1: Enhavas nur la vorton "aŭtoj".
Dokumento 2: Enhavas nur "kamionojn".
Dokumento 3: Enhavas kaj "aŭtojn" kaj "kamionojn".
Dokumento 4: Enhavas nek "aŭtojn" nek "kamionojn".
#000029
Dokumento 1: Enhavas nur la vorton "aŭtoj".
#000030
Dokumento 2: Enhavas nur "kamionojn".
#000031
Dokumento 3: Enhavas kaj "aŭtojn" kaj "kamionojn".
#000032
Dokumento 4: Enhavas nek "aŭtojn" nek "kamionojn".
#000033
Por analizi Search A, klare la serĉo" (aŭtoj AŬ kamionoj)" renkontos Dokumentoj 1, 2, kaj 3-a Tiel la negacio de tiu serĉo (kiu estas Search A) trafos everything alian, kio estas Document 4.
#000034
Analizante Search B, la serĉo" (NE aŭtoj)" renkontos dokumentoj kiuj ne enhavas "aŭtojn", kio estas Dokumentoj 2 kaj 4-a simile la serĉo" (NE kamionoj)" renkontos Dokumentoj 1 kaj 4-a Uzado la Kaj-funkciigisto al tiuj du serĉoj (kiu estas Search B) renkontos la dokumentoj kiuj estas kutimaj por tiujn du serĉojn, kio estas Document 4.
#000035
Simila taksado povas esti uzita por montri ke la sekvaj du serĉoj resendos la saman aron de dokumentoj (Dokumentoj 1, 2, 4):
#000036
La teoremo de De Morgan povas esti aplikita al la negacio de dismetado aŭ la negacio de konjunkcio en ĉio aŭ parto de formulo.
#000038
Kaze de ĝia aplikiĝo al dismetado, pripensu la sekvan aserton: "estas false ke aŭ de A aŭ B estas vera", kiel kiu estas skribita:
#000039
En tio estis establite ke nek A nek B estas veraj, tiam ĝi devas sekvi tiel ambaŭ A estas ne veraj kaj B ne estas vera, kiel kiuj povas esti skribitaj rekte:
#000040
Se aŭ A aŭ B estus veraj, tiam la dismetado de A kaj B estus vera, igante sian negacion malvera.
Prezentita en la angla, tio sekvas la logikon tio "ĉar du aĵoj estas ambaŭ falsan, estas ankaŭ false ke ĉiu el ambaŭ de ili estas veraj".
#000042
Laborante en la kontraŭa direkto, la dua esprimo asertas ke A estas falsa kaj B estas falsa (aŭ ekvivalente ke "ne A" kaj "ne B" estas veraj).
Sciante tion, dismetado de A kaj B devas esti falsa ankaŭ.
La negacio de menciita dismetado devas tiel esti vera, kaj la rezulto estas identa al la unua aserto.
#000043
La apliko de la teoremo de De Morgan al konjunkcio estas tre simila al sia petskribo al dismetado kaj en formo kaj raciaĵo.
Pripensu la sekvan aserton: "estas false ke A kaj B estas ambaŭ veran", kiel kiu estas skribita:
#000044
En ordo por tiu aserto esti vera, aŭ-aŭ ambaŭ de A aŭ B devas esti falsa, por se ili ambaŭ estis veraj, tiam la konjunkcio de A kaj B estus vera, igante sian negacion malvera.
Tiel, unu (minimume) aŭ pli de A kaj B devas esti falsaj (aŭ ekvivalente, unu aŭ pli de "ne A" kaj "ne B" devas esti veraj).
Tio povas esti skribita rekte kiel,
#000045
Prezentita en la angla, tio sekvas la logikon kiu "ĉar estas false ke du aĵoj estas ambaŭ veran, almenaŭ unu el ili devas esti falsa".
#000047
Laborante en la kontraŭa direkto denove, la dua esprimo asertas ke almenaŭ unu el "ne A" kaj "ne B" devas esti veraj, aŭ ekvivalente ke almenaŭ unu el A kaj B devas esti falsa.
Ekde almenaŭ unu el ili devas esti falsa, tiam ilia konjunkcio same estus falsa.
Neado diris ke konjunkcio tiel rezultigas veran esprimon, kaj tiu esprimo estas identa al la unua aserto.
#000048
tio finas la pruvon de la leĝo de De Morgan.
#000049
En etendaĵoj de klasika propozicia logiko, la dueco daŭre tenas (t.e., al iu logika funkciigisto oni ĉiam povas trovi ĝian dualon), poste en la ĉeesto de la identecoj regante negacion, oni ĉiam povas prezenti funkciigiston kiu estas la De Morgan-dualo de alia.
Tio kondukas al grava posedaĵo de logikoj bazitaj sur klasika logiko, nome la ekzisto de negaciaj normalaj formularoj: ĉiu formulo estas ekvivalenta al alia formulo kie negacioj nur okazas validis por la ne-logiaj atomoj de la formulo.
La ekzisto de negacio normalaj formoj motivigas multajn aplikojn, ekzemple en cifereca cirkvito dezajno, kie kutimas manipuli la specojn de logiko-pordetoj, kaj en formala logiko, kie estas bezonite trovi la devontigan normalan formon kaj dismetan normalan formon de formulo.
Komputilprogramistoj uzas ilin por simpligi aŭ konvene nei komplikajn logikajn kondiĉojn.
Ili ankaŭ estas ofte utilaj en komputadoj en elementa probablokalkulo.
#000050
Lasu unun difini la dualon de iu propozicia funkciigisto P ( p, q, ...
depende de elementaj proponoj p, q, ...
#000051
Tiu dueco povas esti ĝeneraligita al kvantoroj, tiel ke ekzemple la universala kvantoro kaj ekzisteca kvantoro estas dualoj:
#000052
Rilatigi tiujn kvantorduecojn al la De Morgan-leĝoj, starigi modelon kun iu malmulto de elementoj en ĝia domajno D, kiel ekzemple
#000053
konfirmante la kvantorduecojn en la modelo.
#000055
Tiam, la kvantorduecoj povas esti etenditaj plu al modala logiko, rilatigante la keston ("nepre") kaj diamanto ("eventuale") funkciigistojn:
#000056
En ĝia petskribo al la bieretikmodalecoj de ebleco kaj neceso, Aristotelo observis tiun kazon, kaj koncerne normalan modalan logikon, la rilato de tiuj modalaj funkciigistoj al la Kvantoro povas esti komprenita starigante modelojn uzantajn Kripke-semantikon.
#000057
Izomorfio - NE funkciigisto kiel izomorfio inter pozitiva logiko kaj negativa logiko
#000058
Povo de aro ( granda)
#000062