1.6 Logical inference and logical equivalence

Logical inference

We say that the sentence A logically entails (implies) the sentence B, or that B is a logical consequence of A, or that B logically follows (can be logically inferred) from A, when it is not possible for B to be false in case A is true. It does not matter whether A or B are true or false in factB may or may not be a logical consequence of A when both are true as well as when both are false. To determine whether B is a logical consequence of A, we have to consider all possible truth values of A and B, not just their actual truth value. A entails B when there is no possibility in which A is true and B is false.

We will use a horizontal line or the symbol “⇒” in order to express that one or more sentences (formulas) logically imply a sentence (formula). For example, that A logically implies B will be expressed by

AB or A
B

To express that А1, A2 and А3 logically entail B, we will write

А1
A2
А3
B

There is a connection between the notion of tautology and the notion of logical inference: (in propositional logic) a sentence B is a logical consequence of a sentence A if and only if the sentence “If A, then B” is a tautology:

АB if and only if “АВ” is a tautology.

The reason for the connection is as follows. B is a logical consequence of A when it is logically impossible A to be true and B false. The conditional sentence “If A, then B” is false exactly when A is true and B is false. Therefore, the logical impossibility for B to be false when A is true (i.e. A logically entailing B) coincides with the impossibility for the sentence “If A, then B” to be false. In propositional logic, however, it is logically impossible for a sentence to be false if and only if it is a tautology.

The above connection gives us the following method to test whether the sentence B is a logical consequence of the sentence A. We form the conditional of A and B (“AB”) and check if is it is a tautology. If it is, then A logically entails B; if it is not, A does not entail B (at least from the point of view of propositional logic). Consider the following inference as an example:

(1) Either it is not the case that the Oracle’s prediction is true and was correctly interpreted, or if there is a sea battle tomorrow, the Persians will not defeat the Greeks.
If there is a sea battle tomorrow and the Persians defeat the Greeks, then either the Oracle’s prediction is not true or it was misinterpreted.

To find out whether the conclusion is validly inferred from the premise, we will symbolically represent the two sentences, then form the conditional of the resulting formulas, and finally check (by a truth table or a truth-value analysis) whether this conditional is a tautology. As the sentences are relatively complex, to be sure that they are symbolized correctly we will use the systematic way for representing natural language sentences introduced in 1.2 Conditional and biconditional.

As a whole, the premise is an “or”-sentence (a disjunction) between “It is not the case that the Oracle’s prediction is true and was correctly interpreted” and “If there is a sea battle tomorrow, the Persians will not defeat the Greeks”:

(It is not the case that the Oracle’s prediction is true and was correctly interpreted) ∨ (If there is a sea battle tomorrow, the Persians will not defeat the Greeks)

The disjunction’s first sentence is a negation of the conjunction of the simple sentences “the Oracle’s prediction is true” and “the Oracle’s prediction was correctly interpreted”. Symbolizing the first by “p” and the second by “q”, we get

¬(pq) ∨ (If there is a sea battle tomorrow, the Persians will not defeat the Greeks)

The disjunction’s second sentence is a conditional whose antecedent is the simple sentence “There will be a see battle tomorrow” and whose consequent is the negation of the simple sentence “Persians will defeat the Greeks”. Symbolizing the first simple sentence by “r” and the second by “s”, we obtain the following presentation of (1)’s premise:

¬(pq) ∨ (r→¬s)

The conclusion of (1) is the conditional of the sentences “There will be a sea battle tomorrow and the Persians will defeat the Greeks” and “Either the Oracle’s prediction is not true or it was misinterpreted”:

(There will be a sea battle tomorrow and the Persians will defeat the Greeks) → (Either the Oracle’s prediction is not true or it was misinterpreted)

The conditional’s antecedent is the conjunction of the simple sentences “There will be a sea battle tomorrow” and “The Persians will defeat the Greeks”, which were symbolized above by “r” and “s” respectively:

(rs) → (Either the Oracle’s prediction is not true or it was misinterpreted)

The consequent of the conditional is the disjunction of the negation of the simple sentence “The Oracle’s prediction is true” and the negation of the simple sentence “The oracle prediction was correctly interpreted”. The first simple sentence was symbolized above by “p” and the second by a “q”. So, we obtain the following symbolic expression for the conclusion of (1):

(rs) → (¬p∨¬q)

Thus, the symbolic representation of the initial inference in (1) is the following:

(2) ¬(pq) ∨ (r→¬s)
(rs) → (¬p∨¬q)

(2) is called an inference scheme. To see whether this inference scheme, and hence the particular inference (1), are logically valid, we have to connect the premise and conclusion of the scheme into a conditional and to check whether it is a tautology. The conditional is

[¬(pq)∨(r→¬s)] → [(rs)→(¬p∨¬q)]

We will check if it is a tautology by truth-value analysis (alternatively we can use a truth table but it will have 16 rows):

[¬(pq)∨(r→¬s)] → [(rs)→(¬p∨¬q)]
Case 1 r: T
[¬(pq)∨(T→¬s)] → [(T∧s)→(¬p∨¬q)]
[¬(pq)∨¬s] → [s→(¬p∨¬q)]
p: T p: F
[¬(T∧q)∨¬s] → [s→(F∨¬q)] [¬(F∧q)∨¬s] → [s→(T∨¬q)]
q∨¬s] → [s→¬q] [¬F∨¬s] → [s→T]
s: T s: F [T∨¬s] → T
q∨F] → [T→¬q] q∨T] → [F→¬q] T
¬q → ¬q T → T
T T
Case 2 r: F
[¬(pq)∨(F→¬s)] → [(F∧s)→(¬p∨¬q)]
[¬(pq)∨T] → [F→(¬p∨¬q)]
T → T
T

The conditional is a tautology, which means that the inference is logically valid – the first sentence in (1) logically entails the second.

By symbolically representing the particular inference (1), we obtained the inference scheme (2), which expresses its logical form. That the inference scheme is logically valid means that (1) as well as any other inference that has the same logical form, i.e. which is obtained from (2) by interpreting “p”, “q”, “r” and “s” as any particular sentences, will also be logically valid.

Let’s summarize. We have the following method for determining whether a natural language sentence B is a logical consequence of a natural language sentence A in terms of propositional logic. Representing symbolically A and B by the formulas α and β respectively, we obtain the inference scheme

α
β

Whether the particular inference is logically valid or not depends on the logical validity or invalidity of this scheme. To find out if the scheme is valid, we connect α and β with conditional and check (by truth-value analysis or a truth table) whether the resulting formula “α→β” is a tautology. If it is a tautology, the inference scheme is logically valid; if it is not, it is not logically valid (at least in terms of propositional logic). The logical validity (respectively invalidity) of the inference scheme indicates the logical validity (invalidity) not only of the particular inference but also of any other inference that has the same logical form.

But what about an inference that has more than one premise? For example, what about the logical validity of

(3) A1
A2
A3
B

where A1, A2, A3 and В are some particular sentences.

When the premises are more than one, they can be combined by conjunctions into one sentence. For example, (3) can be reformulated as:

(4) A1A2A3
B

The reason is that a conjunction sentence is equivalent to the assertion that each of the conjuncts is true, which is why (4), like (3), expresses that if each of А1, А2 and А3 is true, then necessarily B is also true. Therefore, when we want to verify that an inference with more than one premise is logically valid, we can check whether the conditional of the conjunction of the premises and the conclusion (in the example “(А1А2А3)→B”) is a tautology. In general, the procedure for determining the logical validity of an inference within propositional logic is as follows. We want to check the validity of an inference with n premises

(5) A1
A2
...
An
B

First, we symbolize the premises and the conclusion, thus obtaining an inference scheme that expresses the logical form of the inference:

(6) α1
α2
...
αn
β

Since the logical validity of the particular inference (5) depends on its logical form as expressed by the inference scheme (6), (5) will be a logically valid inference if and only if (6) is a logically valid inference scheme (at least from the point of view of propositional logic). To determine whether (6) is a logically valid scheme, we check whether the formula “(α1∧α2∧…∧αn)→β” is a tautology. If it is a tautology, the scheme is logically valid and so is the particular inference; if the formula is not a tautology, the scheme is not logically valid and so is the inference.

I have noted in passing a few times above that if the procedure shows that an inference is not logically valid, it is so only from the point of view of propositional logic. The reason is that the means of logical analysis of propositional logic are limited. If an inference is logically valid in terms of propositional logic, it is logically valid without reservation. However, the opposite is not true – if an inference is not valid for propositional logic, it may be that it is actually valid but to show this a deeper analysis than that of propositional logic is needed. For example, the inference

Socrates is a wise man.
There are wise people.

is logically valid but not according to propositional logic because for the latter its conclusion is a simple sentence. Symbolically, the inference looks like this:

pq
r
p – Socrates is wise
q – Socrates is a man
r – There are wise people

Although the inference is valid, the inference scheme obtained by symbolizing it is not, as there is no connection between the premise and the conclusion (“(pq)→r” is obviously not a tautology). To show that such inferences are logically valid we need predicate logic, which has the resources to analyze the logical structure of sentences that are simple for propositional logic.

Now let us check the validity of the following four relatively simple inferences:

(7) If Alice is sick with the flu, she has a fever.
Alice has a fever.
Alice is sick with the flu.
(8) If Alice is sick with the flu, she has a fever.
Alice does not have a fever.
Alice is not sick with the flu.
(9) If Alice is sick with the flu, she has a fever.
Alice is not sick with the flu.
Alice does not have a fever.
(10) If Alice is sick with the flu, she has a fever.
Alice is sick with the flu.
Alice has a fever.

First, we represent them symbolically obtaining the following four inference schemes (“Alice is sick with the flu” is symbolized by “p” and “Alice has a fever” by “q”):

(7′) pq
q
p
(8′) pq
¬q
¬p
(9′) pq
¬p
¬q
(10′) pq
p
q

To determine which of these inference schemes are logically valid, we have to determine which of the following formulas are tautologies: “[(pq)∧q]→p” for (7)′; “[(pq)∧¬q]→¬p” for (8)′; “[(pq)∧¬p]→¬q” for (9)′; “[(pq)∧p]→q” for (10)′. Let us use truth tables for the first two and truth-value analysis for the other two.

p q pq (pq)∧q [(pq)∧q]→p
T T T T T
T F F F T
F T T T F
F F T F T
p q pq ¬q ¬p (pq)∧¬q [(pq)∧¬q]→¬p
T T T F F F T
T F F T F F T
F T T F T F T
F F T T T T T

The first table shows that “[(pq)∧q]→p” is not a tautology, which implies that the inference scheme (7)′ and the particular inference (7) are not logically valid. The invalidity of this inference scheme means that we are not allowed to deduce the antecedent of a true conditional from its consequence. The fact that Alice has a fever does not entail that she is ill with the flu – she may have a fever because of another illness. The second table shows that “[(pq)∧¬q]→¬p” is a tautology, which implies that the inference scheme (8)′ and hence the particular inference (8) are logically valid. The validity of this inference scheme means that we can always deduce the negation of the antecedent of a true conditional from the negation of its consequent. If Alice does not have a fever, she cannot be sick with the flu, because if she were sick with a flue, the truth of the conditional would guarantee that she would have a fever, which results in her both having and not having a fever. The inference scheme (8)′ is known as modus tollens (Latin: method of denying).

In general, when using a truth table to determine the logical validity of an inference schema, we could save ourselves some of the columns as follows. For an inference scheme to be valid, it should be impossible for the conclusion to be false when all the premises are true. We could directly determine whether it is so without constructing the conditional of the premises and the conclusion and checking if it is a tautology. Take as an example the inference scheme (7)′, whose invalidity was determined in first table. Its premises correspond to the second and third column, and its conclusion to the first column of the table. To find out whether it is possible for the conclusion to be false when the premises are true, it is sufficient to check if there are rows with the value T in the second and third columns and the value F in the first. If there are such rows, it is possible for the conclusion to be false when the premises are true, which means that the scheme is invalid; if there are not such rows, the scheme is valid. In this case, both premises have the value T in the first and third row. In the first row the conclusion also has the T but in the third row it has the value F, which shows that the inference scheme is invalid. This approach saves us the last two columns of the table. Concerning the inference scheme (8)′, its premises correspond to the third and fourth columns of the second table and its conclusion to the fifth column. Here again we could save ourselves the last two columns if we check whether there is a row in the table in which the two premises have the value T and the conclusion the value F. The only case in which both premises have the value of T is the last row. The conclusion also has the value T in it, which shows that it is not possible for the conclusion to be false when the premises are true; so the inference scheme is valid.

Now let us check the logical validity of the inference schemes (9)′ and (10)′ by truth-value analysis instead of truth tables:

[(pq)∧¬p] → ¬q
p: T p: F
[(T→q)∧F] → ¬q [(F→q)∧T] → ¬q
F → ¬q [T∧T] → ¬q
T T → ¬q
¬q
q: T
F
[(pq)∧p] → q
p: T p: F
[(T→q)∧T] → q [(F→q)∧F] → q
qq F → q
T T

The first analysis shows that “[(pq)∧¬p]→¬q” is not a tautology, which means that the inference scheme (9)′, as well as the particular inference (9), are not logically valid. In principle, the negation of the antecedent of a true conditional does not entail the negation of its consequent. In particular, the fact that Alice is not sick with the flu does not entail that she has no fever – her fever may be caused by another illness.

The second truth-value analysis shows that “[(pq)∧p]→q” is a tautology, which means that the inference scheme (10)′, as well as the particular inference (10), are logically valid. The antecedent of a true conditional implies its consequent. This is the most famous inference scheme in propositional logic. Its name is modus ponens (Latin: method of affirming).

Logical equivalence

Two sentences are logically equivalent when they logically follow from each other. Such are, for example, the following two sentences:

(11) It is not true that Alice asked Bob to help her and he refused.

(12) Either Alice didn’t ask Bob to help her or he didn’t refused to help her.

Through the method introduced, we can make sure that the sentences entail one another. If the simple sentences “Alice asked Bob to help her” and “Bob refused to help Alice” are symbolized by “p” and “q” respectively, (11) and (12) are symbolized by the following formulas:

¬(pq)
¬p∨¬q

The truth-value analyzes below show that the two formulas are logical consequences of one another, i.e. that they are logically equivalent:

¬(pq) → (¬p∨¬q) p∨¬q) → ¬(pq)
p: T p: F p: T p: F
¬(T∧q) → (F∨¬q) ¬(F∧q) → (T∨¬q) (F∨¬q) → ¬(T∧q) (T∨¬q) → ¬(F∧q)
¬q → ¬q ¬F → T ¬q → ¬q T → T
T T T T

We will signify logical equivalence by “⇔”. Here we have

“¬(pq)” “(¬p∨¬q)”

This equivalence scheme is called De Morgan’s law.

There is a shorter way to determine if two formulas are logically equivalent. Instead of checking whether β is a logical consequence of α and α of β, we can only check whether their biconditional, α↔β, is a tautology. If it is a tautology, α and β are logically equivalent, if not, they are not logically equivalent. The reason for this is as follows. Earlier in 1.2 Conditional and biconditional we saw that α↔β can be considered as an abbreviation of (α→β)∧(β→α). Therefore, if α↔β is a tautology, it will not be possible for α→β and β→α to be false (otherwise (α→β)∧(β→α) will not be a tautology). But if it is not possible for α→β and β→α to be false, they are tautologies and hence α logically follows from β and β from α, in other words α and β are logically equivalent. We get that if α↔β is a tautology, α and β are logically equivalent. Conversely, if α and β are logically equivalent, they will be logical consequences of each other, and thus α→β and β→α will be tautologies, i.e. it will not be possible for them to be false. But then for their conjunction it will also not be possible to be false, i.e. (α→β)∧(β→α) will be a tautology, and therefore also α↔β. We showed that α and β are logically equivalent if and only if α↔β is a tautology.

So, we have the following procedure to verify that two sentences A and B are logically equivalent. We represent them symbolically by some formulas α and β, and then check whether their biconditional α↔β is a tautology. If it is a tautology, the formulas α and β (as well as the sentences A and B) are logically equivalent; if it is not a tautology, the formulas and the sentences are not logically equivalent (at least in terms of propositional logic).

We saw above that the sentences (11) and (12), which were symbolized by the formulas “¬(pq)” and “¬p∨¬q”, are logically equivalent through two truth-value analyzes, which showed that the formulas and the sentences are logical consequences of each other. As stated in the above two paragraphs, we could also use only one truth-value analysis by checking whether “¬(pq)↔(¬p∨¬q)” is a tautology:

¬(pq) ↔ (¬p∨¬q)
p: T p: F
¬(T∧q) ↔ (F∨¬q) ¬(F∧q) ↔ (T∨¬q)
¬q ↔ ¬q ¬F ↔ T
T T

If we use truth table instead of truth-value analysis, we can save ourselves the last column of the table by checking whether the truth values under α and β are the same (not checking whether α↔β is a tautology). α↔β is true when α and β have the same truth value. Therefore, α↔β is a tautology when the values under α and β are the same, i.e. when the two formulas have the same truth tables. For example, the logical equivalence of “¬(pq)” and “¬p∨¬q” can be seen from the following truth table:

p q pq ¬(pq) ¬p ¬q ¬p∨¬q
T T T F F F F
T F F T F T T
F T F T T F T
F F F T T T T

The table shows that “¬(pq)” and “¬p∨¬q” are logically equivalent as their truth tables (the values below them) are the same. In general, two formulas are logically equivalent in propositional logic if and only if they have the same truth tables.

When two sentences are logically equivalent, they can be considered synonymous. The reason is that when the sentence A logically implies the sentence B, the meaning of B is somehow contained in that of A. Therefore, if the sentences are logically equivalent, the meaning of one will be contained in the meaning of the other, and vice versa, and so the meaning of each of them will contain nothing that is not contained in the meaning of the other.

Another way to see this is through the concept of truth conditions. The truth conditions of a sentence consist in all possible circumstances under which it is true. If one knows principally in what circumstances a particular sentence is true, this indicates that he or she understands it (knows what it means). For example, if we are interested in whether a person who learns English knows the meaning of the sentence “It is raining”, we may ask her (let say it is a girl) in various situations if it is true. If she always replies in the affirmative when it is raining, and in the negative when it is not, this indicates that she knows its truth conditions and therefore understands it. On the contrary, if sometimes she does not answer correctly, it will be a sign that she does not know its truth conditions and will make us suspect that she does not understand its meaning. In propositional logic, a sentence’s truth conditions are given by its truth table. Logically equivalent sentences have the same truth table, so they have the same meaning.

For as much as logically equivalent expressions are synonymous, they are interchangeable with one another. If we replace part of an expression with an expression that has the same meaning, we can expect that the meaning of the whole expression will not change. This is true of the symbolic language of logic. If α and β are logically equivalent formulas and α is a proper part of some more complex formula, we can replace α with β without changing the meaning of the whole formula, which of course means that its truth value will not change either. The fact that logically equivalent expressions can be interchanged when they are parts of other expressions, without changing the true values of the latter, is an important principle in logic. We will call it the principle of substitution of (logical) equivalents.

Substitution of equivalents:
If α and β are logically equivalent formulas and α is a subformula of the formula …α…, then if we replace α with β, the resulting formula …β… will be logically equivalent to …α…

The principle enables us to deduce formulas by replacing parts of formulas with logically equivalent formulas. For example, based on the equivalence between “¬(pq)” and “¬p∨¬q” established above, from “¬[(¬р∨¬q)∧¬r]” we may deduce “¬[¬(pq)∧¬r]”. The latter formula can be validly inferred from the former since it is obtained from it by replacing “¬p∨¬q” with the logically equivalent formula “¬(pq)“.

Exercises

(Download the exercises as a PDF file.)
(1) Determine whether the following inference schemes are logically valid:
1) pq
q
p
2) pq
¬q → ¬p
3) pq
qr
pr
4) p ∨ (qr)
(pq) ↔ (pr)
5) pq
¬p
¬q
6) p ∨ ¬q
¬q ↔ ¬p
p → ¬q
7) p → (qr)
(pq) → (pr)
8) p → (qr)
(pq) ↔ (pr)
(2) Determine whether b) is a logical consequence of a):
1) a) If Bob didn’t do the robbery, Paul did it and Harry lied.
b) Either it isn’t true that neither Bob nor Paul did the robbery, or Harry did not lie.
2) a) The company is responsible if and only if the software is its own and was installed before January.
b) If the software is of the company, then it was installed before January and the company is responsible. If the software is not of the company, then it was not installed before January and the company is not responsible.
3) a) The ships went through either the southern or the northern strait. If the weather was good, they went through the southern strait and were not attacked by pirates. If they went through the northern strait, they were attacked by pirates.
b) If the ships were not attacked by pirates, the weather was good.
4) a) In case the sunset is red, if it is windy tonight, the sea will be stormy tomorrow.
b) If the sunset is red or it is windy tonight, the sea will be stormy tomorrow.
5) a) If John has a beard, I will either not recognize him or, if I recognize him, I won’t greet him.
b) If I greet John, I will have recognized him, and if I don’t greet him, he will have a beard.
6) a) If you moralize to others and you are convinced that you are moral, you are not moral. If you are moral, you do not moralize to others and you are not convinced that you are moral.
b) If you are not convinced that you are moral, you are not moral if and only if you moralize to others.
(3) Prove the following logical equivalences:
1) ¬¬р р
2) pq ¬q→¬p
3) ¬(рq) ¬p∨¬q
4) рq (pq)∨(¬p∧¬q)
5) р∨(qr) (рq)∧(рr)
6) pq ¬(p∧¬q)
7) ¬(рq) ¬p∧¬q
8) [(pq)→p] p
9) ¬(рq) р↔¬q
10) р∧(qr) (рq)∨(рr)
(4) Determine if a) and b) are logically equivalent:
1) a) It’s not true that if Alice doesn’t call Peter, he’ll call her.
b) It’s not true that if Peter doesn’t call Alice, she’ll call him.
2) a) If it is true that if wolfs came at night, the dogs barked, then no wolfs came at night.
b) Neither wolfs came at night nor the dogs barked.
3) a) In case the sunset is red, if it is windy tonight, the sea will be stormy tomorrow.
b) If the sunset is red and it is windy tonight, the sea will be stormy tomorrow.
4) a) If John is guilty, then Peter is innocent, and George is lying.
b) If George is not lying, then John is not guilty, and if John is guilty, then Peter is innocent.
5) a) Kuwait or Saudi Arabia, but not both, will cut oil prices.
b) Kuwait will cut oil prices if and only if Saudi Arabia does not cut them.
6) a) If the guard shot the thief, then if he shot him without warning, the guard is guilty.
b) The guard is either guilty or warned the thief or did not shoot him.
7) a) If Bob have taken Alice’s bike without telling her, then he stole it.
b) If Bob didn’t stole Alice's bike, he either hasn’t taken it or has told her that he had taken it.
8) a) If the swamp is drained and a road is built, in a year people’s well-being will improve and the population in the settlement will increase.
b) If the swamp is drained or a road is built, in a year the population in the settlement will increase. If, in a year, people’s well-being is not improved, neither a road will be built nor the swamp will be drained.
9) a) I have never told you such a thing, nor have I ever thought of it, nor will I ever think of such a thing, let alone tell you.
b) Neither if I have never told you such a thing, I will ever tell you that, nor if I have never thought of such a thing, I will ever think of it.