Quiz

Pytanie 1 z 30

Zaznacz zdania prawdziwe.

Pewne prostokąty łacińskie $p \times n$, w których liczba wystąpień niektórych elementów jest zbyt mała, nie mogą być rozszerzone do kwadratu łacińskiego $n \times n$.

Kwadratem grecko-łacińskim, czyli kwadratem Eulera, nazywamy złożenie dwóch dowolnych kwadratów łacińskich o takim samym rozmiarze.

Każda macierz o wymiarze $p \times q$ zbudowana z elementów ze zbioru $\{1, \dots, n\}$, gdzie $\min(p, q) < n$, w której w żadnym wierszu elementy się nie powtarzają jest prostokątem łacińskim.

Rozszerzenie dowolnego prostokąta łacińskiego o dodatkowe kolumny jest zawsze możliwe, należy jedynie w każdej nowej kolumnie umieszczać elementy występujące najrzadziej.

Rozszerzenie prostokąta łacińskiego $n \times q$ do kwadratu $n \times n$ jest zawsze możliwe i wymaga wyznaczenia transwersali rodziny zbiorów zawierających elementy nie występujące dotychczas w poszczególnych wierszach.

Pytanie 2 z 30

Zaznacz zdania prawdziwe.

Liczba wszystkich $k$-elementowych kombinacji bez powtórzeń z $n$-elementowego zbioru wynosi $\binom{n}{k}$ gdzie $n \leq k$ lub $k < n$

Z każdej $k$-elementowej kombinacji bez powtórzeń ze zbioru $n$-elementowego można utworzyć $k!$ różnych $k$-wyrazowych wariacji bez powtórzeń ze zbioru $n$-elementowego.

Każda $k$-elementowa kombinacja bez powtórzeń ze zbioru $n$-elementowego odpowiada pewnemu podziałowi tego zbioru na $k$ podzbiorów.

Wszystkie $k$-elementowe kombinacje bez powtórzeń z $n$-elementowego zbioru, dla $k=0, \ldots, n$, mogą być wygenerowane za pomocą generacji ze wszystkich liczb binarnych z zakresu od $1$ do $2^n$.

Każde rozmieszczenie $k$ identycznych elementów w $n$ rozróżnialnych pudełkach odpowiada $k$-elementowej kombinacji bez powtórzeń ze zbioru $n$-elementowego.

Pytanie 3 z 30

Wśród poniższych zdań wskaż wszystkie zdania prawdziwe:

Liczby całkowite $a$ i $b$ są względnie pierwsze, jeżeli istnieją liczby całkowite $x$ i $y$, takie że $ax + by = 2$.

Liczby całkowite $a$ i $b$ są względnie pierwsze, jeżeli istnieją liczby całkowite $x$ i $y$, takie że $ax + by = 1$.

Liczby całkowite $a$ i $b$ są względnie pierwsze, jeżeli $\gcd(a, b) = 1$.

Liczby całkowite $a$ i $b$ są względnie pierwsze, jeżeli istnieją liczby całkowite $x$ i $y$, takie że $ax + by = \sqrt{2}$.d

Liczby całkowite $a$ i $b$ są względnie pierwsze, jeżeli $\gcd(a, b) = 0$.

Pytanie 4 z 30

Średnia liczność zbiorów $A_1, A_2, A_3, A_4, A_5, A_6$ będących podzbiorami zbioru 18-elementowego $S$, takimi, że każdy element $S$ należy do dokładnie 3 podzbiorów wynosi:

co najwyżej 9.

nie może być określona.

dokładnie 9.

co najmniej 9.

dokładnie 3.

Pytanie 5 z 30

Zaznacz zdanie prawdziwe.

Liczba wszystkich $k$-elementowych kombinacji z powtórzeniami ze zbioru $n$-elementowego wynosi $\binom{k + n - 1}{n}$ gdzie $k < n$.

Każda $k$-elementowa kombinacja z powtórzeniami ze zbioru $n$-elementowego może być przedstawiona jako permutacja z powtórzeniami dwóch różnych symboli powtarzających się odpowiednio $n$ i $k$ razy.

Kombinacja $k$-elementowa z powtórzeniami ze zbioru $n$-elementowego, to $k$-elementowy podzbiór elementów tego zbioru, w którym kolejność elementów nie jest istotna.

Każda $k$-elementowa kombinacja z powtórzeniami ze zbioru $n$-elementowego może być przedstawiona jako $k$-elementowa permutacja z powtórzeniami ze zbioru $n$-elementowego.

Każda $k$-elementowa kombinacja z powtórzeniami ze zbioru $n$-elementowego może być interpretowana jako rozmieszczenie $k$ identycznych elementów w $n$ rozróżnialnych pudełkach.

Pytanie 6 z 30

Wśród poniższych zdań wskaż wszystkie zdania prawdziwe:

Funkcja $f(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \dots = \sum_{i=0}^{\infty} a_i x^i$ jest wykładniczą funkcją tworzącą sekwencji liczb rzeczywistych $a_0, a_1, a_2, a_3, \dots$.

Funkcja $f(x) = a_0 + a_1 x + \frac{a_2 x^2}{2!} + \frac{a_3 x^3}{3!} + \dots = \sum_{i=0}^{\infty} \frac{a_i x^i}{i!}$ jest wykładniczą funkcją tworzącą sekwencji liczb rzeczywistych $a_0, a_1, a_2, a_3, \dots$.

Funkcja $f(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \dots = \sum_{i=0}^{\infty} a_i x^i$ jest funkcją tworzącą sekwencji liczb rzeczywistych $a_0, a_1, a_2, a_3, \dots$.

Funkcja $f(x) = a_0 x_0 + a_1 x_1 + a_2 x_2^2 + a_3 x_3^3 + \dots = \sum_{i=0}^{\infty} a_i x_i^i$ jest wykładniczą funkcją tworzącą sekwencji liczb rzeczywistych $a_0, a_1 x_1, a_2 x_2, a_3 x_3, \dots$.

Funkcja $f(x) = \frac{1}{a_0} + \frac{x}{a_1} + \frac{2! x^2}{a_2} + \frac{3! x^3}{a_3} + \dots = \sum_{i=0}^{\infty} \frac{i! x^i}{a_i}$ jest wykładniczą funkcją tworzącą sekwencji liczb rzeczywistych $a_0, a_1, a_2, a_3, \dots$.

Pytanie 7 z 30

Niech $p$ i $q$ będą zdaniami logicznymi prostymi, $T_0$ niech będzie dowolną tautologią, a $F_0$ dowolnym zdaniem sprzecznym. Wśród poniższych par zdań wskaż zdania logicznie równoważne.

$p \land F_0, F_0$

$p \lor T_0, p$

$p \land F_0, p$

$p \land T_0, \neg p$

$p \rightarrow q, \neg p \lor q$

Pytanie 8 z 30

Wśród poniższych zdań wskaż zdania prawdziwe.

Graf nieskierowany $G = (V, E)$ jest spójny wtedy i tylko wtedy, gdy posiada drzewo rozpinające.

W drzewie $G = (V, E)$ między każdą parą wierzchołków $x, y \in V$ istnieją co najmniej dwie ścieżki.

Dla każdego drzewa $G = (V, E)$ zachodzi $|V| = |E| - 1$.

W drzewie $G = (V, E)$ między każdą parą wierzchołków $x, y \in V$ istnieje dokładnie jedna ścieżka.

Drzewo $G = (V, E)$ takie, że $|V| \geq 2$, ma co najmniej trzy wierzchołki o stopniu równym 1.

Pytanie 9 z 30

Średnia liczność zbiorów $A_1, A_2, A_3, A_4$ będących podzbiorami zbioru 8-elementowego $S$, takimi, że każdy element $S$ należy do co najmniej 3 podzbiorów wynosi:

co najmniej 8.

co najwyżej 6.

dokładnie 6.

co najmniej 6.

co najwyżej 3.

Pytanie 10 z 30

Wybierz wszystkie poprawne:

Relację, która jest jednocześnie relacją przechodnią, symetryczną i spójną w zbiorze $X$ nazywamy relacją liniowo porządkującą zbiór $X$.

Relację, która jest jednocześnie relacją zwrotną, antysymetryczną i spójną w zbiorze $X$ nazywamy relacją liniowo porządkującą zbiór $X$.

Relację, która jest jednocześnie relacją przechodnią, antysymetryczną, zwrotną i spójną w zbiorze $X$ nazywamy relacją liniowo porządkującą zbiór $X$.

Relację, która jest jednocześnie relacją przechodnią, symetryczną i przeciwzwrotną w zbiorze $X$ nazywamy relacją liniowo porządkującą zbiór $X$.

Relację, która jest jednocześnie relacją zwrotną, przechodnią i antysymetryczną w zbiorze $X$ nazywamy relacją liniowo porządkującą zbiór $X$.

Pytanie 11 z 30

Do 6 rozróżnialnych pudełek wrzucane są w dowolny sposób 4 rozróżnialne elementy. Każdy sposób wrzucenia elementów do pudełek jest przykładem:

6-elementowej permutacji z powtórzeniami ze zbioru 4-elementowego.

4-elementowej wariacji z powtórzeniami ze zbioru 6-elementowego.

4-elementowej kombinacji z powtórzeniami ze zbioru 6-elementowego.

4-elementowej wariacji bez powtórzeń ze zbioru 6-elementowego.

6-elementowej kombinacji z powtórzeniami ze zbioru 4-elementowego.

Pytanie 12 z 30

3 identyczne elementy mogą być wrzucone w dowolny sposób do 6 rozróżnialnych pudełek na

$\binom{6}{3}$ sposobów.

$\binom{6+3-1}{3}$ sposobów.

$3^6$ sposobów.

$\frac{6!}{3!}$ sposobów.

$6^3$ sposobów.

Pytanie 13 z 30

Zaznacz zdania prawdziwe.

Każdy pierwiastek pojedynczy $r$ równania charakterystycznego wprowadza do rozwiązania liniowej jednorodnej zależności rekurencyjnej ze stałymi współczynnikami rzędu $k \geq 2$ czynnik $rc^n$, gdzie $c$ jest pewną stałą, którą można wyznaczyć w oparciu o początkowe wyrazy ciągu.

Rozwiązanie problemu wież z Hanoi, $T_n = 2T_{n-1} + 1, n > 0, T_0 = 0$, jest przykładem niejednorodnej liniowej zależności rekurencyjnej rzędu pierwszego ze stałymi współczynnikami.

Rozwiązanie liniowej jednorodnej zależności rekurencyjnej rzędu pierwszego ze stałymi współczynnikami postaci $a_{n+1} + ca_n = 0$ jest dane wzorem $a_n = ca_0^n$, gdzie $c$ oznacza pewną stałą i $n \in \mathbb{N}$.

Rozwiązanie zależności liniowej jednorodnej rzędu drugiego ze stałymi współczynnikami o równaniu charakterystycznym o jednym pierwiastku podwójnym ma postać $a_n = c_1 r^n + c_2 n r^n$, gdzie wartości stałych $c_1$ i $c_2$ są wyznaczane w oparciu o początkowe elementy ciągu.

Zależność postaci $c_n a_n + c_{n-1} a_{n-1} + \dots + c_k a_k = 0$, gdzie $c_i$ dla $i = n, \dots, k$ są pewnymi stałymi rzeczywistymi, $c_n \neq 0$ i $c_k \neq 0$ nazywamy liniową jednorodną zależnością rekurencyjną rzędu k-tego ze stałymi współczynnikami.

Pytanie 14 z 30

Wśród poniższych zdań wskaż wszystkie zdania będące definicjami odpowiednich obiektów:

Językiem nad alfabetem $\Sigma$ jest zbiór potęgowy zbioru $\Sigma$.

Jeżeli przez $\Sigma^*$ oznaczymy zbiór wszystkich słów zbudowanych z liter alfabetu $\Sigma$, to językiem nad alfabetem $\Sigma$ jest $\Sigma^* \times \Sigma^*$.

Jeżeli przez $\Sigma^*$ oznaczymy zbiór wszystkich słów zbudowanych z liter alfabetu $\Sigma$, to dowolny podzbiór zbioru $\Sigma^*$ jest językiem nad alfabetem $\Sigma$.

Słowem danego alfabetu $\Sigma$ jest dowolny skończony ciąg liter zbioru $\Sigma$, który zawiera co najwyżej jedno wystąpienie każdego z elementów zbioru $\Sigma$.

Słowem danego alfabetu $\Sigma$ jest dowolny skończony ciąg liter zbioru $\Sigma$.

Pytanie 15 z 30

Zaznacz zdanie prawdziwe.

Zasadę włączania i wyłączania można zastosować wyłącznie do obliczenia liczności sumy zbiorów, których części wspólne nie są zbiorami pustymi; zasady tej nie można zastosować dla zbiorów rozłącznych.

Zasada włączania i wyłączania ma postać: $ \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{i=1}^{n} |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \dots + (-1)^{n-1} |A_1 \cap A_2 \cap \dots \cap A_n|$

Zasada włączania i wyłączania jest uogólnieniem prawa iloczynu dla więcej niż dwóch zbiorów skończonych.

Zasadę włączania i wyłączania stosuje się do obliczenia liczności sumy pewnej liczby zbiorów w sytuacji, gdy nie można wyznaczyć elementów należących do tej sumy.

Zasada włączania i wyłączania umożliwia obliczenie liczności części wspólnej $n$ zbiorów $A_1, A_2, ..., A_n$ w oparciu o liczności sum zbiorów z rodziny $\{A_1, A_2, ..., A_n\}$.

Pytanie 16 z 30

Do 7 rozróżnialnych pudełek można wrzucić (w dowolny sposób) 4 identyczne elementy na

$7^4$ sposobów.

$\binom{7}{4}$ sposobów.

$\binom{7+4-1}{4}$ sposobów.

$\frac{7!}{(7-4)!}$ sposobów.

$4^7$ sposobów.

Pytanie 17 z 30

Zaznacz zdanie prawdziwe:

Twierdzenie Zeckendorfa stwierdza, iż każda liczba całkowita dodatnia $n$ może być jednoznacznie przedstawiona w postaci iloczynu pewnych liczb Fibonacciego i zapisana w postaci odpowiedniego ciągu zer i jedynek.

Liczby harmoniczne $H_n$ są dyskretnym odpowiednikiem funkcji $f(x) = \frac{1}{x}$ i tworzą ciąg liczbowy rosnący logarytmicznie wolno dla $n \to \infty$.

Liczby Eulera pierwszego rzędu $\left\langle \begin{array}{c} n \\ k \end{array} \right\rangle$ oznaczają liczbę $n$-elementowych permutacji bez powtórzeń ze zbioru $n$-elementowego zawierających $k$ wzniesień.

Z definicji przyjmuje się, że liczba Stirlinga drugiego rodzaju $S(n,n) = 1$ dla $n \geq 0$, ponieważ opisywany przez nią podział jest niemożliwy.

Liczby Stirlinga drugiego rodzaju opisujące liczbę sposobów podziału zbioru $n$-elementowego na $k$-niepustych podzbiorów są nie mniejsze niż liczby Stirlinga pierwszego rodzaju opisujące liczbę sposobów rozmieszczenia $n$ elementów w $k$ cyklach.

Pytanie 18 z 30

Niech $H$ będzie grafem sprzężonym pewnego grafu $G$. Wśród poniższych zdań wskaż wszystkie zdania prawdziwe:

W grafie $G$ istnieje droga Eulera wtedy i tylko wtedy, gdy w grafie $H$ istnieje ścieżka Hamiltona.

W grafie $G$ istnieje ścieżka Hamiltona wtedy i tylko wtedy, gdy w grafie $H$ istnieje cykl Hamiltona.

W grafie $G$ istnieje cykl Hamiltona wtedy i tylko wtedy, gdy w grafie $H$ istnieje ścieżka Hamiltona.

W grafie $G$ istnieje ścieżka Hamiltona wtedy i tylko wtedy, gdy w grafie $H$ istnieje droga Eulera.

W grafie $G$ istnieje droga Eulera wtedy i tylko wtedy, gdy w grafie $H$ istnieje obwód Eulera.

Pytanie 19 z 30

Zaznacz zdanie prawdziwe.

Dowód kroku indukcyjnego w drugiej zasadzie indukcji wymaga wykazania prawdziwości zdania $S(n_0) \land S(n_0+1) \land ... \land S(k)$ i prawdziwości zdania $S(k+1)$ dla pewnej liczby $k \geq 1$.

Dowód warunku początkowego w drugiej zasadzie indukcji matematycznej wymaga pokazania prawdziwości pewnych zdań $S(n)$ dla dowolnych elementów $n$, takich że $n_0 \leq n \leq n_1$.

Dowód kroku indukcyjnego w drugiej zasadzie indukcji wymaga wykazania prawdziwości zdania $S(k+1)$ dla każdej liczby $k \geq n_0$.

Dowód kroku indukcyjnego w drugiej zasadzie indukcji wymaga pokazania, że dla pewnej konkretnej wartości $k \geq n_0$ zachodzi implikacja $[S(n_0) \land ... \land S(k)] \Rightarrow S(k+1)$.

W zasadzie silnej indukcji matematycznej warunek początkowy ma postać $S(n_0) \land S(n_0+1) \land ... \land S(n_1)$, gdzie $n_0, n_1 \in \mathbb{Z}^+$ i $n_0 \leq n_1$, a $S(n)$ oznacza zdanie otwarte, w którym występuje liczba całkowita dodatnia $n$.

Pytanie 20 z 30

Każdy sposób wrzucenia 4 identycznych elementów do 5 rozróżnialnych pudełek jest przykładem:

5-elementowej wariacji bez powtórzeń ze zbioru 4-elementowego.

4-elementowej permutacji z powtórzeniami ze zbioru 5-elementowego.

4-elementowej wariacji z powtórzeniami ze zbioru 5-elementowego.

5-elementowej kombinacji bez powtórzeń ze zbioru 4-elementowego.

4-elementowej kombinacji z powtórzeniami ze zbioru 5-elementowego.

Pytanie 21 z 30

Zasada indukcji matematycznej może być zastosowana do dowodzenia twierdzeń $S(n)$, w którym $n$ należy do zbioru:

liczb rzeczywistych dodatnich.

dowolnego podzbioru zbioru liczb wymiernych.

liczb rzeczywistych.

liczb naturalnych.

liczb całkowitych.

Pytanie 22 z 30

Zaznacz funkcję tworzącą, która $\textbf{może być}$ wielomianem szachowym $\textbf{dopełnienia}$ podanej szachownicy $B$:

$r_B(x) = 1 + 25x + 35x^2 + 50x^3 + 26x^4 + 4x^5$

$r_B(x) = 1 + 15x + 35x^2 + 50x^3 + 26x^4 + 4x^5$

$r_B(x) = 1 + 10x + 35x^2 + 50x^3 + 26x^4 + 4x^5$

$r_B(x) = 1 + 10x + 35x^2 + 50x^3 + 26x^4 + 4x^6$

$r_B(x) = 1 + 15x + 35x^2 + 50x^3 + 26x^4 + 4x^6$

Pytanie 23 z 30

Wśród poniższych zdań wskaż definicje odpowiednich funkcji.

Funkcją odwrotną do funkcji $f: X \to Y$ jest taka funkcja $f^{-1}$, która każdemu elementowi $y \in Y$ przyporządkowuje element $x \in X$ taki, że $f(x) = x$.

Funkcję różnowartościową $f: X \to Y$, która przekształca zbiór $X$ w zbiór $Y$ nazywamy przekształceniem wzajemnie jednoznacznym zbioru $Y$ na zbiór $X$.

Funkcję różnowartościową $f: X \to Y$, która przekształca zbiór $X$ w zbiór $Y$ nazywamy przekształceniem wzajemnie jednoznacznym zbioru $X$ na zbiór $Y$.

Funkcją odwrotną do funkcji $f: X \to Y$ jest taka funkcja $f^{-1}$, która każdemu elementowi $y \in Y$ przyporządkowuje element $x \in X$ taki, że $f(x) = y$.

Funkcją odwrotną do funkcji $f: X \to Y$ jest taka funkcja $f^{-1}$, która każdemu elementowi $y \in Y$ przyporządkowuje element $x \in X$ taki, że $f(x) = y^{-1}$.

Pytanie 24 z 30

Zaznacz zdania prawdziwe:

Pierwsza zasada indukcji matematycznej dla pewnego $n_0 \in \mathbb{Z}^{+}$ ma postać: $[S(n_0) \land [\forall_{k \geq 1} [S(k) \implies S(k+1)]]] \implies \forall_{n \geq 1} S(n)$.

Pierwszą zasadę indukcji matematycznej stosuje się do dowodzenia twierdzeń, w których prawdziwość pewnego zdania wynika z prawdziwości jednego, dowolnego ze zdań poprzedzających.

Zasada indukcji matematycznej może być wykorzystana do dowodzenia twierdzeń dotyczących dowolnych liczb dodatnich.

Pierwsza zasada indukcji matematycznej dla $n_0 = 1$ ma postać: $[(\forall_{k \geq 1} [S(k) \implies S(k + 1)]) \land S(1)] \implies \forall_{n \in \mathbb{Z}^{+}} S(n)$.

Jeśli pewne twierdzenie $\forall_{n \in \mathbb{Z}^{+}} S(n)$ nie jest prawdziwe dla pewnych początkowych wartości $n \geq 1$, to może ono być udowodnione z wykorzystaniem drugiej zasady indukcji matematycznej.

Pytanie 25 z 30

Pierwsza i druga zasada indukcji matematycznej:

są technikami dowodzenia twierdzeń dotyczących wyłącznie zależności rekurencyjnych jednorodnych.

są równoważne jedynie dla twierdzeń dotyczących liczb naturalnych.

są równoważne.

nie są równoważne.

mogą być zastosowane do dowodzenia twierdzeń dotyczących liczb rzeczywistych dodatnich.

Pytanie 26 z 30

Obiekty kombinatoryczne $D, C, A, B$ i $A, D, C, B$ zostały utworzone ze zbioru $\{A, B, C, D, E\}$ i nie są identyczne (można je odróżnić). Podane obiekty mogą być przykładem:

4-elementowej wariacji bez powtórzeń ze zbioru 5-elementowego.

4-elementowej kombinacji bez powtórzeń ze zbioru 5-elementowego.

Uporządkowanego podziału zbioru na dwa podzbiory.

4-elementowej kombinacji z powtórzeniami ze zbioru 5-elementowego.

5-elementowej wariacji z powtórzeniami ze zbioru 4-elementowego.

Pytanie 27 z 30

Wśród poniższych zdań wskaż wszystkie zdania prawdziwe:

Każdy graf $(\infty, k)$-etykietowalny jest również $(k,nk)$-etykietowalny, gdzie $n$ jest liczbą wierzchołków w grafie.

Każdy graf $(\infty, k)$-etykietowalny jest również $(n-k,k)$-etykietowalny, gdzie $n$ jest liczbą wierzchołków w grafie.

Każdy graf $(\infty, k)$-etykietowalny jest również $(nk,k)$-etykietowalny, gdzie $n$ jest liczbą wierzchołków w grafie.

Grafu niespójnego nie można zaetykietować.

Jeżeli graf $G$ jest etykietowalny za pomocą etykiet o długości $k>2$ zbudowanych nad alfabetem o dowolnej liczności, to jest on również etykietowalny za pomocą etykiet o długości $l=2, \dots, k-1$ zbudowanych nad alfabetem o dowolnej liczności.

Pytanie 28 z 30

Zaznacz zdania prawdziwe:

Dowód zasady szufladkowej Dirichleta wykorzystuje pojęcie uporządkowanego podziału zbioru.

Uogólniona zasada szufladkowa Dirichleta określa wartość średniej arytmetycznej liczb elementów zbiorów $A_1, \dots, A_k$ będących rozłącznymi podzbiorami pewnego skończonego zbioru $S$.

Zasada szufladkowa Dirichleta mówi, że jeśli skończony zbiór $S$ jest podzielony na $k$ rozłącznych niepustych podzbiorów, to każdy z tych podzbiorów zawiera $|S|/k$ elementów lub więcej.

„Klasyczna” zasada szufladkowa Dirichleta w żaden sposób nie wynika z uogólnionej zasady szufladkowej Dirichleta, ponieważ dotyczy zbiorów o odmiennych własnościach.

Z zasady szufladkowej Dirichleta wynika, że jeśli skończony zbiór $S$ jest podzielony na $k$ rozłącznych niepustych podzbiorów, to średnia liczność tych zbiorów wynosi $|S|/k$.

Pytanie 29 z 30

Zaznacz zdania prawdziwe:

Jeśli w dowodzie kroku indukcyjnego wykorzystuje się założenie o prawdziwości tylko jednego ze zdań $S(x)$ poprzedzających zdanie $S(k+1)$, $x \leq k$, to w pierwszej zasadzie twierdzenia wystarczy pierwsza zasada indukcji matematycznej.

W pierwszej zasadzie indukcji matematycznej z prawdziwości warunku początkowego lub kroku indukcyjnego wynika prawdziwość hipotezy indukcyjnej.

Druga zasada indukcji matematycznej jest wykorzystywana do dowodzenia twierdzeń postaci: $\forall_{n \in \mathbb{Z}^+} S(n)$, takich że zdanie $S(n)$ nie jest prawdziwe dla pewnych początkowych wartości $n \in \mathbb{Z}^+$.

Druga zasada indukcji matematycznej dla dowolnych $n_0, n_1 \in \mathbb{Z}^+$, $n_0 \leq n_1$, ma postać: $[[S(1) \land S(2) \land \ldots \land S(n_1)] \land [\forall_{k \geq n_0} [[S(1) \land S(2) \land \ldots \land S(k)] \Rightarrow S(k+1)]]] \Rightarrow \forall_{n \geq n_1} S(n)$

Druga zasada indukcji matematycznej dla $n_0 = 1$, $n_1 \geq 1$ ma postać: $\left[ \forall_{k \geq n_1} [[ S(1) \land S(2) \land \ldots \land S(k) ] \Rightarrow S(k+1)] \land [S(1) \land S(2) \land \ldots \land S(n_1)] \right] \Rightarrow \forall_{n \geq n_1} S(n)$

Pytanie 30 z 30

Zaznacz zdania prawdziwe:

Jeśli szachownica $B$ składa się z dwóch niezależnych obszarów $C$ i $D$, to wówczas $r_B(x) = r_C(x) + r_D(x)$.

Wielomian szachowy $r_B(x) = 1 + r_1x + r_2x^2 + ... + r_kx^k + ... + r_nx^n$, to funkcja, której wartość oznacza liczbę możliwych rozmieszczeń $n$ wzajemnie nieatakujących się wież na szachownicy o wymiarze $x \times x$.

Dekompzycja wielomianów szachowych jest możliwa wyłącznie wówczas, jeśli daną szachownicę można podzielić na dwa rozłączne obszary niemające wspólnych wierszy ani kolumn.

Jeśli w wielomianie szachowym $r_B(x) = 1 + r_1x + r_2x^2 + ... + r_kx^k + ... + r_nx^n$ dla szachownicy $B$ o wymiarze $n \times n$ współczynnik $r_n = 0$, to na szachownicy $B$ nie można rozmieścić $n$ wzajemnie nieatakujących się wież.

Szachownicę $B$ można zdekomponować, poprzez wybór pewnego pola dopuszczalnego $s$, na dwie szachownice $B^1$ i $B^2$, takie że w $B^1$ niedostępny jest wiersz, a w $B^2$ niedostępna jest kolumna zawierająca pole $s$.

Losowa kolejność Reset Start

Korzystanie z serwisu wiąże się z akceptacją regulaminu