Cea mai eficienta metoda de a calcula SoP sau PoS ?

Cea mai eficienta metoda de a calcula SoP sau PoS ???

https://www.electron...-form-pos-form/
SoP = sum of product
Pos = product of sum

Avand expresia booleana: ( ^ = xor)
x1^x2^x9^x10^x11^x12^x15^x17^x18^x19^x21^x23^x24^x26^x29^x30^x32^x37^x38^x39^x40^x44^x47^x48^x49
trebuie sa obtin SoP si PoS.

M-am uitat la codul sursa java al programului BExpred_v0.8:

public TruthTable(BExprTree aTree) {
int varCount = aTree.getVarCount();
this.row_count = two_exp(varCount);
this.col_count = varCount + 1;
this.vars = (ArrayList) aTree.getVars().clone();
this.initializeTT();
boolean bArray[] = new boolean[this.col_count];
int c;
for (int i = 0; i < this.row_count; i++) {
	 c = 0;
	 for (int s = varCount - 1; s >= 0; s--) {
	 bArray[c++] = ((i >> s) & 1) == 1 ? true : false;
	 }
	 bArray[this.col_count - 1] = aTree.evaluate(bArray);
	 this.setRow(i, bArray);
}
}

Problema este row count care este 8388608
dupa evident arunca eroare deoarece incearca sa creeze un array de dimensiune prea mare in this.initializeTT():
this.tt = new boolean[this.row_count][this.col_count];

Din limita mea intelegere creaza true table pentru toate variabilele, ceea ce este foarte ineficient.

Edited by IvanMihai, 04 January 2020 - 20:33.

inca nu-l vad pe maccip pe subiect, o sa fie extrem de pasionat de problema deschisa de tine.

sigur are altceva de facut altfel asta e genul de problema care il atrage enorm

n-input xor este adevarat daca are un numar impar de intrari 1.

MarianG, on 04 ianuarie 2020 - 20:48, said:

Stii cumva un mod matematic de a reprezenta asta?

BExpred v0.8 genereaza asta:

x1 ^ x2 =
(X1 + X2)*(!X1 + !X2)=
(x1 sau x2) si ((x1+1) sau (x2+1))=
(x1==1 sau x2==1) si (x1==0 sau x2==0)

x1 ^ x2 ^ x3 =
(X1 + X2 + X3)*(X1 + !X2 + !X3)*(!X1 + X2 + !X3)*(!X1 + !X2 + X3)
(x1==1 sau x2==1 sau x3==1) si (x1==1 sau x2==0 sau x3==0) si (X1==0 sau x2==1 sau x3==0)...

x1 ^ x2 ^ x3 ^ x4 =
(X1 + X2 + X3 + X4)*(X1 + X2 + !X3 + !X4)*(X1 + !X2 + X3 + !X4)*(X1 + !X2 + !X3 + X4)*(!X1 + X2 + X3 + !X4)*(!X1 + X2 + !X3 + X4)*(!X1 + !X2 + X3 + X4)*(!X1 + !X2 + !X3 + !X4)

x1 ^ x2 ^ x3 ^ x4 ^ x5 =
(X1 + X2 + X3 + X4 + X5)*(X1 + X2 + X3 + !X4 + !X5)*(X1 + X2 + !X3 + X4 + !X5)*(X1 + X2 + !X3 + !X4 + X5)*(X1 + !X2 + X3 + X4 + !X5)*(X1 + !X2 + X3 + !X4 + X5)*(X1 + !X2 + !X3 + X4 + X5)*(!X1 + X2 + X3 + X4 + !X5)*(!X1 + X2 + X3 + !X4 + X5)*(!X1 + X2 + !X3 + X4 + X5)*(!X1 + !X2 + X3 + X4 + X5)*(X1 + !X2 + !X3 + !X4 + !X5)*(!X1 + X2 + !X3 + !X4 + !X5)*(!X1 + !X2 + X3 + !X4 + !X5)*(!X1 + !X2 + !X3 + X4 + !X5)*(!X1 + !X2 + !X3 + !X4 + X5)

este evident o complicare nu o simplificare.

Referitor la true table: din moment ce avem 50 bits asta inseamna 2 la puterea 50 combinatii, ceea ce este mult prea mult pentru a fi reprezentat!

Tu vrei sa afisesi tot tabloul ? Si sa dezvolti intreaga formula in AND OR NOR?

Asa ceva cauti? https://pdfs.semanti...528c6142c53.pdf

 POS.png   11.43K   8 downloads

@dani.user: Exact. Daca as gasii si ceva implementari ar fi bine.

Am gasit programul din document:
https://github.com/berkeley-abc/abc
din pacate este doar pentru Linux.

Edited by MarianG, 05 January 2020 - 15:24.

Am mai gasit niste documente:
http://www.cs.cmu.ed...inimization.pdf

https://www.allabout...xterm-solution/

espresso-ab - tot doar pentru linux,

Simple Solver, dar ar limita de 32 variabile, plus dureaza foarte mult:
https://www.softpedi...le-Solver.shtml

https://en.wikipedia...cal_normal_form

https://stackoverflo...0-variables-wit

https://codereview.s...emory-footprint

https://github.com/y...boolean-algebra

Deci in C++ putem stoca un bit ca bit => de 8 ori mai putin decat un byte si decat ce putem face in Java.
Afisarea Truth Table este tot problematica, plus nu stiu inca de viteza de executie.

Ce ti se cere defapt? Daca e atat de cercetata tema ma gandesc ca nu-i usor/rapid sa obtii un optim.

IvanMihai, on 05 ianuarie 2020 - 20:13, said:

Poti si in java.

IvanMihai, on 05 ianuarie 2020 - 20:13, said:

si chiar vrei sa afisezi un tablou de 2⁵⁰ de elemente ?

Edited by MarianG, 05 January 2020 - 21:04.

https://electronics....-convert-an-expression-from-sop-to-pos-and-back-in-boolean-algebra/22766
https://electronics....the-truth-table

Cel mai bine este explicat aici:
https://pediaa.com/w...en-sop-and-pos/

Deci pentru Sum of Products este utilizat Minterms, si trebuie ca expresia sa fie 1 (true)!
in schimb pentru Product of Sums este utilizat Maxterm, si trebuie ca expresia sa fie 0 (false).

Edited by IvanMihai, 06 January 2020 - 21:38.