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

Relacja podzielności określona jako

$x\mid y$ wtw $\mathrm{\exists }zx\cdot z=y$

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

liczb rzeczywistych $\mathbb{ℝ}$ Źle

liczb wymiernych $\mathbb{\mathbb{Q}}$ Źle

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

liczb naturalnych $\mathbb{\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

$\{0,1\}$ Dobrze

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

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

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

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

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

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

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

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

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

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

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

w zbiorze wszystkich podzbiorów zbioru $\{0,1\}$ Ź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ą Źle

symetryczną.

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=\{2,3,4,5,...13,14,15\}$ 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:

$({\mathbb{\mathbb{Z}}}_n,{\le }_1)$ , gdzie $x{\le }_{1}y$ w.t.w. $x+1=ymodn$ . Źle

$\mathbf{𝐆}=(V,E)$ , gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathbf{G}={\sf 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

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{G},\leq_2 \right) } , gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{G} } jest rodziną wszystkich skończonych nieizomorficznych grafów, zaś $\mathbf{𝐆}{\le }_2\mathbf{𝐇}$ w.t.w. w grafie $\mathbf{𝐇}$ istnie podgraf homeomorficzny do grafu $\mathbf{𝐆}$ . Ź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,\le )$ , to:

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

jeśli $C\subseteq P$ jest łańcuchem o maksymalnym rozmiarze, to $C\cap A\ne \mathrm{\varnothing }$ Źle

istnieje łańcuch $C\subseteq P$ o maksymalnym rozmiarze taki, że $C\cap A\ne \mathrm{\varnothing }$ Źle

poset $\mathbf{𝐏}-A$ jest szerokości co najwyżej Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf width}\!\left( \mathbf{P} \right)-1 } Źle

Jeśli poset $\mathbf{𝐏}$ ma szerokość Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf width}\!\left( \mathbf{P} \right)=10 } , to:

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

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

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

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

Jeśli poset $\mathbf{𝐏}$ ma szerokość Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf width}\!\left( \mathbf{P} \right)=11 } , a każdy jego łańcuch ma co najwyżej $9$ elementów, to:

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

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

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

poset $\mathbf{𝐏}$ 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{P}\!\left( X \right),\subseteq \right) } ma szerokość $252$ Dobrze

poset Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{P}\!\left( X \right),\subseteq \right) } ma szerokość $210$ Źle

poset Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{P}\!\left( X \right),\subseteq \right) } ma wysokość $11$ Dobrze

poset Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{P}\!\left( X \right),\subseteq \right) } ma wysokość $10$ Źle

Jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{R} } jest zbiorem wszystkich relacji równoważności na $10$ -elementowym zbiorze $X$ , to:

para Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{R},\subseteq \right) } jest zbiorem częściowo uporządkowanym Dobrze

para Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{R},\subseteq \right) } jest kratą Dobrze

para Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{R},\subseteq \right) } jest zbiorem częściowo uporządkowanym o szerokości mniejszej niż szerokość posetu Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( \mathscr{P}\!\left( X \right),\subseteq \right) } Źle

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