Deddfau De Morgan

Enwir y deddfau ar ôl Augustus De Morgan (1806-1871),^[3] 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.^[4] Er enghraifft, yn y 14g, ysgrifennodd William o Ockham y deddfau mewn geiriau.^[5] Gwnaeth Jean Buridan, yn ei Summulae de Dialectica, hefyd disgrifio rheolau tebyg i ddeddfau De Morgan.^[6] 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.^[7] Serch hynny, mae'r deddfau hyn yn ddefnyddiol wrth wneud casgliadau dilys mewn profion a dadleuon diddwythol.

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

Rhan 1

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

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

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

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

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

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

Rhan 2

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

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

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

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

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

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

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

Casgliad

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

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