Дискретни структури CSF105I 2011-2012

Здравейте,

В час дадох неправилно условието на една теорема и част от доказателството не излезе. Правилното условие на теоремата и д-вото са следните.

Става дума за теоремата за контурите и частичната подредба.  Тя гласи: "Нека R е рефлексивна и транзитивна. При ТЕЗИ условия, R е релация на частична подредба тогава и само тогава, когато R не съдържа контур".


Доказателство, част 1: Нека R е рел. на част. наредба.  От дефиницията на "частична наредба" следва, че R е антисиметрична.

Допускаме, че в R има контур (a1, a2, ..., an). Извеждаме противоречие точно както направихме това в час.


Доказателство, част 2: Нека R не съдържа нито един контур.

Допускаме, че R не е релация на част наредба. Тъй като по условие R е рефл. и транзитивна, следва, че R не е антисиметрична. Щом не е антисиметрична, съществуват различни елементи a и b в A, такива че aRb и bRa
//това е буквално прилагане на отрицанието
// на дефиницията за антисиметричност
Но тогава (a, b, a) е контур в R.  Това е в противоречие с началното допускане, че R няма контури. Следователно, допускането, че R не е релация на част наредба, е грешно.  Следователно, R е релация на частична наредба.


Поздрави,
ММ