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 fact
– B 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
To express that А_{1}, A_{2} and А_{3} logically entail B, we
will write
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 (“A→B”)
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 truthvalue
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
¬(p∧q) ∨ (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:
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:
(r∧s) →
(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):
Thus, the symbolic representation of the initial inference in (1) is the following:
(2) 
¬(p∧q) ∨ (r→¬s)


(r∧s) → (¬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
[¬(p∧q)∨(r→¬s)] → [(r∧s)→(¬p∨¬q)]

We will check if it is a tautology by truthvalue analysis (alternatively we can use a truth table
but it will have 16 rows):
[¬(p∧q)∨(r→¬s)] → [(r∧s)→(¬p∨¬q)]

Case 1 r: T

[¬(p∧q)∨(T→¬s)] → [(T∧s)→(¬p∨¬q)]

[¬(p∧q)∨¬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

[¬(p∧q)∨(F→¬s)] → [(F∧s)→(¬p∨¬q)]

[¬(p∧q)∨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
truthvalue 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
where A_{1}, A_{2}, A_{3} 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) 
A_{1} ∧ A_{2} ∧ A_{3}


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)

A_{1}


A_{2}


...


A_{n}


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:

p ∧ q



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 (“(p∧q)→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′) 
p → q



q



p


(8′) 
p → q



¬q



¬p


(9′) 
p → q



¬p



¬q


(10′) 
p → q



p



q


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

[(p→q)∧p] → q 
p: T 
p: F 
[(T→q)∧T] → q 
[(F→q)∧F] → q 
q → q 
F → q 
T 
T 
The first analysis shows that “[(p→q)∧¬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 truthvalue analysis shows that “[(p→q)∧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:
The truthvalue analyzes below show that the two formulas are logical consequences of one another,
i.e. that they are logically equivalent:
¬(p∧q) → (¬p∨¬q) 

(¬p∨¬q) → ¬(p∧q) 
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
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 “¬(p∧q)”
and “¬p∨¬q”, are logically equivalent through two truthvalue 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
truthvalue analysis by checking whether “¬(p∧q)↔(¬p∨¬q)” is a tautology:
¬(p∧q) ↔ (¬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 truthvalue 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 “¬(p∧q)” and “¬p∨¬q” can be seen
from the following truth table:
p 
q 
p∧q 
¬(p∧q) 
¬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 “¬(p∧q)” 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 “¬(p∧q)” and “¬p∨¬q”
established above, from “¬[(¬р∨¬q)∧¬r]” we may deduce “¬[¬(p∧q)∧¬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 “¬(p∧q)“.
Exercises
(Download the exercises as a PDF file.)
(1)
Determine whether the following inference schemes are logically valid:

4)

p ∨ (q↔r)


(p∨q) ↔ (p∨r)

7)

p → (q→r)


(p→q) → (p→r)

8)

p → (q↔r)


(p→q) ↔ (p→r)

(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)

p→q
⇔
¬q→¬p

3)

¬(р∧q)
⇔
¬p∨¬q

4)

р↔q
⇔
(p∧q)∨(¬p∧¬q)

5)

р∨(q∧r)
⇔
(р∨q)∧(р∨r)

6)

p→q
⇔
¬(p∧¬q)

7)

¬(р∨q)
⇔
¬p∧¬q

8)

[(p→q)→p]
⇔
p

9)

¬(р↔q)
⇔
р↔¬q

10)

р∧(q∨r)
⇔
(р∧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 wellbeing 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 wellbeing 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.
