Logic 1, WS 2004. Homework 1, given Oct 07, due Oct 14

1. Read carefully the first chapter of the script and write a question or a negative comment related to this chapter.

2. In the definition given during the lecture for the language of propositional logic as a set, express formally the last statement (“F is the smallest set which has the above properties”).

3. Write the grammar (in the sense of formal language theory) which generates the language of propositional logic over the propositional variables A, B, C.

4. Prove:

For any propositional formulae φ_{1}, φ_{2}, …, φ_{n}, ψ,

if φ_{1} ∧ φ_{2} ∧ … ∧ φ_{n} ⊧ ψ then (φ_{1} ∧ φ_{2} ∧ … ∧ φ_{n}) ⇒ ψ is valid

5. Prove:

For any propositional formulae φ_{1}, φ_{2}, …, φ_{n}, ψ,

φ_{1} ∧ φ_{2} ∧ … ∧ φ_{n} ⊧ ψ if and only if φ_{1} ∧ φ_{2} ∧ … ∧ φ_{n} ∧ ¬ψ is inconsistent.