Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Hardest logic problem!

  1. Nov 13, 2012 #1
    1. The problem statement, all variables and given/known data

    A universal (or ∀_1) formula is one of the form ∀x_1∀x_2...∀x_nθ, where θ is quantifi er-free.
    An existential (or ∃_1) formula is one of the form ∃_1∃_2...∃x_n θ.
    Let A be a substructure of B, and s valuation on A.

    a) Show that if ⊨_B ψ and ψ is universal, then ⊨_A ψ . Also show that if ⊨_A ψ and ψ is existential, then ⊨_B ψ .

    b) Use part (a) to show that the sentence (∃x Px) is not logically equivalent to any universal formula, and that (∀x Px) is not logically equivalent to any existential formula.

    2. Relevant equations


    3. The attempt at a solution

    My professor goes too quickly with satisfiability, and he expects me to solve such problem.

    Here are some thoughts I have..

    a) Since ψ is universal, we can say that ⊨_B ∀x_1∀x_2...∀x_n θ . I would say that since θ is quantifier free, no matter what type of symbols you have for θ, then, it must be just ∀x_1∀x_2...∀x_n θ = θ. I am thinking that I need to use induction principle for this part.

    Seems like I lack some understanding of how the proof should work. -___-

    b) I am not sure how to work out part b.
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted