1
vote
Complexity of satisfiability for relational logic on the booleans
Nothing much changes. Every relation $R(x_1,\dots,x_n)$ is equivalent to $\exists t_1,\dots,t_m . \varphi(x_1,\dots,x_n,t_1,\dots,t_m)$ for some fresh variables $t_1,\dots,t_m$ (see the Tseitin ...
D.W.♦
- 156k
1
vote
Accepted
Is there a model for the given logical formula, and if not, why?
Set all variables to false, that way each implication has a false left-hand-side and thus it's satisfied.
- 1,188
1
vote
DFA for even concatenation of strings from a language
The language you are considering is $(W^2)^*$, so you could combine standard constructions for the concatenation and the star operation.
- 6,014
Only top scored, non community-wiki answers of a minimum length are eligible