3 Rollback to Revision 1
source | link

D.W. handled the other cases, so I'll handle the case of AND-of-XORs, but first I'll show how the other cases are elaborated. For the XOR-of-ANDs, we remark that $$f(x_1,\dots,x_n) = g(x_1,\dots,x_{n-1})\oplus h(x_1,\dots,x_{n-1})\land x_n$$ with $g$ and $h$ defined as

$$ \begin{array}{rl} g(x_1,\dots,x_{n-1}) & = & f(x_1,\dots,x_{n-1},0) \$$ g(x_1,\dots,x_{n-1}) = f(x_1,\dots,x_{n-1},0) $$

h(x_1,\dots,x_{n-1}) & = & f(x_1,\dots,x_{n-1},0)\oplus f(x_1,\dots,x_{n-1},1) \end{array} $$$$ h(x_1,\dots,x_{n-1}) = f(x_1,\dots,x_{n-1},0)\oplus f(x_1,\dots,x_{n-1},1) $$

applying this recursively and simplifying the result gives you the XOR-of-AND representation. A similar decomposition is used for then OR-of-ANDs:

$$f(x_1,\dots,x_n) = (f(x_1,\dots,x_{n-1},0) \land \bar x_n) \lor (f(x_1,\dots,x_{n-1},1) \land x_n)$$

And applying De Morgan's law to that give us the OR-of-ANDs:

$$\overline{f(x_1,\dots,x_n)} = (\overline{f(x_1,\dots,x_{n-1},0)} \lor x_n) \land (\overline{f(x_1,\dots,x_{n-1},1)} \lor \bar x_n)$$

in other words:

$$f(x_1,\dots,x_n) = (f(x_1,\dots,x_{n-1},0) \lor x_n) \land (f(x_1,\dots,x_{n-1},1) \lor \bar x_n)$$

You can not decompose an arbitrary function as a AND-of-XORs or a OR-of-XORs (applying De Morgan's law show that if you have one you have the other), even when adding inversers at arbitrary places. It is easy, if somewhat tedious, to convince yourself of that by trying to do so for the 3-variable function $f(x,y,z)=((x \land y) \land \bar z) \lor ((x \lor y) \land z)$ and looking at the truth tables for the six one-variable functions $x,y,z,\bar x, \bar y, \bar z$, the six unique two-variable one ($x \oplus y, x \oplus z, x \oplus z$ and their negation), the three-variable function $x\oplus y \oplus z$ and its negation, and see that you can't build the desired one (only the constant 1 has 1 in all the desired places and to build a function by combining sub-functions with ANDs, all the sub-functions must have 1 at the desired positions in their truth table).

A reference: D. Knuth, The Art of Computer Programming, volume 4A, Combinational Algorithms part 1.

D.W. handled the other cases, so I'll handle the case of AND-of-XORs, but first I'll show how the other cases are elaborated. For the XOR-of-ANDs, we remark that $$f(x_1,\dots,x_n) = g(x_1,\dots,x_{n-1})\oplus h(x_1,\dots,x_{n-1})\land x_n$$ with $g$ and $h$ defined as

$$ \begin{array}{rl} g(x_1,\dots,x_{n-1}) & = & f(x_1,\dots,x_{n-1},0) \

h(x_1,\dots,x_{n-1}) & = & f(x_1,\dots,x_{n-1},0)\oplus f(x_1,\dots,x_{n-1},1) \end{array} $$

applying this recursively and simplifying the result gives you the XOR-of-AND representation. A similar decomposition is used for then OR-of-ANDs:

$$f(x_1,\dots,x_n) = (f(x_1,\dots,x_{n-1},0) \land \bar x_n) \lor (f(x_1,\dots,x_{n-1},1) \land x_n)$$

And applying De Morgan's law to that give us the OR-of-ANDs:

$$\overline{f(x_1,\dots,x_n)} = (\overline{f(x_1,\dots,x_{n-1},0)} \lor x_n) \land (\overline{f(x_1,\dots,x_{n-1},1)} \lor \bar x_n)$$

in other words:

$$f(x_1,\dots,x_n) = (f(x_1,\dots,x_{n-1},0) \lor x_n) \land (f(x_1,\dots,x_{n-1},1) \lor \bar x_n)$$

You can not decompose an arbitrary function as a AND-of-XORs or a OR-of-XORs (applying De Morgan's law show that if you have one you have the other), even when adding inversers at arbitrary places. It is easy, if somewhat tedious, to convince yourself of that by trying to do so for the 3-variable function $f(x,y,z)=((x \land y) \land \bar z) \lor ((x \lor y) \land z)$ and looking at the truth tables for the six one-variable functions $x,y,z,\bar x, \bar y, \bar z$, the six unique two-variable one ($x \oplus y, x \oplus z, x \oplus z$ and their negation), the three-variable function $x\oplus y \oplus z$ and its negation, and see that you can't build the desired one (only the constant 1 has 1 in all the desired places and to build a function by combining sub-functions with ANDs, all the sub-functions must have 1 at the desired positions in their truth table).

A reference: D. Knuth, The Art of Computer Programming, volume 4A, Combinational Algorithms part 1.

D.W. handled the other cases, so I'll handle the case of AND-of-XORs, but first I'll show how the other cases are elaborated. For the XOR-of-ANDs, we remark that $$f(x_1,\dots,x_n) = g(x_1,\dots,x_{n-1})\oplus h(x_1,\dots,x_{n-1})\land x_n$$ with $g$ and $h$ defined as

$$ g(x_1,\dots,x_{n-1}) = f(x_1,\dots,x_{n-1},0) $$

$$ h(x_1,\dots,x_{n-1}) = f(x_1,\dots,x_{n-1},0)\oplus f(x_1,\dots,x_{n-1},1) $$

applying this recursively and simplifying the result gives you the XOR-of-AND representation. A similar decomposition is used for then OR-of-ANDs:

$$f(x_1,\dots,x_n) = (f(x_1,\dots,x_{n-1},0) \land \bar x_n) \lor (f(x_1,\dots,x_{n-1},1) \land x_n)$$

And applying De Morgan's law to that give us the OR-of-ANDs:

$$\overline{f(x_1,\dots,x_n)} = (\overline{f(x_1,\dots,x_{n-1},0)} \lor x_n) \land (\overline{f(x_1,\dots,x_{n-1},1)} \lor \bar x_n)$$

in other words:

$$f(x_1,\dots,x_n) = (f(x_1,\dots,x_{n-1},0) \lor x_n) \land (f(x_1,\dots,x_{n-1},1) \lor \bar x_n)$$

You can not decompose an arbitrary function as a AND-of-XORs or a OR-of-XORs (applying De Morgan's law show that if you have one you have the other), even when adding inversers at arbitrary places. It is easy, if somewhat tedious, to convince yourself of that by trying to do so for the 3-variable function $f(x,y,z)=((x \land y) \land \bar z) \lor ((x \lor y) \land z)$ and looking at the truth tables for the six one-variable functions $x,y,z,\bar x, \bar y, \bar z$, the six unique two-variable one ($x \oplus y, x \oplus z, x \oplus z$ and their negation), the three-variable function $x\oplus y \oplus z$ and its negation, and see that you can't build the desired one (only the constant 1 has 1 in all the desired places and to build a function by combining sub-functions with ANDs, all the sub-functions must have 1 at the desired positions in their truth table).

A reference: D. Knuth, The Art of Computer Programming, volume 4A, Combinational Algorithms part 1.

2 added 12 characters in body
source | link

D.W. handled the other cases, so I'll handle the case of AND-of-XORs, but first I'll show how the other cases are elaborated. For the XOR-of-ANDs, we remark that $$f(x_1,\dots,x_n) = g(x_1,\dots,x_{n-1})\oplus h(x_1,\dots,x_{n-1})\land x_n$$ with $g$ and $h$ defined as

$$ g(x_1,\dots,x_{n-1}) = f(x_1,\dots,x_{n-1},0) $$ $$ \begin{array}{rl} g(x_1,\dots,x_{n-1}) & = & f(x_1,\dots,x_{n-1},0) \

$$ h(x_1,\dots,x_{n-1}) = f(x_1,\dots,x_{n-1},0)\oplus f(x_1,\dots,x_{n-1},1) $$ h(x_1,\dots,x_{n-1}) & = & f(x_1,\dots,x_{n-1},0)\oplus f(x_1,\dots,x_{n-1},1) \end{array} $$

applying this recursively and simplifying the result gives you the XOR-of-AND representation. A similar decomposition is used for then OR-of-ANDs:

$$f(x_1,\dots,x_n) = (f(x_1,\dots,x_{n-1},0) \land \bar x_n) \lor (f(x_1,\dots,x_{n-1},1) \land x_n)$$

And applying De Morgan's law to that give us the OR-of-ANDs:

$$\overline{f(x_1,\dots,x_n)} = (\overline{f(x_1,\dots,x_{n-1},0)} \lor x_n) \land (\overline{f(x_1,\dots,x_{n-1},1)} \lor \bar x_n)$$

in other words:

$$f(x_1,\dots,x_n) = (f(x_1,\dots,x_{n-1},0) \lor x_n) \land (f(x_1,\dots,x_{n-1},1) \lor \bar x_n)$$

You can not decompose an arbitrary function as a AND-of-XORs or a OR-of-XORs (applying De Morgan's law show that if you have one you have the other), even when adding inversers at arbitrary places. It is easy, if somewhat tedious, to convince yourself of that by trying to do so for the 3-variable function $f(x,y,z)=((x \land y) \land \bar z) \lor ((x \lor y) \land z)$ and looking at the truth tables for the six one-variable functions $x,y,z,\bar x, \bar y, \bar z$, the six unique two-variable one ($x \oplus y, x \oplus z, x \oplus z$ and their negation), the three-variable function $x\oplus y \oplus z$ and its negation, and see that you can't build the desired one (only the constant 1 has 1 in all the desired places and to build a function by combining sub-functions with ANDs, all the sub-functions must have 1 at the desired positions in their truth table).

A reference: D. Knuth, The Art of Computer Programming, volume 4A, Combinational Algorithms part 1.

D.W. handled the other cases, so I'll handle the case of AND-of-XORs, but first I'll show how the other cases are elaborated. For the XOR-of-ANDs, we remark that $$f(x_1,\dots,x_n) = g(x_1,\dots,x_{n-1})\oplus h(x_1,\dots,x_{n-1})\land x_n$$ with $g$ and $h$ defined as

$$ g(x_1,\dots,x_{n-1}) = f(x_1,\dots,x_{n-1},0) $$

$$ h(x_1,\dots,x_{n-1}) = f(x_1,\dots,x_{n-1},0)\oplus f(x_1,\dots,x_{n-1},1) $$

applying this recursively and simplifying the result gives you the XOR-of-AND representation. A similar decomposition is used for then OR-of-ANDs:

$$f(x_1,\dots,x_n) = (f(x_1,\dots,x_{n-1},0) \land \bar x_n) \lor (f(x_1,\dots,x_{n-1},1) \land x_n)$$

And applying De Morgan's law to that give us the OR-of-ANDs:

$$\overline{f(x_1,\dots,x_n)} = (\overline{f(x_1,\dots,x_{n-1},0)} \lor x_n) \land (\overline{f(x_1,\dots,x_{n-1},1)} \lor \bar x_n)$$

in other words:

$$f(x_1,\dots,x_n) = (f(x_1,\dots,x_{n-1},0) \lor x_n) \land (f(x_1,\dots,x_{n-1},1) \lor \bar x_n)$$

You can not decompose an arbitrary function as a AND-of-XORs or a OR-of-XORs (applying De Morgan's law show that if you have one you have the other), even when adding inversers at arbitrary places. It is easy, if somewhat tedious, to convince yourself of that by trying to do so for the 3-variable function $f(x,y,z)=((x \land y) \land \bar z) \lor ((x \lor y) \land z)$ and looking at the truth tables for the six one-variable functions $x,y,z,\bar x, \bar y, \bar z$, the six unique two-variable one ($x \oplus y, x \oplus z, x \oplus z$ and their negation), the three-variable function $x\oplus y \oplus z$ and its negation, and see that you can't build the desired one (only the constant 1 has 1 in all the desired places and to build a function by combining sub-functions with ANDs, all the sub-functions must have 1 at the desired positions in their truth table).

A reference: D. Knuth, The Art of Computer Programming, volume 4A, Combinational Algorithms part 1.

D.W. handled the other cases, so I'll handle the case of AND-of-XORs, but first I'll show how the other cases are elaborated. For the XOR-of-ANDs, we remark that $$f(x_1,\dots,x_n) = g(x_1,\dots,x_{n-1})\oplus h(x_1,\dots,x_{n-1})\land x_n$$ with $g$ and $h$ defined as

$$ \begin{array}{rl} g(x_1,\dots,x_{n-1}) & = & f(x_1,\dots,x_{n-1},0) \

h(x_1,\dots,x_{n-1}) & = & f(x_1,\dots,x_{n-1},0)\oplus f(x_1,\dots,x_{n-1},1) \end{array} $$

applying this recursively and simplifying the result gives you the XOR-of-AND representation. A similar decomposition is used for then OR-of-ANDs:

$$f(x_1,\dots,x_n) = (f(x_1,\dots,x_{n-1},0) \land \bar x_n) \lor (f(x_1,\dots,x_{n-1},1) \land x_n)$$

And applying De Morgan's law to that give us the OR-of-ANDs:

$$\overline{f(x_1,\dots,x_n)} = (\overline{f(x_1,\dots,x_{n-1},0)} \lor x_n) \land (\overline{f(x_1,\dots,x_{n-1},1)} \lor \bar x_n)$$

in other words:

$$f(x_1,\dots,x_n) = (f(x_1,\dots,x_{n-1},0) \lor x_n) \land (f(x_1,\dots,x_{n-1},1) \lor \bar x_n)$$

You can not decompose an arbitrary function as a AND-of-XORs or a OR-of-XORs (applying De Morgan's law show that if you have one you have the other), even when adding inversers at arbitrary places. It is easy, if somewhat tedious, to convince yourself of that by trying to do so for the 3-variable function $f(x,y,z)=((x \land y) \land \bar z) \lor ((x \lor y) \land z)$ and looking at the truth tables for the six one-variable functions $x,y,z,\bar x, \bar y, \bar z$, the six unique two-variable one ($x \oplus y, x \oplus z, x \oplus z$ and their negation), the three-variable function $x\oplus y \oplus z$ and its negation, and see that you can't build the desired one (only the constant 1 has 1 in all the desired places and to build a function by combining sub-functions with ANDs, all the sub-functions must have 1 at the desired positions in their truth table).

A reference: D. Knuth, The Art of Computer Programming, volume 4A, Combinational Algorithms part 1.

1
source | link

D.W. handled the other cases, so I'll handle the case of AND-of-XORs, but first I'll show how the other cases are elaborated. For the XOR-of-ANDs, we remark that $$f(x_1,\dots,x_n) = g(x_1,\dots,x_{n-1})\oplus h(x_1,\dots,x_{n-1})\land x_n$$ with $g$ and $h$ defined as

$$ g(x_1,\dots,x_{n-1}) = f(x_1,\dots,x_{n-1},0) $$

$$ h(x_1,\dots,x_{n-1}) = f(x_1,\dots,x_{n-1},0)\oplus f(x_1,\dots,x_{n-1},1) $$

applying this recursively and simplifying the result gives you the XOR-of-AND representation. A similar decomposition is used for then OR-of-ANDs:

$$f(x_1,\dots,x_n) = (f(x_1,\dots,x_{n-1},0) \land \bar x_n) \lor (f(x_1,\dots,x_{n-1},1) \land x_n)$$

And applying De Morgan's law to that give us the OR-of-ANDs:

$$\overline{f(x_1,\dots,x_n)} = (\overline{f(x_1,\dots,x_{n-1},0)} \lor x_n) \land (\overline{f(x_1,\dots,x_{n-1},1)} \lor \bar x_n)$$

in other words:

$$f(x_1,\dots,x_n) = (f(x_1,\dots,x_{n-1},0) \lor x_n) \land (f(x_1,\dots,x_{n-1},1) \lor \bar x_n)$$

You can not decompose an arbitrary function as a AND-of-XORs or a OR-of-XORs (applying De Morgan's law show that if you have one you have the other), even when adding inversers at arbitrary places. It is easy, if somewhat tedious, to convince yourself of that by trying to do so for the 3-variable function $f(x,y,z)=((x \land y) \land \bar z) \lor ((x \lor y) \land z)$ and looking at the truth tables for the six one-variable functions $x,y,z,\bar x, \bar y, \bar z$, the six unique two-variable one ($x \oplus y, x \oplus z, x \oplus z$ and their negation), the three-variable function $x\oplus y \oplus z$ and its negation, and see that you can't build the desired one (only the constant 1 has 1 in all the desired places and to build a function by combining sub-functions with ANDs, all the sub-functions must have 1 at the desired positions in their truth table).

A reference: D. Knuth, The Art of Computer Programming, volume 4A, Combinational Algorithms part 1.