Quine-McKluskey
Masz problem? Zapytaj na forum elektroda.pl
From: "Piotr Wyderski" <piotr.wyderskiREMOVE_at_nospam_hoga.pl>
Subject: Quine-McKluskey
Date: Fri, 4 Jul 2003 18:37:47 +0200
Witam,
Czy wiecie moze, gdzie mozna znalezc dowod formalny,
ze metoda Quine-McKluskeya minimalizacji funkcji
booleowskiej f daje najkrotszy mozliwy ciag klauzul DNF
rownowazny tej funkcji (IIRC elektronicy nazywaja je
mintermami)? O ile wiem, to jeden z "koni roboczych"
elektroniki cyfrowej, dlatego pytam tu. :-)
Pozdrawiam
Piotr Wyderski
========
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed.silweb.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai
From: "krzys_iek" <krzys-iek_at_nospam__spam-no_wp.pl>
Subject: Re: Quine-McKluskey
Date: Fri, 4 Jul 2003 20:18:17 +0200
Piotr Wyderski wrote:
Witam,
Czy wiecie moze, gdzie mozna znalezc dowod formalny,
ze metoda Quine-McKluskeya minimalizacji funkcji
booleowskiej f daje najkrotszy mozliwy ciag klauzul DNF
rownowazny tej funkcji (IIRC elektronicy nazywaja je
mintermami)? O ile wiem, to jeden z "koni roboczych"
elektroniki cyfrowej, dlatego pytam tu. :-)
chyba widzialem to w jednej z tych knig...
Traczyk, Wiesław.. Układy cyfrowe automatyki /Wiesław Traczyk. Warszawa :
Wydawnictwa Naukowo-Techniczne, 1976. -- 423 s. : il. ; 21 cm.
11 Majewski, Władysław.. Układy logiczne /Władysław Majewski. Warszawa :
Wydawnictwa Naukowo-Techniczne, 1992. -- 287 s. [ 000072154]
========
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!not-for-mai
From: J.F. <jfox_at_nospam_poczta.onet.pl.nospam>
Subject: Re: Quine-McKluskey
Date: Fri, 04 Jul 2003 23:45:53 +0200
On Fri, 4 Jul 2003 18:37:47 +0200, Piotr Wyderski wrote:
Czy wiecie moze, gdzie mozna znalezc dowod formalny,
ze metoda Quine-McKluskeya minimalizacji funkcji
booleowskiej f daje najkrotszy mozliwy ciag klauzul DNF
rownowazny tej funkcji (IIRC elektronicy nazywaja je
mintermami)? O ile wiem, to jeden z "koni roboczych"
elektroniki cyfrowej, dlatego pytam tu. :-)
Hm, mowiac szczerze to:
a) nie jestem pewien czy metoda daje optymalny wynik,
wiec moze byc trudno udowodnic :-)
b) Kryterium "najlepszosci" moze sie okazac wcale nie takie proste :-)
J.
========
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!newsfeed.gazeta.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai
From: "Piotr Wyderski" <piotr.wyderskiREMOVE_at_nospam_hoga.pl>
Subject: Re: Quine-McKluskey
Date: Sat, 5 Jul 2003 01:28:35 +0200
J.F. wrote:
Hm, mowiac szczerze to:
a) nie jestem pewien czy metoda daje optymalny wynik,
wiec moze byc trudno udowodnic :-)
W jakichs notatkach widzialem "exact", wiec chyba jest. :-)
Ale dowodliwosc jest bardzo wazna; nie musi byc to Q-M.
Czego proponujesz uzyc w zamian? Musi byc automatyczne,
optymalne i mozliwie wydajne (duzo tego mam...).
b) Kryterium "najlepszosci" moze sie okazac wcale nie takie proste :-)
U mnie jest proste: najkrotszy ciag klauzul w dysjunkcyjnej postaci
normalnej, ktory jest rownowazny podanej funkcji (podanej jako
suma mintermow). Mam wykladniczo duzo funkcji do sprawdzenia
(2^{wielomian_trzeciego_stopnia}); chodzi o znalezienie bazy
dla pewnego dowodu indukcyjnego, wiec zastosowanie jest zupelnie
nieelektroniczne. :-) Hm, a moze ma ktos zrodelka dzialajacego
Q-M albo innego minimalizatora dla ok. 1--30 zmiennych i podobnej
liczby klauzul i zechcialby sie podzielic? -- szczerze mowiac nie chce
mi sie tego samemu implementowac, a tylko tego klocka mi brakuje. :-)
Pozdrawiam
Piotr Wyderski
========
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!newsfeed.gazeta.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mai