本次德国代写主要为梳理逻辑相关的限时测试
练习 1.1（提交形式主义 – 1 分）
确保您提交的材料包括预科编号和所有组的名称
包含成员！
练习 1.2（公理、定义、定理、引理、推论 – 1 + 1 + 1 = 3 分）
在整个学习过程中，您都会遇到这些术语。
a) 用一两句话描述一个公理的含义，一个
定义、命题、引理和推论。
b) 为两个数的最大公约数定义一个函数。
c) 假设您编写了一个算法 Alg (a; b)
计算出的公约数。用一句话说你
算法计算正确的值。
练习 1.3（结构归纳 – 10 分）
命题公式A的深度t(A)定义如下。
• 如果 A 是原子公式，则 t (A) = 0。
• 如果 A = (B C) 对于二元结点，则 t (A) = maxft (B)； t (C) g + 1。
• 如果 A = (: B)，那么我们定义 t (A) = t (B) + 1。
另外，令 jAj 为公式 A 的长度，即 A 中的字符数（括号和
连接也算）。用结构归纳法证明结构
在每个全括号命题逻辑中的命题公式
公式 A。
a) 左括号和右括号的数量相同。
b) jAj 5k + 1，其中 k 是 A 中的加入者数量。
c) jAj 4 2t (A)
Aufgabe 1.1 (Abgabeformalismus — 1 Bonus-Pkt)
Stellen Sie sicher, dass Ihre Abgabe die Matrikelnummer und den Namen aller Gruppen-
mitglieder enthält!
Aufgabe 1.2 (Axiom, Definition, Satz, Lemma, Korollar — 1 + 1 + 1 = 3Pkt)
Diese Begriffe werden Ihnen während des Studiums stets begegnen.
a) Beschreiben Sie mit einem bis zwei Sätzen die Bedeutung eines Axioms, einer
Definition, eines Satzes, eines Lemmas und eines Korollars.
b) Definieren Sie eine Funktion für den größten gemeinsamen Teiler zweier Zahlen.
c) Nehmen Sie an, Sie hätten einen Algorithmus Alg(a; b) geschrieben, der den größten
gemeinsamen Teiler berechnet. Formulieren Sie einen Satz, der besagt, dass ihr
Algorithmus den korrekten Wert berechnet.
Aufgabe 1.3 (Strukturelle Induktion — 10Pkt)
Die Tiefe t(A) einer aussagenlogischen Formel A ist wie folgt definiert.
• Ist A eine atomare Formel, so ist t(A) = 0.
• Ist A = (B C) für einen biänren Junktor , so gilt t(A) = maxft(B); t(C)g + 1.
• Ist A = (:B), so definieren wir t(A) = t(B) + 1.
Außerdem sei jAj die Länge der Formel A, d.h. die Anzahl der Zeichen in A (Klammern und
Junktoren zählen also mit). Beweisen Sie mit struktureller Induktion uüber den Aufbau
der aussagenlogischen Formeln, dass in jeder vollständig geklammerten aussagenlogischen
Formel A
a) die Anzahl der öffnenden und schließenden Klammern übereinstimmt.
b) jAj 5k + 1, wobei k die Anzahl der Junktoren in A ist.
c) jAj 4 2t(A)