Testy

Matematická logika

Seznam všech otázek

1. Které z následujících tvrzení výrokové logiky je tautologie?

   `(\neg A\Rightarrow B)\Rightarrow(B\Rightarrow A)`
   `(A\Rightarrow B)\Rightarrow(B\Rightarrow\neg A)`
   `(A\Rightarrow B)\Rightarrow(\neg B\Rightarrow\neg A)`
   `(A\Rightarrow\neg B)\Rightarrow(B\Rightarrow A)`

2. Která z formulí je úplná konjuktivní normální forma výroku `A \Leftrightarrow B`?

   `(\neg A\vee\neg B)\wedge(\neg B\vee\neg A)`
   `(A \vee B)\wedge(B \vee A)`
   `(A \vee B)\wedge(B \vee \neg A)`
   `(A \vee \neg B)\wedge(B \vee \neg A)`

3. Rozhodněte, která dvojice představuje navzájem ekvivalentní výroky:

   `(A \vee C) \Rightarrow B; A \Rightarrow (B \vee C)`
   `\neg A \Rightarrow (B \vee C); (\neg B \wedge \neg C) \Rightarrow A`
   `\neg A \Rightarrow (B \vee C); (\neg B \vee \neg C) \Rightarrow A`
   `D \Rightarrow (A \vee B); D \Rightarrow (A \wedge B)`

4. Rozhodněte, která věta v přírozeném jazyce odpovídá formuli `(\forall x)(A(x) \Rightarrow F(x))`:

   Každý, kdo mluví anglicky, mluví i francouzsky.
   Každý mluví anglicky a francouzsky.
   Všichni mluví anglicky nebo francousky.
   Všichni mluví anglicky a francouzsky.

5. Nalezněte (např. pomocí K. mapy) minimální vyjádření booleovské funkce `V = \neg (A \Rightarrow \neg B) \vee \neg (C \Rightarrow \neg A).`

   `(A \wedge B) \vee (\neg C \wedge A)`
   `(A \wedge B) \vee (C \wedge A)`
   `(A \wedge C) \vee (\neg A \wedge B)`
   `(A \wedge C) \vee (\neg B \wedge A)`

6. Která z následujících formulí není logicky pravdivá?

   `((\forall x)A(x) \vee (\forall x)B(x)) \Rightarrow (\forall x)(A(x) \vee B(x))`
   `(\forall x)(A(x) \vee B(x)) \Rightarrow ((\forall x)A(x) \vee (\forall x)B(x))`
   `(\forall x)(A(x) \vee B(x)) \Rightarrow ((\exists x)A(x) \Rightarrow (\exists x)B(x))`
   `((\exists x)A(x) \vee (\exists x)B(x)) \Rightarrow (\exists x)A(x) \vee B(x))`

7. Které z následujících tvrzení je tautologickým důsledkem tvrzení "Všichni kuřáci páchnou kouřem. Každý, kdo páchne kouřem, je bezohledný."

   Všichni bezohlední lidé jsou kuřáci.
   Někteří bezohlední lidé jsou kuřáci.
   Všichni, kteří páchnou kouřem, jsou kuřáci.
   Žádný kuřák nepáchne kouřem.

8. Piercův symbol `\downarrow` NOR má následující význam: `A \downarrow B \Leftrightarrow \neg (A \vee B)`. Vyberte, které vyjádření konjunkce pomocí Piercova symbolu je správné:

   `(A \wedge B) \Leftrightarrow ((A \downarrow A) \downarrow (B \downarrow B))`
   `(A \wedge B) \Leftrightarrow ((A \downarrow B) \downarrow A)`
   `(A \wedge B) \Leftrightarrow ((A \downarrow B) \downarrow (A \downarrow B))`
   `(A \wedge B) \Leftrightarrow ((A \downarrow A) \downarrow B)`

9. Které z následujících tvrzení je negací formule `((\exists x)A(x) \wedge (\forall y)B(y)) \Rightarrow (\exists x)\neg C(x)`?

   `(\exists x)\neg A(x) \vee (\forall y)\neg B(y) \Rightarrow (\forall z)C(z)`
   `(\exists x)A(x) \wedge (\forall y)B(y) \wedge (\forall z)C(z)`
   `(\forall x)A(x) \vee (\exists y)B(y) \Rightarrow (\forall z)C(z)`
   `(\forall x)\neg A(x) \wedge (\exists y)\neg B(y) \wedge (\exists z) \neg C(z)`

10. Nechť L obsahuje jeden unární predikátový symbol s(x) a jeden binární funkční symbol f(x,y). Která z následujících formulí není pravdivá v interpretaci I = <N, s, +>, kde N jsou přirozená čísla, s(x) znamená, že x je sudé a f(x,y) intepretujeme jako součet x + y?

    `(\forall x)(\forall y)((s(x) \wedge s(y)) \Rightarrow s(f(x,y)))`
    `(\forall y)(s(x) \Rightarrow (\exists y)(x = f(y,y)))`
    `(\forall x)(\forall y)(s(f(x,y)) \Rightarrow s(f(y,x)))`
    `(\forall x)(\forall y)(s(f(x,y)) \Rightarrow (s(x) \wedge s(y)))`

11. Je následující formule logicky pravdivá? `(\forall x)(A \wedge B) \Rightarrow ((\forall x)A \wedge (\forall x)B)`

    Ano
    Ne

12. Tvrzení `(P \Rightarrow Q) \Leftrightarrow (Q \Rightarrow P)` je:

    Kontradikce.
    Tautologie.
    Splnitelné.

13. Tvrzení `(P \Rightarrow Q) \Rightarrow (\neg Q \Rightarrow \neg P)` je:

    Tautologie.
    Kontradikce.
    Splnitelné.

14. Tvrzení `(A \wedge \neg A)` je:

    Splnitelné.
    Tautologie.
    Kontradikce.

15. Tvrzení `\neg (A \vee \neg A)` je:

    Splnitelné.
    Kontradikce.
    Tautologie.

16. Tvrzení `\neg (P \wedge Q) \Rightarrow (\neg P \vee \neg Q)` je:

    Splnitelné.
    Kontradikce.
    Tautologie.

17. Tvrzení `((A \Rightarrow B) \Rightarrow B) \Rightarrow B` je:

    Splnitelné.
    Kontradikce.
    Tautologie.

18. Tvrzení `((A \Rightarrow B) \Rightarrow A) \Rightarrow A` je:

    Splnitelné.
    Tautologie.
    Kontradikce.

19. 364718705

20. Jaká bude hodnota výrazu 3 || 4?

    1
    2
    7
    8