Blatt06

Page 1

Professur für Rechnerarchitektur
Prof. Dr. Armin Biere
Dr. Mathias Fleury
Freiburg, 5. Juni 2026
Technische Informatik

Übungsblatt 6

Achtung 1: Handgeschriebene Antworten werden nicht benotet.

Vorgeschlagenes Lesethema der Woche: Multiplexer https://www.righto.com/2025/11/unusual-386-standahtml?m=0

Aufgabe 1 (KI/Pflicht Punkte)

Bitte ankreuzen welches von beiden Punkte passt:

□ Ich habe die Aufgaben selbst versucht zu lösen und möchte ein Korrektur

  • a) mir ist bewusst, dass signifikante Bearbeitung reicht zum Bestehen des Blatts
  • b) mir ist bewusst, dass ich vielleicht trotzdem Vorrechnung muss (ohne meine Notizen!)

□ Ich habe irgendwann die KI gefragt und einfach abgeschrieben. In diesem Fall:

  • a) muss ich alle Aufgaben abgeben, das reicht zum Bestehen dieses Blatts
  • b) mir ist bewusst, dass ich keine Korrektur bekommen werde
  • c) mir ist bewusst, dass ich vielleicht trotzdem Vorrechnung muss (ohne meine Notizen!)

Die Bewertung passiert nur wenn diese Aufgabe beantwortet wurde.

Aufgabe 2 (2 + 2 + 2 Punkte)

Löschen Sie alle unnützen Klammern, ohne die Terme umzuordnen:

Aufgabe 3 (13 + 1 + 2 Punkte)

Page 2

Sei eine Boolesche Algebra.

Die Beweise unten dürfen nur durch Anwendung der Axiome (Kommutativität, Assoziativität, Absorption, Distributivität, Komplementregel), die in der Vorlesung bewiesenen Existenz und Eindeutigkeit der neutralen Elemente (inklusive Korollar), die Eindeutigkeit des Komplements und die De-Morgan-Regel¹. In jedem Schritt geben Sie explizit an, welche Regeln angewendet werden.

a)

Wir definieren plus, das inverse und mal als:

Achtung: ist hier nicht die Disjunktion, wenn !

Zeigen Sie, dass ein Boolescher kommutativer Ring ist, d.h.:

a. Assoziativität von

b. Kommutativität von

c. 0 ist das neutrale Element

d. Zu jedem gibt es ein inverses , sodass

e. Assoziativität von

f. Kommutativität von

g. Distributivität

Achtung: Der Beweis ist nicht für eine bestimmte Algebra (also weder für noch für Mengen) gemacht werden.

¹Dieser kann auch abgeleitet werden, aber das wird hier angenommen.

Page 3

b)

Wie heißt der standardmäßig für ?

c)

(mit als und als ) ist auch eine Boolesche Algebra (über Mengen). Ist ein Ring? Was ist der in diesem Fall?

Es ist übrigens immer möglich von dem Booleschen Ring zurück zur Booleschen Algebra zu gehen:

Aufgabe 4 (3 + 4 Punkte)

Wie Ihnen vielleicht aufgefallen ist, wurde in der Vorlesung nur für das NAND-Gatter und den Inverter (NOT) die CMOS-Realisierungen vorgestellt. Dies ist dadurch begründet, dass diese beiden Gatter ausreichen, um alle Booleschen Funktionen zu realisieren. Tatsächlich ist das NAND-Gatter dafür ausreichend.

Realisieren Sie die folgenden Gatter der Standardbibliothek (STD) nur durch Verwendung von NAND-Gattern:

  • AND
  • NOT
  • OR
  • NOR (negiertes OR)
  • XOR
  • XNOR (negiertes XOR)

Die Kosten für die Realisierung eines Gatters dürfen dabei nicht größer als 5 sein.

Achtung: Die Kostenfunktionen kommen erst Montag dran (k331, Folie 22).

Aufgabe 5 (3 + 2 + 3 Punkte)

Die Funktion sei durch ihre ON-Menge gegeben (in der Reihenfolge ):

Page 4

a)

Bestimmen Sie anhand von Karnaugh-Diagrammen die Primimplikanten.

\ 00 01 11 10
00
01
11
10

Hinweis: Es gibt mehr als 5.

b)

Bestimmen Sie die Kosten (, ) (gemäß der Vorlesung)

i) des vollständigen Polynoms (besteht aus allen Mintermen der Funktion) und
ii) des reduzierten Polynoms (besteht aus allen Primimplikanten der Funktion).

Aufgabe 6 (3 + 3 Punkte Bonus Punkte)

Sei eine boolesche Funktion. sei monoton wachsend, d.h. für und gilt:

wobei wie folgt definiert ist:

a)

Zeigen Sie: Jeder Primimplikant von enthält nur positive Literale.

Hinweis: Beweis durch Widerspruch.

b*)

Zeigen Sie: Das Minimalpolynom von ist eindeutig bestimmt.

Hinweis: Zeigen Sie, dass alle Primimplikanten wesentlich sind.

Abgabe: 12. Juni 2026, 1600