Principle of Non-Contradiction/Proof Rule
Theorem
The Principle of Non-Contradiction is a valid deduction sequent in propositional logic.
As a proof rule it is expressed in the form:
- If we can conclude both $\phi$ and $\neg \phi$, we may infer a contradiction.
It can be written:
- $\displaystyle {\phi \quad \neg \phi \over \bot} \neg_e$
Tableau Form
Let $\phi$ be a propositional formula in a tableau proof.
The Principle of Non-Contradiction is invoked for $\phi$ and $\neg \phi$ in the following manner:
Pool: | The pooled assumptions of $\phi$ | |||||||
The pooled assumptions of $\neg \phi$ | ||||||||
Formula: | $\bot$ | |||||||
Description: | Principle of Non-Contradiction | |||||||
Depends on: | The line containing the instance of $\phi$ | |||||||
The line containing the instance of $\neg \phi$ | ||||||||
Abbreviation: | $\operatorname {PNC}$ or $\neg \mathcal E$ |
Explanation
The Principle of Non-Contradiction can be expressed in natural language as follows:
This means: if we have managed to deduce that a statement is both true and false, then the sequence of deductions show that the pool of assumptions upon which the sequent rests contains assumptions which are mutually contradictory.
Thus it provides a means of eliminating a logical not from a sequent.
Also known as
The Principle of Non-Contradiction is otherwise known as:
- Principium contradictionis, Latin for principle of contradiction
- Rule of not-elimination
- Law of contradiction
- Law of non-contradiction
Technical Note
When invoking the Principle of Non-Contradiction in a tableau proof, use the NonContradiction template:
{{NonContradiction|line|pool|first|second}}
or:
{{NonContradiction|line|pool|first|second|comment}}
where:
line
is the number of the line on the tableau proof where the Principle of Non-Contradiction is to be invokedpool
is the pool of assumptions (comma-separated list)first
is the first of the two lines of the tableau proof upon which this line directly dependssecond
is the second of the two lines of the tableau proof upon which this line directly dependscomment
is the (optional) comment that is to be displayed in the Notes column.
Sources
- 2000: Michael R.A. Huth and Mark D. Ryan: Logic in Computer Science: Modelling and reasoning about systems ... (previous) ... (next): $\S 1.2.1$: Rules for natural deduction