When you have to prove that two formulas are logically equivalent, you make a truth table and check whether their their truth table columns are identical. And when you have to prove that a set of formulas logically entails a formula, you are doing the same thing. If I am correct, what is the difference?
[Math] Difference between logical equivalence and semantic entailment
logicpropositional-calculus
Related Solutions
Let's suppose we define a statement form (statement hereafter) as follows:
1) All lower case letters of the Latin alphabet are statements.
2) If $\alpha$ is a statement, then $\alpha$$\lnot$ is statement.
3) If $\alpha$ and $\beta$ are statements, then $\alpha$$\beta$$\land$, $\alpha$$\beta$$\lor$, $\alpha$$\beta$→, and $\alpha$$\beta$≡ (this definition has elegance when working with truth tables).
Though I don't know this text, I would guess that the author would say that all sub-statements or proper sub-statements qualify as component statements of a statement. In other words, if we have a formula $\alpha$ a "component statement" is a statement which appears within $\alpha$.
Now suppose we have a statement which is not a variable or constant, like ab≡c$\lor$a$\land$. I will hope that you find it clear that ≡ does not qualify as a component statement of ab≡c$\lor$a$\land$, nor does b≡. The component statements of ab≡c$\lor$a$\land$ are "a", b, ab≡, c, ab≡c$\lor$, and ab≡c$\lor$a$\land$ (if the statement itself gets allowed to qualify as a component of itself, the last string here listed will qualify as a component statement, if not, then the last statement does not qualify as a component statement.) Consequently, a component statement variable, I would think, comes as nothing more than a component statement which also qualifies as a variable.
When do component statement variables come as identical? When they have the same form. Thus, this passage "Two statements are called logically equivalent if, and only if, they have logically equivalent forms when identical component statement variables are used to replace identical component statements." probably implies that
ab≡c$\lor$a$\land$ is logically equivalent to xb≡c$\lor$x$\land$, as well as fb≡c$\lor$f$\land$, but NOT yb≡c$\lor$z$\land$, because "y" and "z" do not have the same form, but "a" and "a" do have the same form. That may seem trivial, but I will point out that when deriving theses (theorems of the object language) substitutions for variables has to occur uniformly. In other words, substitution has to occur for all instances of the variable in a statement.
If you were to put that example into words, you probably would say something like "the first is equivalent to the second or the third and the first." (it isn't clear in words what this means exactly because we don't have a way to associate the words representing the connectives here naturally). But, you would not say "the second is equivalent to the first or the third and the second" because by doing such you immediately have a second variable appearing before the first variable in that statement. Nor would you say "the first is equivalent to the second or the third and the second," and mean what you said with the first example of this paragraph, because if you did say "the first is equivalent to the second or the third and the second," and they were to mean the same proposition, the first would become the second and it becomes permissible to say "the second is..." which leads back to the other absurdity I spoke about in this paragraph.
The first definition implies the second, but the second does not imply the first. Consequently, he can say that the second definition comes as a special case of the first, and he hasn't contradicted himself.
If you have trouble following the definition given in the first paragraph, you might want to read this Wikipedia.
Basically, the distinction is between talking about a specific situation versus all possible situations.
Suppose I have two different propositional variables $p$ and $q$. Then:
$p$ and $p\wedge p$ are logically equivalent. (Remember that "$\wedge$" means "and.")
$p$ and $q$ are not logically equivalent.
However, $p\iff q$ might be true (e.g. if both $p$ and $q$ happen to be true).
This is ultimately a distinction between talking about general necessities versus specific situations. The keyword here is "model." In the setting of propositional logic (there are other logics), a model is just a specific assignment of truth values to the propositional variables in the language. E.g. suppose our language has propositional atoms $p, q, r$. Then "$p$ and $q$ are true, $r$ is false" (or rather, the function $\nu: \{p, q, r\}\rightarrow\{true, false\}$ sending $p$ and $q$ to $true$ and $r$ to $false$) is a model. Note that given a model, we can also talk about the truth values of more complicated sentences in that model: e.g. "$p\wedge r$" is false according to the model above.
(Indeed, we can prove by "structural induction" that an assignment of truth values to propositional variables uniquely extends to an assignment of truth values to all propositions, which respects the obvious rules - e.g. if $\varphi$ and $\psi$ are both assigned "true," then $\varphi\wedge\psi$ must be assigned "true," and so forth. Sometimes a model is defined as a truth assignment to all propositions, which satisfies these reasonable rules; the proof described in the previous sentence means that we can get away with the simpler definition above.)
When we say that two sentences are logically equivalent, we mean that there is no model in which they have different truth values. The expression "$p\iff q$," however, is a (compound) sentence which is (in general) true in some models and false in others. This is the distinction:
The notion of "logical equivalence" is talking about what things are possible in general.
When we say that a sentence is true/false, we are talking about its truth/falsity in a specific model.
For example, in the model $\nu$ defined above the sentence "$p\iff q$" is true, even though $p$ and $q$ are not logically equivalent (exercise).
At this point, it's useful to introduce a bit of terminology: a sentence which is true in every model is called a tautology. When we say "$\varphi$ and $\psi$ are logically equivalent," we're just saying "$\varphi\iff \psi$ is a tautology."
A bit of more advanced material
There is also a "relative" version of this. Suppose $\varphi$ is some proposition which is true in every model in which the proposition $\psi$ is also true. (Note that this just means that the proposition "$\psi\implies\varphi$" is a tautology.) Then we write "$\psi\models\varphi$."
The value of this new symbol is that it lets us generalize considerably: if $\Gamma$ is a set of propositions, we write "$\Gamma\models\varphi$" iff $\varphi$ is true in every model where every proposition in $\Gamma$ is true. If $\Gamma$ is infinite, this is meaningfully different from just talking about tautologies (since "$\Gamma\implies\varphi$" isn't actually a proposition).
However, one of the most important theorems in logic - the compactness theorem - states that if $\Gamma\models\varphi$ then there is some finite subset $\{\gamma_1, \gamma_2,...\gamma_n\}\subseteq\Gamma$ such that $\{\gamma_1, \gamma_2,...,\gamma_n\}\models\varphi$. And this just means that the proposition "$(\gamma_0\wedge\gamma_1\wedge...\wedge\gamma_n)\implies\varphi$" is a tautology. So via the compactness theorem we can reduce questions about the relation "$\models$" to questions about tautologies, but that's far from obvious.
(And there are important logics which don't have this property, so actually they are meaningfully different in general.)
Related Question
- Conceptual difference between logical equivalency in the context of propositional logic and logical entailment in the context of predicate logic
- Discrete math: logical equivalent statement and statement forms
- Why is this logical expression using $P$, $Q$, $R$ logically equivalent to one using only $P$ and $Q$
Best Answer
To show two formulas, $\varphi$ and $\psi$, are logically equivalent you need to construct a formal proof in the language of propositional logic of $\varphi \leftrightarrow \psi$. To show that $\varphi \vDash \psi$ prove that whenever $\varphi$ is assigned the truth value, then $\psi$ also has the truth value, which as Mauro states is more related to $\varphi \to \psi$. You can do this with truth tables. A priori, constructing a truth table is neither here nor there when it comes to logical (or syntactic) entailment. A witness to logical entailment is a formal proof, and a truth table is not a formal proof.
Now, what we do have is the soundness and completeness theorems which say that $\varphi$ logically entails $\psi$ if and only if $\varphi$ semantically entails $\psi$. These theorems, particularly the completeness theorem, imply that if you can show semantic entailment using truth tables then there exists a formal proof that will show logical entailment. In fact, the completeness theorem is true constructively which is to say that not only does such a formal proof exist in that case, but a constructive proof of completeness is an algorithm that will produce it. The above theorems allow us to conflate logical and semantic entailment for propositional logic, but they are still different things. If I ask you for a formal proof of $\varphi \to \psi$, constructing a truth table and then saying "by completeness" would be like if when I asked you for the inverse of a matrix you checked that the determinant is non-zero and gave me a program for inverting matrices with non-zero determinant. What I expected was an actual matrix! Of course, if I merely asked if the matrix was invertible, then the above would suffice. Luckily, this latter question is indeed what we are usually asking.