de Morgana likumi

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

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

${\begin{aligned}\neg (p\lor q)\iff (\neg p)\land (\neg q)\\\neg (p\land q)\iff (\neg p)\lor (\neg q)\end{aligned}}$

kur

• ¬ ir negācijas operators (NĒ)
• $\land$ ir konjunkcijas operators (UN)
• $\lor$ 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":

${\begin{aligned}{\overline {A\cup B}}&={\overline {A}}\cap {\overline {B}}\\{\overline {A\cap B}}&={\overline {A}}\cup {\overline {B}}\end{aligned}}$

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:

${\begin{aligned}{\overline {\bigcap _{i\in I}A_{i}}}&=\bigcup _{i\in I}{\overline {A_{i}}}\\{\overline {\bigcup _{i\in I}A_{i}}}&=\bigcap _{i\in I}{\overline {A_{i}}}\end{aligned}}$

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".

Vēsture

Likumi ir nosaukti Augusta de Morgana (1806–1871) vārdā, 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 (14. gadsimtā Viliams no Okamas pierakstīja šos likumus vārdiskā formā), 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. Šie likumi ir noderīgi arī, veidojot pareizus slēdzienus, pierādījumus un deduktīvus argumentus.

Neformāls pierādījums

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

Disjunkcijas negācija

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

$\neg (A\lor B)$

Š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:

$(\neg A)\wedge (\neg B)$

Š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

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:

$\neg (A\land B)$

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":

$(\neg A)\lor (\neg B)$

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

Pierādījums

Izmantojot patiesumvērtību tabulu

Š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	p ∨ q	¬(p ∨ q)	¬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	p ∧ q	¬(p ∧ q)	¬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

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:

• x ∈ A ∩ B
• x ∉ A ∩ B
• x ∉ A or x ∉ B
• x ∈ A or x ∈ B
• x ∈ A ∪ B

Tāpēc A ∩ B = A ∪ B. Apgalvojumu A ∪ B = A ∩ B var parādīt līdzīgā veidā.

Skatīt arī

• Būla funkcija
• Loģiskais elements

Ārējās saites

• Eric W. Weisstein, de Morgan's Laws, MathWorld.
• Jānis Buls, Matemātiskās loģikas un kopu teorijas elementi, LU lekciju materiāli (2008).
• Pēteris Daugulis, Diskrētā matemātika Arhivēts 2012. gada 16. septembrī, Wayback Machine vietnē., Rēzeknes Augstskolas lekciju materiāli (2006).