Is there any boolean algebra expression that can not be put into 3SAT?

Question

This seems to me pretty obvious, There is not but I might be leaving a special case. As I see it 1SAT (only one literal per clause) and 2SAT can be easily transformed into 3SAT. An any clause with more than 3 literas has been proven it can be transformed into 3SAT. So maybe the question should be asked as: Do all boolean algebra can be put into SAT? or can we define boolean algebra with ony these operators? AND OR and NOT

Answer 1

No, there is not.

I will not give the full proof but here is the main idea: Write the given formula in a normal form i.e. conjunction of disjunctions. Use induction on the number of variables on an expression. Pick the longest subexpression with n+1 variables, introduce a new variable for some part of subexpression to leave an expression of n variables, add the constraints for the new variable to the formula, repeat the procedure as many times as needed to have a formula where the longest subexpression has n variables.