De Morganove teoreme

Na bazi Bulove algebre, De Morgan je formulisao dvije važne teoreme, koje, u generalizaciji Šenona, imaju jedinstven iskaz:

Za dobijanje komplementa neke Booleove funkcije treba sve promjenljive zamijeniti njihovim komplementima pa zatim operacije "ILI" zamijeniti sa "I", a operacije "I" sa "ILI“.

Ilustrovaćemo kako se savršenom indukcijom može dokazati De Morganova teorema u slučaju dvije promjenjive..
Pošto u iskazu ove teoreme figurišu dvije promenljive, x i y, broj kombinacija njihovih vrijednosti je četiri.

Kao što se može vidjeti za svaku od ove četiri kombinacije, izrazi sa lijeve i desne strane znaka jednakosti daju isti rezultat.

Na ekvivalentan način je moguće provesti i dokaz za više promjenjivih.