{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DS 22 – Karnaugh-Veitch-Diagramme und Minimierung\n",
    "**Informatik 10 – MINT-Zweig | Informatiksysteme**\n",
    "\n",
    "## Lernziel\n",
    "Ich vereinfache die DNF (mit bis zu vier Variablen) mithilfe von Karnaugh-Veitch-Diagrammen."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "sprachhilfe"
    ]
   },
   "source": [
    "## 🗣️ Sprachhilfe\n",
    "- „Für die Eingangswerte … liefert die Schaltung den Ausgangswert …“\n",
    "- „Der Term/die Tabelle repräsentiert die Schaltung, weil …“\n",
    "- „Die Rückkopplung bzw. Gruppierung bewirkt …“"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 📌 Merksätze\n",
    "\n",
    "- Ein **Karnaugh-Veitch-Diagramm (KV-Diagramm)** ordnet alle Belegungen so in einem Raster an, dass sich **benachbarte Felder nur in genau einer Variablen** unterscheiden.\n",
    "- Ziel: Benachbarte `1`-Felder werden zu **Blöcken** der Größe 1, 2, 4, 8 ... zusammengefasst. Je größer der Block, desto **weniger Variablen** braucht der zugehörige Term.\n",
    "- Innerhalb eines Blocks fällt jede Variable weg, die sowohl **negiert als auch nicht-negiert** vorkommt – übrig bleiben nur die Variablen, die im gesamten Block **konstant** sind.\n",
    "- Das KV-Diagramm liefert so eine **minimierte DNF**, die zur ursprünglichen DNF **äquivalent**, aber kürzer ist – wichtig für **kostengünstigere Schaltungen** (weniger Gatter)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 💡 Beispiel: Minimierung von Hand\n",
    "Belegungstabelle mit den `1`-Zeilen `A=0,B=0` und `A=0,B=1`:\n",
    "\n",
    "DNF: `(¬A ∧ ¬B) ∨ (¬A ∧ B)`\n",
    "\n",
    "Im KV-Diagramm liegen beide Felder nebeneinander (beide mit `A=0`) → sie lassen sich zu einem Block zusammenfassen, in dem `B` wegfällt:\n",
    "\n",
    "**Minimierte Form:** `¬A`\n",
    "\n",
    "Das lässt sich leicht mit Python nachprüfen – beide Terme müssen für alle Belegungen denselben Wert liefern:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import product\n",
    "\n",
    "def unminimiert(a, b):\n",
    "    return (not a and not b) or (not a and b)\n",
    "\n",
    "def minimiert(a, b):\n",
    "    return not a\n",
    "\n",
    "for a, b in product([0, 1], repeat=2):\n",
    "    print(a, b, unminimiert(a, b) == minimiert(a, b))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 📝 Übung 1 – KV-Diagramm zeichnen und minimieren\n",
    "Gegeben ist folgende Belegungstabelle für drei Variablen:\n",
    "\n",
    "| A | B | C | Ausgang |\n",
    "|---|---|---|---|\n",
    "| 0 | 0 | 0 | 1 |\n",
    "| 0 | 0 | 1 | 1 |\n",
    "| 0 | 1 | 0 | 0 |\n",
    "| 0 | 1 | 1 | 0 |\n",
    "| 1 | 0 | 0 | 1 |\n",
    "| 1 | 0 | 1 | 1 |\n",
    "| 1 | 1 | 0 | 0 |\n",
    "| 1 | 1 | 1 | 0 |\n",
    "\n",
    "1. Zeichnet auf Papier ein KV-Diagramm und findet die größtmöglichen Blöcke.\n",
    "2. Notiert die minimierte Form.\n",
    "3. Überprüft eure minimierte Form mit Python gegen die unminimierte DNF."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def unminimiert_a(a, b, c):\n",
    "    return ((not a and not b and not c) or (not a and not b and c) or\n",
    "            (a and not b and not c) or (a and not b and c))\n",
    "\n",
    "# TODO: Übung 1 - eure minimierte Form hier eintragen\n",
    "def minimiert_a(a, b, c):\n",
    "    pass\n",
    "\n",
    "for a, b, c in product([0, 1], repeat=3):\n",
    "    print(a, b, c, \"->\", unminimiert_a(a, b, c) == minimiert_a(a, b, c))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 📝 Übung 2 – Von der Alarmanlage zurück zur Minimierung\n",
    "Erinnert euch an die Alarmanlage aus DS 16: `Alarm = (Tuer ∧ Scharf) ∨ Rauch`.\n",
    "Ist dieser Term bereits minimal, oder lässt er sich mit einem KV-Diagramm weiter vereinfachen? Begründet eure Antwort in Worten (kein Python nötig)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*(Eure Begründung hier)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 🚀 Zusatzaufgabe – Vier Variablen\n",
    "Erstellt selbst eine Belegungstabelle mit **vier** Variablen (`A, B, C, D`) und mindestens vier `1`-Zeilen, die sich zu einem einzigen Block zusammenfassen lassen. Prüft eure Minimierung mit Python."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO (freiwillig): eigene 4-Variablen-Belegungstabelle + Minimierung\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.11"
  },
  "v3_revision": {
   "basis": "MINT-Lehrplan Informatik 10 (2026)",
   "didaktik": "fragend-entwickelnder Kern, kurzer Transfer, flexible Reserve",
   "lerngruppe": "11 SuS"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
