Problem

(Quelle: „Mathematik für Informatik“, Lehman, Leighton, Meyers, 2018.)

In dieser Aufgabe untersuchen wir prädikatenlogische Formeln, in denen der Diskursbereich liegt$\mathbb{N}$. Zusätzlich zu den logischen Symbolen können die Formeln ternäre Prädikatsymbole enthalten$A$Und$M$, Wo:

$A(k,m,n)$bedeutet$k = m + n$

$M(k,m,n)$bedeutet$k = mn$

Zum Beispiel eine Formel$Zero(n)$bedeutet, dass$n$Null ist, könnte definiert werden als

$Zero(n)=A(n,n,n)$

Definiert haben$Zero$, es ist jetzt in Ordnung, es in nachfolgenden Formeln zu verwenden. Also eine Formel für$Greater(m,n)$Bedeutung$m > n$könnte definiert werden als

$Greater(m,n) = \exists k \left( \neg \left( Zero(k) \right) \wedge A(m,n,k) \right)$

Dies macht es OK zu verwenden$Greater$in nachfolgenden Formeln.

$M(k,m,n)$bedeutet$k = mn$

Schreiben Sie Prädikatformeln, indem Sie nur die zulässigen Prädikate verwenden$A$,$M$die die folgenden Prädikate definieren:

(A)$Equal(m,n)$bedeutet, dass$m = n$.

(B)$One(n)$bedeutet, dass$n = 1$.

(C)$n = i(m \cdot j + k^2)$.

(D)$Prime(p)$Bedeutung$p$ist eine Primzahl.

(e)$Two(n)$bedeutet, dass$n = 2$.

(F)$Even(n)$Bedeutung$n$ist gerade.

(g) (Goldbach-Vermutung) Jede ganze Zahl$n \geq 4$kann als Summe zweier Primzahlen ausgedrückt werden.

(h) (Fermats letzter Satz) Nehmen wir nun an, wir hätten auch

$X(k,m,n)$bedeutet$k = m^n$

Drücken Sie die Behauptung aus, dass es keine positiven ganzzahligen Lösungen der Gleichung gibt:

$x^n + y^n = z^n$

Wenn$n > 2$.

(i) (Twin-Prime-Vermutung) Es gibt unendlich viele Primzahlen, die sich um zwei unterscheiden.

Lösungsversuch

Versuche für jedes Element:

( Hinweis : Da ich Prädikate in jedem Element definiere, kann ich sie in nachfolgenden Elementen wiederverwenden.)

a) Seit$m=n$dann und nur dann, wenn$m \leq n$Und$n \leq m$:

$Equal(m,n) = \left( \neg Greater(m,n) \right) \wedge \left( \neg Greater(n,m) \right)$

b) Jede natürliche Zahl$n$multipliziert mit 1 ist gleich$n$, So:

$One(n) = \forall k \left(M(k,n,k)\right)$

c) Was ich hier versucht habe, ist, den Ausdruck wie folgt aufzuschlüsseln:$n = i \cdot x_1$für einige$x_1$,$x_1 = (x_2 + x_3)$für einige$x_2$und einige$x_3$,$x_2 = (m \cdot j)$für einige$m$und einige$j$, Und$x_3 = k^2$. Der Versuch wird also:

$C(n) = \exists i \exists x_1 \exists x_2 \exists x_3 \exists j \exists k \left(M(n,i,x_1) \wedge A(x_1,x_2,x_3) \wedge M(x_2,m,j) \wedge M(x_3,k,k)\right)$

d) Es gibt zwei Möglichkeiten, die zu funktionieren scheinen:

$Prime(p) = \forall a \forall i (One(a) \rightarrow \left( \neg Equal(i,a) \wedge \neg Equal(i,p) \rightarrow \neg \exists k \left( M(p,i,k) \right) \right)$

$Prime(p) = \forall i \exists a (One(a) \wedge \left( \neg Equal(i,a) \wedge \neg Equal(i,p) \rightarrow \neg \exists k \left( M(p,i,k) \right) \right)$

e) Es gibt zwei Möglichkeiten, an die ich gedacht habe, die für diesen zu funktionieren scheinen, basierend auf der Tatsache, dass 2 = 1 + 1:

$Two(n) = \exists k \left( One(k) \wedge A(n,k,k) \right)$

$Two(n) = \forall k \left( One(k) \rightarrow A(n,k,k) \right)$

F)$Even(n) = \exists a \exists b \left( Two(a) \wedge M(n,a,b) \right)$

Die Idee ist, dass, falls vorhanden$a$und b so dass$a$ist die Zahl 2, und$n = ab$, Dann$n$ist gerade.

G)$\forall n \forall a \left( Four(a) \wedge \left(Greater(n,a) \lor Equal(n,a)\right) \wedge Even(n) \rightarrow \exists p_1p_2\left( Prime(p_1) \wedge Prime(p_2) \wedge A(n,p_1,p_2) \right ) \right)$

H)$\forall n \forall a \left( Two(a) \wedge Greater(n,a) \rightarrow \left( \neg \exists x,y,z,x_n,y_n,z_n \left ( X(x_n,x,n) \wedge X(y_n, y, n) \wedge X(z_n, z, n) \wedge A(z_n,x_n,y_n) \right ) \right ) \right)$

i) Definieren Sie zunächst ein Prädikat, das testet, ob zwei Zahlen$m$Und$n$sind Primzahlzwillinge, indem überprüft wird, ob sie Primzahlen sind und sich um 2 unterscheiden:

$TwinPrime(m,n) = Prime(m) \wedge Prime(n) \wedge \exists t \left( Two(t) \wedge \left( A(q,n,t) \lor A(n,q,t) \right) \right )$

Dann könnte die Vermutung wie folgt ausgedrückt werden:

$\left( \exists n,m \left( TwinPrime(n,m) \right) \right) \wedge (\forall n,m \left( TwinPrime(n,m) \rightarrow \exists q,p \left ( Greater(q,n) \wedge Greater(p,m) \wedge TwinPrime(q,p) \right ) \right ) )$

Als Versuch auszudrücken, dass es unendlich viele Primzahlzwillinge gibt, sage ich zwei Dinge: (1) es gibt zwei Zahlen, die Primzahlzwillinge sind, (2) wenn es zwei Zahlen gibt$m,n$das sind Primzahlzwillinge, dann gibt es zwei Zahlen$p,q$die größer sind als$m,n$und sind auch Primzahlzwillinge.

Könnte jemand bitte überprüfen, ob diese Versuche sinnvoll sind? Vielen Dank im Voraus.