de Morgana likumi

Vikipēdijas lapa
Pārlēkt uz: navigācija, meklēt

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 | labot pirmkodu]

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


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

kur

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


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

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{align}
  \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{align}

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 | labot pirmkodu]

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 | labot pirmkodu]

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

Disjunkcijas negācija[labot šo sadaļu | labot pirmkodu]

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[labot šo sadaļu | labot pirmkodu]

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[labot šo sadaļu | labot pirmkodu]

Izmantojot patiesumvērtību tabulu[labot šo sadaļu | labot pirmkodu]

Š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 | labot pirmkodu]

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 | labot pirmkodu]

Atsauces[labot šo sadaļu | labot pirmkodu]

  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, 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), engr.iupui.edu.

Ārējās saites[labot šo sadaļu | labot pirmkodu]