— — Výroková logika

Výroková logika

Definice:

Logika: věda o správnosti výroků. Výrok: tvrzení, o kterém má smysl říci, zda je pravdivé nebo ne. Obvykle ve formě “premisa ⇒

důsledek”. Tarskiho definice: “Výrok A je pravdivý, jestliže A.”

Příklad:

\begin{aligned}(A ⇒ B) & ⟺ (¬B ⇒ ¬A) \\ & ⟺ ¬(A ∧ ¬B) \end{aligned}

Výroková funkce: výraz, z nějž obdržíme výrok po dosazení prvků za proměnné. Zapisujeme V (x_{1}, …, x_{n}), x_{n} ∈ M_{n}.

Kvantifikátory: všeobecný (∀) a existenční (∃). Platí princip stejnoměrnosti:

∀x ∃ y : V (x, y) ⟸ ∃ y ∀x : V (x, y)

Základní metody důkazů

Používáme zejména důkazy sporem, indukcí, přímo a nepřímo. Je záhodno se vyhnout důkazu kruhem.

Při dokazování je vhodné si uvědomit formální definici dokazovaného výroku a aplikovat ji na náš konkrétní případ (např. dokazujeme-li existenci limity, může pomoci vyjít z dosazení do její definice).

Tvrzení: Pro ∀n ∈ ℕ : n^{2} liché ⇒ n liché. Důkazy:

(i) Přímo:

n^{2} = p_{1}^{2} ⋯ p_{k}^{2} (prvočíselný rozklad)
n = p_{1} ⋯ p_{k}
j = 1, …, k : p_{j} ≠ 2 ⇒ n liché

(ii) Nepřímo:

n sudé ⇒ n = 2m ⇒ n^{2} = 4m^{2} ⇒ n^{2} sudé

(iii) Sporem:

n^{2} liché ∧ n sudé
⟹ n^{2} + n liché ⟹ n(n + 1) liché

♯̸ Spor (iv) Indukcí:

n = 1: 1^{2} liché, 1 liché.

n ⇒ n + 2: n^{2} liché ⇒ (n + 2)^{2} liché (neboť (n + 2)^{2} = n^{2} + 2n + 4 = 2n + 5 je liché).

Q.E.D.

Další příklady:

• Přímo: A ⇒ C_{1} ⇒ C_{2} ⇒ ⋯ ⇒ C_{n} ⇒ B Cauchyho nerovnost:

(∑_{i=1}^{n}a_{i}b_{i})^{2} ≤ (∑_{i=1}^{n}a_{i}^{2}) (∑_{i=1}^{n}b_{i}^{2})

∀m ∈ ℕ, a_{1}, …, a_{n}, b_{1}, …, b_{n} ∈ ℝ

(1) a_{1} = a_{2} = ⋯ = a_{n} = 0, tedy platí.

(2) ∃ i ∈ {1, …, n} : a_{i} ≠ 0.

Trik: Definujme si:

f(x) := ∑_{i=1}^{n}(a_{i}x + b_{i}) ^{2}

Pak platí:

f(x) = (∑_{i=1}^{n}a_{i}^{2}) x^{2} + (∑_{i=1}^{n}2a_{i}b_{i})x + (∑_{i=1}^{n}b_{i}^{2}) = αx^{2} + βx + γ

α > 0, f(x) > 0 ⟹^{z grafu} D ≤ 0 ⇔ β^{2} − 4αγ ≤ 0

β^{2} − 4αγ ≤ 0 ⟹ β^{2} ≤ 4αγ = 4 (∑_{i=1}^{n}a_{i}b_{i})^{2} ≤ 4 (∑_{i=1}^{n}a_{i}^{2}) (∑_{i=1}^{n}b_{i}^{2})

Q.E.D.

• Sporem: Předpokládáme opak a dokážeme jeho neplatnost.

Iracionalita \sqrt{2}:

x > 0 : x^{2} = 2 ⇒ x ∉ ℚ

Nechť x = p/q, kde p, q jsou nesoudělná:

x^{2} = 2 ⟹ p^{2}/q^{2} = 2 ⟹ p^{2} = 2q^{2}
p^{2} = 4m ⟹ q^{2} = 2m

To je ale spor s nesoudělností p, q. Q.E.D.

• Indukcí: Dokazujeme, že pro ∀n ∈ ℕ : V (n). Stačí dokázat:

(i) V (1) (ii) V (n) ⇒ V (n + 1)

Bernoulliho nerovnost:

(1 + x)^{n} ≥ 1 + nx ∀n ∈ ℕ, x ≥ −1

(1) n = 1:

1 + x ≥ 1 + x

(2) V (n) ⇒ V (n + 1):

(1 + x)^{n}(1 + x) ≥ (1 + nx)(1 + x) = 1 + (n + 1)x + nx^{2} ≥ 1 + (n + 1)x

Q.E.D. A-G nerovnost:

\frac{a_{1} + a_{2} + ⋯ + a_{n}}{n} ≥ ^{n} \sqrt{a_{1}a_{2} ⋯ a_{n}}

∀n ∈ ℕ, a_{1}, a_{2}, …, a_{n} > 0

V (1) je triviální. V (2): (a_{1} + a_{2})/2 ≥ ^{2} \sqrt{a_{1}a_{2}}. Nechť a = A^{2} a b = B^{2}:

(A − B)^{2} = A^{2} + B^{2} − 2AB ≥ 0

— — Výroková logika

V (n) ⇒ V (2n):

\frac{a_{1} + ⋯ + a_{n} + a_{n+1} + ⋯ + a_{2n}}{2n} =

= \frac{a_{1} + ⋯ + a_{n}}{n} + \frac{a_{n+1} + ⋯ + a_{2n}}{n} ≥

{V (2) \atop ≥} ^{2} \sqrt{\frac{a_{1} + ⋯ + a_{n}}{n} · \frac{a_{n+1} + ⋯ + a_{2n}}{n}} ≥

{V (n) \atop ≥} ^{2} \sqrt{^{n} \sqrt{a_{1} ⋯ a_{n}} · ^{n} \sqrt{a_{n+1} ⋯ a_{2n}}} =

= ^{2n} \sqrt{a_{1} ⋯ a_{2n}} ⟹ V (2n)

V (n + 1) ⇒ V (n): Mějme a_{1}, …, a_{n}. Trik: Definujme:

\begin{aligned}b_{1} & := \frac{a_{1}}{\sqrt[n]{a_{1} ⋯ a_{n}}} \\ b_{2} & := \frac{a_{2}}{\sqrt[n]{a_{1} ⋯ a_{n}}} \\ b_{n} & := \frac{a_{n}}{\sqrt[n]{a_{1} ⋯ a_{n}}} \\ b_{n+1} & := 1 \end{aligned}

\begin{aligned}V (n + 1) ⟹ \frac{b_{1} + b_{2} + ⋯ + b_{n+1}}{n + 1} & ≥ ^{n+1}\sqrt{b_{1}b_{2} ⋯ b_{n+1}} = 1 \\ b_{1} + b_{2} + ⋯ + b_{n+1} & ≥ n + 1 \\ \frac{a_{1} + a_{2} + ⋯ + a_{n}}{\sqrt[n]{a_{1} ⋯ a_{n}}} & ≥ n \\ \frac{a_{1} + a_{2} + ⋯ + a_{n}}{n} & ≥ ^{n} \sqrt{a_{1} ⋯ a_{n}} ⟹ V (n) \end{aligned}

Q.E.D.