Is there any way to solve a system of linear equations with both the coefficients and variables coming from $\{0,1\}$ but where addition is considered over the non-negative integers, not $\mathbb{F}_2$?
I have considered trying to solve such systems over $\mathbb{Q}$ and then interpreting the solution in that case: If it is inconsistent then there is also no solution over $\{0,1\}$. If there is a unique solution, then it is easy to check if that is a solution to my problem as well. However, I don't know how to handle the case of infinitely many solutions having free variables. Any suggestions? Thanks.
The unknowns $(x_i)_{i\leq n}$ are in $\{0,1\}$ ; then the number of solutions is finite...
If I understand correctly your question, then one has a system $Ax=b$ where $A=[a_{i,j}]\in M_{p,n}(\{0,1\})$, $b=[b_i]$ with $b_i\in \{0,1\}$ are given, $x$ is as $b$ but is unknown.
We solve the system in $\mathbb{Z}/2\mathbb{Z}$ (with Gauss) ; we assume that there is more than one solution. Then the result is in the form : for every $i\leq k$, $x_i=f_i(x_{k+1},\cdots,x_n)$ where $f_i$ is an affine function and $x_{k+1},\cdots,x_n$ are arbitrary, that is, we obtain $2^{n-k}$ candidates. If $2^{n-k}$ is not a too great number, then we can conclude by brute force. Else we use the following fact: for every $i\leq p$, $cardinality(\{j;a_{i,j}x_j\not=0\})$ is $0$ or $1$.