Výroková logika a kvantifikatory

Řešení příkladu:

Výrok: „Všichni studenti odevzdali domácí úkol.“ lze zapsat pomocí kvantifikátoru jako: \( \forall x \in S: O(x) \), kde \( S \) je množina všech studentů a \( O(x) \) znamená „x odevzdal úkol“.

Negace výroku je: \( \neg (\forall x \in S: O(x)) \equiv \exists x \in S: \neg O(x) \)

Česky: „Existuje student, který neodevzdal domácí úkol.“

Řešení příkladu:

Výrok má tvar implikace: \( A \Rightarrow B \)

\( A: \) Číslo \(4\) je sudé — pravda.

\( B: \) Číslo \(7\) je prvočíslo — pravda.

Celá implikace \( A \Rightarrow B \) je pravdivá, pokud platí \(A\) i \(B\). Tedy výrok je pravdivý.

Řešení příkladu:

Označme: \( E(x): x \text{ je sudé} \), \( D(x): x \text{ je dělitelné třemi} \)

Výrok: \( E(x) \land D(x) \)

Například pro \( x = 6 \): platí obě podmínky, výrok je pravdivý.

Řešení příkladu:

Označme \( F \) množinu květin, \( C(x) \): „x je červená“.

Výrok: \( \exists x \in F: C(x) \)

Česky: Existuje alespoň jedna květina, která je červená.

Řešení příkladu:

\( A: 5 \text{ je liché} \) — pravda

\( B: 8 \text{ je prvočíslo} \) — nepravda

Impkace \( A \Rightarrow B \) je nepravdivá pouze v případě, že \( A \) je pravda a \( B \) nepravda. Tedy výrok je nepravdivý.

Řešení příkladu:

Výrok: \( \exists x \in \mathbb{Z}: Z(x) \land S(x) \), kde \( Z(x) \) je „x je záporné“ a \( S(x) \) je „x je sudé“.

Negace: \( \neg (\exists x: Z(x) \land S(x)) \equiv \forall x: \neg(Z(x) \land S(x)) \)

Pomocí De Morganova pravidla: \( \forall x: \neg Z(x) \lor \neg S(x) \)

Česky: „Pro všechna čísla platí, že nejsou záporná nebo nejsou sudá.“

Řešení příkladu:

A | B | ¬A | B ∧ ¬A | A ∨ (B ∧ ¬A)
-------------------------------
0 | 0 | 1  |   0    |     0
0 | 1 | 1  |   1    |     1
1 | 0 | 0  |   0    |     1
1 | 1 | 0  |   0    |     1
  

Řešení příkladu:

Výrok: \( \forall x \in \mathbb{R}: x^2 \geq 0 \)

Česky: Pro všechna reálná čísla platí, že jejich druhá mocnina není záporná.

Výrok je pravdivý, protože druhá mocnina jakéhokoliv reálného čísla je vždy nezáporná.

Řešení příkladu:

A | B | ¬A | A ⇒ B | ¬A ⇒ (A ⇒ B)
-------------------------------
0 | 0 | 1  |   1   |     1
0 | 1 | 1  |   1   |     1
1 | 0 | 0  |   0   |     1
1 | 1 | 0  |   1   |     1
  

Výrok je pravdivý ve všech případech, tedy se jedná o tautologii.

Řešení příkladu:

Označme: \( C \) — množina lidí, \( K \) — množina knih, \( M(x, y): x \text{ vlastní knihu } y \)

Výrok: \( \forall x \in C: \exists y \in K: M(x, y) \)

Česky: Každý člověk má alespoň jednu knihu.

Řešení příkladu:

\( A: x \text{ je dělitelné 6} \) — pravda (pokud \( x \) je dělitelné 6, je zároveň dělitelné 2)

\( B: x \text{ je dělitelné 2} \) — pravda.

Celá implikace \( A \Rightarrow B \) je pravdivá.

Řešení příkladu:

Výrok: \( \forall x \in \mathbb{R}: (x > 5) \lor (x < -3) \)

Česky: Pro všechna reálná čísla platí, že x je buď větší než \(5\), nebo menší než \(-3\).

Řešení příkladu:

Výrok je pravdivý, protože všechny prvočísla jsou větší než \(1\) (prvočíslo je definováno jako číslo větší než \(1\), které má pouze dva dělitele: \(1\) a sebe).

Řešení příkladu:

Označme \( Q \) množinu čtverců, \( M(x) \): „x je modrý“.

Výrok: \( \exists x \in Q: M(x) \)

Česky: Existuje alespoň jeden čtverec, který je modrý.

Řešení příkladu:

Výrok: \( \forall x \in Z: N(x) \), kde \( N(x) \) znamená „x má čtyři nohy“ a \( Z \) je množina všech zvířat.

Negace: \( \neg (\forall x \in Z: N(x)) \equiv \exists x \in Z: \neg N(x) \)

Česky: „Existuje zvíře, které nemá čtyři nohy.“

Řešení příkladu:

Výrok: \( \forall n \in \mathbb{N}: (E(n) \Rightarrow E(n^2)) \), kde \( E(n) \) znamená, že \( n \) je sudé.

Česky: Pro každé přirozené číslo \( n \) platí, že pokud je \( n \) sudé, pak i \( n^2 \) je sudé.

Řešení příkladu:

Výrok: \( \forall x \in \mathbb{R}: (x > 0) \lor (x < 0) \)

Česky: Pro všechna reálná čísla platí, že x je buď kladné, nebo záporné (nula není zvažována).

Řešení příkladu:

Pokud \( x \) je pozitivní a \( y \) je negativní, pak \( x + y \) může být záporné, nula nebo kladné, v závislosti na velikosti hodnoty \( x \) a \( y \). Tedy výrok není pravdivý ve všech případech.

Řešení příkladu:

Výrok: \( \exists x \in \mathbb{R}: (x < 0) \land (x > -1) \)

Negace: \( \neg (\exists x: (x < 0) \land (x > -1)) \equiv \forall x: \neg ((x < 0) \land (x > -1)) \)

Pomocí De Morganova pravidla: \( \forall x: (x \geq 0) \lor (x \leq -1) \)

Česky: „Pro všechna čísla platí, že buď jsou větší nebo rovna 0, nebo menší nebo rovna -1.“

Řešení příkladu:

Výrok: \( \forall n \in \mathbb{Z}: (4n + 1) \mod 4 = 1 \)

Česky: Pro každé celé číslo \( n \) platí, že číslo \( 4n + 1 \) dělené 4 dává zbytek 1.

Řešení příkladu:

\( A: 5 > 3 \) — pravda

\( B: 10 \text{ není záporné} \) — pravda

Impkace \( A \Rightarrow B \) je pravdivá, pokud platí \(A\) i \(B\). Tedy výrok je pravdivý.

Řešení příkladu:

Označme: \( D_4(x): x \text{ je dělitelné 4} \), \( E(x): x \text{ je sudé} \), \( D_5(x): x \text{ je dělitelné 5} \)

Výrok: \( D_4(x) \lor (E(x) \land D_5(x)) \)

Například pro \( x = 20 \): platí první podmínka \((\)dělitelné \(4)\), výrok je pravdivý.

Řešení příkladu:

\( A: 8 \text{ je sudé} \) — pravda

\( B: 9 > 10 \) — nepravda

Impkace \( A \Rightarrow B \) je nepravdivá pouze v případě, že \( A \) je pravda a \( B \) je nepravda. Tedy výrok je nepravdivý.

Řešení příkladu:

Výrok: \( \forall x \in \mathbb{N}: x < 10 \)

Negace: \( \neg (\forall x \in \mathbb{N}: x < 10) \equiv \exists x \in \mathbb{N}: x \geq 10 \)

Česky: Existuje přirozené číslo, které je větší nebo rovno \(10\).

Řešení příkladu:

\( A: -4 \text{ je záporné} \) — pravda

\( B: 3 > -2 \) — pravda

Impkace \( A \Rightarrow B \) je pravdivá, pokud platí \(A\) i \(B\). Tedy výrok je pravdivý.

Řešení příkladu:

Výrok: \( \exists x \in \mathbb{Z}: Z(x) \land D_3(x) \), kde \( Z(x) \) je „x je záporné“ a \( D_3(x) \) je „x je dělitelné 3“.

Například pro \( x = -6 \): platí obě podmínky, výrok je pravdivý.

Řešení příkladu:

A | B | C | A ∧ B | ¬C | (A ∧ B) ⇒ ¬C
-------------------------------
0 | 0 | 0 |   0   |  1 |      1
0 | 0 | 1 |   0   |  0 |      1
0 | 1 | 0 |   0   |  1 |      1
0 | 1 | 1 |   0   |  0 |      1
1 | 0 | 0 |   0   |  1 |      1
1 | 0 | 1 |   0   |  0 |      1
1 | 1 | 0 |   1   |  1 |      1
1 | 1 | 1 |   1   |  0 |      0
  

Řešení příkladu:

Výrok: \( \forall x \in \mathbb{N}: (E(x) \lor L(x)) \), kde \( E(x) \) znamená, že \( x \) je sudé a \( L(x) \) znamená, že \( x \) je liché.

Česky: Pro všechna přirozená čísla platí, že jsou buď sudá, nebo lichá.

Řešení příkladu:

\( A: 7 > 3 \) — pravda

\( B: 12 \text{ je dělitelné 6} \) — pravda

Impkace \( A \Rightarrow B \) je pravdivá, pokud platí \(A\) i \(B\). Tedy výrok je pravdivý.

Řešení příkladu:

Označme: \( G(x): x > 5 \), \( D_2(x): x \text{ je dělitelné 2} \), \( D_3(x): x \text{ je dělitelné 3} \)

Výrok: \( \exists x: G(x) \land D_2(x) \land \neg D_3(x) \)

Například pro \( x = 6 \): výrok je nepravdivý, protože je dělitelné 3.

Řešení příkladu:

Označme \( S \) množinu studentů, \( Z(x) \): „x má zápisník“.

Výrok: \( \forall x \in S: \exists y \in Z: Z(x) \)

Česky: Každý student má alespoň jeden zápisník.

Řešení příkladu:

Označme \( S \) množinu studentů, \( P(x): x \text{ přišel pozdě} \).

Výrok: \( \exists x \in S: P(x) \)

Česky: Existuje alespoň jeden student, který přišel pozdě.

Řešení příkladu:

Označme \( x \in \mathbb{R} \), \( G(x): x > 100 \) a \( L(x): x < 200 \).

Výrok: \( \exists x \in \mathbb{R}: G(x) \land L(x) \)

Česky: Existuje číslo, které je větší než \(100\) a menší než \(200\).

Řešení příkladu:

Výrok má tvar: \( \forall x \in \mathbb{R}: (x > 0) \Rightarrow (x > -1) \)

Výrok je pravdivý, protože každé kladné číslo je větší než \(-1\).

Řešení příkladu:

Označme \( Z \) množinu zvířat v zoo, \( M(x) \): „x je savec“ a \( P(x) \): „x je pták“.

Výrok: \( \forall x \in Z: (M(x) \lor P(x)) \)

Česky: Všechna zvířata v zoo jsou buď savci, nebo ptáci.

Řešení příkladu:

Označme \( S \) množinu studentů, \( H(x): x umí hrát na klavír \).

Výrok: \( \exists x \in S: H(x) \)

Česky: Existuje alespoň jeden student, který umí hrát na klavír.

Řešení příkladu:

Označme \( n \in \mathbb{N} \), výrok bude: \( \forall n \in \mathbb{N}: n + 1 > n \)

Česky: Pro všechna přirozená čísla platí, že \(n + 1\) je větší než \(n\).

Řešení příkladu:

Označme \( x \in \mathbb{R} \), \( Z(x): x \text{ je záporné} \), \( K(x): x \text{ je kladné} \).

Výrok: \( \forall x \in \mathbb{R}: (Z(x) \lor K(x)) \)

Česky: Pro každé reálné číslo \(x\) platí, že \(x\) je buď záporné, nebo kladné.

Řešení příkladu:

Označme \( x \in \mathbb{Z} \), \( D_5(x): x \text{ je dělitelné 5} \), \( D_3(x): x \text{ je dělitelné 3} \).

Výrok: \( \exists x \in \mathbb{Z}: D_5(x) \land \neg D_3(x) \)

Česky: Existuje číslo, které je dělitelné \(5\), ale není dělitelné \(3\).

Řešení příkladu:

Označme \( Z \) množinu čísel, \( M(x): x \text{ je menší než 0} \), \( D(x): x \text{ je dělitelné 5} \).

Výrok: \( \exists x \in Z: M(x) \land D(x) \)

Česky: Existuje číslo, které je menší než \(0\) a zároveň dělitelné \(5\).