[{"text_idx": "#000000", "text": "La leg\u0302oj de De Morgan"}, {"text_idx": "#000002", "text": "Sorbado / Maniero tollens /"}, {"text_idx": "#000003", "text": "En propozicia logiko kaj bulea algebro, la leg\u0302oj de De Morgan [1] [2] [3] estas paro de transformreguloj kiuj estas ambau\u0306 validaj reguloj de inferenco.\nIli estas nomitaj lau\u0306 Augustus De Morgan, 19-ajarcenta brita matematikisto.\nLa reguloj permesas la esprimon de konjunkcioj kaj dismetadoj sole lau\u0306 unu la alian per negacio."}, {"text_idx": "#000004", "text": "La reguloj povas esti esprimitaj en la angla kiel:"}, {"text_idx": "#000005", "text": "la negacio de konjunkcio estas la dismetado de la negacioj;\nkaj la negacio de dismetado estas la konjunkcio de la negacioj;"}, {"text_idx": "#000006", "text": "la komplemento de la unio de du aroj estas la sama kiel la intersekcig\u0302o de iliaj salutoj;\nkaj la komplemento de la intersekcig\u0302o de du aroj estas la sama kiel la unio de iliaj salutoj."}, {"text_idx": "#000007", "text": "En aroteorio kaj bulea algebro, tiuj estas skribitaj formale kiel"}, {"text_idx": "#000009", "text": "En formala lingvo, la reguloj estas skribitaj kiel"}, {"text_idx": "#000010", "text": "P kaj Q estas proponoj,"}, {"text_idx": "#000011", "text": "Aplikoj de la reguloj inkludas simpligon de logikaj esprimoj en komputilaj programoj kaj ciferecaj cirkvitodezajnoj.\nLa leg\u0302oj de De Morgan estas ekzemplo de pli g\u0302enerala koncepto de matematika dueco."}, {"text_idx": "#000012", "text": "6 Etendaj\u0302o al predikato kaj modala logiko"}, {"text_idx": "#000013", "text": "La negacio de konjunkcio regulo povas esti skribita en sekvent notacio:"}, {"text_idx": "#000015", "text": "La negacio de dismetad regulo povas esti skribita kiel:"}, {"text_idx": "#000017", "text": "kaj esprimita kiel ver-funkcia tau\u0306tologio au\u0306 teoremo de propozicia logiko:"}, {"text_idx": "#000018", "text": "La leg\u0302oj de De Morgan estas normale montritaj en la kompakta formo supraj, kun negacio de la produktaj\u0302o maldekstre kaj negacio de la enigaj\u0302oj dekstraflanke.\nPli klara formo por anstatau\u0306igo povas esti deklarita kiel:"}, {"text_idx": "#000019", "text": "Tio emfazas la bezonon inversigi kaj la enigaj\u0302ojn kaj la produktaj\u0302on, same kiel s\u0302ang\u0302i la funkciigiston, dum farado de anstatau\u0306igo."}, {"text_idx": "#000020", "text": "En aroteorio kaj bulea algebro, g\u0302i ofte estas deklarita kiel \"unio kaj intersekcig\u0302o inters\u0302ang\u0302as sub suplementado\", [4] kiel kiuj povas esti formale esprimitaj:"}, {"text_idx": "#000021", "text": "Estas la negacio de A, la trolinio estanta skribita super la esprimoj por esti neita,\n\u2229 estas la intersekcig\u0302 funkciigisto (KAJ),\n\u222a estas la sindikat funkciigisto (AU\u0306)."}, {"text_idx": "#000022", "text": "kie I estas iun, eventuale nenombreblan, indeksante aron."}, {"text_idx": "#000023", "text": "En metita notacio, la leg\u0302oj de De Morgan povas esti memoritaj utiligi la mnemonikon \"rompas la linion, s\u0302ang\u0302as la signon\"."}, {"text_idx": "#000024", "text": "En elektra kaj komputiling\u0302enieristiko, la leg\u0302oj de De Morgan estas ofte skribitaj kiel:"}, {"text_idx": "#000026", "text": "La leg\u0302oj de De Morgan ofte validas por teksto priserc\u0302anta uzanta-Bu-sonoblikvecfunkciigistojn KAJ, AU\u0306, kaj NE.\nPripensu aron de dokumentoj enhavantaj la vortojn \"au\u0306toj\" kaj \"kamionojn\".\nDe la leg\u0302oj de Morgan diras ke tiuj du serc\u0302oj resendos la saman aron de dokumentoj:"}, {"text_idx": "#000028", "text": "La korpuso de dokumentoj enhavantaj \"au\u0306tojn\" au\u0306 \"kamionojn\" povas esti reprezentita per kvar dokumentoj:"}, {"text_idx": "#000029", "text": "Dokumento 1: Enhavas nur la vorton \"au\u0306toj\".\nDokumento 2: Enhavas nur \"kamionojn\".\nDokumento 3: Enhavas kaj \"au\u0306tojn\" kaj \"kamionojn\".\nDokumento 4: Enhavas nek \"au\u0306tojn\" nek \"kamionojn\"."}, {"text_idx": "#000030", "text": "Dokumento 1: Enhavas nur la vorton \"au\u0306toj\"."}, {"text_idx": "#000031", "text": "Dokumento 2: Enhavas nur \"kamionojn\"."}, {"text_idx": "#000032", "text": "Dokumento 3: Enhavas kaj \"au\u0306tojn\" kaj \"kamionojn\"."}, {"text_idx": "#000033", "text": "Dokumento 4: Enhavas nek \"au\u0306tojn\" nek \"kamionojn\"."}, {"text_idx": "#000034", "text": "Por analizi Search A, klare la serc\u0302o\" (au\u0306toj AU\u0306 kamionoj)\" renkontos Dokumentoj 1, 2, kaj 3-a Tiel la negacio de tiu serc\u0302o (kiu estas Search A) trafos everything alian, kio estas Document 4."}, {"text_idx": "#000035", "text": "Analizante Search B, la serc\u0302o\" (NE au\u0306toj)\" renkontos dokumentoj kiuj ne enhavas \"au\u0306tojn\", kio estas Dokumentoj 2 kaj 4-a simile la serc\u0302o\" (NE kamionoj)\" renkontos Dokumentoj 1 kaj 4-a Uzado la Kaj-funkciigisto al tiuj du serc\u0302oj (kiu estas Search B) renkontos la dokumentoj kiuj estas kutimaj por tiujn du serc\u0302ojn, kio estas Document 4."}, {"text_idx": "#000036", "text": "Simila taksado povas esti uzita por montri ke la sekvaj du serc\u0302oj resendos la saman aron de dokumentoj (Dokumentoj 1, 2, 4):"}, {"text_idx": "#000038", "text": "La teoremo de De Morgan povas esti aplikita al la negacio de dismetado au\u0306 la negacio de konjunkcio en c\u0302io au\u0306 parto de formulo."}, {"text_idx": "#000039", "text": "Kaze de g\u0302ia aplikig\u0302o al dismetado, pripensu la sekvan aserton: \"estas false ke au\u0306 de A au\u0306 B estas vera\", kiel kiu estas skribita:"}, {"text_idx": "#000040", "text": "En tio estis establite ke nek A nek B estas veraj, tiam g\u0302i devas sekvi tiel ambau\u0306 A estas ne veraj kaj B ne estas vera, kiel kiuj povas esti skribitaj rekte:"}, {"text_idx": "#000042", "text": "Se au\u0306 A au\u0306 B estus veraj, tiam la dismetado de A kaj B estus vera, igante sian negacion malvera.\nPrezentita en la angla, tio sekvas la logikon tio \"c\u0302ar du aj\u0302oj estas ambau\u0306 falsan, estas ankau\u0306 false ke c\u0302iu el ambau\u0306 de ili estas veraj\"."}, {"text_idx": "#000043", "text": "Laborante en la kontrau\u0306a direkto, la dua esprimo asertas ke A estas falsa kaj B estas falsa (au\u0306 ekvivalente ke \"ne A\" kaj \"ne B\" estas veraj).\nSciante tion, dismetado de A kaj B devas esti falsa ankau\u0306.\nLa negacio de menciita dismetado devas tiel esti vera, kaj la rezulto estas identa al la unua aserto."}, {"text_idx": "#000044", "text": "La apliko de la teoremo de De Morgan al konjunkcio estas tre simila al sia petskribo al dismetado kaj en formo kaj raciaj\u0302o.\nPripensu la sekvan aserton: \"estas false ke A kaj B estas ambau\u0306 veran\", kiel kiu estas skribita:"}, {"text_idx": "#000045", "text": "En ordo por tiu aserto esti vera, au\u0306-au\u0306 ambau\u0306 de A au\u0306 B devas esti falsa, por se ili ambau\u0306 estis veraj, tiam la konjunkcio de A kaj B estus vera, igante sian negacion malvera.\nTiel, unu (minimume) au\u0306 pli de A kaj B devas esti falsaj (au\u0306 ekvivalente, unu au\u0306 pli de \"ne A\" kaj \"ne B\" devas esti veraj).\nTio povas esti skribita rekte kiel,"}, {"text_idx": "#000047", "text": "Prezentita en la angla, tio sekvas la logikon kiu \"c\u0302ar estas false ke du aj\u0302oj estas ambau\u0306 veran, almenau\u0306 unu el ili devas esti falsa\"."}, {"text_idx": "#000048", "text": "Laborante en la kontrau\u0306a direkto denove, la dua esprimo asertas ke almenau\u0306 unu el \"ne A\" kaj \"ne B\" devas esti veraj, au\u0306 ekvivalente ke almenau\u0306 unu el A kaj B devas esti falsa.\nEkde almenau\u0306 unu el ili devas esti falsa, tiam ilia konjunkcio same estus falsa.\nNeado diris ke konjunkcio tiel rezultigas veran esprimon, kaj tiu esprimo estas identa al la unua aserto."}, {"text_idx": "#000049", "text": "tio finas la pruvon de la leg\u0302o de De Morgan."}, {"text_idx": "#000050", "text": "En etendaj\u0302oj de klasika propozicia logiko, la dueco dau\u0306re tenas (t.e., al iu logika funkciigisto oni c\u0302iam povas trovi g\u0302ian dualon), poste en la c\u0302eesto de la identecoj regante negacion, oni c\u0302iam povas prezenti funkciigiston kiu estas la De Morgan-dualo de alia.\nTio kondukas al grava posedaj\u0302o de logikoj bazitaj sur klasika logiko, nome la ekzisto de negaciaj normalaj formularoj: c\u0302iu formulo estas ekvivalenta al alia formulo kie negacioj nur okazas validis por la ne-logiaj atomoj de la formulo.\nLa 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.\nKomputilprogramistoj uzas ilin por simpligi au\u0306 konvene nei komplikajn logikajn kondic\u0302ojn.\nIli ankau\u0306 estas ofte utilaj en komputadoj en elementa probablokalkulo."}, {"text_idx": "#000051", "text": "Lasu unun difini la dualon de iu propozicia funkciigisto P ( p, q, ...\ndepende de elementaj proponoj p, q, ..."}, {"text_idx": "#000052", "text": "Tiu dueco povas esti g\u0302eneraligita al kvantoroj, tiel ke ekzemple la universala kvantoro kaj ekzisteca kvantoro estas dualoj:"}, {"text_idx": "#000053", "text": "Rilatigi tiujn kvantorduecojn al la De Morgan-leg\u0302oj, starigi modelon kun iu malmulto de elementoj en g\u0302ia domajno D, kiel ekzemple"}, {"text_idx": "#000055", "text": "konfirmante la kvantorduecojn en la modelo."}, {"text_idx": "#000056", "text": "Tiam, la kvantorduecoj povas esti etenditaj plu al modala logiko, rilatigante la keston (\"nepre\") kaj diamanto (\"eventuale\") funkciigistojn:"}, {"text_idx": "#000057", "text": "En g\u0302ia 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."}, {"text_idx": "#000058", "text": "Izomorfio - NE funkciigisto kiel izomorfio inter pozitiva logiko kaj negativa logiko"}, {"text_idx": "#000062", "text": "Povo de aro ( granda)"}]