Де Морганови закони

Проверена верзија на оваа страница, одобрена на 10 декември 2022, се засноваше на оваа преработка.

Де Моргановите закони претставени со Венови дијаграми

Де Морганови закони – пар трансформациски правила во математичката логика и Буловата алгебра. Правилата дозволуваат изразите на конјункција и дисјункција може да се менуваат еден во друг со помош на негација.

Правилата може да се претстават како:

Негација на конјункција претставува дисјункција на негација. Негација на дисјункција претставува конјункција на негација.

или неформално:

„не (A и B)“ е исто што и „(не A) или (не B)“

исто така и,

„не (A или B)“ е исто што и „(не A) и (не B)“

Правилата може да бидат изразени на формален јазик , со две вистинитосни променливи P и Q како:

\neg (P\land Q)\iff (\neg P)\lor (\neg Q)

\neg (P\lor Q)\iff (\neg P)\land (\neg Q)

каде:

¬ е оператор на негација (НЕ)
$\land$ е оператор на конјункција (И)
$\lor$ е оператор на дисјункција (ИЛИ)
⇔ е релација на еквиваленција (АККО)

Овие правила имаат широка примена во поедноставувањето на логичките изрази во сметачките програми, како и во дигиталните кола. Де Моргановите закони се општ пример за поимот дуалност во математиката.

Формален запис

Правилото негација на конјункција може да биде напишано на следниот начин:

\neg (P\land Q)\vdash (\neg P\lor \neg Q)

додека правилото негација на дисјункција може да биде напишано како:

\neg (P\lor Q)\vdash (\neg P\land \neg Q)

Во правилен облик: негација на конјункција

{\frac {\neg (P\land Q)}{\therefore \neg P\lor \neg Q}}

и негација на дисјункција

{\frac {\neg (P\lor Q)}{\therefore \neg P\land \neg Q}}

Искажано преку исказна формула:

\neg (P\land Q)\to (\neg P\lor \neg Q)

\neg (P\lor Q)\to (\neg P\land \neg Q)

каде $P$ и $Q$ претставуваат логички променливи изразени во формален запис.

Форма на замена

Де Моргановите закони обично се прикажуваат во компактен облик, со негација на комплетната лева страна, односно со негирање на влезот на десната страна. Појасен образец за замена може да се запише како:

(P\land Q)\equiv \neg (\neg P\lor \neg Q)

(P\lor Q)\equiv \neg (\neg P\land \neg Q)

Ваквиот запис нагласува дека при заменана конјуктивна во дисјунктивна форма, односно обратно, потребно е да се инвертира излезот, сите влезови, како и да се променат операторите.

Во теорија на множества и Булова алгебра

Во теоријата на множества и Буловата алгебра, често се наидува на унија и пресек под комплемент, каде исто така имаат примена Де Моргановите закони, што може да се запише како:

${\overline {A\cup B}}\equiv {\overline {A}}\cap {\overline {B}}$
${\overline {A\cap B}}\equiv {\overline {A}}\cup {\overline {B}}$

каде:

A е негација од A
∩ е пресек на множества (И)
∪ унија на множества (ИЛИ)

Или воопштено:

{\overline {\bigcap _{i\in I}A_{i}}}\equiv \bigcup _{i\in I}{\overline {A_{i}}}

{\overline {\bigcup _{i\in I}A_{i}}}\equiv \bigcap _{i\in I}{\overline {A_{i}}}

Каде I претставува бесконечен бројач

Инженерство

Во електротехниката, Де Моргановите закони обично се запишуваат како:

{\overline {A\cdot B}}\equiv {\overline {A}}+{\overline {B}}

.

{\overline {A+B}}\equiv {\overline {A}}\cdot {\overline {B}}

.

каде:

$\cdot$ е логичко И
$+$ е логичко ИЛИ
надвлечена линија е комплемент, логичко НЕ.

Историја

Законите го добиле името по Огастес де Морган (1806—1871) кој ја вовел официјалната верзија на законот за класична пропозиционална логика. На Де Моргановата формулација влијаела и алгебразацијата на логиката која ја извел Џорџ Бул, која подоцна го зацврстила Де Моргановото тврдење. Иако слично запазување имал Аристотел и им била позната на Грците и средновековните логичари, на Де Морган му била дадена заслугата за формално наведување на законите и нивно воведување во јазикот на логиката. Де Моргановиот закон може лесно да се докаже и може дури да изгледа тривијално. Сепак, овие закони се од помош при донесување исправни заклучоци во доказите и дедуктивните аргументи.

Неформален доказ

Де Моргановите закони може да се применуваат на комплетен израз негација на дисјункција или негација на конјункција, како и на некој негов дел.

Негација на дисјункција

Во случај на примена на Де Моргановиот закон на дисјункција, ќе го разгледаме следново тврдење: „Не е точно дека А или Б се точни искази“, што може да се запише како:

\neg (A\lor B)

Во тој случај утврдено е дека вистиносниот исказ А или Б не е точен, што значи дека ни А не е точно, ни Б не е точно, што може да се запише како:

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

Ако еден од А или Б е вистинит, нивната дисјункција исто така би била вистинита, што би ја правело оваа негација неточна. Презентирано на говорен јазик, соодветната логика би била „Ако две нешта се неточни, исто така е неточно дека некоја од нив е точна.“

Гледано во спротивна насока, другиот израз ни тврди дека ниту еден од исказите А и Б не се точно, што значи дека не е точна ниту нивната дисјункција. Како во првиот израз е напишана негација на дисјункција, следи дека доказот е успешен.

Негација на конјункција

Примената на Де Моргановиот закон на конјункција е многу слична со претходната. Обете форми се тривијални. Ќе го разгледаме следното тврдење: „Не е точно дека А и Б се точни искази“ што математички може да се запише како:

\neg (A\land B)

За да ова тврдење биде точно, потребно е А и Б да бидат неточни, односно барем еден од нив мора да биде неточен, што може да биде запишано како:

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

Односно, на говорен јазик „Доколку не е точно дека две нешта се точни, тогаш барем едно од нив не е точно“.

Доказот во спротивен правец е исто така тривијален, вториот израз претставува дека барем еден исказ не е точен. Доколку барем еден исказ не е точен, лесно може да се заклучи дека нивната конјункција исто така не е точна:

Формален доказ

За да се докаже дека важи $(A\cap B)^{c}=A^{c}\cup B^{c}$ , прво мора да се докаже дека важи $(A\cap B)^{c}\subseteq A^{c}\cup B^{c}$ , a потоа $A^{c}\cup B^{c}\subseteq (A\cap B)^{c}$ .

Нека е $x\in (A\cap B)^{c}$ . Тогаш $x\not \in A\cap B$ , затоа што $A\cap B=\{y|y\in A{\text{ and }}y\in B\}$ , тогаш или $x\not \in A$ . или $x\not \in B$ . Ако $x\not \in A$ , тогаш $x\in A^{c}$ , од што следи $x\in A^{c}\cup B^{c}$ . Ако $x\not \in B$ , тогаш $x\in B^{c}$ , следи $x\in A^{c}\cup B^{c}$ . Бидејќи ова е точно за произволно $x\in (A\cap B)^{c}$ , тогаш $\forall x\in (A\cap B)^{c},x\in A^{c}\cup B^{c}$ , значи следи $(A\cap B)^{c}\subseteq A^{c}\cup B^{c}$ .

За да се докаже во спротивна насока, се претпоставува дека $\exists x\in A^{c}\cup B^{c}$ , такво што $x\not \in (A\cap B)^{c}$ . Тогаш $x\in A\cap B$ . Следејќи го тоа $x\in A$ и $x\in B$ . Следи $x\not \in A^{c}$ и $x\not \in B^{c}$ . Но тогаш $x\not \in A^{c}\cup B^{c}$ , е во контрадикција со хипотезата $x\in A^{c}\cup B^{c}$ . Затоа, $\forall x\in A^{c}\cup B^{c},x\in (A\cap B)^{c}$ , и $A^{c}\cup B^{c}\subseteq (A\cap B)^{c}$ .

Бидејќи $A^{c}\cup B^{c}\subseteq (A\cap B)^{c}$ и $(A\cap B)^{c}\subseteq A^{c}\cup B^{c}$ , следи $(A\cap B)^{c}=A^{c}\cup B^{c}$ , што го финализира доказот на Де Моргановиот закон.

Другиот Де Морганов закон, односно, да важи $(A\cup B)^{c}=A^{c}\cap B^{c}$ , се докажува на сличен начин.

Екстензии

Самиот факт дека секој израз има свој дуален израз, во голема мера ја проширува исказната логика. Постоењето на негација на нормалната форма во голема мера ја поедноставува комплексноста, а со самото тоа и цената, на дигиталните кола. Исто така, големи олеснувања наоѓаат и програмерите кои го користат дуалниот израз за да ги поедностават често премногу комплицираните логички услови. Често се користа и во пресметките во основната теорија на веројатност.

Нека дефинираме двократна вредност на која било исказна операција P(p, q, ...) во зависност од елементарните предлози p, q, ... да биде операција ${\mbox{P}}^{d}$ дефинирана како

{\mbox{P}}^{d}(p,q,...)=\neg P(\neg p,\neg q,\dots ).

\forall x\,P(x)\equiv \neg \exists x\,\neg P(x),

\exists x\,P(x)\equiv \neg \forall x\,\neg P(x).

За да ги поврземе овие квантификатори со Де Моргановите закони, поставуваме модел со мал број елементи во неговиот домен D, како на пр.

D = {a, b, c}.

тогаш

\forall x\,P(x)\equiv P(a)\land P(b)\land P(c)

и

\exists x\,P(x)\equiv P(a)\lor P(b)\lor P(c).\,

Но, користејќи ги Де Моргановите закони

P(a)\land P(b)\land P(c)\equiv \neg (\neg P(a)\lor \neg P(b)\lor \neg P(c))

и

P(a)\lor P(b)\lor P(c)\equiv \neg (\neg P(a)\land \neg P(b)\land \neg P(c)),

Ги проверуваме квалификаторскте двојности во моделот.

Потоа квантификаторските двојности може да бидат проширени подлабоко во модалната логика, поврзувајќи ги квадратните (задолжителни) и ромбовидните (можни) операции.

\Box p\equiv \neg \Diamond \neg p,

\Diamond p\equiv \neg \Box \neg p.\,

Во оваа апликација за алетички модалности за можност и неопходност, Аристотел го набљудувал овој случај и во случајот на нормална модална логика, врската на овие модални оператори со квантификацијата може да се разбере така што моделите се поставуваат користејќи Крипкова семантика.

Поврзано

Изоморфизам (математика)

Литература

Brown Stephen, Vranesic Zvonko (2002), Fundamentals of Digital Logic with VHDL Design (2. изд.), McGraw-Hill, ISBN 978-0-07-249938-4. See Section 2.5.
Cori Rene, Lascar Daniel (2000), Mathematical Logic: A Course with Exercises, Oxford University Press, ISBN 978-0-19-850048-3. See Chapter 2.
I., Dahn B. (1998), „Robbins Algebras are Boolean: A Revision of McCune's Computer-Generated Solution of the Robbins Problem“, Journal of Algebra, 208 (2): 526–532, doi:10.1006/jabr.1998.7467.
Givant Steven, Paul Halmos (2009), Introduction to Boolean Algebras, Undergraduate Texts in Mathematics, Springer Science Business Media, ISBN 978-0-387-40293-2.
Paul, Halmos (1963), Lectures on Boolean Algebras, Van Nostrand, ISBN 978-0-387-90094-0.
Halmos Paul, Steven Givant (1998), Logic as Algebra, Dolciani Mathematical Expositions, 21, Mathematical Association of America, ISBN 978-0-88385-327-6.
V., Huntington E. (1933), „New sets of independent postulates for the algebra of logic“, Transactions of the American Mathematical Society, American Mathematical Society, 35 (1): 274–304, doi:10.2307/1989325, JSTOR 1989325.
V., Huntington E. (1933), „Boolean algebra: A correction“, Transactions of the American Mathematical Society, American Mathematical Society, 35 (2): 557–558, doi:10.2307/1989783, JSTOR 1989783.
Elliott, Mendelson (1970), Boolean Algebra and Switching Circuits, Schaum's Outline Series in Mathematics, McGraw-Hill, ISBN 978-0-07-041460-0.
Monk J. Donald, R. Bonnet, уред. (1989), Handbook of Boolean Algebras, Elsevier, ISBN 978-0-444-87291-3. In 3 volumes. (Vol.1:. ISBN 978-0-444-70261-6., Vol.2:. ISBN 978-0-444-87152-7., Vol.3:. ISBN 978-0-444-87153-4.)
Padmanabhan Ranganathan, Rudeanu Sergiu (2008), Axioms for lattices and boolean algebras, World Scientific, ISBN 978-981-283-454-6.
Roman, Sikorski (1966), Boolean Algebras, Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer Verlag.
R., Stoll R. (1963), Set Theory and Logic, W. H. Freeman, Reprinted by Dover Publications, 1979., ISBN 978-0-486-63829-4.

Надворешни врски

Хацевинкел, Михил, уред. (2001), „Duality principle“, Математичка енциклопедија, Шпрингер, ISBN 978-1556080104
Булова алгебра (англиски)
Математика на Булова алгебра (англиски)