In
propositional logic
Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations b ...
, material implication
is a
valid rule of replacement
In logic, a rule of replacementMoore and Parker is a transformation rule that may be applied to only a particular segment of an expression. A logical system may be constructed so that it uses either axioms, rules of inference, or both as transf ...
that allows for a
conditional statement to be replaced by a
disjunction
In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...
in which the
antecedent is
negated
In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and fals ...
. The rule states that ''P implies Q'' is
logically equivalent
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
to ''not-
or
'' and that either form can replace the other in
logical proofs. In other words, if
is true, then
must also be true, while if
is true, then
cannot be true either; additionally, when
is not true,
may be either true or false.
Where "
" is a
metalogic
Metalogic is the study of the metatheory of logic. Whereas ''logic'' studies how logical systems can be used to construct valid and sound arguments, metalogic studies the properties of logical systems.Harry GenslerIntroduction to Logic Routledge, ...
al
symbol
A symbol is a mark, sign, or word that indicates, signifies, or is understood as representing an idea, object, or relationship. Symbols allow people to go beyond what is known or seen by creating linkages between otherwise very different con ...
representing "can be replaced in a proof with," and P and Q are any given logical
statements
Statement or statements may refer to: Common uses
*Statement (computer science), the smallest standalone element of an imperative programming language
*Statement (logic), declarative sentence that is either true or false
*Statement, a declarative ...
. To illustrate this, consider the following statements:
*
: Sam ate an
orange
Orange most often refers to:
*Orange (fruit), the fruit of the tree species '' Citrus'' × ''sinensis''
** Orange blossom, its fragrant flower
*Orange (colour), from the color of an orange, occurs between red and yellow in the visible spectrum
* ...
for lunch
*
: Sam ate a
fruit
In botany, a fruit is the seed-bearing structure in flowering plants that is formed from the ovary after flowering.
Fruits are the means by which flowering plants (also known as angiosperms) disseminate their seeds. Edible fruits in particul ...
for lunch
Then, to say, "Sam ate an orange for lunch" "Sam ate a fruit for lunch" (
). Logically, if Sam did not eat a fruit for lunch, then Sam also cannot have eaten an orange for lunch (by
contraposition
In logic and mathematics, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive, and an associated proof method known as proof by contraposition. The contrapositive of a stateme ...
). However, merely saying that Sam did not eat an orange for lunch provides no information on whether or not Sam ate a fruit (of any kind) for lunch.
Partial proof
Suppose we are given that
. Then, we have
by the
law of excluded middle
In logic, the law of excluded middle (or the principle of excluded middle) states that for every proposition, either this proposition or its negation is true. It is one of the so-called three laws of thought, along with the law of noncontrad ...
(i.e. either
must be true, or
must not be true).
Subsequently, since
,
can be replaced by
in the statement, and thus it follows that
(i.e. either
must be true, or
must not be true).
Suppose, conversely, we are given
. Then if
is true that rules out the first disjunct, so we have
. In short,
.
Math StackExchange: Equivalence of a→b and ¬ a ∨ b
/ref> However if is false, then this entailment fails, because the first disjunct is true which puts no constraint on the second disjunct . Hence, nothing can be said about . In sum, the equivalence in the case of false is only conventional, and hence the formal proof of equivalence is only partial.
This can also be expressed with a truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...
:
Example
An example: we are given the conditional fact that if it is a bear, then it can swim. Then, all 4 possibilities in the truth table are compared to that fact.
# If it is a bear, then it can swim — T
# If it is a bear, then it can not swim — F
# If it is not a bear, then it can swim — T because it doesn’t contradict our initial fact.
# If it is not a bear, then it can not swim — T (as above)
Thus, the conditional fact can be converted to , which is "it is not a bear" or "it can swim",
where is the statement "it is a bear" and is the statement "it can swim".
References
{{Classical logic
Rules of inference
Theorems in propositional logic