Deddfau De Morgan

[bawd|Cynrychiolodd deddfau De Morgan â [Diagram Venn|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{align}
 \overline{A \cup B} &= \overline{A} \cap \overline{B}, \\
 \overline{A \cap B} &= \overline{A} \cup \overline{B},
\end{align}

lle

* Setiau yw *A* a *B*,
*  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 \rarr 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 ax \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 \rarr 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.

## Cyfeiriadau 
Categori:Algebra Boole
Categori:Rhesymeg