Introduction and Elimination of Conjunctions and Disjunctions

One of the techniques of classical logic is the introduction and elimination of connectors and disjuncts. Although these techniques are executed in a more or less intuitive way, their justification is not entirely trivial but can be obtained from the rules of propositional logic that we have already demonstrated in previous classes. Formally, the techniques of introducing and eliminating connectors and disjuncts are as follows:

And their demonstrations from propositional logic are shown below:

∨-Introduction

∨-Elimination

∧-Introduction

∧-Elimination

Techniques of Contradictions and Tautologies

Rule of the Excluded Middle or Tautology (tau)

Another notable characteristic of classical logic is the property of the excluded middle (tertium non datur). It states that if there are two statements where one negates the other, then necessarily one of the two must be true; in other words, the conjunction of two statements in which one negates the other necessarily forms a tautology. Formally, this is expressed as:

\vdash (\neg\alpha \vee\alpha)

And its demonstration is easy to obtain.

Another way to state the principle of the excluded middle is through the law of non-contradiction, which establishes that a statement cannot be true and false at the same time, and is formally stated as:

\vdash \neg(\neg\alpha \wedge \alpha)

This property does not need a demonstration, not because it is self-evident by itself, but because it is directly obtained by applying the definition of conjunction on the principle of the excluded middle.

Rule of Contradiction or Principle of Explosion

Another known property of classical logic is the principle of explosion, which is usually stated through the phrase “from contradictory premises, anything follows.” Its formulation is often presented in either of the following two ways:

\{(\neg\alpha \wedge \alpha)\}\vdash \beta

\{\alpha, \neg\alpha\}\vdash \beta

The demonstration of this rule is simple:

∨-Elimination3

Modus ponens can be written in two different ways. One form that we already know is \{\alpha,(\alpha \rightarrow \beta)\}\vdash \beta. The other is a little less familiar:

\{\alpha\}\vdash\beta \; \wedge \; \vdash \alpha \; \Longrightarrow \; \vdash \beta

Focusing on this second form, it is possible to visualize an expansion for this rule that we call ∨-Elimination3, because it resembles a simplification obtained from a disjunction. It tells us that if \gamma can be inferred from \alpha and from \beta (both at once) and at the same time the disjunction between \alpha and \beta is a theorem, then \gamma is a theorem. This is formally summarized as follows:

\{\alpha\}\vdash\gamma\; \wedge \; \{\beta\}\vdash\gamma \; \wedge \; \vdash (\alpha \vee \beta) \Longrightarrow \vdash \gamma

The demonstration of this technique of classical logic is as follows:

Proof by Cases (cas)

Another technique of classical logic is proof by cases. If an expression \beta can be inferred from another expression \alpha as well as from its negation, then the expression \beta is necessarily a theorem. This is formally represented as: \alpha \vdash \beta \; \wedge \; \neg\alpha \vdash \beta \Longrightarrow \vdash \beta. Its demonstration is as follows:

\begin{array}{rll} (1) & \alpha \vdash \beta &; Premise\\ (2) & \neg \alpha \vdash \beta &; Premise \\ (3) & \vdash \alpha \vee \neg\alpha &; TAU \\ (4) & \vdash \beta &; \vee-Elimination3(1,2,3) \end{array}

Reduction to Absurdity (absurdo)

One of the most used techniques of classical logic in demonstrations, especially in mathematics, is the reduction to absurdity. This consists of that if a contradiction (a statement and its negation) is inferred from an expression \alpha, then the negation of \alpha is a tautology. Formally it is expressed as: \{\alpha\}\vdash \beta \; \wedge \; \{\alpha\}\vdash \neg\beta \Longrightarrow \vdash \neg\alpha. And it can be demonstrated through the following reasoning: