Test na Formális és predikátumlogika

Question 1: Egy logikai rendszer akkor korrekt, ha minden φ formula esetén igaz, hogy φ érvényessége implikálja a bizonyíthatóságát.

A. Ano

B. Ne

Explanation: Egy rendszer akkor korrekt, ha minden bizonyítható érvényes (⊢ φ ⇒ |= φ). Ha azt állítjuk, hogy φ érvényessége implikálja a bizonyíthatóságát (|= φ ⇒ ⊢ φ), azzal a teljességet (szemantikai teljességet) definiáljuk, nem a korrektséget.

Question 2: Melyik definíció írja le helyesen egy φ formula rezolúciós bizonyítását az ítéletlogikában?

A. A rezolúciós bizonyítás egy φ-vel végződő formulasorozat, ahol minden formula vagy axióma, vagy az előzőekből levezetett egy levezetési szabállyal.

B. Egy φ formula rezolúciós bizonyítása P feltételekből egy olyan formulasorozat, amelynek tagjai vagy P-hez tartoznak, vagy az előzőekből lettek levezetve a rezolúciós szabállyal.

C. A rezolúciós bizonyítás egy (D, α) pár, ahol D egy halmaz, és α egy olyan leképezés, amely minden változóhoz hozzárendel egy értéket a tartományból.

D. A rezolúciós bizonyítás egy formulasorozat, ahol minden formula a Peano-aritmetika igaz interpretációja.

Explanation: A StudyFi tananyagok szerint egy φ formula rezolúciós bizonyítása P feltételekből egy olyan formulasorozat, amelynek tagjai vagy P-hez tartoznak, vagy az előzőekből lettek levezetve a rezolúciós szabállyal. A többi lehetőség más fogalmakat ír le (Hilbert-típusú bizonyítás, nyelvi interpretáció vagy irreleváns állítás).

Question 3: A (Y Y Z) ∧ ∧ ∨ (Y ¬Z ¬Y) ∧ ∧ kifejezés végső alakja az egyszerűsítés után (Y Z) ∧ ∨ (0).

A. Ano

B. Ne

Explanation: A StudyFi anyagokban az szerepel, hogy az egyszerűsítés után a (Y Z) ∧ ∨ (0) kifejezést kapjuk, és ez a X ∨ 0 ⇔ X szabály szerint tovább egyszerűsödik a (Y Z) ∧ végső alakra. Ezért a (Y Z) ∧ ∨ (0) nem a végső alak.

Question 4: Az alábbi kifejezések közül melyik alkalmazza helyesen a disztributivitás törvényét az A ∨ (B ∧ C) kifejezés konjunktív normálformába (CNF) alakításához a StudyFi tananyagok szerint?

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

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

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

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

Explanation: A StudyFi tananyagok példaként említik a ¬X ∨ (Y ∧ (¬Z ∨ ¬W)) ⇔ (¬X ∨ Y) ∧ (¬X ∨ ¬Z ∨ ¬W)) kifejezést, amely a disztributivitás törvényét szemlélteti. Itt az A ∨ (B ∧ C) alakú kifejezés (ahol A = ¬X, B = Y és C = (¬Z ∨ ¬W)) az (A ∨ B) ∧ (A ∨ C) alakra alakul át. Ez az '(A ∨ B) ∧ (A ∨ C)' opcióval egyezik meg.

Question 5: A ∀ y kvantifikátor áthelyezhető a formula elejére, ha az 'y' változó nem szerepel abban a zárójelben, amelyet át kell ugrania.

A. Ano

B. Ne

Explanation: A StudyFi tananyagok szerint: "A ∀ y kvantifikátort áthelyezhetjük az elejére, mivel az 'y' változó nem szerepel a lila zárójelben".