MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

($a_1$ OR $a_2$ OR $a_3$) AND ($b_1$ OR $b_2$ OR $b_3$) AND ($c_1$ OR $c_2$ OR $c_3$) AND ...
(NOT $A_1$ OR $a_2$ OR $a_3$) AND ($A_1$ OR $a_1$) AND (NOT $B_1$ OR $b_2$ OR $b_3$) AND ($B_1$ OR $b_1$) AND (NOT $C_1$ OR $c_2$ OR $c_3$) AND ($C_1$ OR $C_1$) c_1$) AND ... is. 1 I think 3SAT can be reduced to your problem, since ($a_1$OR$a_2$OR$a_3$) AND ($b_1$OR$b_2$OR$b_3$) AND ($c_1$OR$c_2$OR$c_3$) AND ... is satisfiable iff (NOT$A_1$OR$a_2$OR$a_3$) AND ($A_1$OR$a_1$) AND (NOT$B_1$OR$b_2$OR$b_3$) AND ($B_1$OR$b_1$) AND (NOT$C_1$OR$c_2$OR$c_3$) AND ($C_1$OR$C_1\$) AND ...