Given a expression, such as p | !q, how to find the p,q (i.e. p=1, q=1)to make the expression true? Any help is appreciated.

The problem can be solved recursively. A|B is true when A is true and B is anything or B is true and A is anything. A&B is true when both A and B are true. !A is true when A is false. If you parse the expression into a tree it should not be much trouble. I suggest passing around the results using a map.
Another option would be to simply try them all. If you're not going to have many variables, at least..