Lleis de De Morgan

Les lleis de De Morgan són una part de la Lògica proposicional i analítica, i va ser creada per Augustus De Morgan (Madurai, 1806 - Londres, 1871).[1]

Representació gràfica de les lleis de De Morgan

HistòriaModifica

Les lleis porten el nom d’Augustus De Morgan (1806–1871),[2] que va introduir una versió formal de les lleis a la lògica proposicional clàssica. La formulació de De Morgan va estar influenciada per l’algebraització de la lògica empresa per George Boole, que posteriorment va consolidar la pretensió de De Morgan a la troballa. Tot i això, Aristòtil va fer una observació similar, que era coneguda pels lògics grecs i medievals. Per exemple, al segle XIV, Guillem d'Ockham va escriure les paraules que resultarien llegint les lleis.[3] Jean Buridan, a la seva Summulae de Dialectica, també descriu les regles de conversió que segueixen les línies de les lleis de De Morgan.[4] Tot i així, a De Morgan se li dóna el mèrit d’enunciar les lleis en els termes de la lògica formal moderna i d’incorporar-les al llenguatge de la lògica. Les lleis de De Morgan es poden demostrar fàcilment i fins i tot poden semblar trivials.[5] Tanmateix, aquestes lleis són útils per fer inferències vàlides en proves i arguments deductius.

Les lleis de De MorganModifica

Les lleis de De Morgan declaren que la suma de n variables globalment negades (o invertides) és igual al producte de les n variables negades individualment, i que inversament, el producte de n variables globalment negades és igual a la suma de les n variables negades individualment.[6]

 

 

ProvaModifica

Cal utilitzar les taules de valors de veritat, [7]

 
             
V V V F F F F
V F V F F V F
F V V F V F F
F F F V V V V

Demostració formalModifica

  si i només si   i  .

per a qualsevol x:[7]

  inclusió:

 

 

  o  

  o  

 

Per tant  

  inclusió:

 

  o  

  o  

 

 

Per tant  


  i   per tant   Q.E.D.


per   es pot utilitzar un mètode similar.

Amb proposicionsModifica

La prova utilitza l'associativitat i la distributivitat de les lleis   i  .[8]

  • Veritat
  • Si veritat per n

 

 

 

 

ReferènciesModifica

  1. Hurley, Patrick J. (2015), A Concise Introduction to Logic (12th ed.), Cengage Learning, ISBN 978-1-285-19654-1
  2. DeMorgan’s Theorems at mtsu.edu
  3. William of Ockham, Summa Logicae, part II, sections 32 and 33.
  4. Jean Buridan, Summula de Dialectica. Trans. Gyula Klima. New Haven: Yale University Press, 2001. See especially Treatise 1, Chapter 7, Section 5. ISBN 0-300-08425-0
  5. Augustus De Morgan (1806–1871) Arxivat 2010-07-15 a Wayback Machine. by Robert H. Orr
  6. 2000 Solved Problems in Digital Electronics by S. P. Bali
  7. 7,0 7,1 Hayes, Andy; Wu, Vincent. «De Morgan's Laws». https://brilliant.org/.
  8. Boolean Algebra by R. L. Goodstein. ISBN 0-486-45894-6

Vegeu tambéModifica