Timeline for Systems of equations in Boolean Algebra
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 21, 2014 at 2:12 | vote | accept | Philippe Gaucher | ||
| Nov 20, 2014 at 18:43 | comment | added | François G. Dorais | This Wikipedia entry might clarify your terminological issues: en.wikipedia.org/wiki/Boolean_ring | |
| Nov 20, 2014 at 10:57 | history | edited | Philippe Gaucher | CC BY-SA 3.0 |
edited body
|
| Nov 20, 2014 at 10:52 | answer | added | Benjamin Steinberg | timeline score: 5 | |
| Nov 20, 2014 at 10:51 | comment | added | Philippe Gaucher | $(a_{ij}) (x_k) = (b_l)$, with $1\leq i\leq m, 1\leq j \leq n, 1\leq k \leq n$ and $1\leq l \leq m$. The $\cup$ playing the role of the addition. the vectors $(x_k)$ and $(b_l)$ are column vectors. | |
| Nov 20, 2014 at 10:48 | comment | added | Benjamin Steinberg | Are you multiplying a matrix times a row vector or a column vector? | |
| Nov 20, 2014 at 10:40 | comment | added | Philippe Gaucher | Yes I have an application from $\mathbb{B}^n$ to $\mathbb{B}^m$, where $\mathbb{B}$ is the $2$-element Boolean algebra and I need a necessary and sufficient condition for this map to be one-to-one. | |
| Nov 20, 2014 at 10:34 | comment | added | Benjamin Steinberg | From your question you seem to be using row vectors. I think you have injective iff m\leq n and that you can get a permutation matrix by deleting n-m columns. | |
| Nov 20, 2014 at 10:33 | comment | added | Philippe Gaucher | @BenjaminSteinberg Indeed, it is a system of equations in a semiring. | |
| Nov 20, 2014 at 10:29 | comment | added | Benjamin Steinberg | Solving boolean linear systems is different than working over $F_2$. Only the semiring structure is relevant. A boolean matrix doesn't preserve xor. For example if n=m the only the permutation matrices are 1:1. Over $F_2$ there are more choices. | |
| Nov 20, 2014 at 10:27 | history | edited | Philippe Gaucher | CC BY-SA 3.0 |
deleted 11 characters in body
|
| Nov 20, 2014 at 10:26 | comment | added | Philippe Gaucher | @AlexDegtyarev : a mistake from me indeed; I was wrongly interpreting "xor" as the disjoint union. With $A=\{a,b\}$ and $B=\{b,c\}$, I had $A\sqcup B=\{a,b_1,b_2,c\}$ which is of course not a subset of $\{a,b,c\}$. I edit the question one more time. | |
| Nov 20, 2014 at 10:22 | comment | added | Philippe Gaucher | It is not a numerical system of equations (I cannot take a computer and ask it to solve it), but I understand what you mean. A round trip between the 2-element Boolean algebra and $\mathbb{F}_2$ could help. Anyway, any reference about the subject is welcome. | |
| Nov 20, 2014 at 10:21 | comment | added | Alex Degtyarev | Accidentally, I think your $x+y=xy'\cup x'y$ is "xor" (symmetric difference) for sets. But for just $0$, $1$ it's much simpler, as you can easily see from the truth tables. Anyway, this is just a suggestion, to use the kettle principle. | |
| Nov 20, 2014 at 10:16 | comment | added | Alex Degtyarev | That's exactly my question: on the one hand, all Boolean operations can be interpreted in terms of "and" and "xor"; on the other hand, the latter are merely the operations in the field $\Bbb F_2$, hence, one can apply college linear algebra to your problem. Then, if absolutely necessary, the obvious answer (the matrix has appropriate rank, or nullity is zero, or, in the square case, $\det\ne0$, etc.) can be translated back to "and" and "or". | |
| Nov 20, 2014 at 10:07 | history | edited | Philippe Gaucher | CC BY-SA 3.0 |
added 827 characters in body
|
| Nov 20, 2014 at 9:46 | comment | added | Philippe Gaucher | Probably because I am using the terminology in a wrong way: I don't know almost anything in Boolean algebra. I use "or", union and not "xor", for the addition. For me $1+1=1$, and not $0$. | |
| Nov 20, 2014 at 9:24 | comment | added | Alex Degtyarev | I may be mistaken, but why do you insist on calling this a Boolean algebra? Why not to stick to and and xor and just do usual linear algebra over $\Bbb F_2$. | |
| Nov 20, 2014 at 9:07 | history | edited | Philippe Gaucher | CC BY-SA 3.0 |
deleted 1 character in body
|
| Nov 20, 2014 at 9:01 | history | asked | Philippe Gaucher | CC BY-SA 3.0 |