0.3 Discrete structures logic  (Page 5/23)

Then first "I will go to the beach if it is not snowing" is restated as "If it is not snowing, I will go to the beach". Then symbols P and Q are substituted for the respective sentences to obtain ~P → Q.

Similarly, "It is not snowing and I have time only if I will go to the beach" is restated as "If it is not snowing and I have time, then I will go to the beach", and it is translated as (~P ⋀ R ) → Q.

Reasoning with propositions

Introduction to reasoning

Logical reasoning is the process of drawing conclusions from premises using rules of inference. Here we are going to study reasoning with propositions. Later we are going to see reasoning with predicate logic, which allows us to reason about individual objects. However, inference rules of propositional logic are also applicable to predicate logic and reasoning with propositions is fundamental to reasoning with predicate logic.

These inference rules are results of observations of human reasoning over centuries. Though there is nothing absolute about them, they have contributed significantly in the scientific and engineering progress the mankind have made. Today they are universally accepted as the rules of logical reasoning and they should be followed in our reasoning.

Since inference rules are based on identities and implications, we are going to study them first. We start with three types of proposition which are used to define the meaning of "identity" and "implication".

Some propositions are always true regardless of the truth value of its component propositions. For example (P ⋁¬P) is always true regardless of the value of the proposition P.

A proposition that is always true called a tautology.

There are also propositions that are always false such as (P ⋀¬P). Such a proposition is called a contradiction.

A proposition that is neither a tautology nor a contradiction is called a contingency. For example (P ⋁Q) is a contingency.

These types of propositions play a crucial role in reasoning. In particular every inference rule is a tautology as we see in identities and implications.

Identities

From the definitions (meaning) of connectives, a number of relations between propositions which are useful in reasoning can be derived. Below some of the often encountered pairs of logically equivalent propositions, also called identities, are listed.

These identities are used in logical reasoning. In fact we use them in our daily life, often more than one at a time, without realizing it.

If two propositions are logically equivalent, one can be substituted for the other in any proposition in which they occur without changing the logical value of the proposition.

Below ⇔ corresponds to ↔ and it means that the equivalence is always true (a tautology), while ↔ means the equivalence may be false in some cases, that is in general a contingency.

That these equivalences hold can be verified by constructing truth tables for them.

First the identities are listed, then examples are given to illustrate them.

List of Identities:

1. P ⇔(P ⋁P) ----- idempotence of ⋁