Definition der KgV und Primzahlen mit Prädikatenlogik?
Hallo, wir haben hier ein Problem mit unserer Matheaufgabe. Es sind zwei verschiedene Aufgaben, wir sollen einmal das KgV und einmal eine Primzahl in Prädikatenlogik definieren aber da gibt es ein paar Denkprobleme. Bei der KgV Sache haben wir bereits den Anfang aber sind uns nicht sicher ob es richtig ist und können die Zeichen hier nicht einfügen. Danke schonmal und bitte rettet uns das Studium LG aus Dortmund
1 Antwort
P(x,y,z) soll unter Interpretation in |N genau dann gelten, wenn z=kgV(x,y).
Dann überleg dir. In |N gilt:
z=kgV(x,y) gdw.
x|z & y|z &
(für alle w) (w habe diese Eigenschaft ==> z|w)
Nochmals genauer (ich war am Handy als ich dies schrieb).
Es kommt auf deine Sprache an. Ich gehe von einer Sprache der Signatur {·, …} aus, wobei · für Multiplikation steht.
Definiere
T(x,y) :≣ (∃z) x·z=y
wobei z eine beliebig gewählte Variable
fremd zu {x,y}, d. h. die Wahl häng von x,y ab.
Die Formel lässt sich in ℕ interpretieren als:
(ℕ,·) ⊨ T [n,m] ⟺ ∃k∈ℕ: nk=m
⟺ n|m
Dann
Definiere
K(x,y,z) :≣ T(x,z) ⋀ T(y,z)
⋀ (∀w)[(T(x,w)⋀T(y,w)) —→ T(z,w)]
wobei w eine beliebig gewählte Variable
fremd zu {x,y,z}.
Die Formel lässt sich in ℕ interpretieren als:
(ℕ,·) ⊨ K [a,b,c] ⟺ (ℕ,·) ⊨ T [a,c]
und (ℕ,·) ⊨ T [b,c]
und ∀u∈ℕ:
wenn (ℕ,·) ⊨ T [a,u]
& (ℕ,·) ⊨ T [b,u]
dann
(ℕ,·) ⊨ T [c,u]
⟺ a|c & b|c
und ∀u∈ℕ:
wenn a|u & b|u
dann c|u
⟺ c=Min{u∈ℕ : a|u & b|u}
⟺ c=kgV(a,b).
Darum ist die Formel K(x,y,z) als eine Kodierung von KGV.
Für Primzahl:
P(x) :≣ (∀y)(T(y,x) —→ (y=S0 ⋁ y=x))
⋀ ¬(x=0) ⋀ ¬(x=S0)
Hier gehe ich von der Sprache {·,S,0,...} aus, wobei S als Nachfolger (‘successor’) interpretiert werden soll und 0 als die Null.