Is it possible to encode logical expression and interpret it with SQL?
Using disjunctive normal form (DNF) representation. The following 3 tables arrangement seems to solve the problem (NB: using better names for tables, not same as in the question):

&gt; select * from F;
+------+------+
| f1   | f2   |
+------+------+
|    1 |    1 |
|    1 |    2 |
+------+------+

&gt; select * from C;
+------+------+
| c1   | c2   |
+------+------+
|    1 | A    |
|    1 | B    |
|    2 | C    |
+------+------+

&gt; select * from V;
+------+------+
| v1   | v2   |
+------+------+
| A    |    0 |
| B    |    0 |
| C    |    1 |
+------+------+


Where F is a table for formulae, mapping from formula number to a table of conjuncts (C), which has a pointers into table of variables (V). The formula encoded here is (A AND B) OR C.

Doing conjunction is simply a matter of applying min() and disjunction is done by max().

Evaluating formula (number 1 in the example above) can be done by the following query:

&gt; select max(A.v) as result from F, (select min(v2) as v, c1 from C, V 
                                     where c2 = v1 group by c1) as A 
  where c1 = f2 and f1 = 1;
+--------+
| result |
+--------+
|      1 |
+--------+


The above approach is a bit simplified - NOT is not possible to express, but it is easy to add it as an extra boolean column of table C and XORing it with the variable value.