CNF, DNF – Python – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

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

 

6. 3. 2006   #1
-
0
-

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()

Nahlásit jako SPAM
IP: ...–
geon0
Grafoman
12. 3. 2006   #2
-
0
-

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

Nahlásit jako SPAM
IP: ...–
geon. volume doprava.
12. 3. 2006   #3
-
0
-

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



CNF - konjunktivna normalna forma je forma booleanskej formuly . Je to vlastne konjunkcia disjunkcii, tzn. medzi kazdym literalom v zatvorke je disjunkcia a medzi zatvorkami su konjunkcie (a | b | c) & (!a | c | !b) & (!a | b | c) je CNF.

DNF - disjunktivna normalna forma je opak - je to disjunkcia konjunkcii, teda v zatvorkach su konjunkcie a medzi zatvorkami disjunkcie (a & b) | (!a & b)

http://mathworld.wolfram.com/ConjunctiveNormalForm.html
http://en.wikipedia.org/wiki/Conjunctive_normal_form
http://www.google.sk/search?hl=sk&q=conjunctive+normal+form&btnG=Vyh%C4%BEada%C5%A5+v+Google&meta=

Nahlásit jako SPAM
IP: ...–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 5 hostů

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032024 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý