# Logical Equivalence of Wffs in Sentence, Predicate Logic using Tables, Interpretations Resp.

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.

Thanks.

• What do you mean with two statements being equivalent? – Git Gud Apr 11 '15 at 15:48
• 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. – gary Apr 11 '15 at 15:50
• In sentential logic it's just another way of writing the completeness theorem. – 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).

Note

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|$.

• Thanks, +1 , is there a name for this result? – gary Apr 11 '15 at 16:08
• @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. – Mauro ALLEGRANZA Apr 11 '15 at 16:13
• Can we extend this to truth trees, I guess, using interpretations? – gary Apr 11 '15 at 16:17