Test na Formální a predikátová logika

Otázka 1: Logický systém je korektní, pokud pro všechny formule φ platí, že platnost φ implikuje její dokazatelnost.

A. Ano

B. Ne

Vysvětlení: Systém je korektní, pokud vše dokazatelné je platné (⊢ φ ⇒ |= φ). Tvrdí-li se, že platnost φ implikuje její dokazatelnost (|= φ ⇒ ⊢ φ), definuje se tím úplnost (sémantická), nikoli korektnost.

Otázka 2: Která z následujících definic správně popisuje rezoluční důkaz formule φ ve výrokové logice?

A. Rezoluční důkaz je sekvence formulí končící φ, kde každá formule je buď axiom nebo je z předchozích odvozena odvozovacím pravidlem.

B. Rezoluční důkaz φ z množiny předpokladů P je sekvence formulí patřících buď do P nebo odvozených z předchozích rezolučním pravidlem.

C. Rezoluční důkaz je dvojice (D, α), kde D je množina a α je zobrazení, která každé proměnné přiřazuje hodnotu z domény.

D. Rezoluční důkaz je sekvence formulí, kde všechny formule jsou pravdivé interpretace Peanovy aritmetiky.

Vysvětlení: Dle studijních materiálů je rezoluční důkaz φ z množiny předpokladů P sekvence formulí patřících buď do P nebo odvozených z předchozích rezolučním pravidlem. Ostatní možnosti popisují jiné koncepty (Hilbertovský důkaz, interpretace jazyka nebo irelevantní tvrzení).

Otázka 3: Konečný tvar výrazu (Y Y Z) ∧ ∧ ∨ (Y ¬Z ¬Y) ∧ ∧ po úpravě je (Y Z) ∧ ∨ (0).

A. Ano

B. Ne

Vysvětlení: V materiálech je uvedeno, že po úpravě se dostane výraz (Y Z) ∧ ∨ (0) a ten se následně podle pravidla X ∨ 0 ⇔ X upraví na konečný tvar (Y Z) ∧. Tudíž (Y Z) ∧ ∨ (0) není konečný tvar.

Otázka 4: Které z následujících vyjádření správně aplikuje zákon distributivity k převedení výrazu A ∨ (B ∧ C) do konjunktivní normální formy (CNF) podle studijních materiálů?

A. (A ∧ B) ∨ (A ∧ C)

B. (A ∨ B) ∧ (A ∨ C)

C. (A ∨ B) ∨ (A ∨ C)

D. (A ∧ B) ∧ (A ∧ C)

Vysvětlení: Studijní materiály uvádějí příklad ¬X ∨ (Y ∧ (¬Z ∨ ¬W)) ⇔ (¬X ∨ Y) ∧ (¬X ∨ ¬Z ∨ ¬W)), který demonstruje zákon distributivity. Zde se výraz ve tvaru A ∨ (B ∧ C) (kde A je ¬X, B je Y a C je (¬Z ∨ ¬W)) převádí na tvar (A ∨ B) ∧ (A ∨ C). To odpovídá možnosti '(A ∨ B) ∧ (A ∨ C)'.

Otázka 5: Kvantifikátor ∀ y je možné přesunout na začátek formule, pokud se proměnná 'y' nevyskytuje v závorce, kterou má přeskočit.

A. Ano

B. Ne

Vysvětlení: Podle studijních materiálů: "∀ y můžeme přesunout na začátek, jelikož se proměnná ' y ' nevyskytuje ve fialové závorce".