web counter


https://www.amazon.it/dp/B0CT9YL557

We support WINRAR [What is this] - [Download .exe file(s) for Windows]

CLASSICISTRANIERI HOME PAGE - YOUTUBE CHANNEL
SITEMAP
Audiobooks by Valerio Di Stefano: Single Download - Complete Download [TAR] [WIM] [ZIP] [RAR] - Alphabetical Download  [TAR] [WIM] [ZIP] [RAR] - Download Instructions

Make a donation: IBAN: IT36M0708677020000000008016 - BIC/SWIFT:  ICRAITRRU60 - VALERIO DI STEFANO or
Privacy Policy Cookie Policy Terms and Conditions
Dysjunkcyjna postać normalna - Wikipedia, wolna encyklopedia

Dysjunkcyjna postać normalna

Z Wikipedii

Dysjunkcyjna postać normalna (ang. disjunctive normal form, DNF) formuły logicznej to formuła zapisana w postaci dysjunkcji (alternatywy) klauzul dualnych.

Na przykład dysjunkcyjną postacią normalną wyrażenia (a \or b) \and c jest (a \and c) \or (b \and c).

Każde wyrażenie logiczne ma dysjunkcyjną postać normalną.

Spis treści

[edytuj] Definicja formalna

Formuła φ jest w dysjunktywnej postaci normalnej jeśli jest ona alternatywą klauzul, z których każda jest koniunkcją literałów, tzn. ma następującą postać

(p_{11} \wedge p_{12} \wedge ... \wedge p_{1k_1}) \vee (p_{21} \wedge p_{22} \wedge ... \wedge p_{2k_2}) \vee ... \vee (p_{n1} \wedge p_{n2} \wedge ... \wedge p_{nk_n})

gdzie każde pij jest literałem.

[edytuj] Problem znajdowania wartościowania

Problem znajdowania wartościowania spełniającego formuły w postaci DNF jest problemem łatwym, tzn. istnieje algorytm wielomianowy rozwiązujący ów problem. Jeśli bowiem jest choć jedna klauzula dualna, która nie zawiera ani fałszu ani jednocześnie pewnej zmiennej i jej negacji, możemy wszystkim wystąpieniom pozytywnym przyporządkować prawdę, negatywnym zaś fałsz, przez co ta klauzula dualna będzie spełniona, a zatem i cały DNF.

Jeśli natomiast każda klauzula dualna zawiera albo fałsz (a więc jest fałszywa), albo jednocześnie zmienną i jej zaprzeczenie (z których przynajmniej jedno musi być fałszywe), to oznacza to, że nie jest ona spełnialna.

Przykład algorytmu wielomianowego znajdującego wartościowanie formuły podanej w postaci DNF podany jest poniżej.

Podobny problem, znajdowania wartościowania formuły w koniunkcyjnej postaci normalnej jest NP-zupełny.

[edytuj] Wielomianowy algorytm znajdujący wartościowanie spełniające

Przyjmijmy następujące założenia co do wejścia i wyjścia algorytmu:

  • formuła φ podana na wejściu jest zbiorem klauzul,
  • każda klauzula jest zbiorem literałów,
  • algorytm zwraca zbiór zmiennych, którym należy nadać wartość true (pozostałym zmiennym należy nadać wartość false) aby formuła φ była spełniona jeśli formuła jest spełnialna, w przeciwnym przypadku zwraca specjalną wartość nil.
foreach C_i \in \phi
begin
    ok := true;
    foreach a_j \in C_i
        foreach b_k \in C_i
            if a_j = \neg b_k then ok := false;
    if ok then
    begin
        T := \empty;
        foreach a_j \in C_i
            if aj jest niezanegowaną zmienną xl then T := T \cup \{x_l\};
        return T;
    end
end
return nil;

Algorytm dla każdej klauzuli sprawdza czy jest ona niesprzeczna. Gdy znajdzie niesprzeczną klauzulę zwraca zbiór zmiennych, które w niej występują jako literały bez negacji. Można łatwo sprawdzić, że algorytm ten ma złożoność czasową nie gorszą niż O(n²), gdzie n to liczba literałów w formule φ.

Algorytm ten nie może posłużyć do rozwiązania NP-zupełnego problemu spełnialnosci formuł w postaci CNF ponieważ w ogólnym przypadku rozmiar formuły przy przekształcaniu jej z postaci CNF do DNF może wzrosnąć wykładniczo.

[edytuj] Zobacz też

Static Wikipedia 2008 (no images)

aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - en - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu -

Static Wikipedia 2007 (no images)

aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - en - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu -

Static Wikipedia 2006 (no images)

aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu -

Sub-domains

CDRoms - Magnatune - Librivox - Liber Liber - Encyclopaedia Britannica - Project Gutenberg - Wikipedia 2008 - Wikipedia 2007 - Wikipedia 2006 -

Other Domains

https://www.classicistranieri.it - https://www.ebooksgratis.com - https://www.gutenbergaustralia.com - https://www.englishwikipedia.com - https://www.wikipediazim.com - https://www.wikisourcezim.com - https://www.projectgutenberg.net - https://www.projectgutenberg.es - https://www.radioascolto.com - https://www.debitoformtivo.it - https://www.wikipediaforschools.org - https://www.projectgutenbergzim.com