Logik und Formalisierung von Modellen Flashcards
Was bedeutet Erfüllbarkeit in der Aussagenlogik?
Eine Formel ist erfüllbar wenn es eine Bewertung der Formel (true/false) gibt.
Was bedeutet tautologisch in der Aussagenlogik?
Eine Formel ist tautologisch/allgemeingültig, wenn die Formel für jede Bewertung wahr ist.
Was bedeutet widerspruchsvoll in der Aussagenlogik?
Eine Formel ist widerspruchsvoll/unerfüllbar, wenn die Formel für jede Bewertung falsch ist.
Was bedeutet falsifizierbar in der Aussagenlogik?
Eine Formel ist falsifizierbar, wenn es für die Formel eine Bewertung gibt, deren Wert falsch ist.
Welche Operatoren gibt es in der Aussagenlogik?
- NICHT: Es regnet nicht. ¬R
- ODER: Es regnet oder die Straße ist nass. R ∨ S
- UND: Es regnet und die Straße ist nass. R ∧ S
- WENN/DANN: Wenn es regnet, ist die Straße nass. R → S
- GENAU WENN/DANN: Genau dann, wenn es regnet, ist die Straße nass. R ↔ S
- ENTWEDER/ODER: Entweder die Straße ist nass, oder es regnet. (R ∨ S) ∧ (¬R ∨ ¬S)
Wofür wird DEVS angewendet?
DEVS oder DES (discrete event simulation) wird zur Formalisierung und Modellierung ereignisbasierter diskreter Systeme verwendet.
Es können sowohl gekoppelte als auch atomare Modelle beschrieben werden.
Welche grundlegenden Bestandteile hat ein atomates Modell in DEVS?
AM = (X, Y, S, δint, δext, ta, λ)
- 7-er Tupel
- Bestmöglich mit hoher Kohäsion
X: Eingabemenge
Y: Ausgabemenge
S: Menge der Zustände
ta: S → R+: Zeitschrittfunktion, die jedem Zustand eine Zeitspanne assoziiert, in der der Zustand von alleine bestehen bleibt, bevor ein interner Zustandsübergang ausgelöst wird
δint : S → S: interne Übergangsfunktion auf Basis der Zeitspanne
δext : Q × X → S: externe Übergangsfunktion, getriggert durch äußere Ereignisse
λ : S → Y: Ausgabefunktion
Welche grundlegenden Bestandteile hat ein atomares Modell in PDEVS?
PDEVS - AM = (X, Y , S, ta, δint , δext , δcon, λ)
- 8-er Tupel
- Erweiterung von DEVS um gleichzeitig stattfindende Ereignisse
X: Eingabemenge
Y: Ausgabemenge
S: Menge der Zustände
ta: S → R+: Zeitschrittfunktion, die jedem Zustand eine Zeitspanne assoziiert, in der der Zustand von alleine bestehen bleibt, bevor ein interner Zustandsübergang ausgelöst wird
δint : S → S: interne Übergangsfunktion auf Basis der Zeitspanne
δext : Q × X → S: externe Übergangsfunktion, getriggert durch äußere Ereignisse
δcon: konfluente Übergangsfunktion, wird ausgeführt, wenn δint und δext auf gleichem Zeitpunkt liegen, durch Parallelität wird keine Select Funktion benötigt
λ : S → Y: Ausgabefunktion
Welche grundlegenden Bestandteile hat ein gekoppeltes Modell in DEVS?
CM = (X, Y, D, Md. EIC, EOC, IC, Select)
- 8-er Tupel
- welche Unterkomponenten gehören zum System und wie sind sie miteinander verbunden
- haben keinen internen Zustand, jeder ergibt sich aus der Menge aller Zustände aus den Subsystemen
X: Eingabemenge
Y: Ausgabemenge
D: Menge der Namen der Komponenten
M(d): DEVS-Modell als Bestandteil des gekoppelten Modells
EIC: Menge der externen Eingabekopplungen
EOC: Menge der externen Ausgabekopplungen
IC: Menge der internen Kopplungen
Select: 2^D → D: die Funktion, die bestimmt, welche der Komponenten Priorität hat, wenn mehrere Komponenten ein internes Ereignis ausführen wollen
Inwiefern unterscheiden sich atomare und gekoppelte Modelle?
Atomare Modelle zeigen ein System stets in einem bestimmten Zustand.
Gekoppelte Modelle haben keinen eigenen Zustand, dieser ergibt sich aus der Menge aller Zustände der Kindmodelle.
In beiden Fällen können die Folgezustände sicher berechnet werden.
Welche Vor- und Nachteile besitzt das klassische DEVS?
Vorteile:
- Ermöglicht die Modellierung und Simulation komplexer Systeme
- Längere Abläufe können in kurzer Zeit simuliert werden
- Genaue Berechenbarkeit der Zustände
Nachteile:
- Parallele Ereignisse können nur sequenziell ausgeführt werden
- Statische Struktur erlaubt keine Veränderung der Modellbestandteile, wenn sich das Modell verändert/es fortgeschrieben wird
=> Für die Nachteile gibt es jeweils entsprechende Erweiterungen des DEVS
Inwiefern unterscheidet sich PDEVS von DEVS?
PDEVS ermöglicht grundsätzlich die parallele Zustandsänderung.
Daher wird aus der Eingabemenge X statt einer Menge an Zuständen nun eine Menge aus Tupeln von Eingabeort p und Eingabewert v.
Parallel dazu wird aus der Ausgabemenge Y eine Menge aus Tupeln von Ausgabeort und Ausgabewert.
Entscheidend ist, dass die vergangene Zeit im PDEVS immer kleiner ist als die Summe der Zeitspannen einzelner Zustände. Ohne die parallele Verarbeitung kann sie zwar kleiner sein, kann aber auch der Summe entsprechen.
Was sind die grundlegenden Bestandteile eines zellulären Automaten?
L: d-dimensionaler Zellraum => L ist eine Menge an homogen über den Raum verteilter Zellen (Zellen sind also gleichmäßig angeordnet).
Nb(r): Liste der Nachbarn einer Zelle r, wobei b die Nummer im Koordinatensystem darstellt
S: endlicher Zustandsraum
G: aktueller Zustand des zellulären Automaten
Ginit: initialer Zustand des zellulären Automaten
R: Zustandsüberführungsregel
Wie funktioniert ein zellulärer Automat?
Zunächst werden für jede Zelle im Zellraum L alle Nachbarn betrachtet. Dann werden entsprechend der Zustandsübergangsregel (z.B. wenn 4 deiner 8 Nachbarn weiß sind, werde schwarz) alle Zellen quasi vorgemerkt und im letzten Schritt alle Zellen gleichzeitig auf ihren neuen Zustand geschaltet.
Was sind die Vor- und Nachteile eines zellulären Automaten?
Vorteile:
- Modellierung räumlich diskreter Systeme mit n Dimensionen möglich
- Modellierung teilweise komplexer biologischer oder chemischer Systeme möglich
Nachteile:
- Oft aufwendige Initialisierung der Dimensionen (jeder Zellzustand muss bei Simulationsbeginn bekannt sein)
- Simulation terminiert nicht zwangsläufig
- Statisch (zwar ändert sich der Zellraum fortlaufend, aber die Regeln verändern sich nicht)
Wie ist ein Petrinetz formell definiert?
Petrinetze sind gerichtete, bipartite Graphen.
Petrinetze haben 2 verschiedene Arten von Knoten - Stellen und Transitionen.
Ein Netz ist dabei definiert als ein Tripel aus Stellen, Transitionen und Flussrelationen:
N = (S, T, F)
S und T zusammen dürfen dabei nicht leer sein. F ergibt sich als Teilmenge der Wertepaare S x T und T x S => es kann nicht mehr Flussrelationen geben als Knoten Beziehungen zueinander haben.
Zusätzlich dazu gibt es noch Kantengewichte W für jede Flussrelation F, Kapazitäten K für jede Stelle S und jede Transition T und eine Anfangsmarkierung M0
