Introduction

Preliminaries

Logic is an approximation of natural language, which tries to capture the relation among symbols. Reasoning through logic consists of manipulating symbols without knowing their meaning. There are different form of reasoning:

• Deductive reasoning. Deriving conclusions based on the inference rules of logic.
• Inductive reasoning. Deriving conclusions from observations.
  • I have seen 1000 black cars
  • I have never seen one white car
  • Therefore, all cars are black
• Abductive reasoning. Deriving causes from effects. We tend to conclude a cause even when we haven't enumerated all possible causes.
• Reasoning by analogy. Deriving conclusions based on the similarity between objects.

Nevertheless, deduction is the only form of reasoning which is guaranteed to derive conclusions valid in all cases.

Definitions

Logical entailment. A set of premises $\Sigma$ logical entails a conclusion $\phi$ iff every truth assignment satisfying $\Sigma$ satisfies also $\phi$. To this purpose, we use the notation $\Sigma\models\phi$.

Contradiction. We use the notation $\perp$.

Proof. A conclusion $\phi$ is derived from a set of premises $\Sigma$ by a formal system $S$ iff there exists a sequence of steps following the inference rules defined by the logic using $S$, which transforms $\Sigma$ into $\phi$. We use the notation $\Sigma\vdash_S\phi$ or alternatively $\Sigma\vdash\phi$ (when it is clear which formal system we are using).

Soundness. If a formal system $S$ can prove $\phi$ from $\Sigma$ and $\Sigma\models\phi$, then $S$ is sound with respect to logical entailment, namely $$\Sigma\vdash\phi\implies\Sigma\models\phi$$ Informally, a sound system ensures that if you find a set of steps deriving the conclusion from the premises, then you have the guarantee that the premises logically entail the conclusion.

Completeness. If for every logical entailment there exists a proof from the formal system $S$, then $S$ is complete with respect to logical entailment, namely $$\Sigma\models\phi\implies\Sigma\vdash\phi$$ It is important to mention that completeness only ensures the existence of a proof. It doesn't say anything about how to find it.

Decidability. A logical system is decidable iff there is a method which tells (in finite number of steps) whether or not arbitrary statements are theorems of the logical system.