Zusammenfassung Lernzettel Grundbegriffe der Informatik WS 24/25 KIT

Mengen Alphabete , ,
Relationen und Abbildungen

Vereinigung ArB oder
"
31 2 33 v53
, , ,
4 , 53 = 31 , 2 ,
3, 4, 53 UMi
it p
1 21 ,
=
23 Mi = MeuMa
Durchschnitt An B und" 21,2 33 ~E3 4 , 53
, ,
= 333
Mi 1 = 21
,
23 Mi =
Men M
disjunkte Mengen An B = 0

Mengendifferenz AlBA ohne B" [1 2 33 153 4 53
, , ,
=
31 23 ,
,




KardinalitätIA) 131 231 + 122 331
, ,
= 2 + 2 = 4 + 3 =
131 , 2 , 331 = 131, 23022, 33/



Paar (a , b) (1 , 2) + (2 1)
,




kartesisches Produkt AxB AxB =
S(abslacA und beB3 M2 MxM = M3 MxMxM =




Allquantor V
Existenzquantor 7

M203 enthält ein Element ,
IBA =
IBIA
2 oder (M/ ((21
Potenzmenge Menge aller Teilmengen ,
2, 33) = 30, 513 323 333 , , ,
31, 23 , 31 , 33 , 32, 33, 21 , 2 ,
333


Relation RE AxB

Linkstotal FacAJbeB : (a, b)cR

rechtseindeutig VatA FbeBVbeB : wenn (a , b) eR und La , baleR ,
dann be ba =




Abbildung/Funktion Linkstotale und rechtseindeutige Relation
: R : ABADefinitionsbereich BZielbereich

partielle Funktion nicht Linkstotal :
rechtseindeutig ,
nur



Linkseindeutig Flan buleR Flaziba)ER wenn an Faz dann butb2
,
:
,



rechtstotal FbeBJacA (a :
,
b) e R


injektiv Linkseindeutig
surjektiv rechtstotal
bijektiv= injektiv + surjektiv




Wörter


Wort ist eine
Abbildung w: En A

Länge des Wortes Iw
Leere Wort
*
A Sa b3
*

Menge aller Wörter über AlphabetA A :
,
A z .B . a b
,
aa ba , aaa
,
abb ...
, ,


101 = 0 15331 1 =




Menge aller Wörter der Länge neNo A Sa , b3
= A 233 Ar da b3 Al
=
=
,
= Saa ab ba bb , , ,
...
*
A = AA vA2 ...
= UAi
itNo
Konkatenation"
"
.

(W W2l ·
·



Wg = Wn(m2 Wg) Baum Stammt Stamm Baum .
(wn Wel · =
IwnltIwal neutrales Elements w
.

z = w =
zw


I w" = n
·
In ↳ assoziativ ↳ nicht kommutativ wo = 3 w wow = Sw = w we w" w (mo. w)
= = ·
w= llg w) w) = wow

, Aussagenlogik

Jede Aussage ist entweder falsch oder wahr

Negation-P
logisches und Pr Q

Logisches oder Pr Q

logische Folgerung P - Q

Alphabet der
Aussagenlogik Aan : SC , 1 , 1
,
1 ,
r
, 30 Varaz VarazcEP, lieNo


Bindungsstärke : 1
.

.
2 1


3 . v

4. -



5 .
7x




Boolesche Funktionen B Ew f3
=
. Implikation nur f wenn P wahr Q falsch



Auswertung von Formeln val , (F) ((P) wI(Q) f
= = F = (PeQ) = /val , (F) = w




Aquivalente Formeln F = G < P = PP =
xQ = ( + PlrQP-Q = +Q- + P67H & (6-H(n(H >
-

6)
De Morgan <(PxQ) = PrzQ
: und IPrQIzaPenQ FrF=F FrFF kommutativ assoziativ Distributivgesetze
, ,



Tertium non datur GVG Exfalso quod libet FALSCH G (FH) = FraH



Interpretation I Modell von einer Formel F ,
wenn val (Fl w ist. =
,


Interpretation I Modell für Formelmenge T, wenn /Modell jeder Formel FET

Jedes Modell von Tauch Modell von F TFF

Tautologie :
wenn für jede Interpretation Modell #F Wenn G = H, dann ist GH Tantologie.
7767366-36 7666- (H >
-
6)(61H) -66666616736(6 - H) =-( H -
76) ...




erfüllbar :
wenn für mindestens ein I wahr



Beweisbarkeit im Aussagenkalkül
Axiome mit G , H ,k Formeln Axaze G + (H -
> 6)

AxAzz (G -
(H -
> ()) = ((6 - H) + (6 - k) G H G
oder MP :
H
AxAys(-H - +6) - ((H = G) - H) ↓


Schlussregel Modus Ponens MP : wir wissen G-H gilt und wir wissen
,
das 6 gilt .
Dann gilt auch H MP S(6H
.
=
,
G , H)16, HeForal


Hypothesen oder Prämissen T = ForA

Ableitung von F aus T TtF wennT= +F Fheißt Theorem


Induktion
mehrere Induktionsanfänge
starke Induktion im Induktionsschritt Benutzung aller früherer" Aussagen nicht nur von An-
An ist wahr , falls A für alle kan wahr ist" IV : A ist wahr für allekn

IA (meist n= 0

IV Für ein beliebiges aber festes ,
n-1 ENo gelte An-1
IS (n ? 1)