Keskustelu:Disjunktiivinen normaalimuoto

Äskeisestä (klo 15:55) Jmk:n poistosta

Myönnän toki, että poistamasi kohta oli artikkelin turhin kohta ja sen voi nähdä jaarittelunakin, mutta halusin siinä vain alleviivata sitä, että $0_{\mathbf {} }$-funktion tapauksessa käytetetyn esityksen rakenne poikkeaa monella tavalla muista tapauksista. Olinkin pistänyt sen sulkuihin, joista lukija luultavasti arvaa, että se on epäoleellisempaa, jonka yli voi halutessaan hypätä. NettiKirjoittaja 9. lokakuuta 2009 kello 16.16 (EEST)

Oikeastaan ihan kelpo klo 16:13 lisäys. Jmk sanoo siinä: "On huomattava, ettei mikä tahansa TAI-, JA- ja EI-konnektiiveja yhdistelemällä muodostettu lauseke ole disjunktiivisessa normaalimuodossa. Normaalimuoto edellyttää, että TAI-konnektiivit ovat uloimpana, JA-konnektiivit seuraavalla tasolla, ja EI-konnektiivit sisimpänä suoraan literaalien edessä.". Tuo "3-tasoisuus" oli hyvä erikseen mainita, vaikka se kyllä implisiittisesti näkyy minunkin esityksestäni. Oikeastaan itse suunnittelin kirjoittavani myöhemmin jatkon, jossa olisi erikseen sanottu tuo 3-tasoisuus (alla negaatioita käytetään literaaleissa, keskellä konjunktioita ja ylinnä disjunktiota) ja annettu esimerkkikuva, jossa tämä 3-tasoisuus olisi näkynyt puuesityksen muodossa. Tällaiset lausekkeethan voi esitää myös puiden avulla, mutta sellaisen piirtäminen tuntuu senverran hankalalta, että heti en viitsinyt siihen ryhtyä, vaan pistin ensimmäisen version artikkelista näkyville viime yönä. Edelleen suunnittelen sen puun laittamista, ja erillisen artikkelinkin voisi esimerkkeineen tehdä lausekkeiden puuesityksistä. NettiKirjoittaja 9. lokakuuta 2009 kello 16.23 (EEST)

Muokkasin vähän, kun Jmk sanoi minusta hieman epäselvästi "Totuusfunktion sanotaan olevan disjunktiivisessa normaalimuodossa,". Vaikka sinunkin selostuksestasi asia tuli kyllä ilmi, minusta tuo muotoilu tuo julki paremmin sen, että on tehtävä ero totuusfunktion ja sen esitysten välille. NettiKirjoittaja 9. lokakuuta 2009 kello 16.31 (EEST)

Ihan hyvä täsmennys. Ja negaatiotkin olivat minulla lipsahtaneet "literaalien" eteen (po. propositiomuuttujien). – Joka tapauksessa tässä artikkelissa on pyrittävä heti kärkeen kuvaamaan se, miltä semmoinen DNF-kaava näyttää, sen sijaan että selostetaan ensin kappalekaupalla liitännäisyyttä jne. Toisaalta – kaikesta pitkällisyydestään huolimatta – artikkelista puuttuu esim. se keskeinen huomio, että vaikka minkä tahansa propositiokaavan voi kyllä muuntaa DNF:ään, sen pituus voi samalla kasvaa eksponentiaalisesti. (En-wikin artikkeli onnistuu sen kaikessa lyhyydessään mainitsemaan.) Tämä ihan vain esimerkkinä siitä, että tekstin pituus ei takaa sen kattavuutta. --Jmk 9. lokakuuta 2009 kello 16.37 (EEST)

Jmk sanoo:"vaikka minkä tahansa propositiokaavan voi kyllä muuntaa DNF:ään". Niin enkkuwiki sanoo asian näin, ja sanoo käytettävän "double negative elimination, De Morgan's laws and the distributive law". Minulla kuitenkin tuo normaalimuodon tärkeyden perustelu on toinen kuin saavutettavuus noiden muunnosten avulla. Minä selitän sen sillä yksinkertaisemmalla havainnollisella tavalla, että esitys "poimii" disjunktioon erikseen jokaisen totuusjakauman, jolla totuusfunktio saa arvon $1_{\mathbf {} }$. Tämän jälkeen on selvää, että jokaiselle (oikein muodostetulla) esitykselle löytyy ekvivalentti normaalimuoto, sillä jokainen esitys esittää jotain totuusfunktiota, ja äsken selitetyn "poimimisen" takia jokainen totuusfunktio voidaan antaa normaalimuodossa. Kysymys on siis myös lähestymistapojen erosta minun selostukseni ja enkkuwikin artikkelin esityksen välillä. Toki aina jää asioita puuttumaan, kun esimerkiksi samalla nimellä kulkevista lauseista on eri versioita, joista toinen on paljon yleisempi kuin toinen. Minäkin tiedän enkkuwikistä artikkeleita, joissa on mainittu lauseesta vain versio, jota yleisemmän minäkin olen todistuksineen nähnyt. NettiKirjoittaja 9. lokakuuta 2009 kello 16.49 (EEST)

Et tainnut ihan ymmärtää tuota en-wikin huomautusta lausekkeen pituuden kasvusta. Ei se ole kiinni siitä, mitä normalisointimenetelmää käytetään (de Morgan yms. vai totuustaulusta "poimiminen" vai jotain muuta). On helppo esittää lausekkeita (en-wikissä annetaan yksi esimerkki), joille DNF-muoto on väistämättä eksponentiaalisen pituinen (verrattuna alkuperäisen pituuteen). Tämä ei ole mikä tahansa trivialiteetti vaan merkityksellinen laskennallisen kompleksisuuden teoriassa. --Jmk 9. lokakuuta 2009 kello 17.00 (EEST)

Pah. Kyllä minä tasantarkkaan ymmärsin sen mitä enkkuwikissä sanottiin. Ei se eksponentiaalinen "räjähdys" tosiaan riipu muunnostavasta, koska siinä vertailu on lyhimpään mahdolliseen disjunktiiviseen normaalimuotoon, jossa mm. alkeiskonjunktioissa ei tarvitse esiintyä kaikkia propositiomuuttujia.(esimerkiksi $x_{1}\mathbf {}$ ajaa yksin saman asian kuin $x_{1}x_{2}\lor x_{1}\neg x_{2}\mathbf {}$) Minun esittelemäni normaalimuoto oli oikeastaan täysi disjunktiivinen normaalimuoto. Se mitä ajoin takaa oli se, että enkkuwikin artikkelissa ei erikseen todistettu, että JOKAISELLA totuusfunktiolla on DNF-esitys, vaan lähdettiin jo valmiiksi siitä, että totuusfunktio on peräisin JOSTAIN peruskonnektiiveilla toteutetusta esityksestä ja sitten "(DNF) is a standardization (or normalization) of a logical formula which is a disjunction of conjunctive clauses". Ei välttämättä äkkipäätään olisi itsestäänselvää, että jokaiselle totuusfunktiolle ylipäätään on esitys peruskonnektiivien avulla, mutta sitten se onkin selvää, kun mennään totuusfunktiosta suoraan DNF:ään kuvaamani "poimimismenetelmän" avulla. Kuvaamani juttu on toki melko yksinkertainen asia, mutta eikö kannata selittää perusasia ENNEN kuin mennään vaikeampiin ja kaukaisempiin asioihin kuten laskennan kompleksisuuden teoriaan. Koko artikkelini tarkoitus olikin vain sanoa, että DNF:llä saa esitettyä kaikki totuusfunktiot ja se mihin tämä väite perustuu. NettiKirjoittaja 9. lokakuuta 2009 kello 22.15 (EEST)

Yksi asia on kyllä totta. Nimittäin se, että artikkelini "kärki" oli sen osoittamisessa, että DNF tarjoaa esityksen kaikille totuusfunktioille, jolloin itse DNF:n muodon esittäminen (jonka pitäisi olla pääosassa artikkelissa nimeltä "Disjunktiivinen normaalimuoto") jäi tekstissäni melko epäselväksi, vaikka kyllä sen sieltä "implisiittisesti" näkee. Tästä syystä Jmk:n lisäys artikkelin alkuun oli varsin hyvä. Yritän jossain vaiheessa hioa artikkelin ilmaisuja, mutta mielestäni se kyllä on oleellinen osa DNF:n tärkeyttä se, että se tarjoaa oivan tavan osoittaa peruskonnektiivit täydelliseksi joukoksi. Toki se pituuden "eksponentiaalinen räjähdys" voidaan myös mainita. NettiKirjoittaja 11. lokakuuta 2009 kello 21.53 (EEST)

Kirjoitustavasta

Artikkelia on kritisoitu, että se on jaaritteleva ja liian laaja. Näkisin, että tämä pitää paikkansa vain osittain.

Itse ehdottaisin paremminkin, että asian yleistasolla määrittelevää alkukappaletta täsmennettäisiin. Silloin toimisi hyvin se idea, että yleistiedon haluava lukee vain alkukappaleen, mutta syvemmin ja täsmällisemmin asiasta tietoa hakeva lukee loputkin.

Artikkelin nimi on "Disjunktiivinen normaalimuoto" eikä siinä tulisi mennä syvemmälle muunnoksiin - muunnokset ovat eri asia kuin muoto. Olisiko mahdollista perustaa järkevästi jokin sivuava artikkeli muuntamisesta?

Ehkä parasta olisi, että esimerkkejä ja muunnosmenetelmiä kuvattaisiin kirjaston puolella. Jos materiaalia ei saa kohtuudella, ehkä sitä ei olisi hätiköitävä kokonaan poistamaankaan. --Aulis Eskola 9. lokakuuta 2009 kello 17.38 (EEST)

Kannattaisiko sellainen muutos, että...

Kannattaisiko minun teidän mielestänne tehdä sellainen muutos, että perustaisin oman artikkelin liittyen totuusfunktio-joukon täydellisyyteen, ja siirtäisin sinne niin täältä tuon totuusfunktion DNF-esityksen muodostamisen kuvailun kuin myös Totuusfunktio-artikkelista aloittamani (Minun pitäisi kirjoittaa se loppuun.) jutun siitä, että miten mieliv. totuusfunktio-joukon täydellisyyttä voidaan tutkia vertaamalla sitä viiteen eri totuusfunktio-luokkaan. Senkin menetelmän todistus (ainakin näkemäni) nojautuu siihen, että siitä riippumattomasti "peruskonnektiivit" on voitu osoittaa täydelliseksi joukoksi "totuustaulusta 1:n poimimisen" menetelmällä. NettiKirjoittaja 14. lokakuuta 2009 kello 23.51 (EEST)