Natural Deduction

Natural deduction is a proof theory for showing the validity of an argument in propositional logic.

Natural deduction is a collection of rules, called inference rules, each of which allows us to infer new formulas from given formulas.

Natural deduction is a form of forward proof. Starting from the premises, we use the inference rules to deduce new formulas that logically follow from the premises. Using the formulas we have proven and the premises, we use the rules to deduce more formulas. We continue this process until we have deduced the conclusion. So we use Logical Implication.

Natural Deduction Rules

The names:

• and_i = and-inclusion
• and_e = and-elimination
• etc.

Some Strategies:

Any natural deduction proof can be Transformational Proof. But be careful, this is in transformational proof

NOT THE SAME AS Because the above is stronger. We need to use the first interpretation.

If you are still confused, see Logical Implication

Examples

b |- a => b um this is wrong

Some more proofs

Prove this: |- (p | !p)

Proving De Morgan’s Laws (DML) through De Morgan’s Laws (DML) through Natural Deduction: