Boolean Functions

[Boyov]

Zdarova

Kto nibud' mojet priduamt' algoritm kotory bi minimiziroval Bulevi funkcii , zadannie v SDNF
(Soverhennaya Dizyunktivnaya Normal'naya Forma) ili tablichno.
Ya znayu chto esrt' algoritm Kveina-Maklavski ( ya ne uveren v pravil'nosti napisaniya imen) , kotori , po suti, yavlyaetsya mashinnoy realizaciey algoritma Bleyk-a.
Esli ne slojno napi****e pliz. ego naibolee prostuyu ( na vash vzglyad ) realizaciyu toje .
Ya dumayu chto ego mojno napisat' s ispolzovaniem dinamicheskix vektorov , no ya ne mogu ponyat' kakoe naibolee optimal'noe uslovie doljno slujit' signalom dlya okonchaniem etogo algoritma.

Spasibo

Boyov

[greka]

ox-ox, надо все это дело вспоминать :) я забыл уже.
;)

[VX]

Es "Chust"-i kursaini vra es mtatsum BTW?

[Nemra]

Хе-хе... это было моей курсовой на 4-ом курсе.... вроде и файлы реализации есть, надо поискать ;) там пара-тройка классов и алгоритмов...

[GeniusRaf]

Zdarovo Tyom! dumayu chto eto mojet tebe pomochy ne smotrya na to chto eto ne programa(a prosto dumayu shto xoroshii algoritm).
p q (1) (2) (3) (4) (5) (6) (7)
0 0 .0...0...1...0...1...1...1
0 1 .0...1...1...1...0...1...0
1 0 .0...1...0...1...0...1...1
1 1 .1...1...1...0...1...0...0
p^q and (1)
pvq or (2)
p=>q implication(3)
p+q xor(4)
p<=>q equvaluant(5)
p|q not or(6)
p\q not and(7)
not x toje samoe chto(~x)
not=~
eto prosto dlya togo chto b@ t@ v dalyneyshem ponimal moi znaki .
Ya dumayu t@ znaesh svoistva bulev@x funkcii tak chto ya eto ne napishu no esli ponadobitsa mogu skazaty.
Ladno pereidu ka algoritmu ...
1.
p<=>q=(p=>q)(q=>p),
p=>q=(~p)vq
p+q=(~p)qvp(~q)
dlya togo chto b@ ustanity operacii =>,<=>,+ ostaviv tolyko and ,or,not
2.
ispolyzuem zakon@ de Morgana
~(pvq)=(~p)(~q),
~(pq)=(~p)v(~q)
dlya togo chto b@ kajdaya operaciya
otricanie otnosilasy tolyko k odnoi
peremennoi .
3.
ispolyzuem svoistvo distributivnosti i drugie svoistvo ,chtob@ poluchity normalynuyu formu.Chasto dlya poluchenie sknf(KKNDz)nujno ispolyzovaty sleduyushie svoistvo distributivnosti:
(pq)vr=(pvr)(qvr)
vse..
a tepery odin premer ...
f(p,q,r)=(~p)vq+rq(pvr)

f(p,q,r)=(~p)vq+rq(pvr)=
=(~(~pvq)rq(pvr))v(~pvq)~(rq(pvr))=
=p~qrq(pvr)v(~pvq)(~rv~qv(~p~r))=
=(~pvq)(~rvqv(~p~r))=
=(~pvq)(~rv~qv~p)(~rv~qv~r)=
=(~pvq)(~qv~r).

takim obrozom ,ya poluchil
(Kataryal Normal Dzev) funkcii f(p,q,r).
Chtob@ poluchity ee (KKNDz),nujno kajd@i dizyunkt ,v kotorom ne xvataet
kakoi-libo peremennoi ,povtority dvajd@: s etoi peremennoi i ee otricaniem:
f(p,q,r)=(~pvqvr)(~pvqv~r)(pv~qv~r)(~pv~qv~r).

Poka!:)

[Boyov]

Originally posted by VX
Es "Chust"-i kursaini vra es mtatsum BTW?

Tochno tochno . xexe

Хе-хе... это было моей курсовой на 4-ом курсе.... вроде и файлы реализации есть, надо поискать там пара-тройка классов и алгоритмов

Chto za algoritm? Sam pisal ? Esli ne slojno postni please.

Zdarovo Tyom! dumayu chto eto mojet tebe pomochy ne smotrya na to chto eto ne programa(a prosto dumayu shto xoroshii algoritm).
.........................


Privet Raf, Vo pervix mne nujno bilo Minimizirovat' etu funciyu a ne poluchit' ee KND ( esli ti ne zametil bila zadana SDNF (KDNdz Kataryal Dizyunktiv Normal Dzev), tak chtmo mne KND vse ravno chto
Ribe zontik (ili zayacu STOP signal, same **** :) ). I eshe odno tvoy algoritm napisan tol'ko dlya 3-x peremennix, u menya ix 5!,
i voobshe menya interesuet algorithm dlya funkcii ot n peremennix.
Potom esli eto vse ravno delaetsya v ruchnuyu naibolee optimal'nim metodom ya schitayu karti KARNO, prikin' esli u tebya budet 10 peremnnix qo algorithm Zadoxnetsya
No vse ravno Spasibo ;-).
BTW ti etot algoritm sam pridumal te et Blake-i algoritgmi izotop-a?

wishes

Boyo6

[GeniusRaf]

Privet!
Artem a zachem t@ ne ispolyzuesh metod
Kvayna (ayspes asats sosndzumov)??
potom esli b@ t@ b@l vnimatelyn@m t@ b@ zametil chto v primere ya skazal neskolyko slovami kak minimizirovaty etu funkciu...
Ladno, kstati kak ya ponyal t@ ne xochesh ispolyzovaty metod Karno vobshem sluchii ,tak kak eto ocheny dolgo i ne optimalno.No ya mogu pomoch s etim Algoritmom esli zaxochesh??..
A chto kasaetsya "source" moix znanii pravda govorya esty odna zamechatelynaya kniga "Teoriya Avtomatov",no ya dumayu vse chto tebe nujno b@lo svyazano s etoi problemoi ya tebe uje soobshil.
Esli ponadobitysa esho chto nibudy to ya vsegda rad otvetity v ramkax moix znanii.
Paka:)

[Boyov]

Originally posted by GeniusRaf
Privet!
Artem a zachem t@ ne ispolyzuesh metod
Kvayna (ayspes asats sosndzumov)??

Nu ti skazal Rafik, ti mojesh sebe predstavit' ego realizaciyu ???
Pojaluysta vnimatelnee chitay posti, ya je naverxu napisal chto Metod Quine-McCluskey eto MASHINNAYA (t..e. compyuternaya ) realizaciya algorithma Bleyka (algoritm Bleyka ili Quine -a) odno i toje.

Originally posted by GeniusRaf

potom esli b@ t@ b@l vnimatelyn@m t@ b@ zametil chto v primere ya skazal neskolyko slovami kak minimizirovaty etu funkciu...


Tak ya je prosil normal'no rabotayushii algorithm a ne "neskolyko slovami"

Originally posted by GeniusRaf

Ladno, kstati kak ya ponyal t@ ne xochesh ispolyzovaty metod Karno vobshem sluchii ,tak kak eto ocheny dolgo i ne optimalno.No ya mogu pomoch s etim Algoritmom esli zaxochesh??..


Povtoryayu dlya tex kto v BRONEPOEZDE mmne nujen algoritm dly KOMPYUTERA a ne cheloveka, karti Karno klevaya i ochen' udobnaya vesh' , no vo pervix eto chisto VISUALNIY (ne podxodyashi ,ili ploxo podxodyashi dlya compyutera) metod, a vo vtorix
kogda ti minimiziruesh po kartam Karno ti naxodish odnu iz Tupikovix (Pakughayin) DNF.

[GeniusRaf]

Originally posted by Boyov

Pojaluysta vnimatelnee chitay posti, ya je naverxu napisal chto Metod Quine-McCluskey eto MASHINNAYA (t..e. compyuternaya ) realizaciya algorithma Bleyka (algoritm Bleyka ili Quine -a) odno i toje.
(Pakughayin) DNF.
Slushay da t@ voobshe znaish chto takoe "Search Engine"naprimer (alltheweb.com)napishi ka tam t@ etot
tvoi MASHINN@I metod "Quine-McCluskey " i uvidish mnogo ss@lok v kotor@x napisano pochti vse ob etom metode.(mojet T@ ne ponimaesh po Angliskii:D),
Ya b@ s udovolystiem pomog tebe prosto u menya net vremeni v dann@i moment.(Tak chto sam chitai)
Udachi:)

[Nemra]

Sorry, не нашел файл-ов... а дело было лет 5 назад так что наизусть не помню...
Алгоритм был "изотоп"-ом Блейка, как вы выражаетесь :) Получая формулу в виде нормальной коньюктивной формы и используя две операции (поглощения и склейки) алгоритм делал проход пока возможно применение. Всех тонкостей я к сожалению просто не помню. Извини...
А реализация что-то вроде:
enum Bool {NEGATIVE, POSITIVE, NOTPRESENT};
typedef std::vector<Bool> ElementaryConjunction;
typedef std::list<ElementaryConjunction> NormalDisjunctiveForm;

[Boyov]

Originally posted by GeniusRaf
Slushay da t@ voobshe znaish chto takoe "Search Engine"naprimer (alltheweb.com)napishi ka tam t@ etot
tvoi MASHINN@I metod "Quine-McCluskey " i uvidish mnogo ss@lok v kotor@x napisano pochti vse ob etom metode.(mojet T@ ne ponimaesh po Angliskii:D),
Ya b@ s udovolystiem pomog tebe prosto u menya net vremeni v dann@i moment.(Tak chto sam chitai)
Udachi:)

Vo pervix ne uchi menya chto i gde nado iskat' , :mad: (nedoros eshe) vo vtorix esli ti dumaesh chto ya ne znayu chto takoe search engine , to ti v glubokom zablujdenii (pochemu ti tak uveren v tom chto ya ne iskal eto v kakom nibud' google-e ???), v tretyix ete mi bainc KURSI CHES ( opyat' je chitay chto ya napisal v samom pervom poste) to ne nado postit' prosto tak, naschet angliyskogo
ya ne dumayu chto u tebya est' pricihini dumat' chto ya ne ponimayu po angliyski,



Ya b@ s udovolystiem pomog tebe prosto u menya net vremeni v dann@i moment.(Tak chto sam chitai)
Udachi:) [/B]
A ti uveren chto smojesh ? :devil:
I nexera davat' mne tupie soveti tipa "(Tak chto sam chitai)".
VSE.



Sorry, не нашел файл-ов... а дело было лет 5 назад так что наизусть не помню...Алгоритм был "изотоп"-ом Блейка, как вы выражаетесь Получая формулу в виде нормальной коньюктивной формы и используя две операции (поглощения и склейки) алгоритм делал проход пока возможно применение. Всех тонкостей я к сожалению просто не помню. Извини...
А реализация что-то вроде:
enum Bool {NEGATIVE, POSITIVE, NOTPRESENT};
typedef std::vector<Bool> ElementaryConjunction;
typedef std::list<ElementaryConjunction> NormalDisjunctiveForm.

Thanks anyway :)