Brief introduction to logic
When one wishes to know the certainty of the
things he believes, he asks himself how he can know that anything
is true. He questions the basis of all his conclusions. And he
searches for a general method of deducing the truth that applies
to every circumstance that he may find. Then, when he applies it
to some particular field of knowledge, he knows that he is free
of any bias or presumption that might lead him astray. This then
is the realm of logic.
Logic is the study of the methods used to determine correct from
incorrect reasoning. Logic tells us that if we use a correct form
of reasoning and the basis of our argument is true, then we can
know beyond any doubt whatsoever that our conclusion is also
true.
There are many branches to the study of logic, and a complete
study of the subject could be quite long and involved. My intent
here is to give a brief introduction to propositional logic, which studies the
truth or falsity of statements. This is also known as Sentential logic or Binary
logic. The readers need not be
concerned about memorizing anything. They may concern themselves
with only understanding the principles as they are explained. For
I provide a reference guide here on a
separate page so the reader may keep track of the results
obtained. The principles derived are numbered so that when they
are mentioned again in later discussion, they can be easily found
in the reference guide. You should be able to go back and forth
between the discussion and the reference guide using the back and
forward buttons on your Web browser without loosing your place.
You may wish to view the reference guide
now as a preview of what will be discussed.
Since we are interested in "proof ", I have chosen to
briefly introduce the concepts of propositional logic. The
concepts developed below are valid in and of themselves and do
not need the use of any additional features of logic to support
them. Some people may be tempted to think that the study of logic
is difficult for the average reader to understand. But I have
chosen not to go into great detail, and I think you’ll find
my treatment of the subject very intuitive and easy to
understand. Considering the subject that can be better
understood, I think it is imperative to try to understand this
material.
Propositional logic is concerned with how sentences combine
propositions to form statements whose truth depends on the
propositions involved. The study of logic does not make reasoning
more difficult. But propositional logic attempts to reduce the
amount of effort it takes to understand general principles. By
using signs and symbols to represent concepts and propositions,
propositional logic reduces the task of reasoning to a mere
mechanical procedure of substituting concepts with equivalent
concepts. So the best place to start our study is to explain what
propositions are.
Propositions are declarative sentences
that make statements about facts. And in that sense they differ
from questions, commands, and exclamations that do not
necessarily assert anything as a fact. Other names used for the
concept of a proposition are "statement",
"fact", "assertion", "assumption",
"supposition", "claim", etc. The following
are examples of propositions:
The light is on. Abraham loves Sarah. The sky is blue. Angels can walk through walls. The grass is green. Creation was once prefect. All men are mortal. Leviathan inhabit the ocean. Some men are evil. This fish is larger. No one is perfect. There is only one God. The end is near. There will come a new heaven and earth.
All these statements are either true
or false. And there are many other types of propositions too. But
every proposition has the quality that it can be asserted as
either true or it can be asserted as false. A proposition is
either true or false. It cannot be both true and false. And it
cannot be neither true nor false. We can only examine the
consequences that result if a given proposition is true, or we
can examine the consequences that result if the proposition is
false. There is no middle ground. What statement do you know that
is both true and false at the same time? Or what statement do you
know that is neither true nor false? If we don’t know
whether a given proposition is true or false, it is because the
proposition is not defined well enough to determine the answer.
Or there is no evidence to support a conclusion.
But just because we make a statement or write it down on paper
doesn’t automatically mean that the statement is true. And
it doesn’t mean that it’s false. We could state a
proposition only for the purpose of debating whether it is true
or false.
And it doesn’t matter what language is used to state a
proposition. We could write a proposition in any language that
exists. We could use different words, different sentence
structure, different spelling, and a totally different set of
symbols. But this would not change the meaning of the statement.
As long as everyone understands what you are referring to, it
doesn’t matter what symbols you use to represent your
proposition.
In fact, it is much easier to visualize concepts if we reduce the
amount of writing it takes to represent propositions. So, for
example, let us agree that instead of writing "the sky is
blue", we will write the letter "B". And instead
of writing "The Moon is made of green cheese", let us
write "C ". And instead of writing "The light is
on", let us write "L". And instead of writing
"The switch is up", let us write "U". So we
have the following abbreviations:
Abbreviation The proposition that it stands for B The sky is Blue C The Moon is made of green Cheese L The Light is on U The switch is Up
Now everyone knows that the sky is blue - in the daytime,
anyway, without any clouds. So we say that the proposition that
the sky is blue is true. And if we use the abbreviations above,
it is easier to write:
B is true.
And everyone knows that the Moon is not made of green cheese. So
the proposition that the Moon is made of green cheese is false.
Or we could more easily write:
C is false.
But without looking, however, we don’t know whether the
light is on or not. So if we were to consider it true that the
light is indeed on, we would write:
L is true.
But if we were to consider the light to be off, then the
proposition that the "The light is on" would be false,
and we would write:
L is false.
And the same goes for the switch being up. We could write:
U is true.
Or we could write:
U is false.
Of course, we could make things easier if we
make some further abbreviations. So, instead of writing the word
"true", let us agree to write "T". And let us
write "F" for the word "false". And instead
of writing the word "is", let us write the equal sign
"=". These are the abbreviations commonly used in this
subject. And this would reduce the previous discussion to the
following:
B=T C=F L=T OR L=F U=T OR U=F
Much easier to write and to visualize!
It is customary to let capital letters
represent specific propositions that have been defined in the
context of what you are reading. "B", "C",
"L", and "U" are examples of specific
propositions that have been defined
above.
It might be debated whether "B", "C",
"L", or "U" are actually true or false. But
the symbols "T" and "F", however, have a
special and unique meaning. "T" is a proposition that
is always true. In other words, it is not even possible to
imagine that "T" is false. And likewise, "F"
is a proposition that must always be considered false.
But if we wish to know whether any other proposition is true or
false, then we are asking what its "truth value" is.
The truth value of a false statement is "false" or
"F". The truth value of a true statement is
"true" or "T".
And it is also customary to let lower
case letters such as "a", "b", "c",
etc., represent generic propositions that have no specific
definition at all. They are just place holders for whatever statements you might
consider. And since they have no particular meaning
attached to them, we must consider the consequences that result
if they are true, and we must consider separately the
consequences if they are false. Such general propositions can be
called "arbitrary" propositions because their truth
values can be arbitrarily assigned. And since their truth values
can vary, they are also called "variables".
Propositional logic makes quite a lot of use of these generic
propositions or variables as they are called. For logic is not so
much concerned about the specific propositions used in language.
But it is concerned more with how propositions in general are
connected in language in order to determine the truth of a
statement.
So, at this point it would be
helpful to classify statements in two ways. A statement can be
classified as either a compound statement or as a simple
statement. A simple statement declares only one thing about one
subject. A compound statement contains two or more simple
statements. It requires at least one sentence to describe a
simple statement. But a compound statement may consist of more
than one sentence. We have already shown some simple statements.
We labeled them "B", "C", "L", and
"U" in the text above. Below are some compound
statements:
1. Some men are not evil 2. It is not true that all snakes are poisonous. 3. It was stated that the earth is flat. But it is not true. 4. God is just and God is kind. 5. Abraham loves Isaac and Ishmael. 6. The pants fit. But the shirt is too short. 7. It will rain or it will shine. 8. One or the other will own the land. 9. You may spend your money now. Or you may save it for later. 10. If the switch is up, then the light is on. 11. The car will move when you step on the gas peddle. 12. Whatever goes up must come down.
Each of the compound statements numbered above is a
proposition in and of itself even if it takes more than one
sentence to describe it. And like any other proposition each
compound statement is either true in its entirety or it is false.
And also like any other proposition, we could label each compound
statement with a capital letter to abbreviate it. Then we might
discuss whether each such labeled statement is true or false. And
we would discover that the truth of these compound statements
depends on the truth value of the simple statements that are
contained in them.
Upon closer examination, we can see that these compound
statements consist of simple statements connected by words like
"and", "or", "not", "if
", "then", "but", and "when".
These words are called connectives. The truth of compound
statements depends on the meaning of these connectives. And we
shall study the meaning of these words as they apply to general
propositions.
From the list of compound statements
above, statements 1, 2, and 3 are repeated again below:
1. Some men are not evil
2. It is not true that all snakes are poisonous.
3. It was stated that the earth is flat. But it is not true.
Statements 1, 2, and 3 are examples of negation. Negation
reverses the truth value of propositions. If a statement would
otherwise be true, then negating it will make it false. And if a
statement would otherwise be false, then negating it will make it
true.
The negation of a statement is usually formed in English by
inserting the word "not" in the original statement.
Other ways of expressing the negation of a statement in English
is to prefix the phrase "it is not the case that" or
"it is not true that".
The symbol commonly used to represent negation is "~"
which is called the "curl" or the "tilde".
Now, since whatever is not true is false and whatever is not
false is true, we may write:
~T=F (eq.1) and ~F=T. (eq.2)
And if the lower case letter "p" represents some
arbitrary proposition, then its negation would be symbolized as
"~ p", and it would be read as, "not p".
You might think that a statement that expresses negation is not a
compound statement since only one statement is involved. But a
compound statement is also a statement whose truth value depends
on the truth value of simple statements. And the dependence that
negation has on a simple statement can be shown in the truth
table below.
p | ~p (def.1) T F F T
The left column lists all the truth values that a simple
statement can have with one value for each row. And for each row
the right column lists the corresponding value for negation. So
this truth table is what is used to define the meaning of the
symbol "~".
Notice also that if p is true, then ~ p is
false, and ~ ~ p is true. And if p is false, then ~ p is true,
and ~ ~ p is false. And if we put this in a truth table, we get:
p | ~p | ~~p T F T F T F
This shows that no matter what the value of p is, p has the
same truth value as
~ ~ p. Or written in symbols we get:
p = ~~p (eq.3)
This is called the law of double negation. And it states that
if anything is negated twice, it is the same as not being negated
at all. Sentences that contain a double negation can be a little confusion. For
example when someone says, "It's not true that something isn't right."
One usually has to think a moment longer to understand that this means that this
something is actually right.
Propositional logic uses truth tables like the one above to
define symbols that represent connectives like "and",
"or", "not", and "if-then". We have
already defined "~" for the word "not". Now
let’s see how a truth table can be used to define the
connective word "and".
From the list of compound statements
above, statement 4, 5, and 6 are repeated again below:
4. God is just and God is kind. 5. Abraham loves Isaac and Ishmael. 6. The pants fit. But the shirt is too short.
Statement 4, 5, and 6 are examples of conjunction. Conjunction
is usually formed by placing the word "and" between two
simple statements. However, other words that indicate a
conjunction are "yet", "also",
"but", "although", "still",
"however", "moreover",
"nevertheless", and so on. Even the comma or a
semicolon can indicate statements joined conjunctively. It might
not seem as though statement 5 above is a conjunction. But
statement 5 can also be written as "Abraham loves Isaac and
Abraham loves Ishmael". And then the conjunction of two
simple statements becomes clear. Statement 6 above uses the word
"But" to join two statements. It also shows how a
compound statement may consist of more that one sentence.
Conjunction can also be called the "AND function". And
two statements joined conjunctively can be said to be
"ANDed" together.
The symbol used for conjunction is the dot "*". So, for
example, in statement 4 above we have two simple statements, one
is "God is just", and the other is " God is
kind". And the conjunction of these two simple statements
can be written as:
God is just*God is kind.
And this would be read as "God is just and God is
kind".
Now some might argue over whether either of these simple
statements is true. But the entire compound statement itself is
not true unless both these simple statements are considered true.
If either one or both of these simple statements is false, then
the entire compound statement is false. For example, if it is not
true that God is just, but it is true that God is kind, then it
is false to assert both that "God is just and God is
kind". Only if it is true that God is just and it is also
true that God is kind is it true to assert that "God is just
and God is kind".
So, if we replace both of the simple statements above with
generic propositions, we can derive a general definition of the
conjunction between any two propositions. Let us replace the
specific proposition "God is just" with the general
proposition "p". And let us replace the specific
proposition "God is kind" with the general proposition
"q". Then the conjunction of p and q can be symbolized
as p*q and is read as "p and q".
p*q is also called a statement because it is the symbolic form of
a statement - a compound statement. But the truth value of the
statement p*q depends on the truth value of p and the truth value
of q. Since p and also q are both variables, any general
definition of conjunction will have to account for every possible
combination of truth values that these two variable can have. It
may be possible that both p and q are false. It may be that p is
false and q is true. It may be that p is true and q is false. Or
it may be that both p and q are true. Then we will want to record
for each combination whether the statement p*q is true or false.
The truth table shown below uses this procedure to define
conjunction for any two arbitrary propositions.
p q | p*q (def.2) F F F F T F T F F T T T
In the truth table shown above, the first two columns on the
left show every possible combination of the two variables p and q
; each row is a different combination. And for each combination
of p and q , the third column shows the corresponding truth value
for the conjunction of that combination. This truth table, then,
defines the meaning of the symbol "*". As can be seen
from the table, the statement p*q is not true unless both p and q
are true. If either one or both p and q is false, then the
statement p*q is false.
And it would not matter whether we were to write p*q or if we
were to write q*p. For neither statement is true unless both q
and p are true. So, we have the following equality:
p*q=q*p (eq.4)
We can also easily form the conjunction of any number of
propositions. If p,q,r,s,t are all generic propositions, then
their conjunction is written as p*q*r*s*t. And their conjunction
is not true unless all these propositions are true. If any one or
more of these propositions are false, then the whole conjunction
statement is false.
It’s worth noting that any proposition ANDed together with a
false statement is always false. Or, if we let p represent our
generic proposition, then
p*F = F (eq.5)
And if a proposition is ANDed together with a true statement,
then the truth value of that conjunction is the same as the
proposition as shown in the following truth table:
p T | p*T See definition of p*q F T F T T T
Or, in other words:
p*T = p (eq.6)
And below is the truth table for a proposition ANDed together with itself:
p p | p*p See definition of p*q F F F T T T
Which shows:
p = p*p (eq.7)
And below is the truth table for a proposition ANDed together with its own negation:
p | ~p | p*~p See definition of p*q F T F T F F
Which shows:
p*~p = F (eq.8)
From our list of compound statements above, statements 7, 8, and 9 are repeated again below:
7. It will rain or it will shine. 8. One or the other will own the land. 9. You may spend your money now. Or you may save it for later.
Statements 7, 8, and 9 are examples of disjunction.
Disjunction is usually formed by placing the word "or"
between two simple statements. However, the word
"unless" can be used to indicate disjunction as in the
sentence "The picnic will be held unless it rains." It
might not seem as though statement 8 above forms the disjunction
of two simple statements. But statement 8 can also be written as
"One will own the land or the other will own the land."
And then the disjunction of two simple statements is made clear.
Statement 9 above shows how a compound disjunctive statement may
consist of more than one sentence.
Disjunction can also be called the "OR function". And
statements joined disjunctively can be said to be
"ORed" together.
The symbol used for disjunction is the plus sign "+".
So, for example, in statement 7 above we have two simple
statements; one is "It will rain", and the other is
"it will shine". And the disjunction of these two
simple statements can be written as:
It will rain + it will shine.
And this would be read as "It will rain or it will
shine".
Now some might argue over whether either of these simple
statements is true. But the entire compound statement itself is
true if either one or both of these simple statements is true.
Only if both of these simple statements are false is the entire
compound statement false. For example, if it is not true that it
will rain, and if it is not true that it will shine ( just a
cloudy day ), then it is false to assert that "it will rain
or it will shine". But if it either rains or the sun comes
out, then it is true to assert that "it will rain or it will
shine".
And since we wish to generalize our discussion, let us replace
these two specific simple statement with the arbitrary variables
p and q. Then the disjunction of p and q can be symbolized as p+q
and is read as "p or q". The truth table shown below
shows how the truth value of the statement
p+q depends on the truth values of p and q .
p q | p+q (def.3) F F F F T T T F T T T T
This truth table defines the meaning of the symbol
"+". And as can be seen from the table, the statement
p+q is true if either p or q or both is true. The statement p+q
is false only when both p and q are false.
And it would not matter whether we were to write p+q or if we
were to write q+p. For neither statement is false unless both p
and q are false. So, we have the following equality:
p+q = q+p (eq.9)
And we can also easily form the disjunction of any number of
propositions. If p,q,r,s,t are all generic propositions, then
their disjunction is written as p+q+r+s+t . And their disjunction
is not false unless all these propositions are false. If any one
or more of these propositions are true, then the whole
disjunction is true.
It is worth noting that any proposition ORed together with a true
statement is always true. Or, if we let p represent any arbitrary
proposition, then
p+T = T (eq.10)
And if any proposition is ORed together with a false statement, then the truth value of that disjunction is the same as the proposition - as is shown in the following truth table:
p F | p+F See definition of p+q F F F T F T
Or, in other words,
p+F = p (eq.11)
And below is the truth table for a proposition ORed together with itself:
p p | p+p See definition of p+q F F F T T T
Which shows:
p = p+p (eq.12)
And below is the truth table for a proposition ORed together with its own negation:
p | ~p | p+~p See definition of p+q F T T T F T
Which shows:
p+~p = T (eq.13)
Compound statements can contain a mixture of AND’s and OR’s and NOT’s. Consider the following statement:
p*q+r
The statement as written is confusing. It could mean that we
are to first find the truth value of p*q and then OR the result
with r. Or it could mean that we are to first find the truth
value of q+r and then AND the result with p . If p is false, and
q and r are both true, then the first interpretation makes the
entire statement true, but the second interpretation makes the
entire statement false. So there needs to be a way to eliminate
this type of confusion.
Parentheses are used to eliminate confusion of this type. The
first interpretation would be written as:
(p*q)+r
The second interpretation would be written as:
p*(q+r)
Parentheses must be used in statements where confusion would otherwise result. And when parentheses are used, the truth value of what is inside the parentheses must be determined first before what is outside the parentheses can be determined. And, of course, there can be parentheses inside of parentheses as in the following statement:
p*(q+(r*s))
And by convention, ~p+q means (~p)+q
. It does not mean ~(p+q).
We should note at this point that (p*q)*r
= p*(q*r) = (p*q*r) since none of these statements is true
unless p , q , and r are all true. (eq.14)
And (p+q)+r = p+(q+r) = (p+q+r)
since none of these statements is false unless p , q, and r are
all false. (eq.15)
So far we have been talking about the inclusive sense of the word
"or". It is called inclusive because the truth of p+q
includes the possibility of both p and q being true. But there is
also an exclusive sense of the word "or". For example,
when we say, "a statement is true or a statement is
false", we do not mean to say that a statement can be both
true and false at the same time. We mean to say one or the other
exclusively - excluding the possibility of both being true at the
same time.
There is no need to develop another symbol for the exclusive or,
however. For the exclusive or can be described with symbols we
have already defined. If we wish to make it explicitly clear that
we intend to use the inclusive or in English, we can use the
phrase "and/or" as in "something and/or
something". And we symbolize this as p+q . But if we wish to
make it explicitly clear that we intend to use the exclusive or,
then we can add the phrase "but not both" as in
"one or the other but not both". And we can symbolize
the exclusive or as (p+q)*~(p*q).
Now that we have studied the functions of AND and OR and
NOT and the use of parentheses, it is possible to show how the
AND function can be described in terms of the OR function and
visa versa.
The truth table below shows how the AND function can be described
with the OR function.
1 2 3 4 5 6 7 p q | p*q | ~p | ~q | ~p+~q | ~(~p+~q) F F F T T T F F T F T F T F T F F F T T F T T T F F F T
Columns 1 and 2 show every possible combination of p and q .
Column 3 shows the conjunction of columns 1 and 2. Column 4 is
the negation of column 1. Column 5 is the negation of column 2.
Column 6 is the disjunction of columns 4 and 5. And column 7 is
the negation of column 6.
Since column 7 is the same as column 3 for every possible
combination of p and q , column 7 is logically equivalent to
column 3. For there is no possible combination of p and q for
which column 7 is not the same as column 3. So we may write:
p*q = ~(~p+~q) (eq.16)
Or, in language, to say that we have p and q is exactly the
same as saying that we can not have neither p nor q .
We will use a different method to show that the OR function can
be described with the AND function.
Starting with the fact that p*q = ~(~p+~q), let us negate both sides of the equal sign. For
we know that if we do the same thing to both sides of the equal
sign, the equality of what results will still hold true. Thus we
get:
~(p*q) = ~~(~p+~q)
And the rule of double negation gives:
~(p*q) = (~p+~q)
Now if you recall, we can label a statement with any symbol we can imagine as long as it is clear from context what the symbol represents. So let the letter "s" represent the statement "~ p". Or, we may write s = ~ p . And if we negate both sides of this and use the rule of double negation, we get ~ s = p. Similarly, let t = ~ q , then ~ t = q. And if we substitute s and t into ~(p*q) = (~p+~q) , we will get:
~(~s*~t) = (s+t)
Since the above is true for any two propositions no matter what they are labeled, then the above equation is also true for propositions p and q . As long as we exchange the same symbol wherever we find it, both sides will remain equal. We will exchange p for s , and we will exchange q for t. Then we get:
~(~p*~q) = (p+q)
And since it doesn’t matter which side is on the right or left of the equal sign, we can write:
p+q = ~(~p*~q) (eq.17)
as we wished to show.
From our list of compound statements above, statements 10, 11,
and 12 are repeated again below:
10. If the switch is up, then the light is on. 11. The car will move when you step on the gas peddle. 12. Whatever goes up must come down.
Statements 10, 11, and 12 are examples of conditional
statements. They are called conditional statements because one
fact is asserted to be true on the condition that another fact is
true. A conditional statement is usually indicated by the use of
the words "if " and "then". Statements 11 and
12, however, show other ways to express a conditional statement.
But since all conditional statements can best be expressed as an
"if-then" statement, we will discuss conditional
statements in terms of "if " and "then".
The simple statement which comes after the "if " but
before the "then" is called the antecedent. The simple
statement that comes after the "then" is called the
consequent. For example, in statement 10 above, it is stated,
"If the switch is up, then the light is on". The
antecedent is the simple statement, "the switch is up".
The consequent is the simple statement, "the light is
on". A conditional statement asserts that IF the antecedent
is true, THEN the consequent must also be true. In other words,
the consequent is true on the condition that the antecedent is
true.
A conditional statement does not assert that the antecedent is
necessarily true. It only asserts that if the antecedent is true,
then the consequent is true. And a conditional statement does not
assert that the consequent is necessarily true. It asserts that
the consequent is true only if the antecedent is true. So a
conditional statement allows us to consider every possible truth
value for the antecedent or the consequent.
A conditional statement describes a relationship between the
antecedent and the consequent. This relationship is called
"material implication" because the antecedent being
true implies that the consequent is true.
And we symbolize the relation of material implication with a
right pointing arrow "=>". So, if we let the
arbitrary variable p represent a generic antecedent, and if we
let the variable q represent a generic consequent, then the
relationship of material implication between p and q is
symbolized as p=>q and is read " p implies q " . Or,
we could equally say, "IF p is true, THEN q is true."
The right pointing arrow is an appropriate symbol for material
implication because it symbolizes the truth of p being
transferred to q .
Conditional statements are very closely related to the concept of
an argument. Both arguments and conditional statements convey the
sense that one fact implies another. An argument occurs when one
proposition is claimed to logically follow from other
propositions. An argument asserts that one proposition is
required to be true on the basis of the fact that other
propositions are true. The propositions that forms the basis of
an argument are called the premises. The proposition that is
claimed to follow logically from the premises is called a
conclusion. In an argument, the conclusion is asserted to be true
on the basis that the premises are true. The premises provide
reasons that require us to believe that the conclusion is true.
Below are some examples of arguments (The premise (p) and the
conclusion (c) are labeled in each)
We know that the Moon is not made of green cheese (c) since the
astronauts have brought back Moon rocks (p).
Because the car is moving up the mountain at constant speed (p),
the car must have a motor (c).
All humans are mortal, and Socrates is human (p).
Therefore, Socrates is mortal (c).
A conclusion typically follows words like
"therefore", "hence", "thus",
"so", "consequently", "it follows
that", "we may infer that", "we may
conclude", etc. And a premise typically follows words like
"since", "because", "for",
"as", "in as much as", and "for the
reason that".
Conditional statements do not assert that any statement is true.
They assert only that if one statement is considered true, then
another statement must also be considered true. However,
arguments definitely assert that propositions are true. Arguments
assert that the premises are indeed true. And since they also
claim that the conclusion therefore follows, they assert that the
conclusion is also true. Thus, the language of arguments do not
allow us the option of possibly considering the premises or the
conclusion to be false. And in that sense the language of
arguments is too restrictive for use in the discussion of general
principles. For a general discussion of logical principles must
allow us the option of considering every possible truth value for
all the generic propositions involved.
However, if we replace the specific propositions used in an
argument with generic variables, then we will have a construction
for the general form of an argument. Let p represent the generic
premise of an argument. And let q represent the generic
conclusion of an argument. Then an argument has a form which can
be stated as " p proves q ". An argument form can also
be stated as " Because of p , therefore q ", " q
is implied by p", " p, hence q", "we may
conclude q for the reason p ", etc.
Since the lower case letters, p and q , are generic propositions,
it is understood that we are allowed the option to consider
either of them true or false. Then the argument form is
understood to not be stating that any proposition is necessarily
true. And so the argument form is equivalent to a conditional
statement. The generic premise of an argument is the antecedent
of a conditional statement, and the generic conclusion is the
consequent. And so, the relationship of material implication is
symbolized as p=>q . And material implication may be stated in
any of the following ways:
If p , then q . Since p , hence q . Because p , we may conclude q . When p , we get q . In as much as p , we have q . q is true for the reason p . q is required by the fact of p . p leads us to believe q . p is evidence for q. q is proven by the fact of p . p is responsible for the fact of q . p gives us cause to believe q . p proves q . p demonstrates q . p implies q . p determines q . p produces q . p causes q . p establishes q . p creates q . p verifies q . p justifies q . p supports q . p vindicates q . p , therefore q . p , consequently q . p , thus q . p , for q . q is proven by p . q is demonstrated by p . q is implied by p . q is determined by p . q is established by p . q is produced by p . q is deduced from the fact of p . q is discerned from p . p results in q . q results from p q is supported by p . q is verified by p .
All these ways and more describe the relationship of material implication. Each states that p materially implies q . And each can be symbolized by writing:
p=>q
And all these different ways of describing material
implication only stresses the importance of understanding it. The
meaning of proof is the most important thing to understand about
logic. For learning by definition is discovering how facts follow
from other facts. And if we are ever to be sure that we have
proven anything, then we need to know what is meant by saying one
fact proves another.
But proof is just another way of describing material implication.
And this means that it is imperative to understand the meaning of
material implication. In other words, we need to know the truth
table for p=>q . What
combinations of truth values for p and q are allowed if it is
true that p materially implies q ? And what combinations of p and
q are disallowed by material implication?
Material implication asserts that if the premise of an argument
is true, then we are required to assert that the conclusion is
also true. So, let p be the premise, and let q be the conclusion.
And we have the following part of the truth table:
p q | p=>q T T T
But if the definition of implication requires q to be true when p is true, then if q is false when p is true, then the statement that p implies q is not true. And we have the following part of the table:
p q | p=>q T F F
Instead, if q is false, then p must also be false for the
statement of implication to be true.
And we have the following part of the table:
p q | p=>q F F T
But nothing in the form of an argument prevents the conclusion from being true even though the premise may be false. For there may be other reasons why the conclusion is true. And stating that a true premise requires a true conclusion does not mean that a true conclusion requires anything from the premise. So a valid argument allows the condition of a true conclusion with a false premise. And so we have the last part of the table:
p q | p=>q F T T
Now, putting all parts of the table together, we get:
p q | p=>q (def.4) F F T F T T T F F T T T
It may help to give a few examples that illustrate the
relationship of material implication.
Suppose there is a switch that completes an electrical circuit
that operates an incandescent light bulb. Then this situation is
described by the conditional statement:
"If the switch is closed, then the light is on."
Let C represent the statement, "the switch is closed".
So if the switch is closed, then C is true. And if the switch is
open, then C is false. And let L represent the statement,
"the light is on". So if the light is on, then L is
true. But if the light is off, then L is false. And the situation
can be symbolized as C=>L .
If everything is wired correctly, then if it is true that the
switch is closed, then it must be true that the light is on. Or,
in symbols,
(C=>L) = T, for C = T, and L = T.
But since that switch causes power to flow to the light, if the
light is off, then the switch must be open. Or, in symbols,
(C=>L) = T, for C = F , and L = F.
And we know that the circuit is not operating correctly when the
switch is closed, but the light is off. Or, in symbols,
(C=>L) = F when C = T, but L = F.
However, even though our circuit is operating correctly, there
may be other switches that cause power to flow to the light even
though our switch is open. Or, in symbols,
(C=>L) = T for C = F , and L = T .
And all four paragraphs above demonstrate the truth table for
material implication as we have already shown.
As another example of material implication, we know that the
following conditional statement is true:
"If a certain man has died, then that certain man was
born."
Let D now represent the statement, "a certain man has
died". So, if we find that a certain man has died, then D is
true. But if we find that this certain man has not died, then D
is false. And let B now represent the statement, "that
certain man was born". So, if a certain man by name was
born, then B is true. But if we find that a certain man by name
was not born, then B is false. And this situation can be
symbolized as (D=>B).
Now, we know that if it is true that a certain man is found dead,
then it is also true that this certain man was born. Or, in
symbols
(D=>B) = T, for D = T, and B = T.
And we also know that if a certain man by name was never born,
then it’s not possible for him to die. Or, in symbols,
(D=>B) = T, for D = F , and B = F.
But if we should ever find a man that is found dead, and we can
prove that he was never born, then we will know that our
conditional statement is not true. Or, in symbols
(D=>B) = F, for D = T, and B = F.
And our conditional statement is still true even if we know that
this certain man with a given name was born but he has not yet
died. Or, in symbols,
(D=>B) = T, for D = F, and B = T.
And again, the truth table for material implication is
demonstrated by this situation.
Therefore, we will use the following truth table as the
definition of the "=>" symbol.
p q | p=>q F F T F T T T F F T T T
What this table basically states is that no argument allows
there to be a true premise with a false conclusion.
It should be noted that material implication in and of itself is
blind to the propositions involved. For instance, someone might
say, "Because the grass is green, the sky is blue."
Then someone else might say that these two facts are totally
unrelated. And they might further say that material implication
can not involve two arbitrary propositions whatsoever as can the
AND and OR functions. But the thing to remember here is that even
though we may not agree with their statement, if someone does
asserts that the sky is blue because the grass is green, then he
also means to state that if the sky is not blue, then the grass
is not green. And he also means to imply that the grass can't be
green without the sky also being blue. Since we can state a
material implication between any two arbitrary propositions
whatsoever, material implication in and of itself does not
necessarily reflect reality. But if we derive general principle
using material implication which are valid for all propositions,
then it must apply to reality as well.
And now that we have a definition for material
implication, it can be shown that the AND function and the OR
function can be expressed in term of material implication. Thus,
consider the truth table below:
1 2 3 4 5 6 p q | ~q | p=>~q | ~(p=>~q) | p*q F F T T F F F T F T F F T F T T F F T T F F T T
Columns 1 and 2 list all possible combinations of true and
false that the two propositions p and q can have. Column 3 is
formed by negating column 2. Column 4 is formed by referring to
columns 1 and 3. Column 1 is the premise of the argument
expressed in column 4; column 3 is the conclusion. By definition
of material implication, column 4 is true for every row of the
truth table except for any row that has a true premise (column 1)
with a false conclusion (column 3). The bottom row is the only
row that has a true premise with a false conclusion. So the
bottom row is the only place in column 4 that has an F. Column 5
is the opposite of column 4 since it is the negation of column 4.
Column 6 is simply the definition of conjunction for columns 1
and 2.
Notice that for every row of the truth table, column 5 has the
same truth value as column 6. This means that for every
combination of p and q , the truth value of p*q is the same as the truth value of ~(p=>~q). Or written in
symbols, we have:
p*q = ~(p=>~q) (eq.18)
So, for example, saying, "God is just and God is
kind", is equivalent to saying, "It’s not true
that God being just proves that God is not kind".
And if we switch the variables around, writing q for p and
writing p for q, then the last expression above is written as:
q*p = ~(q=>~p)
But since p*q = q*p , then
p*q = ~(q=>~p) (eq.19)
And comparing both equations for p*q , we have:
(p=>~q) = (q=>~p) (eq.20)
Which can be proven with a truth table.
We can also show how material implication can be expressed in
terms of conjunction. We start with an equation that we have
already derived:
p*q = ~(p=>~q) (eq.18)
Negate both sides to get:
~(p*q) = (p=>~q)
Now, let r = ~ q. This means that ~ r = q. And substitute both of these into the last equation to get:
~(p*~r) = (p=>r)
Or,
(p=>r) = ~(p*~r) (eq.21)
We of course recognize p as the premise and r as the
conclusion in the above argument so that the above equation is
exactly what we have already stated: an argument means that you
can not have a true premise and a false conclusion.
Disjunction can also be described in terms of material
implication as the following truth table shows:
1 2 3 4 5 p q | ~p | (~p+q) | (p=>q) F F T T T F T T T T T F F F F T T F T T
Columns 1 and 2 list every combination of the independent
variable p and q. Column 3 is the negation of column 1. Column 4
is the disjunction of columns 2 and 3. And column 5 is simply the
definition of material implication.
As can be seen from the table, column 4 is the same as column 5
for every possible combination of p and q . This means that the
two columns are logically equivalent, or:
(~p+q) = (p=>q)
So let the temporary variable r = ~ p, then p = ~ r. And we get:
(r+q) = (~r=>q)
But since this equation is true for any two propositions whatsoever, then it is also true for p and q. And so we get:
(p+q) = (~p=>q) (eq.22)
It should be noted, however, that (p=>q) is not equal to (q=>p) as can be seen from the following truth table:
p q | (p=>q) | (q=>p) F F T T F T T F T F F T T T T T
Since the truth table for (p=>q)
is not the same as for (q=>p)
for every combination of p and q, these two expression are not
equal.
As was also done for AND and OR, we will also wish to note how
material implication behaves when it is involved with true
statements, false statements, propositions involved with
themselves, and propositions involved with their own negation.
Below is the truth table for which the premise may vary but the
conclusion is always true:
p T | p=>T See definition of p=>q F T T T T T
Or, in symbols,
(p=>T) = T (eq.23)
Or, everything proves what is true.
Below is a truth table for which the premise is always true but
the conclusion may vary:
T p | T=>p See definition of p=>q T F F T T T
Or, in symbols,
(T=>p) = p (eq.24)
Below is the truth table for which the premise may vary but the
conclusion is always false:
p F | p=>F See definition of p=>q F F T T F F
Or, in symbols,
(p=>F) = ~p (eq.25)
Below is the truth table for which the premise is always false
but the conclusion may vary:
F p | F=>p See definition of p=>q F F T F T T
Or, in symbols,
(F=>p) = T (eq.26)
Below is the truth table for which the premise is the same as the
conclusion:
p p | p=>p See definition of p=>q F F T T T T
Or, in symbols,
(p=>p) = T (eq.27)
Below is the truth table for which the premise is the negation of
the conclusion:
~p p | ~p=>p See definition of p=>q F T T T F F
Or, in symbols,
(~p=>p) = p (eq.28)
And the above can be used to prove the following:
p=>(~p=>p) (eq.29) Start with this. It equals the following:
= p=>p Since (~p=>p)= p Or, (eq.28)
= T Since (p=>p) = T Or, (eq.27)
And since the equation has been reduced to the truth, it is
true for any proposition whatsoever.
The following can also be reduced to the truth:
(~p=>p)=>p (eq.30) Start with this. It equals the following: = p=>p Since (~p=>p)= p Or,(eq.28) = T End of proof, since (eq.27)
Below is the truth table for which the conclusion is the negation of the premise:
p ~p | p=>~p See definition of p=>q F T T T F F Or, in symbols,
(p=>~p) = ~p (eq.31)
And this can be used to prove the following:
~p=>(p=>~p) (eq.32) Start with this. It equals: = ~p=>~p Since (eq.31) = T End of proof Since (eq.27) applied to ~ p.
(p=>~p)=>~p (eq.33) Start with this. It equals: = ~p=>~p Since (eq.31) = T End of proof since (eq.27)
Also, consider the following truth table:
1 2 3 4 5 6 p q | p=>q | ~q | ~p | ~q=>~p F F T T T T F T T F T T T F F T F F T T T F F T
Column 1 and 2 are every combination of p and q . Column 3
states that column 1 implies column 2. Column 4 is the negation
of column 2. Column 5 is the negation of column 1. And column 6
states that column 4 implies column 5.
Since column 6 above is the same as column 3 for every possible
combination of p and q, we have the following truth:
(p=>q) = (~q=>~p) (eq.34)
We can also express the relationship of equivalence in terms of implication.
1 2 3 4 5 6 p q | (p=q) | p=>q | q=>p | (p=>q)*(q=>p) F F T T T T F T F T F F T F F F T F T T T T T T
Column 3 shows that two propositions are not equal unless they both have the same truth value. And since column 6 is the same as column 3, we have the following equality:
(p = q) = [(p=>q)*(q=>p)] (eq.35)
Which states that if one thing proves another and the other
proves the one, then one is equivalent to the other.
And it will be useful to also prove the following statement:
p=>(q=>r) Start with this. It equals: = p=>~(q*~r) Using (eq.21) on q and r above = ~[p*~(~(q*~r))] Using (eq.21) on p and [~( q*~ r )] above = ~[p*(q*~r)] Double negation (eq.3) on ~[~(q*~ r)] above = ~[(p*q)*~r] Associative property (eq.14)
= (p*q)=>r Using (eq.21) in reverse on r and (p*q)
[p=>(q=>r)] = [(p*q)=>r] (eq.36) And since p*q = q*p : apply (eq.4) to last equation gives [ p=>(q=>r)] = [ q=>(p=>r)] (eq.37)
And with these we can prove the following:
[(p=>q)*p ]=>q (eq.38) Start with this.
= (p=>q)=>(p=>q) Using (eq.36) on p and (p=>q)
= T End of proof since (eq.27)
applied to (p=>q) and (p=>q)
Which states that if the argument is just and the premise is
true, then the consequence must also be true.
And we can also prove the following:
[(p=>q)*~q ]=>~p (eq.39) Start with this = (p=>q)=>(~q=>~p) using (eq.36) on ~q and (p=>q) = (p=>q)=>(p=>q) using (eq.34) on the above = T End of proof since (eq.27)
Which states that if the argument is just but the conclusion is false, then the premise must also be false.
And we can also prove the following:
T Start with this = (p=>T) From (eq.23) = [ p=>(s=>s)] Since (eq.27) = [(p*s)=>s ] Using (eq.36) on the above = [(p*p*s)=> s ] Using (eq.7) on the above = [(p*s*p)=>s ] Using (eq.4) on the above = [((p*s)*p)=>s ] Using (eq.14) = [(p*s)=>(p=>s)] (eq.40) Using (eq.36) on (p*s) and p
And since this was proven from the truth itself, it is true
for all values of p and s . It states that if two facts coexist,
then one may be used to prove another.
But we may replace p*s with ~(p=>~s) in the last equation to get:
~(p=>~s)=>(p=>s) (eq.41) Using (eq.18)
Which states that if one proposition does not disprove
another, then that proposition can be used to prove the other. In
other words, if no fact can prove that something is not, then
every fact can only prove that it is.
Consider the following truth table:
1 2 3 4 5 6 7 8 p q r | q*r | p =>(q*r) | p=>q | p=>r | (p=>q)*(p=>r) F F F F T T T T F F T F T T T T F T F F T T T T F T T T T T T T T F F F F F F F T F T F F F T F T T F F F T F F T T T T T T T T
Columns 1, 2, and 3 show every combination of truth values that three independent variables can have. Notice that 8 rows are required to show every combination of three variables. In general, it requires 2n rows to show every combination of n independent variables. And since column 8 is the same as column 5:
[ p=>(q*r)] = [(p=>q)*(p=>r)] (eq.42)
This is called the distributive law of implication for
conjunction. It shows how the relation of material implication is
distributed throughout a conjunction.
For completeness I include the next two distributive laws as
well. They can be proven with the use of truth table like those
above.
p*(q+r) = (p*q)+(p*r) (eq.43 and p+(q*r) = (p+q)*(p+r) (eq.44)
Now we are in a position to collect what we have learned and
start relating it to reality.
Click here for a reference guide of
results we have obtained.