Правила де Моргана — властивість булевих алгебр, що дозволяє виразити одну з двоїстих операцій через іншу і унарну операцію доповнення (заперечення).
Правила де Моргана | |
Названо на честь | Ауґустус де Морган |
---|---|
Досліджується в | логіка |
Формула | і |
Позначення у формулі | , , , , і |
Допустиме правило в | класична логіка |
Підтримується Вікіпроєктом |
Використовуються у алгебрі множин (в теорії множин) та алгебрі логіки (в численні висловлень). Названі на честь британського математика і логіка Аугустуса де Моргана.
Твердження
Для булевої алгебри
Нехай є деяка булева алгебра, тоді для справджується:
Мають місце також узагальнені правила де Моргана:
- ,
- .
Для алгебри логіки
- ,
- ;
В обох цих формулах — логічна диз'юнкція, — логічна кон'юнкція, — логічне заперечення (негація), p, q — деякі логічні висловлення.
Істинність даних правил можна підтвердити за допомогою таблиць істинності
0 0 0 1 1 1 1 0 1 0 1 1 1 0 1 0 0 1 1 0 1 1 1 1 0 0 0 0
0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 1 0 0 0 0
Для алгебри множин
Нехай — деяка множина і — її підмножини. Тоді виконується:
- ,
де — стандартні позначення для об'єднання, перетину та доповнення множин.
Використавши третю множину і операцію різниці множин, це можна переписати як.
Також виконуються і узагальнені правила
- ,
- ,
де
Доведення в теорії
Правила засновані на відношеннях
- ,
які графічно представлені ілюстраціями нижче. Дано дві множини A і В, які є підмножинами Ω (універсуму). Діаграма 1 показує їх розташування відносно одна до одної. У діаграмі 2 показано, як формується . У діаграмі 3 на прикладі можна побачити що обидві множини рівні.
Розподіл простору в А та В |
Історія
Правила названі на честь британського математика Ауґустуса де Моргана (1806—1871), який застосував формальну версію правил до класичної логіки висловлювань. Формуляція де Моргана створена на основі логіки, започаткованої Джорджем Булем. Схожі спостереження були зроблені Арістотелем, відомим грецьким логіком. Закони де Моргана можуть бути підтверджені просто і навіть здатися тривіальними. Тим не менше, ці закони є корисними в створенні значимих висновків в доказах і результатах дедуктивного міркування.
Див. також
Джерела
- Куратовский К., Мостовский А. Теория множеств = Set Theory (Teoria mnogości). — М. : Мир, 1970. — 416 с.(рос.)
- Weisstein, Eric W. Правила де Моргана(англ.) на сайті Wolfram MathWorld.
- Правила де Моргана на PlanetMath.(англ.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Pravila de Morgana vlastivist bulevih algebr sho dozvolyaye viraziti odnu z dvoyistih operacij displaystyle lor land cherez inshu i unarnu operaciyu displaystyle lnot dopovnennya zaperechennya Pravila de Morgana Nazvano na chestAugustus de Morgan Doslidzhuyetsya vlogika Formula P Q P Q displaystyle neg P land Q vdash neg P lor neg Q i P Q P Q displaystyle neg P lor Q vdash neg P land neg Q Poznachennya u formuliP displaystyle P Q displaystyle Q displaystyle land displaystyle lnot displaystyle lor i displaystyle vdash Dopustime pravilo vklasichna logika Pidtrimuyetsya VikiproyektomVikipediya Proyekt Matematika Zakoni de Morgana u viglyadi diagram Venna U vipadkah 1 ta 2 rezultovna mnozhina u vidtinkah sinogo koloru Logichna shema pravil de Morgana Vikoristovuyutsya u algebri mnozhin v teoriyi mnozhin ta algebri logiki v chislenni vislovlen Nazvani na chest britanskogo matematika i logika Augustusa de Morgana TverdzhennyaDlya bulevoyi algebri Nehaj B 0 1 displaystyle B lor land 0 1 ye deyaka buleva algebra todi dlya a b B displaystyle a b in B spravdzhuyetsya a b a b displaystyle overline a lor b overline a land overline b a b a b displaystyle overline a land b overline a lor overline b Mayut misce takozh uzagalneni pravila de Morgana i I a i i I a i displaystyle overline left lor i in I a i right land i in I overline a i i I a i i I a i displaystyle overline left land i in I a i right lor i in I overline a i Dlya algebri logiki p q p q displaystyle lnot p land q iff lnot p lor lnot q p q p q displaystyle lnot p lor q iff lnot p land lnot q V oboh cih formulah displaystyle lor logichna diz yunkciya displaystyle land logichna kon yunkciya displaystyle lnot logichne zaperechennya negaciya p q deyaki logichni vislovlennya Istinnist danih pravil mozhna pidtverditi za dopomogoyu tablic istinnosti p q p q displaystyle lnot p land q iff lnot p lor lnot q p displaystyle p q displaystyle q p q displaystyle p land q p q displaystyle lnot p land q p q displaystyle lnot p lor lnot q p displaystyle lnot p q displaystyle lnot q 0 0 0 1 1 1 1 0 1 0 1 1 1 0 1 0 0 1 1 0 1 1 1 1 0 0 0 0 p q p q displaystyle lnot p lor q iff lnot p land lnot q p displaystyle p q displaystyle q p q displaystyle p lor q p q displaystyle lnot p lor q p q displaystyle lnot p land lnot q p displaystyle lnot p q displaystyle lnot q 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 1 0 0 0 0 Dlya algebri mnozhin Nehaj X displaystyle X deyaka mnozhina i A B X displaystyle A B subset X yiyi pidmnozhini Todi vikonuyetsya A B c A c B c displaystyle A cup B c A c cap B c A B c A c B c displaystyle A cap B c A c cup B c de A c displaystyle cup cap A c standartni poznachennya dlya ob yednannya peretinu ta dopovnennya mnozhin Vikoristavshi tretyu mnozhinu i operaciyu riznici mnozhin ce mozhna perepisati yak C A B C A C B displaystyle C A cup B C A cap C B C A B C A C B displaystyle C A cap B C A cup C B Takozh vikonuyutsya i uzagalneni pravila i I A i c i I A i c displaystyle left bigcup i in I A i right c bigcap i in I A i c i I A i c i I A i c displaystyle left bigcap i in I A i right c bigcup i in I A i c de I N displaystyle I subset mathbb N Dovedennya v teoriyi Pravila zasnovani na vidnoshennyah A B A B displaystyle overline A cup overline B overline A cap B yaki grafichno predstavleni ilyustraciyami nizhche Dano dvi mnozhini A i V yaki ye pidmnozhinami W universumu Diagrama 1 pokazuye yih roztashuvannya vidnosno odna do odnoyi U diagrami 2 pokazano yak formuyetsya A B displaystyle overline A cup overline B U diagrami 3 na prikladi A B displaystyle A cap B mozhna pobachiti sho obidvi mnozhini rivni Rozpodil prostoru v A ta V A B displaystyle overline A cup overline B A B displaystyle overline A cap B IstoriyaPravila nazvani na chest britanskogo matematika Augustusa de Morgana 1806 1871 yakij zastosuvav formalnu versiyu pravil do klasichnoyi logiki vislovlyuvan Formulyaciya de Morgana stvorena na osnovi logiki zapochatkovanoyi Dzhordzhem Bulem Shozhi sposterezhennya buli zrobleni Aristotelem vidomim greckim logikom Zakoni de Morgana mozhut buti pidtverdzheni prosto i navit zdatisya trivialnimi Tim ne menshe ci zakoni ye korisnimi v stvorenni znachimih visnovkiv v dokazah i rezultatah deduktivnogo mirkuvannya Div takozhPortal Matematika DzherelaKuratovskij K Mostovskij A Teoriya mnozhestv Set Theory Teoria mnogosci M Mir 1970 416 s ros Weisstein Eric W Pravila de Morgana angl na sajti Wolfram MathWorld Pravila de Morgana na PlanetMath angl