Matematické Fórum

Mohl by mi někdo poradit s těmito otázkami (resp. zkontrolovat ty, které už mám vypracované)?

1) Ať A je množina logických proměnnych, ať B, C jsou podmnožiny množiny A. Dale jsou φ a ψ dvě formule takové, ze B |= φ  a C |= ψ. Rozhodněte, zda potom nutně platí:
(i)B ⋃ C |=  φ ∧ ψ (Podle mě platí)
(ii)B’ |= ⌐φ, kde B’ = A \ B (Podle mě neplatí)


2) Rozhdněte, zda je pravdive nasledující tvrzení: Jsou dány dvě množiny formulí A,B, dale jsou dany dvě formule α a β  takové, ze α není sémantickým důsledkem A a β není sémantickým důsledkem B. Pak α∧β  není sémantickým důsledkem A⋃B. Jestliže tvrzení platí, zdůvodněte, jestliže neplatí, najděte protipříklad.

Ne; protipříklad lze ověřit tabulkou pro 2 proměnné a, b. A = {a ∨ b}, B = {¬a ∧ ¬b}, alfa = ¬(¬a => b), beta = ¬¬b. Pak A⋃B je {a ∨ b,  ¬a ∧ ¬b}, a toto sjednocení je vždy nepravdivé. Tím pádem sémantickým důsledkem A⋃B je cokoliv, alfa ∧ beta je pravdivá ve všech ohodnoceních, ve kterých je pravdivá množina A⋃B (tj. v žádném).

4) Ať A je množina logických proměnnych, ať B, C jsou podmnožiny množiny A. Dale jsou φ a ψ dvě formule takové, ze B |= φ  a C |= ψ. Rozhodněte, zda potom nutně platí:
(i)B ⋂ C |=  φ ∧ ψ .


(ii)A ⋃ C  |=  φ ⇒ ψ
Ano; A ⋃ C plati jen v pripade ze je množina A nebo C pravdivá. φ ⇒ ψ je pravdive pokud C |= ψ plati, to lze splnit jen kdyz je A ⋃ C pravdiva.

5) Je dána formule ɑ a množina formulí S. Jestliže platí S |= ɑ, pak také S |= (ɑ⇒β) pro každou formuli β. Jestliže tvrzení platí, zdůvodněte, jestliže neplatí, najděte protipříklad.
Ne, tvrzení neplatí. Jelikož formule β může být kontradikce a to nám pokazí implikaci.
6) Je dána formule ɑ a množina formulí S. Jestliže platí S |= ɑ, pak také S |= (β⇒ɑ). Jestliže tvrzení platí, zdůvodněte, jestliže neplatí, najděte protipříklad.
Ano, tvrzení platí. Jelikož platí S |= ɑ, tak implikace je vždy pravdivá ať už dostaneme jakoukouli formuli β.

GRAFY

1) O prostém neorientovaném grafu víte, že má n > 3 vrcholů, n hran a 2 komponenty souvislosti. Kolik nejméně a kolik nejvíce kružnic graf G obsahuje.


2) Existuje souvislý graf G s n > 2 vrcholy, který je acyklický a současně obsahuje otevřený orientovaný eulerovský tah? Jestliže existuje, nakreslete příklad takového grafu G (a zdůvodněte, že je acyklický a že v něm existuje otevřený orientovaný eulerovský tah), jestliže neexistuje, zdůvodněte.
Ne, neexistuje. Pokud je graf acyklický, tak je to graf, který neobsahuje cyklus a v tom případě nemůže obecně nastat případ, že by eulerovský tah obsahoval všechny hrany.

Děkuji za odpověď