M. Held, S. Huber, P. Palfrader Universit¨at Salzburg SS 2015 Fachbereich Computerwissenschaften PS Diskrete Mathematik“ ” 1. Aufgabenblatt fu ¨ r PS am 12.3.2015 Aufgabe 1 Geben Sie f¨ ur die folgenden Formeln die Wahrheitstabellen an. 1. p ñ q _ r 2. pp ñ qq ^ pq ñ rq 3. pp ^ qq ^ p q _ rq ^ pr ñ pq Aufgabe 2 Zeigen Sie, dass die folgenden Aussagen Tautologien sind. 1. pp ^ pp ñ qqq ñ q 2. p p ^ pp _ qqq ñ q 3. ppp ñ qq ^ p p ñ qqq ñ q Aufgabe 3 Bestimmen Sie durch Umformung der folgenden Formel, ob es sich um eine Tautologie oder eine Kontradiktion handelt. p pp r ^ pq ô pq ñ qq ^ p pp ^ rq ô rq Aufgabe 4 Geben Sie in den folgenden Formeln die freien und gebundenen Variablen an und negieren Sie die Formeln, sodass Negationszeichen h¨ochstens vor den Termen stehen. 1. @y gpyq “ y 2. P pxq ñ Dx f pxq “ x 3. @xDy hpx, zq “ y Aufgabe 5 Wir betrachten ein Schachbrett und das zweistellige Pr¨adikat P u ¨ber der Menge t1, . . . , 8u mit P px, yq “ T genau dann wenn ein Bauer auf der Reihe x und Spalte y steht. Erl¨autern Sie anhand dieses Beispiels die Schlussregel von der Vertauschung der Quantoren (Seite 53 im Skriptum) mit φ “ P px, yq, sowie die Ung¨ ultigkeit der Umkehrung dieser Regel. Aufgabe 6 Sei f : R Ñ R eine reellwertige Funktion einer reellen Ver¨anderlichen. Weiters bezeichne R` die Menge der positiven reellen Zahlen. Formulieren Sie in Pr¨adikatenlogik die folgenden Aussagen: 1. F¨ ur jedes ε P R` und jedes reelle x gibt es ein δ P R` derart, dass f¨ ur jedes reelle x1 die 1 1 Ungleichung |f pxq ´ f px q| ă ε aus |x ´ x | ă δ folgt. 2. F¨ ur jedes ε P R` gibt es ein δ P R` , sodass f¨ ur alle reellen Zahlen x und x1 mit |x ´ x1 | ă δ gilt, dass |f pxq ´ f px1 q| ă ε. Sind diese beiden Aussagen a¨quivalent? Aufgabe 7 Formulieren Sie die gegebenen Aussagen in der Sprache der Pr¨adikatenlogik. 1. F¨ ur jede reelle Zahl x gilt, dass x ¨ 0 sich zu 0 ergibt. 2. Zu jeder nat¨ urlichen Zahl n existiert eine nat¨ urliche Zahl m, welche gr¨oßer als n ist. 3. F¨ ur jedes Element x aus der Menge G existiert ein gr¨oßer als 0 derart, dass K pxq eine Teilmenge von G ist. (Tipp: Die Menge der nat¨ urlichen Zahlen wird mit N bezeichnet; die Menge der reellen Zahlen mit R. Anstatt “F¨ ur alle nat¨ urlichen Zahlen n” schreibt man oft auch kurz @n P N.) Die Angaben sind unter www.cosy.sbg.ac.at/~held/teaching/diskrete_mathematik/ps_bsp.pdf auch im WWW verf¨ ugbar. Sofern nicht explizit anders angegeben, sind alle Antworten detailliert zu begr¨ unden. Bitte benutzen Sie die in der Vorlesung verwendete Schreibweise und Terminologie. M. Held, S. Huber, P. Palfrader Universit¨at Salzburg SS 2015 Fachbereich Computerwissenschaften PS Diskrete Mathematik“ ” 2. Aufgabenblatt fu ¨ r PS am 19.3.2015 Aufgabe 8 Beweisen oder widerlegen Sie: 1. Ein Minimum einer halbgeordneten Menge ist stets auch das einzige minimale Element. 2. Ein minimales Element einer total geordneten Menge ist stets auch ein Minimum. 3. Eine unendliche halbgeordnete Menge, die nicht auch total geordnet ist, hat nie ein Minimum. Aufgabe 9 Beweisen oder widerlegen Sie: Falls s das einzige minimale Element einer Menge S mit Halbordnung ľ ist, dann hat S auch s als Minimum. Aufgabe 10 Beweisen oder widerlegen Sie: Jede totale Ordnung ľ einer endlichen Menge S ist eine Wohlordnung auf S. n Aufgabe 11 Die Funktionswerte von F : N0 Ñ N legen wir wie folgt fest: F pnq :“ 2p2 q `1. Beweisen Sie mit Induktion: n´1 ź F piq “ F pnq ´ 2 f¨ ur alle n P N. i“0 Aufgabe 12 Eine weitverbreitete Turnierform f¨ ur sportliche Wettk¨ampfe mit mehreren TeilnehmerInnen, die nicht alle gleichzeitig gemeinsam gegeneinander antreten k¨onnen, ist ein “Rundenturnier”: Alle Teilnehmer treten insgesamt jeweils m-mal (in allen m¨oglichen Paarungen) paarweise gegen einander in einem “Vergleich” (Spiel, Wettstreit, Kampf, etc.) an. Wir betrachten ein Rundenturnier mit m :“ 1 und n Teilnehmern, mit n P Nzt1u. Weiters nehmen wir an, daß kein Vergleich unentschieden endet, so daß es in jedem Vergleich eine Siegerin oder einen Sieger gibt. Wenn ein Teilnehmer ti gegen einen anderen Teilnehmer tj gewinnt, dr¨ ucken wir dies durch ti ą tj aus. Ist es am Ende eines derartigen Turniers immer m¨oglich, die Teilnehmer so von 1 bis n durchzunummerieren, daß tats¨achlich f¨ ur alle 1 ď i ď n ´ 1 jeweils der i-te Teilnehmer gegen den pi ` 1q-ten Teilnehmer gewonnen hat? (Also, daß t1 ą t2 ą t3 ą . . . ą tn´1 ą tn erf¨ ullt ist.) Ist diese Nummerierung immer eindeutig? Handelt es sich bei ą um eine strikte Halbordnung? Aufgabe 13 Zeigen Sie mittels Induktion: (1) Das ToH-Problem aus der Vorlesung kann f¨ ur jede beliebige Anzahl von n Scheiben immer (rekursiv) gel¨ost werden. (2) Die rekursive L¨osung erfordert die Bewegung von mindestens 2n ´ 1 vielen Scheiben. Die Angaben sind unter www.cosy.sbg.ac.at/~held/teaching/diskrete_mathematik/ps_bsp.pdf auch im WWW verf¨ ugbar. Sofern nicht explizit anders angegeben, sind alle Antworten detailliert zu begr¨ unden. Bitte benutzen Sie die in der Vorlesung verwendete Schreibweise und Terminologie. M. Held, S. Huber, P. Palfrader Universit¨at Salzburg SS 2015 Fachbereich Computerwissenschaften PS Diskrete Mathematik“ ” 3. Aufgabenblatt fu ¨ r PS am 26.3.2015 Aufgabe 14 Gegeben ist die Folge han i mit a0 “ a1 “ 0, a2 “ 2 und an “ 6an´3 ´ 11an´2 ` 6an´1 f¨ ur n ě 3. Zeigen Sie mittels vollst¨andiger Induktion an “ 3n ´ 2n`1 ` 1 f¨ ur alle n P N0 . Aufgabe 15 Auf Lusitania ist seit der Umstellung der Credit (C) die neue W¨ahrung. Leider ist die Bank mit dem Drucken der Geldscheine noch nicht fertig und es existieren erst Banknoten mit den Werten 5C und 7C. a) Zeigen Sie, dass es nicht m¨oglich ist, einen Betrag von 23C genau zu bezahlen. b) Zeigen Sie (durch vollst¨andige Induktion), dass jeder h¨ohere Betrag genau bezahlbar ist. Aufgabe 16 Sie haben ein rechteckiges, kariertes Blatt Papier, das n “ a ˆ b K¨astchen groß ist. Sie sollen dieses Blatt mit einer Schere so oft zerschneiden, bis nur mehr St¨ ucke u ¨brig sind, die genau ein K¨astchen groß sind. Dazu w¨ahlen sie in jedem Schritt aus dem vor Ihnen liegenden Haufen genau ein Papierst¨ uck, welches noch gr¨oßer als ein K¨astchen ist. Dieses St¨ uck zerschneiden Sie entlang einer beliebigen Gerade in zwei Teile. Sind nur mehr 1 ˆ 1 große St¨ ucke u ¨brig, sind Sie fertig. Ein Beispiel f¨ ur ein 3ˆ3 großes Anfangsst¨ uck sehen Sie rechts. Die jeweils gew¨ahlte Schnittgerade ist strichliert gezeichnet. Es gibt nat¨ urlich viele weitere Pfade, um dieses Papierst¨ uck zu zerschneiden. Beweisen Sie: egal wie und in welcher Reihenfolge sie Ihr Papier zerschneiden, sie werden immer genau n ´ 1 Schnitte brauchen. Aufgabe 17 Sei R Ă N ˆ N die Teilbarkeitsrelation, also pa, bq P R (auch geschrieben als a b) genau dann wenn b durch a ohne Rest teilbar ist. Beweisen oder widerlegen Sie: a) R ist eine Halbordnung, b) R ist eine strikte Halbordnung, c) R ist eine totale Ordnung. Gibt es ein minimales und ein maximales Element in N bez¨ uglich R? Wenn ja, welches. Wenn nein, warum? (Nutzen Sie die Definition von Teilbarkeit aus der Vorlesung (Definition 51). Sollten Sie Teile von Lemma 52 nutzen, sind diese zu zeigen.) Aufgabe 18 Beweisen oder widerlegen Sie f¨ ur a, b, c, d P N: a) Wenn a b und a c, dann auch a pa ` b ` cq. b) Wenn ab cd, dann gilt a c oder a d. ? ? c) Sind a und b Quadratzahlen und a b, dann gilt auch a b. Aufgabe 19 B¨ ucher werden heutzutage u ¨ber ihre International Standard Book Number (ISBN) identifiziert. ISBN-10, eine Version dieses Standards, definiert eine 10-stellige Zahl, x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 , wobei x10 eine Pr¨ ufziffer zwischen 0 und 10 (10 wird durch X kodiert) ist, sodass der Wert des Terms p10x1 ` 9x2 ` 8x3 ` 7x4 ` 6x5 ` 5x6 ` 4x7 ` 3x8 ` 2x9 ` x10 q ” 0 pmod 11q. a) Ist 0-8125-5070-3 eine g¨ ultige ISBN? Wenn nein, was w¨are die passende Pr¨ ufziffer? b) Finden Sie den Wert der unleserlich gewordenen Ziffer x in 3-540-77x73-6. Die Angaben sind unter www.cosy.sbg.ac.at/~held/teaching/diskrete_mathematik/ps_bsp.pdf auch im WWW verf¨ ugbar. Sofern nicht explizit anders angegeben, sind alle Antworten detailliert zu begr¨ unden. Bitte benutzen Sie die in der Vorlesung verwendete Schreibweise und Terminologie. M. Held, S. Huber, P. Palfrader Universit¨at Salzburg SS 2015 Fachbereich Computerwissenschaften PS Diskrete Mathematik“ ” 4. Aufgabenblatt fu ¨ r PS am 16.4.2015 Aufgabe 20 Zeigen Sie, dass gcdpa, a ` bq b f¨ ur alle a, b P N gilt. Aufgabe 21 Man zeige, dass n! ` 1 und pn ` 1q! ` 1 relativ prim sind. urliche Zahlen und deren Aufgabe 22 Es seien a “ pa11 pa22 ¨ ¨ ¨ pann und b “ pb11 pb22 ¨ ¨ ¨ pbnn zwei nat¨ “erweiterte Primfaktorzerlegung”, mit n P N und f¨ u r 1 ď i ď n ist a , b i i P N0 , sowie pi paarweise śn minpai ,bi q verschiedene Primzahlen. Man zeige gcdpa, bq “ i“1 pi . Aufgabe 23 Bestimmen Sie drei aufeinanderfolgende ganze Zahlen, sodass die erste durch drei, die zweite durch f¨ unf, und die dritte durch sieben teilbar ist. Wie lautet das kleinste positive derartige Tripel von Zahlen? Wieviele derartige Tripel gibt es im Interval r0, 400s? Die Angaben sind unter www.cosy.sbg.ac.at/~held/teaching/diskrete_mathematik/ps_bsp.pdf auch im WWW verf¨ ugbar. Sofern nicht explizit anders angegeben, sind alle Antworten detailliert zu begr¨ unden. Bitte benutzen Sie die in der Vorlesung verwendete Schreibweise und Terminologie.