Законы Дэ Моргана

**Зако́ны**, або **пра́вілы Дэ Мо́ргана** — два правілы пераўтварэньня ў лёгіцы выказваньняў і булевай альгебры, якія зьяўляюцца адначасна і дзейнымі правіламі вывядзеньня. Названыя ў гонар брытанскага матэматыка XIX стагодзьдзя Агастэса Дэ Моргана. Гэтыя правілы дазваляюць выразіць кан’юнкцыю і дыз’юнкцыю адна праз другую з дапамогай адмаўленьня.

Словамі гэтыя правілы можна выразіць так:
* Адмаўленьне дыз’юнкцыі ёсьць кан’юнкцыя адмаўленьняў
* Адмаўленьне кан’юнкцыі ёсьць дыз’юнкцыя адмаўленьняў
ці
* Дапаўненьне аб’яднаньня двух мностваў роўнае перасячэньню іхніх дапаўненьняў
* Дапаўненьне перасячэньня двух мностваў роўнае аб’яднаньню іхніх дапаўненьняў
ці
* не (A або B) = (ня A) і (ня B)
* не (A і B) = (ня A) або (ня B)
дзе «A ці B» ёсьць «інклюзіўным або», то бок *прынамсі* адзін з A або B, а ня «выключальнае або», якое патрабуе *дакладна* адно з A або B.

Па сваёй сутнасьці гэтыя законы — гэта сувязь максімума празь мінімум і наадварот. Дыз’юнкцыя грае ролю максімума, кан’юнкцыя — мінімума. Такая сувязь дзейнічае ня толькі ў дыскрэтных прасторах:

min(a, b) = -max(-a, -b)
max(a, b) = -min(-a, -b)

У тэорыі мностваў і булевай альгебры яны фармальна запісваюцца такім чынам:
: \begin{align}
  \overline{A \cup B} &= \overline{A} \cap \overline{B}, \\
  \overline{A \cap B} &= \overline{A} \cup \overline{B},
\end{align}
дзе
* A і B — мноствы,
* \overline{A} — дапаўненьне A,
* \cap — перасячэньне,
* \cup — аб’яднаньне.

Законы Дэ Моргана ў запісе фармальнай мовай выглядаюць так:
: \neg(P\lor Q)\iff(\neg P)\land(\neg Q),
і
: \neg(P\land Q)\iff(\neg P)\lor(\neg Q)
дзе
* *P* і *Q* — выказваньні,
* <math>\neg</math> — апэратар лягічнага адмаўленьня (NOT),
* <math>\land</math> — апэратар лягічнай кан’юнкцыі (AND),
* <math>\lor</math> — апэратар лягічнай дыз’юнкцыі (OR),
* <math>\iff</math> — мэталягічны сымбаль са значэньнем «можа быць заменены ў лягічным доказе на», часта называны папросту «тады і толькі тады». У любым спалучэньні ісьцінных/ілжывых значэньняў P і Q левы і правы бакі стрэлкі пасьля вылічэньняў будуць мець аднолькавыя значэньні ісьціннасьці.

Яшчэ адна форма выражэньня законаў Дэ Моргана прыведзеная на схеме справа.
: A -(B \cup C) = (A - B) \cap (A - C),
: A -(B \cap C) = (A - B) \cup (A - C).
Правілы Дэ Моргана прымяняюцца дзеля спрашчэньня лягічных выразаў у кампутарных праграмах і распрацоўцы мікрасхемаў. Гэтыя правільны ёсьць прыкладам шырэйшага панятку матэматычнай дуальнасьці.

## Мінуўшчына
Законы названыя ў гонар Агастэса Дэ Моргана (1806—1871), які ўвёў у клясычнае зьлічэньне выказваньняў фармальную вэрсію законаў. Што праўда, яшчэ Арыстотэль правёў падобныя назіраньні, таму старажытным грэкам і сярэднявечным лёгікам яны былі вядомыя. Прыкладам, у XIV стагодзьдзі Ўільям Окам выразіў правілы словамі на паперы. Жан Бурыдан у сваёй *Summulae de Dialectica* таксама апісвае законы перамяненьня, якія адпавядаюць дэморганавым. Тым ня меней, менавіта Дэ Морган сфармуляваў іх у тэрмінах сучаснай фармальнай лёгікі і паклаў іх на мову лёгікі. Гэтыя фармулёўкі лёгка даказаць, і яны нават выглядаюць трывіяльнымі.

## Нефармальны доказ
Дэмораганава тэарэма можа дастасоўвацца да адмаўленьня дыз’юнкцыі або адмаўленьня кан’юнкцыі ва ўсіх частках формулы.

### Адмаўленьне дыз’юнкцыі
Дзеля дастасаваньня да дыз’юнкцыі разгледзім такое сьцьверджаньне: «Хлусьня тое, што альбо A, альбо B ісьцінныя» — якое запісваецца так:
: \neg(A\lor B).
Такім чынам, паколькі *ані* A, *ані* B ня ісьцінныя, адсюль вынікае, што як A ня ісьціннае, так і B ня ісьціннае, што можна запісаць так:
: (\neg A)\wedge(\neg B).
Калі б A ці B *былі* ісьціннымі, тады дыз’юнкцыя а A і B была б ісьціннай, а ейнае адмаўленьне хлусьлівым. Словамі гэта адпавядае лёгіцы «паколькі абодва сьцьверджаньні хлусьлівыя, то хлусьліва і тое, што адно зь іх ісьціннае».

І наадварот, другі выраз сьцьвярджае, што A хлусьлівае і B хлусьлівае (або іначай, «ня A» і «ня B» ісьцінныя). Ведаючы гэта, ведаем, што і дыз’юнкцыя A і B таксама будзе хлусьлівай. А адмаўленьне такой дыз’юнкцыі будзе ісьцінным, што ідэнтычна першаму сьцьверджаньню.

### Адмаўленьне кан’юнкцыі
Дастасаваньне тэарэмы Дэ Моргана да кан’юнкцыі падобна дастасаваньню да дыз’юнкцыі як у форме, так і ў доказе. Разгледзім такое сьцьверджаньне: «Хлусьня тое, што A і B абодва ісьцінныя» — якое запісваецца так:
: \neg(A\land B).
Каб гэтае сьцверджаньне было ісьцінным, адно з ці абодва A і B мусяць быць хлусьлівымі, бо калі б яны абодва былі ісьціннымі, то кан’юнкцыя A і B была б ісьціннай, тады сьцьверджаньне стала б хлусьлівым. Адсюль (прынамсі) адно ці болей з A і B мусяць быць хлусьлівымі (або іначай, адно ці болей зь «ня A» і «ня B» мусяць быць ісьціннымі). Гэта можна запісаць так:
: (\neg A)\lor(\neg B).
Кажучы простай мовай, гэта адпавядае лёгіцы «паколькі сьцьверджаньне пра тое, што абодва сьцьверджаньні ісьцінныя — хлусьлівае, прынамсі адно зь іх мусіць быць хлусьлівым».

І зноўку ў адваротным кірунку, другі выраз сьцьвярджае, што прынамсі адно зь «ня A» і «ня B» мусяць быць ісьціннымі (або іначай, прынамсі адно з A і B мусіць быць хлусьлівым). Паколькі прынамсі адно зь іх хлусьлівае, тады іхняя кан’юнкцыя таксама будзе хлусьлівай. Адмаўленьне такой кан’юнкцыі становіцца ісьцінным, што ідэнтычна першаму сьцьверджаньню.

## Глядзіце таксама
* Пазытыўная лёгіка
* Ізамарфізм — апэратар NOT ёсьць ізамарфізмам між пазытыўнай і нэгатыўнай лёгікай

## Крыніцы

## Літаратура
* Логіка выказванняў: вучэбны дапаможнік / Гарбузаў, Віктар Мікалаевіч; Немец, Уладзімер Сьцяпанавіч; ГрДУ імя Я. Купалы. — Гродна: ГрДУ, 1997. — 44 с.
* Матэматыка: вучэб.-мэтад. дапам. У 2 ч. Ч. 1 — 2-е выд., перапрац. / Баранцэвіч, Канстанцін Зянонавіч; Пакала, Аляксандар Анатольевіч. — Мн., БДПУ, 2005. — 176 с.
* Матэматыка: вучэб.-мэтад. дапам. У 2 ч. Ч. 1. / Баранцэвіч, Канстанцін Зянонавіч; Пакала, Аляксандар Анатольевіч. — Мн., 1996.
* Геаметрыя 7 — 11. / Пагарэлаў А. — Мн., 1991.
* Задачнік-практыкум па матэматыцы / Пакала А. А. — Мн., 1994.
* Асновы пачатковага курса матэматыкі / Стойлава Л. П., Пышкала А. М.— Мн., 1990.

## Вонкавыя спасылкі
* 
* 
* 
* Дуальнасьць у лёгіцы і мове, *Інтэрнэт-энцыкляпэдыя філязофіі*.

Катэгорыя:Артыкулы з доказамі
Катэгорыя:Булева альгебра
Катэгорыя:Тэорыі дваістасьці
Катэгорыя:Правілы вывядзеньня
Катэгорыя:Тэарэмы ў лёгіцы выказваньняў