Boolean Functions

Boyov · Mar 19, 2003, 15:29

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 · Mar 19, 2003, 17:19

ox-ox, надо все это дело вспоминать

я забыл уже.

VX · Mar 19, 2003, 18:44

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

Nemra · Mar 19, 2003, 19:15

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

там пара-тройка классов и алгоритмов...

GeniusRaf · Mar 19, 2003, 20:39

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 · Mar 20, 2003, 08:50

Quote:

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

Tochno tochno . xexe

Quote:

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

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

Quote:

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 · Mar 20, 2003, 10:40

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 · Mar 20, 2003, 12:38

Quote:

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.

Quote:

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"

Quote:

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 · Mar 20, 2003, 15:54

Quote:

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

),
Ya b@ s udovolystiem pomog tebe prosto u menya net vremeni v dann@i moment.(Tak chto sam chitai)
Udachi

Nemra · Mar 22, 2003, 20:14

Sorry, не нашел файл-ов... а дело было лет 5 назад так что наизусть не помню...
Алгоритм был "изотоп"-ом Блейка, как вы выражаетесь

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

Boyov · Mar 24, 2003, 21:06

Quote:

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),
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' ,

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

Quote:

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 ?

I nexera davat' mne tupie soveti tipa "(Tak chto sam chitai)".
VSE.

Quote:

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

Thanks anyway

Mar 19, 2003, 15:29	#1
Boyov 4294967296 Join Date: Mar 2002 Location: /proc/1 Posts: 378 Rep Power: 7 Reputation: 10	Boolean Functions 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 __________________ Free your mind and your OS will follow

Mar 19, 2003, 17:19	#2
greka Administrator Join Date: Sep 2001 Location: @work Posts: 5,347 Rep Power: 10 Reputation: 23	ox-ox, надо все это дело вспоминать я забыл уже. __________________ И повешенные могут качаться в неположенную сторону. /С.Е.Лец/

Mar 19, 2003, 18:44	#3
VX Консервативный Демагог Join Date: Jan 2002 Location: Кавказская Албания Posts: 889 Rep Power: 7 Reputation: 10	Es "Chust"-i kursaini vra es mtatsum BTW? __________________ Праздник к нам приходит... \|^^^^^^^^^'''^\\| \|\|\__ \| ВОДКА-ВОДКА \| \|\|','''\|'''''''\_____,_ \| _..... _ \| \|\|_ _\|'__\|_____\|\|.........\| \| '(@)'(@)'(@)''''''''''''''''''''''\|(@)""""\|(@)

Mar 19, 2003, 19:15	#4
Nemra Дошкольник Join Date: Jul 2002 Location: South Park Posts: 82 Rep Power: 0 Reputation: 10	Хе-хе... это было моей курсовой на 4-ом курсе.... вроде и файлы реализации есть, надо поискать там пара-тройка классов и алгоритмов... __________________ std::for_each( users.begin(), users.end(), std::bind2nd( std::mem_fun(&ForumMember::sendMessage), "Hello"))

Mar 19, 2003, 20:39	#5
GeniusRaf Младенец Join Date: Jun 2002 Location: Armenia,Yerevan Posts: 11 Rep Power: 0 Reputation: 10	Boolean function !!! 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! __________________ The best way to save money is to invest it in knowledge and/or information area...

Mar 20, 2003, 10:40	#7
GeniusRaf Младенец Join Date: Jun 2002 Location: Armenia,Yerevan Posts: 11 Rep Power: 0 Reputation: 10	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 __________________ The best way to save money is to invest it in knowledge and/or information area...

Mar 22, 2003, 20:14	#10
Nemra Дошкольник Join Date: Jul 2002 Location: South Park Posts: 82 Rep Power: 0 Reputation: 10	Sorry, не нашел файл-ов... а дело было лет 5 назад так что наизусть не помню... Алгоритм был "изотоп"-ом Блейка, как вы выражаетесь Получая формулу в виде нормальной коньюктивной формы и используя две операции (поглощения и склейки) алгоритм делал проход пока возможно применение. Всех тонкостей я к сожалению просто не помню. Извини... А реализация что-то вроде: enum Bool {NEGATIVE, POSITIVE, NOTPRESENT}; typedef std::vector<Bool> ElementaryConjunction; typedef std::list<ElementaryConjunction> NormalDisjunctiveForm; __________________ std::for_each( users.begin(), users.end(), std::bind2nd( std::mem_fun(&ForumMember::sendMessage), "Hello"))

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode