Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Ця стаття не містить посилань на джерела Ви можете допомогти поліпшити цю статтю додавши посилання на надійні авторитетн

Досконала кон'юнктивна нормальна форма

Досконала кон'юнктивна нормальна форма
Ця стаття не містить . Ви можете допомогти поліпшити цю статтю, додавши посилання на . Матеріал без джерел може бути піддано сумніву та вилучено. (липень 2022)

Досконалою кон’юнктивною нормальною формою (ДКНФ) булевої функції називається кон’юнкція тих конституент нуля, які перетворюються в нуль на тих самих наборах змінних, що й задана функція. Також по аналогії з ДДНФ, будь-яка булева функція має одну ДКНФ (кількість її членів дорівнює кількості нульових значень функції) і декілька КНФ. Можна навести такі властивості ДКНФ, що виділяють її з усіх КНФ:

  • в ній немає однакових співмножників;
  • жоден із співмножників не містить двох однакових доданків;
  • жоден із співмножників не містить якої-небудь змінної разом з її запереченням;
  • в кожному окремому співмножнику є як складова або змінна xi, або її заперечення для будь-якого i=1,2,…,n.

Приклад знаходження ДКНФ

Для того, щоб отримати ДКНФ функції, потрібно скласти її таблицю істинності. Наприклад, візьмемо одну з таблиць істинності з статті Метод Куайна:

image
image
image
image
image
0 0 0 0 1
0 0 0 1 1
0 0 1 0 1
0 0 1 1 0
0 1 0 0 0
0 1 0 1 0
0 1 1 0 1
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 0
1 1 0 1 0
1 1 1 0 1
1 1 1 1 1

В комірках стовпця image відмічаються лишень ті комбінації, які приводять логічний вираз до нуля.

Наприклад, четвертий рядок містить 0 в даній комірці image

  • image = 0
  • image = 0
  • image = 1
  • image = 1

В диз'юнкцію змінна записується без інверсії, якщо в наборі вона дорівнює 0, і з інверсією, якщо вона дорівнює 1. Перший член ДКНФ даної функції має такий вигляд: image image image image image

Всі інші члени ДКНФ складаються по аналогії і тоді отримується наступна ДКНФ:

image
image
image

Див. також

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Cya stattya ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno lipen 2022 Doskonaloyu kon yunktivnoyu normalnoyu formoyu DKNF bulevoyi funkciyi nazivayetsya kon yunkciya tih konstituent nulya yaki peretvoryuyutsya v nul na tih samih naborah zminnih sho j zadana funkciya Takozh po analogiyi z DDNF bud yaka buleva funkciya maye odnu DKNF kilkist yiyi chleniv dorivnyuye kilkosti nulovih znachen funkciyi i dekilka KNF Mozhna navesti taki vlastivosti DKNF sho vidilyayut yiyi z usih KNF v nij nemaye odnakovih spivmnozhnikiv zhoden iz spivmnozhnikiv ne mistit dvoh odnakovih dodankiv zhoden iz spivmnozhnikiv ne mistit yakoyi nebud zminnoyi razom z yiyi zaperechennyam v kozhnomu okremomu spivmnozhniku ye yak skladova abo zminna xi abo yiyi zaperechennya dlya bud yakogo i 1 2 n Priklad znahodzhennya DKNFDlya togo shob otrimati DKNF funkciyi potribno sklasti yiyi tablicyu istinnosti Napriklad vizmemo odnu z tablic istinnosti z statti Metod Kuajna x 1 displaystyle mathbf x 1 x 2 displaystyle mathbf x 2 x 3 displaystyle mathbf x 3 x 4 displaystyle mathbf x 4 f x 1 x 2 x 3 x 4 displaystyle mathbf f x 1 x 2 x 3 x 4 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 V komirkah stovpcya f x 1 x 2 x 3 x 4 displaystyle mathbf f x 1 x 2 x 3 x 4 vidmichayutsya lishen ti kombinaciyi yaki privodyat logichnij viraz do nulya Napriklad chetvertij ryadok mistit 0 v danij komirci f x 1 x 2 x 3 x 4 displaystyle mathbf f x 1 x 2 x 3 x 4 x 1 displaystyle mathbf x 1 0 x 2 displaystyle mathbf x 2 0 x 3 displaystyle mathbf x 3 1 x 4 displaystyle mathbf x 4 1 V diz yunkciyu zminna zapisuyetsya bez inversiyi yaksho v nabori vona dorivnyuye 0 i z inversiyeyu yaksho vona dorivnyuye 1 Pershij chlen DKNF danoyi funkciyi maye takij viglyad x 1 displaystyle x 1 vee x 2 displaystyle x 2 vee x 3 displaystyle overline x 3 displaystyle vee x 4 displaystyle overline x 4 Vsi inshi chleni DKNF skladayutsya po analogiyi i todi otrimuyetsya nastupna DKNF x 1 x 2 x 3 x 4 x 1 x 2 x 3 x 4 x 1 x 2 x 3 x 4 x 1 x 2 x 3 x 4 displaystyle x 1 lor x 2 lor overline x 3 lor overline x 4 land x 1 lor overline x 2 lor x 3 lor x 4 land x 1 lor overline x 2 lor x 3 lor overline x 4 land x 1 lor overline x 2 lor overline x 3 lor overline x 4 land x 1 x 2 x 3 x 4 x 1 x 2 x 3 x 4 x 1 x 2 x 3 x 4 x 1 x 2 x 3 x 4 displaystyle overline x 1 lor x 2 lor x 3 lor x 4 land overline x 1 lor x 2 lor x 3 lor overline x 4 land overline x 1 lor x 2 lor overline x 3 lor x 4 land overline x 1 lor x 2 lor overline x 3 lor overline x 4 land x 1 x 2 x 3 x 4 x 1 x 2 x 3 x 4 displaystyle overline x 1 lor overline x 2 lor x 3 lor x 4 land overline x 1 lor overline x 2 lor x 3 lor overline x 4 Div takozhNormalna forma formuli u logici predikativ DNF KNF Doskonala diz yunktivna normalna forma

Дата публікації:
Топ