Rule of Conjunction/Proof Rule
Jump to navigation
Jump to search
Proof Rule
The Rule of Conjunction 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 $\psi$, we may infer the compound statement $\phi \land \psi$.
It can be written:
- $\ds {\phi \qquad \psi \over \phi \land \psi} \land_i$
Tableau Form
Let $\phi$ and $\psi$ be two propositional formulas in a tableau proof.
The Rule of Conjunction is invoked for $\phi$ and $\psi$ in the following manner:
Pool: | The pooled assumptions of each of $\phi$ and $\psi$ | |||||||
Formula: | $\phi \land \psi$ | |||||||
Description: | Rule of Conjunction | |||||||
Depends on: | Both of the lines containing $\phi$ and $\psi$ | |||||||
Abbreviation: | $\operatorname {Conj}$ or $\land \mathcal I$ |
Explanation
The Rule of Conjunction can be expressed in natural language as:
- If we can show that two statements are true, then we may build a compound statement expressing this fact, and be certain that this is also true.
Also known as
The Rule of Conjunction can also be referred to as:
- the rule of and-introduction
- the rule of adjunction.
Also see
- This is a rule of inference of the following proof system:
Technical Note
When invoking the Rule of Conjunction in a tableau proof, use the {{Conjunction}}
template:
{{Conjunction|line|pool|statement|first|second}}
or:
{{Conjunction|line|pool|statement|first|second|comment}}
where:
line
is the number of the line on the tableau proof where the Rule of Conjunction is to be invokedpool
is the pool of assumptions (comma-separated list)statement
is the statement of logic that is to be displayed in the Formula column, without the$ ... $
delimitersfirst
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
- 1959: A.H. Basson and D.J. O'Connor: Introduction to Symbolic Logic (3rd ed.) ... (previous) ... (next): $\S 4.2$: The Construction of an Axiom System: $RST \, 4$
- 1964: Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning ... (previous) ... (next): $\text{II}$: 'AND', 'OR', 'IF AND ONLY IF': $\S 3$
- 1965: E.J. Lemmon: Beginning Logic ... (previous) ... (next): $\S 1.3$: Conjunction and Disjunction
- 1980: D.J. O'Connor and Betty Powell: Elementary Logic ... (previous) ... (next): $\S \text{II}$: The Logic of Statements $(2): \ 1$: Decision procedures and proofs: $9$
- 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