Geben Sie für jedes n eine Formel ψn an...

Question

Aufgabe:

Geben Sie für jedes n eine Formel ψ_n (x₀, . . . , x_n-1) an, sodass I genau dann ein Modell von
_ψn ist, wenn |{i : I(X_i) = 1}| durch drei teilbar ist.

Answer 1

Überlege dir zunächst eine Formel \(\varphi_{2,4}(x_0,x_1,x_2,x_3)\), die genau dann wahr ist, wenn genau zwei der vier Variablen mit 1 belegt wurden.

Verallgemeinere deine Überlegungen zu einer Formel \(\varphi_{m,n}\left(x_0,\dots,x_{n-1}\right)\), die genau dann wahr ist, wenn genau \(m\) der \(n\) Variablen mit 1 belegt wurden.

Dann ist

        \(\psi_n\left(x_0,\dots,x_{n-1}\right) = \bigvee\limits_{k=0}^{\left\lfloor\frac{n}{3}\right\rfloor}\varphi_{3k,n}\left(x_0,\dots,x_{n-1}\right)\).