Deddfau De Morgan

Mewn rhesymeg osodiadol ac algebra Boole, mae deddfau De Morgan yn bâr o reolau trawsnewidiad dilys. Fe'u henwir ar ôl Augustus De Morgan, mathemategydd Prydeinig o'r 19eg ganrif. Mae'r rheolau yn caniatáu mynegi uniadau a chroestoriadau yn nhermau ei gilydd trwy eu cyflenwad.

Cynrychiolodd deddfau De Morgan â diagramau Venn. Ymhob achos, y set sydd angen yw'r set o bob pwynt yn y cysgod las.

Gellir mynegi'r rheolau yn Gymraeg fel:

mae cyflenwad uniad dwy set yr yn hafal i groestoriad eu cyflenwadau; a

mae cyflenwad croestoriad dwy set yn hafal i uniad eu cyflenwadau.

neu

nid (A neu B) = nid A ac nid B; a

nid (A a B) = nid A neu beidio B.

Mewn damcaniaeth setiau ac algebra Boole, ysgrifennir y rhain yn ffurfiol fel

${\begin{aligned}{\overline {A\cup B}}&={\overline {A}}\cap {\overline {B}},\\{\overline {A\cap B}}&={\overline {A}}\cup {\overline {B}},\end{aligned}}$

lle

• Setiau yw A a B,
• A yw cyflenwad A,
• ∩ yw'r croestoriad, ac
• ∪ yw'r uniad.

Hanes

Enwir y deddfau ar ôl Augustus De Morgan (1806-1871), a gyflwynodd fersiwn ffurfiol o'r deddfau hyn mewn rhesymeg osodiadol glasurol. Cafodd ffurfiad De Morgan ei ddylanwadu gan waith George Boole a chymhwysodd algebra i resymeg. Serch hynny, gwnaeth Aristoteles sylw tebyg, ac roedd yn hysbys i logistegwyr Groegaidd a Chanoloesol. Er enghraifft, yn y 14g, ysgrifennodd William o Ockham y deddfau mewn geiriau. Gwnaeth Jean Buridan, yn ei Summulae de Dialectica, hefyd disgrifio rheolau tebyg i ddeddfau De Morgan. Ond rhoddir clod i De Morgan am nodi’r deddfau yn nhermau rhesymeg ffurfiol fodern, a’u hymgorffori yn iaith rhesymeg. Gellir profi deddfau De Morgan yn hawdd, a gallant hyd yn oed ymddangos yn ddibwys. Serch hynny, mae'r deddfau hyn yn ddefnyddiol wrth wneud casgliadau dilys mewn profion a dadleuon diddwythol.

Prawf ffurfiol

Fan hyn defnyddiwn $A^{\complement }$ i ddynodi cyflenwad A. Mae'r prawf bod$(A\cap B)^{\complement }=A^{\complement }\cup B^{\complement }$ yn cael ei gwblhau mewn dau gam trwy brofi bod $(A\cap B)^{\complement }\subseteq A^{\complement }\cup B^{\complement }$ a bod $A^{\complement }\cup B^{\complement }\subseteq (A\cap B)^{\complement }$.

Rhan 1

Gadewch i $x\in (A\cap B)^{\complement }$. Yna, $x\not \in A\cap B$ .

Oherwydd bod $A\cap B=\{y\;|\;y\in A\land y\in B\}$, rhaid ei fod yn wir fod $x\not \in A$ neu $x\not \in B$.

Os yw $x\not \in A$, yna mae $x\in A^{\complement }$, felly mae $x\in A^{\complement }\cup B^{\complement }$.

Yn yr un modd, os yw $x\not \in B$, yna mae $x\in B^{\complement }$, felly mae $x\in A^{\complement }\cup B^{\complement }$.

Felly, $\forall x(x\in (A\cap B)^{\complement }\rightarrow x\in A^{\complement }\cup B^{\complement })$;

hynny yw, $(A\cap B)^{\complement }\subseteq A^{\complement }\cup B^{\complement }$.

Rhan 2

I brofi'r cyfeiriad gwrthwyneb, gadewch i $x\in A^{\complement }\cup B^{\complement }$, ac er mwyn cael gwrthddywediad tybiwch fod $x\not \in (A\cap B)^{\complement }$.

O dan y dybiaeth honno, rhaid ei bod yn wir fod $x\in A\cap B$,

felly mae'n dilyn bod $x\in A$ ac $x\in B$, ac felly bod $x\not \in A^{\complement }$ a$x\not \in B^{\complement }$.

Fodd bynnag, mae hynny'n golygu bod $x\not \in A^{\complement }\cup B^{\complement }$, yn groes i'r rhagdybiaeth bod $x\in A^{\complement }\cup B^{\complement }$,

felly, ni all y dybiaeth $x\not \in (A\cap B)^{\complement }$ fod yn wir, sy'n golygu bod $x\in (A\cap B)^{\complement }$.

Felly, $\forall x(x\in A^{\complement }\cup B^{\complement }\rightarrow x\in (A\cap B)^{\complement })$,

hynny yw, $A^{\complement }\cup B^{\complement }\subseteq (A\cap B)^{\complement }$.

Casgliad

Os yw $A^{\complement }\cup B^{\complement }\subseteq (A\cap B)^{\complement }$ ac $(A\cap B)^{\complement }\subseteq A^{\complement }\cup B^{\complement }$, yna mae $(A\cap B)^{\complement }=A^{\complement }\cup B^{\complement }$; mae hyn yn cyflawni prawf deddf De Morgan.

Gallwn brofi'r ddeddf De Morgan arall, $(A\cup B)^{\complement }=A^{\complement }\cap B^{\complement }$, yn yr un modd.