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.

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



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),DeMorgan’s Theorems  at mtsu.edu 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.William of Ockham, Summa Logicae, part II, sections 32 and 33. Gwnaeth Jean Buridan, yn ei Summulae de Dialectica, hefyd disgrifio rheolau tebyg i ddeddfau De Morgan.Jean Buridan, Summula de Dialectica. Trans. Gyula Klima. New Haven: Yale University Press, 2001. See especially Treatise 1, Chapter 7, Section 5.  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.Augustus De Morgan (1806–1871)   gan Robert H. Orr Serch hynny, mae'r deddfau hyn yn ddefnyddiol wrth wneud casgliadau dilys mewn profion a dadleuon diddwythol.

 Prawf ffurfiol 
Fan hyn defnyddiwn  i ddynodi cyflenwad A. Mae'r prawf bod yn cael ei gwblhau mewn dau gam trwy brofi bod  a bod .

 Rhan 1 
Gadewch i . Yna,  .

Oherwydd bod , rhaid ei fod yn wir fod  neu .

Os yw , yna mae , felly mae .

Yn yr un modd, os yw , yna mae , felly mae .

Felly, ;

hynny yw, .

 Rhan 2 
I brofi'r cyfeiriad gwrthwyneb, gadewch i , ac er mwyn cael gwrthddywediad tybiwch fod .

O dan y dybiaeth honno, rhaid ei bod yn wir fod ,

felly mae'n dilyn bod  ac , ac felly bod  a.

Fodd bynnag, mae hynny'n golygu bod , yn groes i'r rhagdybiaeth bod ,

felly, ni all y dybiaeth  fod yn wir, sy'n golygu bod .

Felly, ,

hynny yw, .

 Casgliad 
Os yw  ac , yna mae ; mae hyn yn cyflawni prawf deddf De Morgan.

Gallwn brofi'r ddeddf De Morgan arall, , yn yr un modd.

 Cyfeiriadau 

Categori:Algebra Boole
Categori:Rhesymeg