just curious if there is a formal name for the results that:

a) Two wffs in Sentence Logic are equivalent iff their truth tables are equal , as binary functions of {T,F}

b) Two wffs A,B in Predicate logic are equivalent when : I is an interpretation for A iff I is an interpretation for B.


  • 1
    $\begingroup$ What do you mean with two statements being equivalent? $\endgroup$ – Git Gud Apr 11 '15 at 15:48
  • $\begingroup$ When we can find a derivation/proof of one from he other, e.g., $P \rightarrow Q $ I equivalent to $-P \/ Q$ basically, P,Q are equivalent whenever P iff Q holds. $\endgroup$ – gary Apr 11 '15 at 15:50
  • $\begingroup$ In sentential logic it's just another way of writing the completeness theorem. $\endgroup$ – Git Gud Apr 11 '15 at 15:54

We have that [see Enderton, page 88] :

$\varphi$ and $\psi$ are logically equivalent ($\varphi \equiv \psi$) iff $\varphi \vDash \psi$ and $\psi \vDash \varphi$,

where :

Let $\Gamma$ be a set of wffs, $\varphi$ a wff. Then $\Gamma$ logically implies $\varphi$, written $\Gamma \vDash \varphi$, iff for every structure $\mathfrak A$ for the language and every function $s : V \to |\mathfrak A|$ such that $\mathfrak A$ satisfies every member of $\Gamma$ with $s$, $\mathfrak A$ also satisfies $\varphi$ with $s$.

We have that $\varphi \equiv \psi$ iff $\vDash \varphi \leftrightarrow \psi$ (where : $\leftrightarrow$ is the bi-conditional connective).


A structure $\mathfrak A$ for a first-order language, sometimes called an interpretation, is

a function whose domain is the set of symbols of the language and such that

  1. $\mathfrak A$ assigns to the quantifier symbol ∀ a nonempty set $|\mathfrak A|$ called the universe (or domain) of $\mathfrak A$.

  2. $\mathfrak A$ assigns to each $n$-place predicate symbol $P$ an $n$-ary relation $P^A ⊆ |\mathfrak A|^n$, i.e., $P^A$ is a set of $n$-tuples of members of the universe.

  3. $\mathfrak A$ assigns to each constant symbol $c$ a member $c^A$ of the universe $|\mathfrak A|$.

  4. $\mathfrak A$ assigns to each $n$-place function symbol $f$ an $n$-ary operation $f^A$ on $|\mathfrak A|$, i.e., $f^A : |\mathfrak A|^n \to |\mathfrak A|$.

| cite | improve this answer | |
  • $\begingroup$ Thanks, +1 , is there a name for this result? $\endgroup$ – gary Apr 11 '15 at 16:08
  • $\begingroup$ @gary - they are the general definitions of : logical implication and logical equivalence. For propositional calculus, they coincide with the usual definition in terms of truth valuations, implemented through the truth-table algorithm. $\endgroup$ – Mauro ALLEGRANZA Apr 11 '15 at 16:13
  • $\begingroup$ Can we extend this to truth trees, I guess, using interpretations? $\endgroup$ – gary Apr 11 '15 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.