> Wenn die linke Seite vom Implikationszeichen war ist dann ist auch die rechte wahr
Für gültige Implikationen ist das so laut Definition der Implikation. Deine Aufgabe ist, herauszufinden ob die Implikation
f(n) = Ω(g(n)) ∧ g(n) = Ω(h(n)) ⇒ f(n) = Ω(h(n))
gültig ist oder nicht, und deine Entscheidung zu begründen.
Der Beweis von
f(n) = Ω(g(n)) ∧ g(n) = Ω(h(n)) ⇒ f(n) = Ω(h(n))
beginnt meisten mit den Worten "Seien f, g, h Funktionen, so dass f(n) = Ω(g(n)) ∧ g(n) = Ω(h(n)) gilt." Dann wird die Definition von Ω herangezogen um zu schlussfolgern, dass auch f(n) = Ω(h(n)) gilt.
Die Wiederlegung von
f(n) = Ω(g(n)) ∧ g(n) = Ω(h(n)) ⇒ f(n) = Ω(h(n))
verläuft meistens so, dass konkrete Funktionen f, g und h angegeben werden, so dass f(n) = Ω(g(n)) ∧ g(n) = Ω(h(n)) gilt, aber f(n) = Ω(h(n)) nicht gilt.
