CNF, DNF – Python – Fórum – Programujte.com

Tu je skriptik, ktory prevadza booleansku formulu do Konjunktivnej normalnej formy ci Disjunktivnej normalnej formy

#############################################################

#!!!!!!Prevod booleanskej formule do tvaru CNF alebo DNF!!!!!

#Booleansku formulu zadavajte v korektnom prefixovom tvare

#povolene operatory su

# ! NOT

# & konjunkcia

# | disjunkcia

# - implikacia

#############################################################



#funkcia prevedie cislo do binarnej formy s danym poctom miest

#vracia list 

def toBin(cislo,miest):

    ret = [];

    while(cislo>0):

        v = divmod(cislo,2)

        ret.append(v[1])

        cislo = v[0]

    while(len(ret)<miest):

        ret.append(0);

    ret.reverse()

    return ret



#negacia - nahrada za built_in fciu not, ktora vracia true - false

#tato vracia 0,1

def neg(cislo):

    return (cislo + 1) % 2



#fcia vytvori v zavislosti na pocte premennych

#tabulku ohodnoteni premennych

def makeTable(premennych):

    table = []

    for i in xrange(2**premennych):

        table.append(toBin(i,premennych))

    return table



#fcia ktora ohodnoti zadanu bool formulu a vytvori tabulku ohodnoteni

#var je dict s ohodnoteniami premennych

def ohodnocuj(formula,var):

    ev = 0;

    if (formula[0] not in OPERATORY):

        ev = var[formula[0]],1

    elif (formula[0] == '&'):

        ev1 = ohodnocuj(formula[1:],var)

        ev2 = ohodnocuj(formula[1+ev1[1]:],var)

        ev = ev1[0] and ev2[0],ev1[1]+ev2[1]+1

        #ev = ohodnocuj(formula[1:],var) and ohodnocuj(formula[2:],var)

    elif (formula[0] == '|'):

        ev1 = ohodnocuj(formula[1:],var)

        ev2 = ohodnocuj(formula[1+ev1[1]:],var)

        ev =  ev1[0] or ev2[0],ev1[1]+ev2[1]+1

    elif (formula[0] == '-'):

        ev1 = ohodnocuj(formula[1:],var)

        ev2 = ohodnocuj(formula[1+ev1[1]:],var)

        ev = neg(ev1[0]) or ev2[0], ev1[1]+ev2[1]+1

    elif (formula[0] == '!'):

        ev1 = ohodnocuj(formula[1:],var);

        ev = neg(ev1[0]),ev1[1]+1;

    

    return ev



def main():

    # & - and, | - or, ! - not, - - implikacia

    OPERATORY = set('&|!-')

    

    var = {}

    #nastavit na CNF alebo DNF

    forma = 'CNF'

    forma = raw_input(u"Zadajte vystupnu formu [CNF,DNF]: ")

    formula = raw_input(u"Zadaj korektnu Bool formulu v prefixovom tvare: ")

    #formula = '&|!ab|!ba '

    #najdeme si vsetky premenne

    for l in formula[:-1]:

        if ((l not in OPERATORY) and (not var.has_key(l))):

            var[l] = None

    

    cVar = len(var)

    tabulka = makeTable(cVar)

    

    #ohodnotime si vyrok

    tabOhod = {}

    for ohod in tabulka:

        for v in xrange(cVar):

            var[var.keys()[v]] = ohod[v]

        tabOhod[tuple(ohod)] = ohodnocuj(formula[:-1],var)[0]

        #tabOhod.append(ohodnocuj(formula[:-1],var)[0])

    

    #print tabOhod

        

    #z tabulky ohodnoteni urobime vyrok v cnf alebo dnf

    c = 0;

    vysledok = ''

    if (forma == 'CNF'):

        for o in tabOhod.keys():

            if (not tabOhod[o]):

                vysledok +='('

                for v in xrange(cVar):

                    if (o[v]):

                        vysledok += '!' + str(var.keys()[v]) + '|'

                    else:

                        vysledok += str(var.keys()[v]) + '|'

                vysledok = vysledok[:-1]

                vysledok += ')'

                vysledok += '&'                

            c += 1

        vysledok = vysledok[:-1]        

    else:

        for o in tabOhod.keys():

            if (tabOhod[o]):            

                vysledok +='('

                for v in xrange(cVar):

                    if (o[v]):

                        vysledok += str(var.keys()[v]) + '&'

                    else:

                        vysledok += '!' + str(var.keys()[v]) + '&'

                vysledok = vysledok[:-1]

                vysledok += ')'

                vysledok += '|'                

            c += 1

        vysledok = vysledok[:-1]

            

    print vysledok

    

if __name__ == "__main__":

    main()

A co si představuješ pod takovým "Konjunktivnej normalnej formy ci Disjunktivnej normalnej formy" :-D

My jsme tady všichni buď hluboce před vysokou nebo hluboce za, takže to vyjde nastejno :-D

geon napsal:

a co si představuješ pod takovým "Konjunktivnej normalnej formy ci Disjunktivnej normalnej formy" :-D

My jsme tady všichni bud hluboce pšed vysokou nebo hluboce za, takže to vyjde nastejno :-D