Theorem 7. Let p be an open formula of predicate logic. We may view p as formula or of propositional logic by regarding every atomic subformula of y as a propositional letter. With this correspondence, yp is a valid formula of predicate logic if and only if ypl is valid in propositional logic Before proof, consider the following example mple 11. Consider an open formula p of predicate logic and a corresponding proposition by rding every atomic subformula of p as a propositional letter. For example 1.A(x)V=A(x), Here, you can establish a connection between the truth of an atomic formula and a proposition letter. Then you can compare them with their formation tree in further Exercises 1. Let L contain a constant c, a binary function f and a unary predicate P. Give two structures for L: one in which V. P(f(a,c)is true and one in which it is fal 2. Given an example of an unsatisfiable sentence. 3. Prove that A F 3. co(r)+A Varno(r). Does it matter if o has free variables other than 4. Prove that, for any sentence y,Ah(v→彐ro(x)分A上彐(→叭(x). What happens if v is a formula in which a is free? 5. Prove that, for any sentence v, A Fro()v)+AF Va(o(r),v). What happens if a is a formula in which a is free? 6. Translate the following statements into predicates. You can fool some of the people all of the time You can fool all of people some of the time You can't fool all of the people all of the time One or more of the above may be ambiguous, in which case you will need more than one translation 7. Prove Theorem 7Theorem 7. Let φ be an open formula of predicate logic. We may view φ as formula φ′ of propositional logic by regarding every atomic subformula of φ as a propositional letter. With this correspondence, φ is a valid formula of predicate logic if and only if φ′ is valid in propositional logic. Before proof, consider the following example. Example 11. Consider an open formula φ of predicate logic and a corresponding proposition by regarding every atomic subformula of φ as a propositional letter. For example 1. A(x) ∨ ¬A(x), 2. A ∨ ¬A. Here, you can establish a connection between the truth of an atomic formula and a proposition letter. Then you can compare them with their formation tree in further. Exercises 1. Let L contain a constant c, a binary function f and a unary predicate P. Give two structures for L: one in which ∀xP(f(x, c)) is true and one in which it is false. 2. Given an example of an unsatisfiable sentence. 3. Prove that A |= ¬∃xϕ(x) ⇔ A |= ∀x¬ϕ(x). Does it matter if ϕ has free variables other than x? 4. Prove that, for any sentence ψ, A |= (ψ → ∃xϕ(x)) ⇔ A |= ∃x(ψ → ϕ(x)). What happens if ψ is a formula in which x is free? 5. Prove that, for any sentence ψ, A |= (∃xϕ(x) → ψ) ⇔ A |= ∀x(ϕ(x) → ψ). What happens if ψ is a formula in which x is free? 6. Translate the following statements into predicates. • You can fool some of the people all of the time. • You can fool all of people some of the time. • You can’t fool all of the people all of the time. One or more of the above may be ambiguous, in which case you will need more than one translation. 7. Prove Theorem 7. 6