Quine-McKluskey



Masz problem? Zapytaj na forum elektroda.pl

Poprzedni Następny
Wiadomość
Spis treści
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

Poprzedni Następny
Wiadomość
Spis treści
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

Poprzedni Następny
Wiadomość
Spis treści
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

Poprzedni Następny
Wiadomość
Spis treści
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