|
Logik |
|
WAHR |
FALSCH |
|
| (A
\/ ¬B) besitzt den Werteverlauf 1011 |
|
x |
|
| Die
Wahrheitsfunktion Φ62 besitzt den Werteverlauf
0111 |
Richig
ist 1010 |
|
x |
| (A <-> ¬B)
ist äquivalent zu (¬A
<-> B) |
beide Formeln liefern die boolesche
"Antivalenz" |
x |
|
| (A
\/ ¬B) ist äquivalent zu (A --> B). |
|
|
x |
| ((A
/\ B) -> C) folgt logisch aus ((A \/ B) -> C). |
|
x |
|
| ((A
/\ B) \/ C) folgt logisch aus ((A \/ B) /\ C). |
|
x |
|
| {B,
¬A} ist ein Resolvent von {¬A, ¬B} und {A, B}. |
|
|
x |
| {A,
B, ¬C} ist ein Resolvent von {A,¬A, ¬C} und {A, B}. |
|
x |
|
| Die
aussagenlogische Formeln ((A /\ B) \/ (B /\ ¬C))
besitzt die kanonische disjunktive Normalform ((A /\
B /\ C) \/ (A /\ B /\ ¬C)) |
|
|
x |
| Die
Formel ((A /\ B) \/ C) ist in konjunktiver Normalform. |
|
|
x |
| Die aussagenlogische Formel (F -> (F ->
G)) ist ein Axiom im Hilbert-Kalkül. |
(F -> (G -> F) wäre das Axiom
"Prämissenverschmelzung" |
|
x |
| Gilt |= (F
/\ G), so gilt auch |= F und |= G. |
eine Tautologie, denn wegen der Konjunktion
müssen F und G mit 1 belegt sein. |
x |
|
| Gilt |= (F
\/ G), so gilt auch |= F und |= G. |
in der Disjunkton ist es ausreichend,
wenn nur eine der beiden Formeln mit 1 belegt ist. Es gilt z.B.
|= F und |=/= G. |
|
x |
| ¬P(x)
bedeutet: Das Prädikat P trift auf x nicht zu. |
|
x |
|
| (¬\-/xP(x)
\/ [es existiert]xP(x)) ist eine Aussage im prädikatenlogischen
Sinn. |
es liegt eine
Aussage vor wenn die Formel geschlossen ist, d.h. es kommen keine freien
Variablen vor. |
x |
|
| (R(x) /\ [es existiert]xS(x))[x/a] = |
richtig: (R(a) /\ [es existiert]aS(a)) |
|
x |
| Die
prädikatenlogische Struktur A mit UA = |N und PA
= |N passt zur Formel (¬\-/xP(x) \/ es existiert ein
xP(a)). |
|
|
x |
| P(h(x)),y) und P(z,g(b)) sind unifizierbar. |
|
x |
|
| {a}ist
das Herbrand-Universum zur prädikatenlogischen Formel {{P(f(x))},{Q(y)}}. |
|
|
x |
| [z/x][y/h(a)]
ist ein allgemeinster Unifikator der Menge von Literalen {T(x,y),
T(z,h(u))} |
|
|
x |
| {{A,C},
{¬C}, {¬A}, ¤} ist eine Deduktion der leeren Klausel |
|
|
x |
| (
\-/X gilt P(x) \/ es existiert ein x ¬P(x)) ist erfüllbar. |
|
x |
|
| Im
Resolutionskalkül gibt es keine Axiome. |
|
x |
|
| Bei
einer N-Resolution muss eine Elternklausel negativ sein. |
|
x |
|
| ((es
existiert ein)xP(x) /\ Q(x)) befindet sich in bereinigter Pränexform. |
|
|
x |
| PROLOG-Programme
verwenden die Tiefensuche. |
|
x |
|
| In PROLOG gilt: [a,b,[c,d]].=[a|[b,c,d]]. |
|
|
x |
| In
PROLOG wird ein Datentyp nicht explizit überprüft. |
|
x |
|
| Das built-in-Prädikat fail
führt in PROLOG-Programmen zum sofortigen Abbruch
der Rechnung. |
|
|
x |
| Das
PROLOG-Programm
/*(1)*/ stop(X):-stop(Y).
/*(2)*/ stop(X).
stoppt zur Zielklausel ?-stop(Z). nie. |
|
x |
|
| |
|
|
|
| Theorie
1 |
|
|
|
| |
|
|
|
| L
* Ø = {ε} * L. |
|
|
x |
| Sei
A ein NEA mit n Zuständen. Wenn B der minimale DEA
ist mit L(A)=L(B), dann hat B maximal n2 Zustände. |
B
hat maximal 2n Zustände |
|
x |
| Zu
jedem DEA gibt es einen äquivalenten DEA
mit genau einem Endzustand. |
|
|
x |
| Für jede reguläre Menge
gibt es einen DEA mit nur einem akzeptierten Endzustand. |
|
|
x |
| Seien A1 und A2 vollständige
DEAs mit n1 bzw. n2 Zuständen. Der minimale
DEA für das Komplement von[L(A1) geschnitten mit
L(A2)] hat höchstens n1 * n2 Zustände. |
|
x |
|
| L(
(a*b)+) = L( (a+b)*b ). |
|
|
x |
| Seien L1, L2 echte
Teilmengen von Sigma* und regulär. Dann ist auch {uv
aus Sigma* | u aus L1 oder v aus L2}regulär. |
|
x |
|
| {
anbm | es existiert ein k aus der Menge der
ganzen Zahlen: n – m = k * 2002 } ist regulär. |
|
x |
|
| {
anbm | n ist äquivalent zu „m
mod 3“} ist regulär. |
|
x |
|
| L((ab)*(a*
+ b*)) geschnitten mit der Menge {w aus {a,b}* | |w|b
> |w|a} ist regulär. |
|
x |
|
| {w
sei aus {a}* | w=wR} ist nicht regulär. |
|
|
x |
| Sei n eine natürliche Zahl. Die Sprache
{anbn} ist nicht regulär. |
|
|
x |
| Zu jeder nicht-regulären determistisch
kontextfreien Sprache L gibt es nicht-reguläre dkf
Sprache L' mit der Eigenschaft: "L vereinigt mit L'
ist regulär". |
|
x |
|
| Sei
h: {a, b}* -> {0, 1}* ein Homomorphismus mit h(a) = 01 und h(b)
= 0. Dann ist h-1(L( (10+1)*) ) = {an | n
>= 0}. |
|
|
x |
| Sei
G eine kontextfreie Grammatik in Chomsky-Normalform. Dann besteht
jede Ableitung eines Wortes w aus der Sprache L(G) (die ohne das
leere Wort) aus genau 2 * |w| Ableitungsschritten. |
|
|
x |
| Zu
jeder kontextfreien Sprache L gibt es einen (mit leerem
Keller akzeptierenden) Kellerautomaten A mit L(A) = L
mit genau einem Zustand. |
|
x |
|
| Jede
reguläre Sprache ist eine eindeutig kontextfreie
Sprache. |
|
x |
|
| Sprachen,
deren Komplement endlich ist, sind kontextfrei. |
|
x |
|
| Sei
L kontextfrei und w aus L. Dann ist L \ {w}
kontextfrei. |
|
x |
|
| Die Sprache
{aibuvbi | u=u^rev, v=v^rev, i aus |N} ist kontextfrei. |
|
x |
|
| Die Sprache
{aibjckdl | (i=j /\ k=l) \/
(i=l /\ j=k)} ist kontextfrei. |
|
x |
|
| {aibjck
| i != j und j != k} ist kontextfrei. |
|
|
x |
| Die
Klasse aller nicht regulären Sprachen ist abgeschlossen unter
Komplementbildung. |
|
x |
|
| Das
Komplement der Menge {an bn cn |
n ist aus |N} ist kontextfrei. |
|
x |
|
| Sei
L = {an bn cn | n >= 0}. Dann
gilt { v ist aus {a,b,c}* | ab5c7v ist aus L}=
{ v ist aus {a,b,c}* | a7b5cv ist aus L}. |
|
x |
|
| Wenn
R regulär und |R| unendlich ist, dann
existiert ein L als echte Teilmenge von R mit: L
ist nicht rekursiv aufzählbar. |
weil
|L| auch unendlich ist |
x |
|
| Eine Sprache L ist endlich
gdw. alle Teilmengen von L entscheidbar sind. |
|
x |
|
| Eine Sprache L ist endlich
gdw. alle Teilmengen von L rekursiv aufzählbar sind. |
|
x |
|
| L((a*b*)*)
= L((ab* + b*a)*). |
|
|
x |
| Alle Sprachen sind vom Typ 0. |
Gegenbeispiel: das Komplement des Halteproblems |
|
x |
| |
|
|
|
| Theorie
2 |
|
|
|
| |
|
|
|
| A
<= B und B rekursiv aufzählbar => A ist entscheidbar. |
|
|
x |
| {
<M> | M ist Turingmaschine und L(M) geschnitten mit {a}*
= Ø } ist rekursiv aufzählbar. |
|
|
x |
| {<M1, M2>
| M1 und M2 sind Turingmaschinen
mit L(M1) geschnitten L(M2) != Ø}
ist rekursiv aufzählbar. |
|
x |
|
| Wenn A eine echte Teilmenge von B ist und
B rekursiv aufzählbar, dann ist auch A rekursiv aufzählbar. |
|
|
x |
| Wenn
A und B NP-vollständig sind, dann auch A disjunkt B. |
|
|
x |
| Es gibt eine kontextsensitive Sprache die
NP-vollständig ist. |
|
x |
|
| Die
Sprache { <M,x,s> | Turingmaschine M hält auf Eingabe
x nach maximal s Schritten } ist entscheidbar. |
|
x |
|
| {n ist eine natürliche Zahl
| jede Turingmaschine M terminiert bei Eingabe n} ist entscheidbar. |
das Wortproblem (Enthaltenseinproblem)
ist auf reguläre Mengen entscheidbar. |
x |
|
| Wenn L eine echte Teilmenge von Sigma* entscheidbar
ist, dann ist auch {u | [es existiert]v aus Sigma*: uv ist in L}entscheidbar. |
|
|
x |
| Seien A,B echte Teilmengen aus Sigma*. Ist
B regulär und kann A in Polynomialzeit auf B reduziert
werden, so ist auch A regulär. |
|
|
x |
| Wenn P!=NP, dann kann jede Sprache
in NP durch eine deterministische Turing-Maschine erkannt werden. |
|
x |
|
| KF
= P |
|
|
x |
| Die
Menge {a^2n | n >= 1} ist aus P. |
|
x |
|
| {T | T ist die Multiplikaionstabelle einer
kommutativen endlichen Gruppe} ist in P. |
|
x |
|
| P
geschnitten mit NP = Ø |
|
|
x |
| KF
geschnitten co-KF ist keine echte Teilmenge von KF, wobei KF = Klasse
der kontextfreien Sprachen, co-KF = { L | „L quer“
ist aus KF}). |
|
x |
|
| Die Klasse der Typ-0 Sprachen
ist disjunkt zur Klasse der Typ-1 Sprachen. |
|
|
x |
| Wenn
L1 und L2 nicht entscheidbar
sind, dann ist auch nicht L1 geschnitten L2
entscheidbar. |
|
|
x |
| Wenn
L nicht entscheidbar, dann sind L und „L
quer“ (das Komplement von L) nicht aufzählbar. |
|
|
x |
| Jede
entscheidbare Sprache lässt sich auf das Halteproblem
reduzieren. |
|
x |
|
| Sei
L = {a} und H das Halteproblem. Dann gilt L
<=p H. |
|
|
|
| ENT
\ KS = Ø, wobei ENT bzw. KS = Menge der entscheidbaren bzw.
kontextsensitiven Sprachen |
|
|
x |
| Für
jede totale primitiv rekursive Funktion f ist auch μ f total. |
|
|
x |
| Sei
P != NP. Dann ist die Sprache { F | F ist erfüllbare aussenlogische
Formel über den Variablen x1, ..., x99}
NP-vollständig. |
|
|
x |
| {(an
bn cn)n | n >= 1} ist kontextsensensitiv. |
|
x |
|
| Die
Menge {<G, w> | G kontextfreie Grammatik, w aus Σ*,
w aus L(G)} ist aus P. |
|
x |
|
| |
|
|
|
| Diskrete
Mathematik |
|
|
|
| |
|
|
|
| Der
vollständige Graph mit 6 Knoten ist planar. |
|
|
x |
| Z/4Z
× Z/9Z ist eine zyklische Gruppe. |
|
x |
|
| Wenn
G eine abelsche Gruppe ist und H eine Untergruppe von G,
dann ist G/H ebenfalls eine Gruppe. |
|
x |
|
| Es
gibt Körper mit 6 Elementen. |
|
|
x |
| Wenn
K ein Körper ist, dann ist auch K[x], die Menge der Polynome
in der Variablen x über K, ein Körper. |
|
|
x |
| Kombinatorik:
(n über (k+1) = ( (n-1) über k) + (n über k). |
|
|
x |
| Halbgruppen
können mehrere rechtsneutrale Elemente haben. |
|
x |
|
| {(x,y)
| x,y aus der Menge der ganzen Zahlen, x – y gerade} ist eine Äquivalenzrelation. |
|
x |
|
| Für
alle n >= 2 existiert ein Monoid M mit n Elementen. |
|
x |
|
| In jedem Monoid M gilt:
\-/a,b,c aus M: ac=bc => a=b |
c ist ein rechtsneutrales Element |
x |
|
| Seien
V1, V2 Teilmengen von V und (V1, E1),
(V2, E2) zwei Bäume. Dann ist auch (V1
disjunkt V2 , E1 disjunkt E2) ein
Baum. |
|
|
x |
| Die
Eulerformel lässt sich auf alle bipartiten Graphen
anwenden. |
|
|
x |
| In
jedem Ring gilt: \-/a,b aus |R: (a+b)(a-b) = a2 - b2 |
|
|
x |
| Wenn I und J Ideale eines Rings
R sind, dann ist auch I vereinigt J ein Ideal von
R. |
|
|
x |
| Eine
Gruppe G, in der für jedes Element die Beziehung a2
= a gilt, ist endlich und kommutativ. |
|
x |
|
| Seien G und H endliche Gruppen.
Wenn |G|=|H|, dann sind G und H isomorph. |
|
|
x |
| In jeder Gruppe G gilt:
\-/a,b in G und \-/ganze Zahlen n: (ab)n
= an bn. |
|
|
x |
| Für
jede Menge M ist (2M, Schnittoperator, M) ein
Monoid. |
|
x |
|
| Sei
M eine endliche Menge, |M| gerade und R eine Teilmenge aus dem
kartesischen Produkt M × M eine Äquivalenzrelation.
Dann ist |R| gerade. |
|
x |
|
| Sei G=(V,E) ein Graph. Dann
ist E eine Äquivalenzrelation. |
|
|
x |
| Das
erzeugende Element einer zyklischen Gruppe ist eindeutig. |
|
|
x |
| Eine zyklische Gruppe von
Primzahlordnung hat p-1 Erzeuger. |
|
x |
|
| Auf
jeder nicht-leeren Menge M lässt sich eine assoziative
Verknüpfung ° : M × M --> M
definieren. |
|
x |
|
| Sei
(M, +. *, 0, 1) ein Körper. Dann ist (M, *, 1) eine Gruppe. |
|
|
x |
| Jeder endlicher Graph, bei
dem jeder Knoten den Grad 2 hat, kann in die Ebene eingebettet
werden. |
|
x |
|
| K7,9 besitzt ein Matching
mit 7 Kanten. |
|
x |
|
| Der
Graph K2,3 besitzt einen Eulerweg. |
|
x |
|
| Die Anzahl der Wörter
der Länge 19 über dem Alphabet {a, b, c} ist 193. |
|
|
x |
| Seien a,b ganze Zahlen.Dann teilt ggT(a,b)
jeden Teiler von a. |
|
|
x |
| In
der λ-Notation gilt: [(λh.h + h)(λh.h +1)](3)
= (λs.2s)(5). |
|
|
x |
| |
|
|
|
Volker Ziesing | © Mathlab.de | Impressum