Beweiser-Gegenspieler-Prinzip Logik & Quantoren

Question

Hey, Ich verstehe nicht wie ich folgende Aussagen durch ein Beweiser-Gegenspieler Argument begründen soll.

Aufgabe:

Betrachten Sie das Prädikat Q(x,y,z) : x + y > z mit drei Variablen über dem Universum U = N.

Bestimmen Sie die Wahrheitswerte der folgenden vier Aussagen. Begründen Sie wahre Aussagen durch ein Beweiser-Gegenspieler Argument und falsche Aussagen durch ein Beweiser-Gegenspieler Argument für die negierte Aussage.


(a) ∀z∃y∀x : Q(x, y, z)
(b) ∀z∃y∀x : Q(x,y,z)
(c) ∀z∀y∃x: Q(x, y, z)
(d) ∀z∃y∃x: Q(x, y, z) ∧ Q (x, y, z)

Danke im Voraus

Answer 1

Der Beweiser wählt die Werte für existenzquantifizierte Variablen.

Der Gegenspieler wählt die Werte für allquantifizierte Variablen.

In der Reihenfolge, wie die Quantoren in der Formel auftreten.

(a) ∀z∃y∀x : Q(x, y, z)

Die Aussage ist wahr.

Sei z₀ ∈ ℕ (Gegenspieler).

Sei y₀ = z₀+1 (Beweiser). Insbesondere darf der Beweiser die Wahl des Gegenspielers in seine Wahl einfließen lassen, weil ∃y nach ∀z kommt.

Sei x₀ ∈ ℕ (Gegenspieler).

Dann ist

        x ₀ + y₀ = x₀ + z₀ + 1 > z₀

wegen x₀ ≥ 0 und 1 ≥ 0. Also hat der Beweiser gewonnen.

(b) ∀z∃y∀x : Q(x,y,z)

Das wird genauso wie bei (a) gemacht. Wortwörtlich genauso. Ohne irgendwelche Änderung. Weil das die selbe Formel wie bei (a) ist.

(c) ∀z∀y∃x: Q(x, y, z)

Die Aussage ist falsch. Negation ist

        ∃z∃y∀x: x + y ≤ z.

Sei z₀ = 1 (Beweiser),

Sei y₀ = 2 (Beweiser),

Sei x₀ ∈ ℕ (Gegenspieler),