L-Formeln < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Wir betrachten die Sprache [mm] $L=\{0,+,\cdot\}$ [/mm] und die L-Struktur [mm] $\mathcal{N}=\{\mathbb{N},0,+,\cdot\}$.
[/mm]
Geben Sie für jede der folgenden Bedingungen eine entsprechende L-Formel [mm] $\phi(x,y,z)$ [/mm] an (d.h. die Bedingung soll in der Struktur [mm] $\mathcal{N}$ [/mm] genau dann gelten, wenn [mm] $\mathcal{N}\models\phi[\beta]$ [/mm] für alle Belegungen [mm] $\beta$ [/mm] mit [mm] $\beta(x)=m, \beta(y)=n$ [/mm] und [mm] $\beta(z)=l$).
[/mm]
1) m<n
2) m teilt n
3) m, n, l sind paarweise teilerfremd
4) m ist eine Primzahl
5) Es gibt unendlich viele Primzahlzwillinge |
Hallo,
ich habe eine Frage zu dieser Aufgabe.
Für 1) m<n habe ich einfach die Formel
[mm] $\exists a\in\mathbb{N} ((m+a=n)\wedge\neg(a=0))$
[/mm]
angegeben.
Für 2) m teilt n wollte ich es fast analog machen mit
[mm] $\exists a\in\mathbb{N} ((m\cdot a=n)\wedge\neg(m=0))$
[/mm]
Hier frage ich mich jedoch ob das ausreichend ist und ob ich nicht die Formel aus 1) einbringen muss, also ich fordern muss, dass m<n oder m=n gilt und nicht m>n, oder steckt das in obiger Formel bereits drin?
Für 3) habe ich leider noch keinen so richtigen Ansatz gefunden wie ich das am besten in der Gegebenen Struktur machen kann.
Ich muss ja irgendwie ausdrücken, dass "1" der größte gemeinsame Teiler dieser Zahlen ist, ohne das ich die "1" verwenden darf.
Für 4) muss ich irgendwie Ausdrücken können, dass m genau 2 Teiler hat (1 und sich selbst)
Für 5) habe ich noch keine so rechte Idee. Die Unendlichkeit auszudrücken sollte noch recht einfach sein, indem ich einfach sage, dass für jede natürliche Zahl n solche Primzahlzwillinge [mm] $p_1, p_2$ [/mm] existieren mit [mm] $n
Dann muss ich die Formel aus 4) einbauen und am schwierigsten sollte es sein irgendwie auszudrücken, dass die Differenz dieser Primzahlzwillinge 2 ist.
Denn ich habe ja weder eine Differenz (was nicht so gravierend ist) noch die Zahl 2 (was schon schlimmer ist, denke ich).
Grundsätzlich bauen die Formeln ja jeweils aufeinander auf.
Über Anregungen würde ich mich sehr freuen.
Vielen Dank.
(Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:05 Sa 18.04.2015 | | Autor: | hippias |
![[willkommenvh]](/images/smileys/willkommenvh.png "[willkommenvh]")
> Wir betrachten die Sprache [mm]L=\{0,+,\cdot\}[/mm] und die
> L-Struktur [mm]\mathcal{N}=\{\mathbb{N},0,+,\cdot\}[/mm].
> Geben Sie für jede der folgenden Bedingungen eine
> entsprechende L-Formel [mm]\phi(x,y,z)[/mm] an (d.h. die Bedingung
> soll in der Struktur [mm]\mathcal{N}[/mm] genau dann gelten, wenn
> [mm]\mathcal{N}\models\phi[\beta][/mm] für alle Belegungen [mm]\beta[/mm]
> mit [mm]\beta(x)=m, \beta(y)=n[/mm] und [mm]\beta(z)=l[/mm]).
>
> 1) m<n
>
> 2) m teilt n
>
> 3) m, n, l sind paarweise teilerfremd
>
> 4) m ist eine Primzahl
>
> 5) Es gibt unendlich viele Primzahlzwillinge
>
> Hallo,
>
> ich habe eine Frage zu dieser Aufgabe.
>
> Für 1) m<n habe ich einfach die Formel
>
> [mm]\exists a\in\mathbb{N} ((m+a=n)\wedge\neg(a=0))[/mm]
>
> angegeben.
Das ist inhaltlich richtig. Beachte aber, dass Du eine $L$-Sprache hast. Du hast eine Mischung aus formaler Sprache und Metasprache verwendet; genauer: die von Dir angegebene Symbolreihe ist kein Element der Sprache mit der Signatur $L$.
>
> Für 2) m teilt n wollte ich es fast analog machen mit
>
> [mm]\exists a\in\mathbb{N} ((m\cdot a=n)\wedge\neg(m=0))[/mm]
>
> Hier frage ich mich jedoch ob das ausreichend ist und ob
> ich nicht die Formel aus 1) einbringen muss, also ich
> fordern muss, dass m<n oder m=n gilt und nicht m>n, oder
> steckt das in obiger Formel bereits drin?
Laut Definition wird $n$ von $m$ geteilt, wenn es ein $a$ gibt, sodass $n= ma$ gilt. Weitere Bedingungen gibt es nicht. Zur $L$-Sprache: s.o.
>
> Für 3) habe ich leider noch keinen so richtigen Ansatz
> gefunden wie ich das am besten in der Gegebenen Struktur
> machen kann.
> Ich muss ja irgendwie ausdrücken, dass "1" der größte
> gemeinsame Teiler dieser Zahlen ist, ohne das ich die "1"
> verwenden darf.
Tip: $1$ hat die schoene Eigenschaft, dass ihr Quadrat sich selbst ergibt. Aber Achtung: dadurch ist die $1$ nicht eindeutig bestimmt.
>
> Für 4) muss ich irgendwie Ausdrücken können, dass m
> genau 2 Teiler hat (1 und sich selbst)
>
> Für 5) habe ich noch keine so rechte Idee. Die
> Unendlichkeit auszudrücken sollte noch recht einfach sein,
> indem ich einfach sage, dass für jede natürliche Zahl n
> solche Primzahlzwillinge [mm]p_1, p_2[/mm] existieren mit [mm]n
> [mm]n
> Dann muss ich die Formel aus 4) einbauen und am
> schwierigsten sollte es sein irgendwie auszudrücken, dass
> die Differenz dieser Primzahlzwillinge 2 ist.
> Denn ich habe ja weder eine Differenz (was nicht so
> gravierend ist) noch die Zahl 2 (was schon schlimmer ist,
> denke ich).
Wenn Du die $1$ hinbekommen hast, dann wird die $2$ ein leichtes werden.
>
>
> Grundsätzlich bauen die Formeln ja jeweils aufeinander
> auf.
Gut erkannt. Wenn noch irgendwelche Fragen auftauchen, dann zeige kurz, was schon geschafft hast, damit man Dir gezielt helfen kann.
>
> Über Anregungen würde ich mich sehr freuen.
> Vielen Dank.
>
> (Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.)
>
|
|
|
| |
|
Vielen Dank für den Tipp. Die 1 zu erzeugen ist dann ja kein Problem.
Diese Anmerkung verstehe ich leider nicht:
> Beachte aber, dass Du eine $ L $-Sprache hast. Du hast eine Mischung aus
> formaler Sprache und Metasprache verwendet; genauer: die von Dir angegebene > Symbolreihe ist kein Element der Sprache mit der Signatur $ L $.
Meinst du damit, dass ich Zeichen verwendet habe, die ich nicht verwenden darf?
Ich soll ja eine L-Formel angeben. Laut unserer Definition ist eine L-Formel eine Zeichenfolge die aus den logischen Zeichen, Klammern und den Zeichen aus $L$ gebildet werden.
Logische Zeichen sind Variablen, Gleichheitszeichen, Negation, Konjunktion und der Existenzquantor.
Oder verstehe ich dich gerade komplett falsch?
Die 1 sollte ich folgendermaßen beschreiben können.
[mm] $\exists b\in\mathbb{N} (b\cdot b=b\wedge [/mm] (0<b))$
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:47 Sa 18.04.2015 | | Autor: | hippias |
> Vielen Dank für den Tipp. Die 1 zu erzeugen ist dann ja
> kein Problem.
>
> Diese Anmerkung verstehe ich leider nicht:
>
> > Beachte aber, dass Du eine [mm]L [/mm]-Sprache hast. Du hast eine
> Mischung aus
> > formaler Sprache und Metasprache verwendet; genauer: die
> von Dir angegebene > Symbolreihe ist kein Element der
> Sprache mit der Signatur [mm]L [/mm].
>
> Meinst du damit, dass ich Zeichen verwendet habe, die ich
> nicht verwenden darf?
Ja, das wollte ich sagen: weder [mm] $\in$ [/mm] noch [mm] $\IN$ [/mm] sind Symbole, die in der Sprache mit der gegebenen Signatur auftauchen. Man schreibt einfach [mm] $\exists b\: a\cdot [/mm] b=c$.
Ferner: ich wette, dass ihr fuer Variable die Symbole $x$, $y$, $z$ etc. reserviert habt. Daher verwende auch nur diese in deinen Formeln. Verwechsle sie nicht mit den natuerlichen Zahlen $n$,$m$, $k$ etc. $x$ ist ein Variablensymbol der Sprache, $n$ der Wert einer bestimmten Belegung in einer Struktur.
>
> Ich soll ja eine L-Formel angeben. Laut unserer Definition
> ist eine L-Formel eine Zeichenfolge die aus den logischen
> Zeichen, Klammern und den Zeichen aus [mm]L[/mm] gebildet werden.
> Logische Zeichen sind Variablen, Gleichheitszeichen,
> Negation, Konjunktion und der Existenzquantor.
>
> Oder verstehe ich dich gerade komplett falsch?
Nein, eher verstehst Du es richtig. Aber man soll auch nichts hinzufuegen.
>
> Die 1 sollte ich folgendermaßen beschreiben können.
>
> [mm]\exists b\in\mathbb{N} (b\cdot b=b\wedge (0
Ich glaube nicht, dass das Symbol $<$ in Deiner Signatur auftaucht. Versuche also "$b$ ist nicht $0$" anders auszudruecken.
>
|
|
|
| |
|
Das ist natürlich einleuchtend, dass ich [mm] $\in$ [/mm] und [mm] $\mathbb{N}$ [/mm] nicht verwenden darf. Ich werde es anpassen.
Ja, du hast recht "<" kann ich als Zeichen nicht verwenden. Das ist mir aber erst aufgefallen als du bereits geantwortet hast...
Zur Darstellung der "1"
[mm] $\exists [/mm] x [mm] (x\cdot x=x\wedge \neg(x=0))$
[/mm]
(3) m, n, l sind paarweise teilerfremd habe ich mittlerweile folgendes gedacht
[mm] $\exists [/mm] x,y [mm] (xa=m\wedge xb=n\wedge yc=m\wedge [/mm] yd=n [mm] (ye=x(x\cdot x=x\wedge(\neg(x=0))))$
[/mm]
Strenggenommen müsste ich dies jetzt noch 2 mal hintereinanderschalten bisher habe ich ja nur das m und l teilerfremd sind, aber ich bräuchte noch "m und l" und "n und l"
Im Grunde habe ich hier nur versucht die Definition des ggT darzustellen und das dieser 1 sein muss. Ich hoffe das ist mir gelungen. Wirklich schön ist es ja nicht.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:10 Sa 18.04.2015 | | Autor: | hippias |
Nocheinmal moechte ich Dir dringend ans Herz legen keine Variablen wie $n,m,a,b$ etc. in den $L$-Formeln zu verwenden. Das wird Dir bestimmt als Fehler angestrichen!
> Das ist natürlich einleuchtend, dass ich [mm]\in[/mm] und
> [mm]\mathbb{N}[/mm] nicht verwenden darf. Ich werde es anpassen.
>
> Ja, du hast recht "<" kann ich als Zeichen nicht verwenden.
> Das ist mir aber erst aufgefallen als du bereits
> geantwortet hast...
>
>
> Zur Darstellung der "1"
>
> [mm]\exists x (x\cdot x=x\wedge \neg(x=0))[/mm]
Ich wuerde sagen: in einer Struktur, die diesen Satz erfuellt, existiert eine $1$.
>
> (3) m, n, l sind paarweise teilerfremd habe ich
> mittlerweile folgendes gedacht
>
> [mm]\exists x,y (xa=m\wedge xb=n\wedge yc=m\wedge yd=n (ye=x(x\cdot x=x\wedge(\neg(x=0))))[/mm]
>
Ich verstehe das nicht gut. Es ist aber syntaktisch falsch: diese Zeichenreihe ist nicht gemaess den Regeln eurer Sprache gebildet, denn auf eine Relation $ye=x$ kann nicht eine offene Klammer folgen. Abgesehen davon fehlt das $2$-stellige Funktionssymbol [mm] $\cdot$. [/mm] Auch [mm] $\exists [/mm] x,y$ ist nach den ueblichen sytaktischen Regeln falsch.
Ein Beispiel:
Es seien $n,m$ natuerliche Zahlen und [mm] $\mathcal{N}$ [/mm] Deine $L$-Struktur. Es seien $x,y$ Variablen und [mm] $\beta$ [/mm] eine Belegung mit [mm] $\beta(x)= [/mm] n$ und [mm] $\beta(y)= [/mm] m$. Es sei [mm] $\phi= \forall z(\exists a\exists b(a\cdot x=z\wedge b\cdot y=z)\rightarrow \exists c((x\cdot y)\cdot [/mm] c=z))$.
Dann gilt [mm] $\phi$ [/mm] in [mm] $(\mathcal{N}, \beta)$ [/mm] genau dann, wenn $nm$ das kleinste gemeinsame Vielfache von $n$ und $m$ ist (beachte, dass ich nur deswegen $a,b,c$ als Variablennamen benutze, weil ich nicht mit eurer Konvention vertraut bin).
Beweis: [mm] $\Rightarrow:$ [/mm] Es gelte [mm] $(\mathcal{N}, \beta)\models \phi$. [/mm] Dies bedeutet (kurz gefasst): fuer jede natuerliche Zahl gilt: wenn sie von $n$ und $m$ geteilt wird, dann wird sie auch von dem Produkt $nm$ geteilt.
Nun sei $k$ das kgV von $n$ und $m$. Nach Definition des kgV wird $k$ von $n$ und $m$ geteilt. Aus der Voraussetzung folgt jetzt aber, aber $k$ auch von $nm$ geteilt wird.
Umgekehrt wird $nm$ nach Definition des kgV von dem kgV geteilt. Folglich ist $k= nm$.
[mm] $\Leftarrow:$ [/mm] Der kgV von $n$ und $m$ sei $nm$. Nach Definition der Modellbeziehung gilt [mm] $(\mathcal{N}, \beta)\models \phi$ [/mm] genau dann, wenn fuer [mm] $r\in \IN$ [/mm] gilt: wenn $r$ von $n$ und $m$ geteilt wird, dann wird $r$ auch von $nm$ geteilt. Dies ist aber genau die Definition des kleinsten gemeinsamen Vielfachen, und da dieses nach Annahme $=nm$ ist, ist [mm] $(\mathcal{N}, \beta)\models \phi$.
[/mm]
Beachte, dass die Modellbeziehnung aus Bequemlichkeitsgruenden nur informell aufgedroeselt habe.
> Strenggenommen müsste ich dies jetzt noch 2 mal
> hintereinanderschalten bisher habe ich ja nur das m und l
> teilerfremd sind, aber ich bräuchte noch "m und l" und "n
> und l"
>
> Im Grunde habe ich hier nur versucht die Definition des ggT
> darzustellen und das dieser 1 sein muss. Ich hoffe das ist
> mir gelungen. Wirklich schön ist es ja nicht.
|
|
|
| |
|
> Ich wuerde sagen: in einer Struktur, die diesen Satz erfuellt, existiert eine $ 1 $.
Damit möchtest du sagen, dass diese Formel richtig ist, oder wie ist dies zu verstehen?
Zu dem Beispiel und dem Beweis:
Leider verstehe ich nicht was du mir damit sagen möchtest, bzw. den Zusammenhang zu dieser Aufgabe wo ich eine Formel angeben muss.
> Es sei $ [mm] \phi= \forall z(\exists a\exists b(a\cdot x=z\wedge b\cdot y=z)\rightarrow \exists c((x\cdot y)\cdot [/mm] c=z)) $.
Wäre dies ein Beispiel für eine passende Formel?
Ich denke ich habe ein paar grundlegende Fragen.
1.
Wie unterscheidet man generell Variable und Konstante, abgesehen von vereinbarten Konventionen?
So hatte ich etwa a, b, c, d, e in meiner Formel eigentlich gar nicht als Variablen gemeint, sondern Konstanten, was wohl sehr dumm ist.
2.
In deiner Formel treten m, n und l gar nicht auf.
Wie genau ist das mit der Belegung [mm] $\beta(x)=m$ [/mm] gemeint (zum Beispiel).
Eine Belegung ist ja lediglich eine Funktion
[mm] $\beta:\{v_0,..., v_{n-1}\}\to [/mm] M$ für eine L-Struktur [mm] $\mathcal{M}=(M, [/mm] ...)$
Ich weise also einer Variablen [mm] $v_i$ [/mm] irgendeine "Bedeutung" aus $M$ zu.
In der vorliegenden Aufgabe wäre [mm] $M=\mathbb{N}$ [/mm] ich weise den Variablen also einfach eine natürliche Zahl zu.
3.
Den Allquantor und die Implikation haben wir nicht als logische Zeichen hinzugefügt. Den Allquantor kann ich ja auch durch [mm] $\neg\exists$ [/mm] ausdrücken, wie stünde es mit der Implikation [mm] $\rightarrow$?
[/mm]
Ich habe nun nochmal ins Skript geschaut. Eine besondere Konvention für Variablen scheinen wir nicht zu haben. Vorsichtshalber werde ich nun einfach als Variable [mm] $x_i$ [/mm] mit i=1,2,3, ... nehmen. Oder ist diese Indizierung auch nicht in Ordnung, weil ich die Zahlen ja nicht gegeben habe... Irgendwie verwirrend...
Was ich mit meiner obigen Zeichenkette ausdrücken wollte, war die Definition des ggT.
d|a und d|b
Wenn c ein weitere Teiler von a und b ist, so gilt c|d
>Abgesehen davon fehlt das $ 2 $-stellige Funktionssymbol $ [mm] \cdot [/mm] $.
Meinst du damit, dass ich anstelle von $xa$ hätte [mm] $x\cdot [/mm] a$ schreiben müssen. Ja das stimmt natürlich. Das habe ich nur aus Gewohnheit gemacht. :(
Entschuldigung für die Umstände.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:45 Sa 18.04.2015 | | Autor: | hippias |
Ich wollte dich nicht verwirren. Deine Ueberlegungen scheinen alle grundsaetzlich richtig zu sein. Aber ich wollte Dich auf einige Verbesserungen auf formaler Seite hinweisen.
Zu den Variablen: Ihr habt also, wie ueblich, [mm] $v_{0}, v_{1},\ldots$ [/mm] als Variablensymbole vereinbart. Dann tue es auch in Deinen Formeln der $L$-Sprache.
> > Ich wuerde sagen: in einer Struktur, die diesen Satz
> erfuellt, existiert eine [mm]1 [/mm].
>
> Damit möchtest du sagen, dass diese Formel richtig ist,
> oder wie ist dies zu verstehen?
Richtig ist, dass fuer eine beliebige Belegung [mm] $\beta$ [/mm] gilt, dass [mm] $(\mathcal{N},\beta)\models (v_{0}\cdot v_{0}= v_{0}\wedge v_{0}\neq [/mm] 0)$ genau dann, wenn [mm] $\beta(v_{0})= [/mm] 1$.
Uebrigens: ich hatte zuerst [mm] $(\mathcal{N},\beta)\models (v_{0}\cdot v_{0}= v_{0}\wedge v_{0}\neq 0)\iff \beta(v_{0})= [/mm] 1$ getippt: mit [mm] $\iff$. [/mm] Vermeide in der Logik anfangs die Vermischung von formaler und Meta-Sprache. Das ist zwar auch anstrengend, hilft aber auch die abstrakte Seite (Formeln, Sprachen) von der konkreten (Strukturen) zu trennen.
>
> Zu dem Beispiel und dem Beweis:
>
> Leider verstehe ich nicht was du mir damit sagen möchtest,
> bzw. den Zusammenhang zu dieser Aufgabe wo ich eine Formel
> angeben muss.
Ich wollte Dir lediglich ein aehnliches Beispiel zeigen, damit Du siehst, worauf die hinsichtlich Syntax zu achten hast. Auch hoffte ich, dass es Dir helfen kann die Teilerfremdheit der drei Zahlen zu formalisieren.
>
> > Es sei [mm]\phi= \forall z(\exists a\exists b(a\cdot x=z\wedge b\cdot y=z)\rightarrow \exists c((x\cdot y)\cdot c=z)) [/mm].
>
> Wäre dies ein Beispiel für eine passende Formel?
> Ich denke ich habe ein paar grundlegende Fragen.
>
> 1.
> Wie unterscheidet man generell Variable und Konstante,
> abgesehen von vereinbarten Konventionen?
> So hatte ich etwa a, b, c, d, e in meiner Formel
> eigentlich gar nicht als Variablen gemeint, sondern
> Konstanten, was wohl sehr dumm ist.
Konstanten(symbole) werden in der Signatur aufgefuehrt. Deine Signatur enthaelt keine Konstanten. Du musst also [mm] $v_{0}$ [/mm] etc. benutzen.
>
> 2.
> In deiner Formel treten m, n und l gar nicht auf.
Das sollen sie auch nicht: die natuerlichen Zahlen sind naemlich kein Teil der $L$-Sprache. Es koennen aber Variable, die zur Sprache gehoeren, als Zahlen $m$ etc. interpretiert bzw. belegt werden.
> Wie genau ist das mit der Belegung [mm]\beta(x)=m[/mm] gemeint (zum
> Beispiel).
>
> Eine Belegung ist ja lediglich eine Funktion
>
> [mm]\beta:\{v_0,..., v_{n-1}\}\to M[/mm] für eine L-Struktur
> [mm]\mathcal{M}=(M, ...)[/mm]
>
> Ich weise also einer Variablen [mm]v_i[/mm] irgendeine "Bedeutung"
> aus [mm]M[/mm] zu.
> In der vorliegenden Aufgabe wäre [mm]M=\mathbb{N}[/mm] ich weise
> den Variablen also einfach eine natürliche Zahl zu.
Richtig.
>
> 3.
> Den Allquantor und die Implikation haben wir nicht als
> logische Zeichen hinzugefügt. Den Allquantor kann ich ja
> auch durch [mm]\neg\exists[/mm] ausdrücken, wie stünde es mit der
> Implikation [mm]\rightarrow[/mm]?
[mm] \psi\rightarrow\phi$ [/mm] ist logisch aequivalent zu [mm] $\neg\psi \vee \phi$. [/mm]
>
>
> Ich habe nun nochmal ins Skript geschaut. Eine besondere
> Konvention für Variablen scheinen wir nicht zu haben.
> Vorsichtshalber werde ich nun einfach als Variable [mm]x_i[/mm] mit
> i=1,2,3, ... nehmen. Oder ist diese Indizierung auch nicht
> in Ordnung, weil ich die Zahlen ja nicht gegeben habe...
> Irgendwie verwirrend...
Benutze [mm] $v_{0}, v_{1},\ldots$, [/mm] wenn dies so im Skript steht. Natuerlich ist das nervig, weshalb man natuerlich Vereinbarungen trifft wie: die Symbole $x$, $y$ stehen fuer eine der Variablen [mm] $v_{i}$. [/mm] Sonst wuerde man ja verrueckt. Aber wenn ihr dergleichen noch nicht gemacht habt, bleibe sicherheitshalber bei den $v$'s.
>
> Was ich mit meiner obigen Zeichenkette ausdrücken wollte,
> war die Definition des ggT.
>
> d|a und d|b
>
> Wenn c ein weitere Teiler von a und b ist, so gilt c|d
>
> >Abgesehen davon fehlt das [mm]2 [/mm]-stellige Funktionssymbol
> [mm]\cdot [/mm].
>
> Meinst du damit, dass ich anstelle von [mm]xa[/mm] hätte [mm]x\cdot a[/mm]
> schreiben müssen. Ja das stimmt natürlich. Das habe ich
> nur aus Gewohnheit gemacht. :(
Ja, das wollte ich nur sagen. Dass Du es vergessen hast, ist wohl voellig normal  Man muss sich bei diesen Aufgaben etwas dumm stellen: wie ein dummer, sturer Computer auch zu dumm ist mein Programm zu verstehen und erst einmal Syntaxfehler reklamiert.
>
> Entschuldigung für die Umstände.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:10 So 19.04.2015 | | Autor: | hippias |
Ich wollte noch ein anderes Beispiel bringen, das etwas naeher an der eigentlichen Aufgabenstellung angesiedelt ist.
Betrachte die Formel [mm] $\phi:= \exists v_{3}\exists v_{4}(v_{0}\cdot v_{3}=v_{1}\vee v_{0}\cdot v_{4}=v_{2})$. [/mm] Sei nun [mm] $\beta$ [/mm] eine Belegung mit [mm] $\beta(v_{0})= [/mm] m$, [mm] $\beta(v_{1})= [/mm] n$ und [mm] $\beta(v_{2})= [/mm] k$. Dann gilt [mm] $(\mathcal{N}, \beta)\models \phi$ [/mm] genau dann, wenn $m$ ein gemeinsamer Teiler von $n$ und $k$ ist. (Versuche ruhig dies zu beweisen).
Wenn ich formalisieren moechte, dass Zahlen teilerfremd sind, dann kann ich [mm] $\phi$ [/mm] folgendermassen modifizieren: [mm] $\psi:= \forall v_{0}(\phi\rightarrow \epsilon)$, [/mm] wobei [mm] $\epsilon:= v_{0}\cdot v_{0}= v_{0} \wedge \neg v_{0}=0$ [/mm] die Charakterisierung der $1$ war.
Ausfuehrlich geschrieben: [mm] $\psi= \forall v_{0}(\exists v_{3}\exists v_{4}(v_{0}\cdot v_{3}=v_{1}\vee v_{0}\cdot v_{4}=v_{2}) \rightarrow (v_{0}\cdot v_{0}= v_{0} \wedge \neg v_{0}=0))$
[/mm]
Hier gilt [mm] $(\mathcal{N},\beta)\models\psi$ [/mm] genau dann, wenn $n$ und $k$ teilerfremd sind.
|
|
|
| |
|
Hi,
ich habe jetzt noch einmal rumprobiert und bin nun erstmal auf folgendes gekommen.
Ich möchte erstmal nur zeigen, dass m und n teilerfremd sind. Damit es nicht zu unübersichtlich ist wähle ich als Belegung [mm] $\beta(x)=m, \beta(y)=n$. [/mm] Ich möchte die Definition des ggT formalisieren, also
1. d|m und d|n
2. Wenn c|m und c|n dann gilt c|d
Bei 2. habe ich ja eine Implikation enthalten, also muss ich diese durch [mm] $\neg\psi \vee\phi$ [/mm] umschreiben. Weil ich kein [mm] $\vee$ [/mm] habe, muss ich dies durch [mm] $\wedge\neg\psi$ [/mm] ausdrücken.
Ich versuche meine Formel einmal zu kommentieren, damit du es hoffentlich nachvollziehen kannst, falls es nicht stimmt, da doch recht viele Variablen auftauchen...
[mm] $\exists v_0\exists v_1\exists v_3\exists v_4\exists v_7(v_0\cdot v_2=x\wedge v_1\cdot v_2=y\wedge\neg(v_3\cdot v_5=x\wedge v_4\cdot v_5=y)\wedge\neg(\neg(v_5\cdot v_6=v_2)\wedge\neg(v_5\cdot v_5=v_5\wedge(0+v_7=v_5))))$
[/mm]
[mm] $v_0\cdot v_2=x$ [/mm] soll der Bedingung entsprechen, dass es ein d gibt, welches m teilt. Das d wäre hier dann das [mm] $v_2$.
[/mm]
Also lautet die Bedingung d|n dann [mm] $v_1\cdot v_2=n$.
[/mm]
Nun kommt die Bedingung mit der Implikation, welche ich ja umschreiben muss.
Wenn c|m und c|n, dann c|d
[mm] $v_3\cdot v_5=x$ [/mm] hier wäre das [mm] $v_5$ [/mm] nun das $c$.
Ebenso
[mm] $v_4\cdot v_5=y$
[/mm]
In meiner Formel taucht nun eine "doppelte" Negation auf.
Das kommt daher, weil ich ja wieder eine Implikation habe. Ich muss ja nun ausdrücken, dass wenn c|d gilt, dass dann c bereits die 1 ist.
Wobei ich das "oder" ja immer durch [mm] $\vee\neg(...)$ [/mm] umschreiben soll.
Ich hoffe du kannst nachvollziehen wie ich das meine und das es richtig ist.
Dies müsste ich jetzt noch 2 mal aufschreiben für m, l sind paarweise teilerfremd und n, l sind paarweise teilerfremd.
|
|
|
| |
|
Ich sehe gerade, dass wir die anderen logischen Zeichen wie die Implikation, "oder" und den Allquantor als abkürzende Schreibweisen eingeführt haben. Es ist also doch nicht ganz so aufwendig hinzuschreiben.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:23 Mo 20.04.2015 | | Autor: | hippias |
> Hi,
>
> ich habe jetzt noch einmal rumprobiert und bin nun erstmal
> auf folgendes gekommen.
> Ich möchte erstmal nur zeigen, dass m und n teilerfremd
> sind. Damit es nicht zu unübersichtlich ist wähle ich als
> Belegung [mm]\beta(x)=m, \beta(y)=n[/mm]. Ich möchte die Definition
> des ggT formalisieren, also
>
> 1. d|m und d|n
> 2. Wenn c|m und c|n dann gilt c|d
>
> Bei 2. habe ich ja eine Implikation enthalten, also muss
> ich diese durch [mm]\neg\psi \vee\phi[/mm] umschreiben. Weil ich
> kein [mm]\vee[/mm] habe, muss ich dies durch [mm]\wedge\neg\psi[/mm]
> ausdrücken.
>
> Ich versuche meine Formel einmal zu kommentieren, damit du
> es hoffentlich nachvollziehen kannst, falls es nicht
> stimmt, da doch recht viele Variablen auftauchen...
>
> [mm]\exists v_0\exists v_1\exists v_3\exists v_4\exists v_7(v_0\cdot v_2=x\wedge v_1\cdot v_2=y\wedge\neg(v_3\cdot v_5=x\wedge v_4\cdot v_5=y)\wedge\neg(\neg(v_5\cdot v_6=v_2)\wedge\neg(v_5\cdot v_5=v_5\wedge(0+v_7=v_5))))[/mm]
>
> [mm]v_0\cdot v_2=x[/mm] soll der Bedingung entsprechen, dass es ein
> d gibt, welches m teilt. Das d wäre hier dann das [mm]v_2[/mm].
> Also lautet die Bedingung d|n dann [mm]v_1\cdot v_2=n[/mm].
>
> Nun kommt die Bedingung mit der Implikation, welche ich ja
> umschreiben muss.
>
> Wenn c|m und c|n, dann c|d
>
> [mm]v_3\cdot v_5=x[/mm] hier wäre das [mm]v_5[/mm] nun das [mm]c[/mm].
> Ebenso
> [mm]v_4\cdot v_5=y[/mm]
>
> In meiner Formel taucht nun eine "doppelte" Negation auf.
> Das kommt daher, weil ich ja wieder eine Implikation habe.
> Ich muss ja nun ausdrücken, dass wenn c|d gilt, dass dann
> c bereits die 1 ist.
> Wobei ich das "oder" ja immer durch [mm]\vee\neg(...)[/mm]
> umschreiben soll.
>
> Ich hoffe du kannst nachvollziehen wie ich das meine und
> das es richtig ist.
Ehrlich gesagt, ist es mir zu muehselig die Formel zu deuten. Es waere nett, wenn Du Implikationspfeile etc. benutzen wuerdest.
Der Anfang der Formel, mit dem Du sagen moechtest, dass [mm] $\beta(v_{2})$ [/mm] ein gemeinsamer Teiler von [mm] $\beta(x)$ [/mm] und [mm] $\beta(y)$ [/mm] ist, ist richtig. Nur warum schreibst Du $x$ und $y$? Dann kommt wohl die Implikation und darauf habe ich in dieser Form keine rechte Lust. Dir sind aber auf jeden Fall dabei $2$ Fehler unterlaufen: 1. Fuer alle gemeinsamen Teiler $c$ gilt, dass [mm] $c\vert [/mm] d$. Daher muss da irgendwo ein Allquantor auftauchen. 2. Die Teilformel am Ende [mm] $\neg((v_5\cdot v_5=v_5)\wedge(0+v_7=v_5))$ [/mm] kommt mir ziemlich unsinnig vor. Zumal das [mm] $v_{7}$ [/mm] nirgends sonst auftaucht und Du es benutzt, um zu sagen, dass es existiert und [mm] $=v_{5}$ [/mm] ist.
> Dies müsste ich jetzt noch 2 mal aufschreiben für m, l
> sind paarweise teilerfremd und n, l sind paarweise
> teilerfremd.
|
|
|
| |
|
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Ja, die Form ist wirklich sehr unschön zu lesen, und wenn es richtig ist, dann kann man wohl kaum nachvollziehen was damit gemeint ist. Ich wollte gestern auch noch eine verschönerte Fassung posten, habe es aber irgendwie versäumt...
Ich versuche die einzelnen Teile der Formel mal zu unterscheiden.
Darstellen möchte ich folgende Definition, deren Teile ich mal beziffer:
1. d|a
2. d|b
3. Wenn c ein (weiterer) Teiler von a
4. und von b ist,
5. so gilt c|d
Ich hoffe folgendes ist nun richtig. Ich werde auch die Variablen versuchen eindeutiger darzustellen:
$\exists v_{d_1}\exists v_{d_2}\forall v_c (\underbrace{v_{d}v_{d_1}=\beta(x)}_{1}\wedge\underbrace{v_{d}v_{d_2}=\beta(y)}_{2}\wedge((\underbrace{v_{c}v_{c_1}=\beta(x)}_{3}\wedge\underbrace{v_{c}v_{c_2}=\beta(y)}_{4})\underbrace{\rightarrow(v_{c}v_{c_3}=v_d)}_{5})$
Das wäre dann die Teilerfremdheit von m und n.
Das m eine Primzahl ist müsste vielleicht folgender maßen gehen:
$\forall v_1\forall v_x ((v_1v_x=\beta(x))\rightarrow ((((v_1=v_1\cdot v_1)\wedge (0+v_0=v_1))}\wedge v_x=\beta(x)))\vee ((((v_x=v_x\cdot v_x)\wedge (0+v_0=v_x))\wedge v_1=\beta(x))))$
Leider entsteht hier ein Zeilenumbruch den ich leider nicht wegbekomme...
Ich hoffe diese Formel ist verständlich.
Was ich ausdrücken möchte ist, dass wenn ich mein m in Faktoren zerlegen kann, dann muss einer der beiden Faktoren 1 sein und der andere m, oder es ist eben umgekehrt.
Wenn ich die 1 darstelle benötige ich noch die Bedingung, dass es größer Null ist.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:20 Mi 22.04.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
