2

I am trying to prove that equisatisfiability is an equivalence relation and I have to name the number of equivalence classes.

I know I have to prove that it is reflexive, symmetric and transitive. This is what i have so far:

(φ ≈ ψ) if φ is satisfiable ⇐⇒ ψ is satisfiable

  1. Reflexive: φ ≈ φ is true because when φ is satisfiable <--> φ is satisfiable
  2. Symmetric: φ ≈ ψ implies ψ ≈ φ? Yes, coz φ ⇐⇒ ψ is the same as ψ ⇐⇒ φ
  3. Transitive: When φ ≈ ψ and ψ ≈ χ it implies that φ ≈ χ

Is my way of thinking correct? I am not really sure if this is enough for to prove it.

When it comes to the equivalence classes I am totally stuck. Maybe someone can help me here a little bit? Thank you.

Carl Mummert
  • 81,604
canon
  • 31

0 Answers0