We can call formal logic the entirety of maths. We start based on some assumed information, and we try to produce new information from it. This process of transforming information is called reasoning and the steps invloved while doing so is called inference. Logic is the study of this reasoning.

Formal languages are collection of strings, string itself being a sequence of symbols. Automatas are state machines with rules on how those state changes while processing an input, and these state machines can be used to decide if a string belongs to a particular language. Formal logic uses this idea of formal languages and automata theory to study reasoning.

The Language of Sentential Logic

We will first look at a system of formal logic called sentential logic. Since we are doing it via formal languages, we need to decide what symbols we will use, how to build a well formed formula using these symbols, and how to interpret these formulas.

Symbols

We need three kinds of symbols here:

  1. Sentential connective symbols $\set{\bot,\rightarrow}$
  2. Parenthesis to group a section of symbols
  3. Sentence symbols $\set{A_1,\ldots,A_n}$

Sentential connective symbols and parenthesis together are called logical symbols. Sentence symbol assumes its value from a set called boolean $\set{F,T}$. There are other sentential connective symbols like not $(\neg)$, and $(\land)$, or $(\lor)$ etc., but using just $\bot$ and $\rightarrow$ suffices and they are easy to write definition on.

Grammar

We can define a well formed formula in sentential logic recursively as

  1. Every sentence symbol and $\bot$ is a $\mathrm{wff}$
  2. If $\alpha$ and $\beta$ are $\mathrm{wff}$, then so is $(\alpha\rightarrow\beta)$

Interpretation in FOL

The truth assignment or model $v$ for a set $S$ of sentence symbols is a function $v:S\rightarrow\set{F,T}$. Using $v$, we can define $\overline{v}:W\mapsto\set{F,T}$ where $W$ is the set of $\mathrm{wff}$ in sentential logic. $$ \overline{v}(\phi)= \begin{cases} v(\phi)&\text{if}\ w\in S\\ T&\text{if}\ w=(\alpha\rightarrow\beta)\text{ and }(\overline{v}(\alpha),\overline{v}(\beta))\ne(T,F)\\ F&\text{otherwise} \end{cases} $$

A model $v$ satisfies $\phi$ $\mathrm{iff}$ $\overline{v}(\phi)=T$

A set of $\textrm{wff},\Sigma$ tautologically implies a $\mathrm{wff},\tau$ (written as $\Sigma\models\tau$) $\mathrm{iff}$ every model that satisfies every member of $\Sigma$ also satisfies $\tau$ $\varnothing\models\tau$ $\mathrm{iff}$ every truth assignment satisfies $\tau$. $\tau$ in this case is called a tautology (written as $\models\tau$).

Boolean Functions and Sentential Connective

The arity of a connective is the number of argument it takes.

  • 0-ary connectives: $\bot=\set{(,F)}$ and $\top=\set{(,T)}$
  • 1-ary connectives: $\neg=\set{(F,T), (T, F)}$
  • 2-ary connectives: $\rightarrow,\land,\lor$

A boolean function is of the form $B:\set{F,T}^n\mapsto\set{F,T}$. $B_\alpha$ denotes the boolean function realized by $\mathrm{wff}$ $\alpha$. If $F<T$, then $\alpha\rightarrow\beta\longleftrightarrow\alpha\le\beta$.

Every boolean function can always be realized with some $\mathrm{wff}$ in disjunctive normal form from its truth table.

A set of sentential connective, $X$ is complete if every boolean function can be realized by $\mathrm{wff}\ \alpha$ constructed using the sentential connective in $X$.

The sets $\set{\neg,\land},\set{\neg,\lor},\set{\neg,\rightarrow},\set{\mathrm{nand}},\set{\mathrm{nor}}$ are complete.

The $\set{\bot,\rightarrow}$ is called supercomplete because it can also realize boolean function of 0-arity$ .

Compactness and Effectiveness

Compactness Theorem

Let $\Sigma$ be a set of $\textrm{wff}$s. If for every subset of $\Sigma$, there is a model that satisfies each of its member, then there is a model that satisfies every member of $\Sigma$.

An effective procedure must

  • Be a program of finite instructions
  • Run on an automata
  • Halt for a decision problem

A language $\Sigma$ is decidable if an effective procedure can decide if $\alpha\in\Sigma$. The language of sentential logic is decidable. A language $\Sigma$ is effectively enumerable if an effective procedure can list all its member in some order.

  • A language $\Sigma$ is semidecidable if an effective procedure returns $T$ only if $\alpha\in\Sigma$.
  • A language is effectively enumerable $\mathrm{iff}$ it is semidecidable.