Matematyka dyskretna 2/Test 2: Porządki Częściowe i twierdzenie Dilworth'a

Relacja podzielności określona jako

$x\mid y$ wtw $\exists z\ \ x\cdot z=y$

jest relacją częściowego porządku w zbiorze:

liczb rzeczywistych $\mathbb {R}$ Źle

liczb wymiernych $\mathbb {Q}$ Źle

liczb całkowitych $\mathbb {Z}$ Źle

liczb naturalnych $\mathbb {N}$ Dobrze

liczb naturalnych nieparzystych Dobrze

Relacja podzielności jest relacją liniowego porządku w zbiorze:

liczb naturalnych będących potęgami liczby $2$ Dobrze

liczb naturalnych będących potęgami liczby $6$ Dobrze

liczb naturalnych będących potęgami liczby $2$ lub $6$ Dobrze

liczb naturalnych będących równocześnie potęgami liczby $2$ i $6$ Źle

$\left\lbrace 0,1\right\rbrace$ Dobrze

Relacja inkluzji $\subseteq$ jest relacją częściowego porządku w zbiorze:

w zbiorze wszystkich podzbiorów zbioru liczb rzeczywistych $\mathbb {R}$ Dobrze

w zbiorze wszystkich podzbiorów zbioru liczb wymiernych $\mathbb {Q}$ Dobrze

w zbiorze wszystkich podzbiorów zbioru liczb całkowitych $\mathbb {Z}$ postaci $[-k,k]$ Dobrze

w zbiorze wszystkich podzbiorów zbioru liczb całkowitych $\mathbb {Z}$ postaci $[k,l]$ Dobrze

w zbiorze wszystkich podzbiorów zbioru liczb naturalnych $\mathbb {N}$ Dobrze

Relacja inkluzji $\subseteq$ jest relacją liniowego porządku w zbiorze:

w zbiorze wszystkich podzbiorów zbioru liczb całkowitych $\mathbb {Z}$ postaci $[0,k]$ Dobrze

w zbiorze wszystkich podzbiorów zbioru liczb całkowitych $\mathbb {Z}$ Źle

w zbiorze wszystkich podzbiorów zbioru liczb całkowitych $\mathbb {Z}$ postaci $[-k,k]$ Dobrze

w zbiorze wszystkich podzbiorów zbioru liczb całkowitych $\mathbb {Z}$ postaci $[k,l]$ Źle

w zbiorze wszystkich podzbiorów zbioru $\left\lbrace 0,1\right\rbrace$ Źle

Wiedząc, że $R,S\subseteq A\times A$ są relacjami częściowego porządku na zbiorze $A$ zaznacz prawdziwe zależności:

$R\cap S$ jest relacją częściowego porządku na zbiorze $A$ Dobrze

$R\cup S$ jest relacją częściowego porządku na zbiorze $A$ Źle

$R\circ S$ jest relacją częściowego porządku na zbiorze $A$ Źle

$R\circ R=R$ Dobrze

$R=R^{\leftharpoonup }$ Źle

Zaznacz zdania prawdziwe:

W skończonym zbiorze częściowo uporządkowanym istnieje co najmniej jeden element minimalny. Dobrze

Jeśli w zbiorze częściowo uporządkowanym jest element najmniejszy, to jest on jedynym elementem minimalnym. Dobrze

W zbiorze liniowo uporządkowanym element minimalny o ile istnieje, jest elementem najmniejszym. Dobrze

W zbiorze liniowo uporządkowanym nie każdy skończony niepusty podzbiór ma element najmniejszy i największy. Źle

W zbiorze częściowo uporządkowanym każdy skończony niepusty podzbiór ma elementy minimalne i maksymalne. Dobrze

Zaznacz zdania prawdziwe:

Porządek produktowy porządków liniowych jest zawsze porządkiem liniowym. Źle

Każdy zbiór ograniczony z góry i z dołu ma kresy. Źle

Elementów minimalnych może w zbiorze uporządkowanym nie być wcale. Dobrze

Kres górny w zbiorze uporządkowanym i ograniczenie górne - to to samo. Źle

Porządek leksykograficzny jest zawsze liniowy. Dobrze

Zaznacz zdania prawdziwe:

Każda relacja równoważności jest relacją symetryczną. Dobrze

Suma dowolnej rodziny relacji zwrotnych jest zwrotna. Dobrze

Relacja porządku nie musi być relacją zwrotną. Źle

Każda relacja przechodnia i zwrotna jest relacją symetryczną. Źle

Relacja porządku musi być relacją symetryczną. Źle

Zaznacz zdania prawdziwe:

Każdy zbiór jednoelementowy jest łańcuchem. Dobrze

W łańcuchu każde dwa elementy są porównywalne. Dobrze

Łańcuch jest zbiorem liniowo uporządkowanym. Dobrze

Relacja częściowego porządku jest spójna. Źle

Jeśli relacja $R$ porządkuje częściowo zbiór $X$, to relacja $R^{-1}$ też częściowo porządkuje zbiór $X$. Dobrze

Rozważamy zbiór $T=\left\lbrace 2,3,4,5,...13,14,15\right\rbrace$ z relacją podzielności ograniczoną do elementów zbioru $T$. Zaznacz zdania prawdziwe:

W zbiorze tym są dokładnie trzy łańcuchy trzyelementowe. Źle

W zbiorze tym są dokładnie cztery łańcuchy trzyelementowe. Dobrze

W zbiorze tym nie ma łańcuchów trzyelementowych. Źle

Między innymi $3$ i $7$ są elementami minimalnymi. Dobrze

Między innymi $9$ i $15$ są elementami maksymalnymi. Dobrze

Zaznacz zbiory częściowo uporządkowane:

$\left(\mathbb {Z} _{n},\leq _{1}\right)$ , gdzie $x\leq _{1}y$ w.t.w. $x+1=y\mod n$ . Źle

$\mathbf {G} =\left(V,E\right)$ , gdzie $\mathbf {G} ={\mathsf {TC}}\left(\mathbf {H} \right)\cup \left\lbrace \left(x,x\right):x\in V\right\rbrace$ , gdzie $H$ jest prostym acyklicznym grafem skierowanym. Dobrze

$\left(\mathbb {N} ,\leq \right)$ , gdzie $x\leq _{1}y$ w.t.w. istnieje $a\in \mathbb {N}$ takie, że $x+a=y$ . Dobrze

$\left({\mathcal {G}},\leq _{2}\right)$ , gdzie ${\mathcal {G}}$ jest rodziną wszystkich skończonych nieizomorficznych grafów, zaś $\mathbf {G} \leq _{2}\mathbf {H}$ w.t.w. w grafie $\mathbf {H}$ istnie podgraf homeomorficzny do grafu $\mathbf {G}$ . Źle

Zaznacz zdania poprawnie opisujące zbiór $X$ będący równocześnie łańcuchem oraz antyłańcuchem w zbiorze częściowo uporządkowanym:

Nie istnieje taki zbiór $X$ . Źle

Zbiór $X$ jest pusty. Źle

Zbiór $X$ jest co najwyżej jednoelementowy. Dobrze

Zbiór $X$ jest co najwyżej dwuelementowy. Źle

Jeśli $A$ jest maksymalnym antyłańcuchem w posecie $\mathbf {P} =\left(P,\leq \right)$ , to:

dowolny element $p\in P$ jest porównywalny z którymś elementem $a\in A$ , czyli $p\leq a$ lub $a\leq p$ Dobrze

jeśli $C\subseteq P$ jest łańcuchem o maksymalnym rozmiarze, to $C\cap A\neq \emptyset$ Źle

istnieje łańcuch $C\subseteq P$ o maksymalnym rozmiarze taki, że $C\cap A\neq \emptyset$ Źle

poset $\mathbf {P} -A$ jest szerokości co najwyżej ${\mathsf {width}}\!\left(\mathbf {P} \right)-1$ Źle

Jeśli poset $\mathbf {P}$ ma szerokość ${\mathsf {width}}\!\left(\mathbf {P} \right)=10$ , to:

najliczniejszy łańcuch w posecie $\mathbf {P}$ ma $10$ elementów Źle

najliczniejszy antyłańcuch w posecie $\mathbf {P}$ ma $10$ elementów Dobrze

da się pokryć $10$ antyłańcuchami Źle

da się pokryć $10$ łańcuchami Dobrze

Jeśli poset $\mathbf {P}$ ma szerokość ${\mathsf {width}}\!\left(\mathbf {P} \right)=11$ , a każdy jego łańcuch ma co najwyżej $9$ elementów, to:

poset $\mathbf {P}$ ma co najwyżej $99$ elementów Dobrze

poset $\mathbf {P}$ ma co najwyżej $100$ elementów Dobrze

poset $\mathbf {P}$ ma co najmniej $19$ elementów Dobrze

poset $\mathbf {P}$ ma co najmniej $20$ elementów Źle

Każdy $100$ -elementowy ciąg liczb rzeczywistych zawiera:

$11$ -elementowy podciąg niemalejący lub $11$ -elementowy podciąg malejący Źle

$10$ -elementowy podciąg niemalejący lub $12$ -elementowy podciąg malejący Dobrze

$10$ -elementowy podciąg niemalejący lub $10$ -elementowy podciąg malejący Dobrze

żadna z pozostałych odpowiedzi nie jest poprawna Źle

Jeśli $X$ jest zbiorem $10$ -elementowym, to:

poset $\left({\mathcal {P}}\!\left(X\right),\subseteq \right)$ ma szerokość $252$ Dobrze

poset $\left({\mathcal {P}}\!\left(X\right),\subseteq \right)$ ma szerokość $210$ Źle

poset $\left({\mathcal {P}}\!\left(X\right),\subseteq \right)$ ma wysokość $11$ Dobrze

poset $\left({\mathcal {P}}\!\left(X\right),\subseteq \right)$ ma wysokość $10$ Źle

Jeśli ${\mathcal {R}}$ jest zbiorem wszystkich relacji równoważności na $10$ -elementowym zbiorze $X$ , to:

para $\left({\mathcal {R}},\subseteq \right)$ jest zbiorem częściowo uporządkowanym Dobrze

para $\left({\mathcal {R}},\subseteq \right)$ jest kratą Dobrze

para $\left({\mathcal {R}},\subseteq \right)$ jest zbiorem częściowo uporządkowanym o szerokości mniejszej niż szerokość posetu $\left({\mathcal {P}}\!\left(X\right),\subseteq \right)$ Źle

Żadna z pozostałych odpowiedzi nie jest prawdziwa. Źle