Formālajā loģikā de Morgana likumi saista loģiskos operatorus UN un VAI tādā veidā, ka, izmantojot negāciju, no viena var pāriet uz otru, proti:

NE (P VAI Q) = (NE P) UN (NE Q)
NE (P UN Q) = (NE P) VAI (NE Q)

Formāla definīcija labot šo sadaļu

Izteikumu loģikā de Morgana likumus pieraksta formā:

 

kur

  • ¬ ir negācijas operators (NĒ)
  •   ir konjunkcijas operators (UN)
  •   ir disjunkcijas operators (VAI)
  • ⇔ nozīmē loģiski ekvivalents (tad un tikai tad)

Kopu teorijā un Būla algebrā tie bieži tiek minēti kā "apvienojuma un šķēluma savstarpējā apmaiņa, lietojot negāciju":[1]

 

kur darbības ar kopām tiek apzīmētas šādi:

  • A ir kopas A papildinājums; virslīnija tiek rakstīta virs elementiem, uz kuriem tas attiecas
  • ∩ ir šķēluma operators (UN)
  • ∪ ir apvienojuma operators (VAI)

Šos likumus var vispārināt patvaļīgam kopu skaitam:

 

kur I ir indeksācijas kopa, kura var būt nesanumurējama.

De Morgana likumus ir viegli atcerēties, iegaumējot principu "pārtraucot līniju, ir jāmaina zīme".[2]

Vēsture labot šo sadaļu

Likumi ir nosaukti Augusta de Morgana (1806–1871) vārdā,[3] kurš ieviesa formālu šo likumu versiju klasiskajā izteikumu loģikā. De Morgana formulējumu ietekmēja loģikas algebrizācija, kuru uzsāka Džordžs Būls un kas vēlāk nodrošināja de Morgana tiesības uz šo atklājumu. Kaut gan līdzīgus novērojumus bija veicis Aristotelis, un tie bija zināmi grieķiem un viduslaiku loģiķiem[4] (14. gadsimtā Viliams no Okamas pierakstīja šos likumus vārdiskā formā[5]), de Morganam tiek piešķirts gods par šo likumu formālu pierakstīšanu un par to iekļaušanu loģikas valodā. De Morgana likumi ir vienkārši pierādāmi, un tie pat var šķist triviāli.[6] Šie likumi ir noderīgi arī, veidojot pareizus slēdzienus, pierādījumus un deduktīvus argumentus.

Neformāls pierādījums labot šo sadaļu

De Morgana likumus var pielietot disjunkcijas vai konjunkcijas negācijai visā formulā vai tās daļā.

Disjunkcijas negācija labot šo sadaļu

Disjunkcijas gadījumā apskatīsim apgalvojumu "nav taisnība, ka A ir patiess vai B ir patiess", ko var pierakstīt šādi:

 

Šis apgalvojums izsaka to, ka ne A, ne B nav patiess. Citiem vārdiem, "A nav patiess un B nav patiess" (ja kaut viens no apgalvojumiem būtu patiess, tad A un B disjunkcija arī būtu patiesa, padarot tās negāciju aplamu).

Analizējot šo pašu situāciju no otras puses, apskatīsim šādu apgalvojumu:

 

Šis apgalvojums izsaka to, ka gan A, gan B ir aplams (vai "ne A" un "ne B" ir patiesi). No tā izriet, ka A un B disjunkcijai arī jābūt aplamai. Šīs disjunkcijas negācija noved pie patiesa apgalvojuma, kas ir loģiski ekvivalents sākotnējajam apgalvojumam. Citiem vārdiem, "ja divi apgalvojumi ir aplami, nav taisnība, ka kāds no tiem ir patiess".

Konjunkcijas negācija labot šo sadaļu

De Morgana likumu pielietojums konjunkcijai ir ļoti līdzīgs to pielietojumam disjunkcijai. Apskatīsim šādu apgalvojumu: "nav taisnība, ka A ir patiess un B ir patiess", ko var pierakstīt šādi:

 

Lai šis apgalvojums būtu patiess, vienam no A vai B jābūt aplamam (ja tie abi būtu patiesi, tad arī A un B konjunkcija būtu patiesa, padarot tās noliegumu aplamu). Tātad sākotnējo apgalvojumu var izteikt kā "vai nu A ir aplams vai B ir aplams" jeb "A noliegums ir patiess vai B noliegums ir patiess":

 

Citiem vārdiem, "ja nav taisnība, ka abi apgalvojumi ir patiesi, tad vismaz viens no tiem ir aplams".

Pierādījums labot šo sadaļu

Izmantojot patiesumvērtību tabulu labot šo sadaļu

Šos likumus var pierādīt, izmantojot patiesumvērtību tabulu, kurā "1" nozīmē, ka apgalvojums ir patiess, bet "0" — aplams.

Vispirms pierādīsim, ka ¬(p ∨ q) ⇔ (¬p) ∧ (¬q):

p q pq ¬(pq) ¬p ¬q p) ∧ (¬q)
0 0 0 1 1 1 1
0 1 1 0 1 0 0
1 0 1 0 0 1 0
1 1 1 0 0 0 0

Tā kā visām iespējamajām p un q vērtībām tabulas ceturtā un pēdējā kolonna sakrīt, atbilstošie izteikumi ir loģiski ekvivalenti.

Apgalvojumu ¬(p ∧ q) ⇔ (¬p) ∨ (¬q) ar šo pašu metodi pierāda līdzīgi:

p q pq ¬(pq) ¬p ¬q p) ∨ (¬q)
0 0 0 1 1 1 1
0 1 0 1 1 0 1
1 0 0 1 0 1 1
1 1 1 0 0 0 0

Izmantojot kopas labot šo sadaļu

Divas kopas sakrīt, tad un tikai tad, ja tās satur vienus un tos pašus elementus. Jebkuram x ir minētie apgalvojumi ir ekvivalenti:

  • xAB
  • xAB
  • xA or xB
  • xA or xB
  • xAB

Tāpēc AB = AB. Apgalvojumu AB = AB var parādīt līdzīgā veidā.

Skatīt arī labot šo sadaļu

Atsauces labot šo sadaļu

  1. R. L. Goodstein (2007), Boolean Algebra, Dover Publications, ISBN 978-0-48-645894-6.
  2. S. P. Bali (2005), 2000 solved problems in digital electronics, Tata McGraw-Hill, ISBN 978-0-07-058831-8.
  3. DeMorgan’s Theorems Arhivēts 2008. gada 23. martā, Wayback Machine vietnē., mtsu.edu.
  4. Joseph M. Bocheński (1961), A history of formal logic, University of Notre Dame Press.
  5. William of Ockham, Summa Logicae, part II, sections 32 & 33.
  6. Robert H. Orr, Augustus De Morgan (1806 -1871) Arhivēts 2010. gada 15. jūlijā, Wayback Machine vietnē., engr.iupui.edu.

Ārējās saites labot šo sadaļu