Proofs

We can use logical equivalences and logical implications to derive new true propositions from the given true propositions.

A proof is a list of formulas. The proof starts with some premises, and every other formula on the list must follow the rules of proofs:

• Logically equivalent to the formula above it.
• Logically implied by the formula above it.
• The $AND$ of some formulas above it.
• Logically implied by the $AND$ of some formulas above it.

Example

Premises:

1. Socrates is mortal or Socrates is not human ($M \lor \lnot H$).
2. Socrates is human ($H$).

We can conclude:

3. Socrates is not human or Socrates is mortal (using $M \lor \lnot H \equiv \lnot H \lor M$). - This is logically equivalent to line 1.
4. Socrates is not not human ($H \equiv \lnot \lnot H$). - This is logically equivalent to line 2.
5. Socrates is mortal (logical implication).

Step 5 is logically implied by the $AND$ of some formulas above it.

Therefore the $AND$ of 3 and 4 is $(\lnot H \lor M) \land \lnot \lnot H \models M$. This formula can be found in logical implication - MORE EXAMPLES.

Proofs and Logical Implications

A proof produces a new logical implication $P \models Q$ where

• $P$ is the $AND$ of all the premises.
• $Q$ is the last line of the proof.

tip

A proof says that, assuming all the premises are true, the conclusion is also true.

Proof Examples

References

• Week5 Materials