WS21/22 A2 Allgemeingueltigkeit aussagenlogischer Formeln

WS18/19 A1 Theorie Multiple Choise

SS18 A1 Theorie Multiple Choise

WS17/18 A1 Theorie Multiple Choise

WS17/18 A1 Herbrand

• Nennen Sie zwei Methoden, mit denen man die Aequivalenz zweier aussagenlogischer Formeln A,B zeigen kann. (SS22)

  • Vergleich von Wahrheitswerttabellen
  • Aquivalenzumformungen, um B aus A zu erhalten
  • Allgemeingueltigkeit von A < = > B mit einem Kalkuel beweisen

• Ist die Aequivalenz praedikatenlogischer Formeln entscheidbar? Wenn ja, geben Sie das Entscheidungsverfahren an. Wenn nein, begruenden Sie! (SS22)

  • Nein, allgemeingueltigkeit von praedikatenlogischer Formeln ist unentscheidbar. Sonst koennte man A < = > 1 checken.

• Wann heißt eine aussagenlogische Formel A eine Horn-Formel? (WS21/22)

  • Wenn sie in form !A, !B, !C…!X → Y steht

• Wann heit ein Reduktionssystem noethersch? (WS20/21)

  • Wenn es keine unendliche Folgen gibt

• Was beschreibt eine assignable-Klausel in JML-Methodenvertraegen? (WS20/21)

  • Ob man die existierende Objekte auf Heap aendern kann
  • strict: Ob man neue objekte erstellen kann

• Nennen Sie eine Konsequenz des Goedelschen Unvollstandigkeitssatzes. (WS20/21)

  • Arithmetik ist nicht axiomatisierbar
  • Es gibt mathematische Aussagen, die man nicht formal uberpruefen kann

• Welche Eigenschaften muss eine Formel der Praedikatenlogik (PL1) besitzen, damit ihre Erfuellbarkeit mit dem Algorithmus nach Shostak geprueft werden kann?

  • Keine Quantoren
  • Predikatensymbole auser Gleichheit
  • Konjunktion von Literalen (Formel zumindest in DNF)