Preview only show first 10 pages with watermark. For full document please download

Aufgaben Zum 3.5.2016 - Friedrich-schiller

   EMBED

Share

Transcript

Sommersemester 2016 ¨ Ubungsaufgaben zur Vorlesung Logik und Beweisbarkeit http://tinyurl.com/Logik2016 Friedrich-Schiller-Universit¨at Jena Institut f¨ ur Informatik Martin Mundhenk Aufgaben zum 3.5.2016 (Abgabe bis zum Beginn der Vorlesung) Aufgabe 10: . Induktion statt .. . Der Beweis von Lemma 2.5 ist unsch¨on wegen der .. . . F¨ uhren Sie den Beweis sch¨oner als Induktionsbeweis ohne .. . Aufgabe 11: auf den Folien fehlende Beweise I Beweisen Sie die folgende Aussage (Lemma 2.9). F¨ ur alle m, n ∈ N gilt M Nat m · n = m · n. Aufgabe 12: auf den Folien fehlende Beweise II Beweisen Sie die folgende Aussage. Die Regel (= E) ist korrekt. D.h. f¨ ur alle Formeln ϕ, Terme σ, τ und Variablen xi gilt: wenn N |= τ = σ und N |= ϕ[τ /xi ], dann folgt N |= ϕ[σ/xi ]. L¨osen Sie eine der Aufgaben ordentlich. Schreiben Sie Ihre Konstruktionen und Beweise so auf, dass sie gut lesbar und leicht nachvollziehbar sind. Bei einem Induktionsbeweis ist es h¨aufig hilfreich, sich (und dem Korrekteur) klar zu machen, was in den einzelnen Schritten zu beweisen ist. Falls Sie Fragen haben, dann fragen Sie mich (z.B. in der Sprechstunde freitags 10-12 oder n.V.)!