Deddfau De Morgan

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

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.

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{array}{cc}\overline{A\cup B}& =\bar{A}\cap \bar{B},\\ \overline{A\cap B}& =\bar{A}\cup \bar{B},\end{array}$

lle

• Setiau yw A a B,
• Nodyn:Overline 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\in ̸A\cap B$ .

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

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

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

Felly, $\mathrm{\forall }x(x\in (A\cap B{)}^{\complement }\to 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\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\in ̸A^{\complement }$ a$x\in ̸B^{\complement }$.

Fodd bynnag, mae hynny'n golygu bod $x\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\in ̸(A\cap B{)}^{\complement }$ fod yn wir, sy'n golygu bod $x\in (A\cap B{)}^{\complement }$.

Felly, $\mathrm{\forall }x(x\in A^{\complement }\cup B^{\complement }\to 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.