Crowdly
Додати до Chrome
Diskreetne matemaatika (LTMS.00.066)
Шукаєте відповіді та рішення тестів для Diskreetne matemaatika (LTMS.00.066)? Перегляньте нашу велику колекцію перевірених відповідей для Diskreetne matemaatika (LTMS.00.066) в moodle.ut.ee.
Отримайте миттєвий доступ до точних відповідей та детальних пояснень для питань вашого курсу. Наша платформа, створена спільнотою, допомагає студентам досягати успіху!
Kuidas võib muutuda suunatud graafi tugevalt sidusate komponentide arv, kui graafist üks kaar kustutada?
Loengukonspektis tõestatakse, et suunatud tsükleid ja silmuseid mittesisaldavas graafis leidub sisend ja väljund.
Teoreem. Kui suunatud graafis pole suunatud tsükleid ja silmuseid, siis leidub graafil vähemalt üks sisend ja vähemalt üks väljund. Tõestus. |
Määra iga järgneva lause puhul, kas lause on selle teoreemi sõnastuses eeldus või väide või pole kumbki.
Vaatleme suunatud graafide tipuastmete teoreemi tõestust.
Teoreem. Igas suunatud graafis on tippude sisendastmete summa võrdne tippude väljundastmete summaga: Σv∈V d−(v) = Σv∈V d+(v). Tõestus. Tippude sisendastmete summa on võrdne graafi kaarte arvuga, sest selle summa leidmisel arvestame iga kaart ühe korra. Samamoodi on väljundastmete summa võrdne kaarte arvuga. Järelikult on need summad võrdsed. |
Milline lause võtab selle tõestuse kõige paremini kokku?
Ülesanne. Tõesta järeldumine ∀x(F(x)∨G) ⊨ ∀xF(x)∨G.
Tõestus. Valime vabalt interpretatsiooni α ja vabade muutujate väärtused. Eeldame, et ∀x(F(x)∨G) = 1. Siis iga elemendi m ∈ Mα puhul F(m)∨G = 1. On kaks võimalust: G = 1 või G = 0.
| 1) | Eeldame, et G = 1. Siis ∀xF(x)∨G = 1. | |
| 2) | Eeldame, et G = 0. Siis iga elemendi m ∈ Mα puhul F(m) = F(m)∨G = 1. Järelikult ∀xF(x) = 1. Seega ∀xF(x)∨G = 1. |
Mis lause sobiks järgmiseks?
Ülesanne. Tõesta järeldumine ∀x(F(x)∨G) ⊨ ∀xF(x)∨G.
Tõestus. Valime vabalt interpretatsiooni α ja vabade muutujate väärtused. Eeldame, et ∀x(F(x)∨G) = 1. Siis iga elemendi m ∈ Mα puhul F(m)∨G = 1. On kaks võimalust: G = 1 või G = 0.
| 1) | Eeldame, et G = 1. Siis ∀xF(x)∨G = 1. | |
| 2) | Eeldame, et G = 0. Siis iga elemendi m ∈ Mα puhul F(m) = F(m)∨G = 1. Järelikult ∀xF(x) = 1. |
Mis lause sobiks järgmiseks?
Ülesanne. Tõesta järeldumine ∀x(F(x)∨G) ⊨ ∀xF(x)∨G.
Tõestus. Valime vabalt interpretatsiooni α ja vabade muutujate väärtused. Eeldame, et ∀x(F(x)∨G) = 1. Siis iga elemendi m ∈ Mα puhul F(m)∨G = 1. On kaks võimalust: G = 1 või G = 0.
| 1) | Eeldame, et G = 1. Siis ∀xF(x)∨G = 1. | |
| 2) | Eeldame, et G = 0. Siis iga elemendi m ∈ Mα puhul F(m) = F(m)∨G = 1. |
Mis lause sobiks järgmiseks?
Ülesanne. Tõesta järeldumine ∀x(F(x)∨G) ⊨ ∀xF(x)∨G.
Tõestus. Valime vabalt interpretatsiooni α ja vabade muutujate väärtused. Eeldame, et ∀x(F(x)∨G) = 1. Siis iga elemendi m ∈ Mα puhul F(m)∨G = 1. On kaks võimalust: G = 1 või G = 0.
| 1) | Eeldame, et G = 1. Siis ∀xF(x)∨G = 1. | |
| 2) | Eeldame, et G = 0. |
Mis lause sobiks järgmiseks?