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
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.
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
logic × 981first-order-logic × 130
propositional-logic × 118
complexity-theory × 75
satisfiability × 71
algorithms × 65
boolean-algebra × 60
computability × 45
lambda-calculus × 44
linear-temporal-logic × 43
proof-techniques × 39
type-theory × 39
terminology × 38
programming-languages × 36
reference-request × 29
circuits × 29
model-checking × 29
formal-languages × 28
formal-methods × 25
temporal-logic × 24
hoare-logic × 23
automated-theorem-proving × 23
computer-architecture × 22
proof-assistants × 22
artificial-intelligence × 20