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

From Studia Informatyczne

Relacja podzielności określona jako

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

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

liczb rzeczywistych \displaystyle \mathbb{R}

liczb wymiernych \displaystyle \mathbb{Q}

liczb całkowitych \displaystyle \mathbb{Z}

liczb naturalnych \displaystyle \mathbb{N}

liczb naturalnych nieparzystych


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

liczb naturalnych będących potęgami liczby \displaystyle 2

liczb naturalnych będących potęgami liczby \displaystyle 6

liczb naturalnych będących potęgami liczby \displaystyle 2 lub \displaystyle 6

liczb naturalnych będących równocześnie potęgami liczby \displaystyle 2 i \displaystyle 6

\displaystyle \left\lbrace 0,1 \right\rbrace


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

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

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

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

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

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


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

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

w zbiorze wszystkich podzbiorów zbioru liczb całkowitych \displaystyle \mathbb{Z}

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

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

w zbiorze wszystkich podzbiorów zbioru \displaystyle \left\lbrace 0,1 \right\rbrace


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

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

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

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

\displaystyle R \circ R = R

\displaystyle R= R^\leftharpoonup


Zaznacz zdania prawdziwe:

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

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

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

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

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


Zaznacz zdania prawdziwe:

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

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

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

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

Porządek leksykograficzny jest zawsze liniowy.


Zaznacz zdania prawdziwe:

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

Suma dowolnej rodziny relacji zwrotnych jest zwrotna.

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

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

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


Zaznacz zdania prawdziwe:

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

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

Łańcuch jest zbiorem liniowo uporządkowanym.

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

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


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

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

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

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

Między innymi \displaystyle 3 i \displaystyle 7 są elementami minimalnymi.

Między innymi \displaystyle 9 i \displaystyle 15 są elementami maksymalnymi.


Zaznacz zbiory częściowo uporządkowane:

\displaystyle \left( \mathbb{Z}_n,\leq_1 \right) , gdzie \displaystyle x\leq_1 y w.t.w. \displaystyle x+1=y \mod n .

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

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

\displaystyle \left( \mathscr{G},\leq_2 \right) , gdzie \displaystyle \mathscr{G} jest rodziną wszystkich skończonych nieizomorficznych grafów, zaś \displaystyle \mathbf{G}\leq_2 \mathbf{H} w.t.w. w grafie \displaystyle \mathbf{H} istnie podgraf homeomorficzny do grafu \displaystyle \mathbf{G} .


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

Nie istnieje taki zbiór \displaystyle X .

Zbiór \displaystyle X jest pusty.

Zbiór \displaystyle X jest co najwyżej jednoelementowy.

Zbiór \displaystyle X jest co najwyżej dwuelementowy.


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

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

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

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

poset \displaystyle \mathbf{P}- A jest szerokości co najwyżej \displaystyle {\sf width}\!\left( \mathbf{P} \right)-1


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

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

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

da się pokryć \displaystyle 10 antyłańcuchami

da się pokryć \displaystyle 10 łańcuchami


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

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

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

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

poset \displaystyle \mathbf{P} ma co najmniej \displaystyle 20 elementów


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

\displaystyle 11 -elementowy podciąg niemalejący lub \displaystyle 11 -elementowy podciąg malejący

\displaystyle 10 -elementowy podciąg niemalejący lub \displaystyle 12 -elementowy podciąg malejący

\displaystyle 10 -elementowy podciąg niemalejący lub \displaystyle 10 -elementowy podciąg malejący

żadna z pozostałych odpowiedzi nie jest poprawna


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

poset \displaystyle \left( \mathscr{P}\!\left( X \right),\subseteq \right) ma szerokość \displaystyle 252

poset \displaystyle \left( \mathscr{P}\!\left( X \right),\subseteq \right) ma szerokość \displaystyle 210

poset \displaystyle \left( \mathscr{P}\!\left( X \right),\subseteq \right) ma wysokość \displaystyle 11

poset \displaystyle \left( \mathscr{P}\!\left( X \right),\subseteq \right) ma wysokość \displaystyle 10


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

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

para \displaystyle \left( \mathscr{R},\subseteq \right) jest kratą

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

Żadna z pozostałych odpowiedzi nie jest prawdziwa.