Propositional Logic

Overview

Propositional logic refers to the logical system in which proposition symbols are formed from the following five sentential connective symbols:

1. Negation ($\mathrm{\neg }$)
2. Conjunction ($\wedge$)
3. Disjunction ($\vee$)
4. Conditional ($⟹$)
5. Biconditional ($⟺$)

A sentence refers to any particular utterance, i.e. a string of symbols/words. A declarative sentence that can be true or false is called a statement or assertion. A proposition is the abstract content of a statement that bears the truth-value.

For example, "It is snowing outside" is a sentence. The same expression specified in a different language, e.g. Korean, is also a sentence. If we have an associated time and location the sentence is grounded in, both the English and Korean sentences could be considered statements. Regardless of the language used to state the assertion, both refer to the same proposition.

Well-Formed Formulas

The WFFs of propositional logic are those built up from the proposition symbols by applying some finite number of times the following formula-building operations:

1. ${\mathcal{E}}_{\mathrm{\neg }}(\alpha )=(\mathrm{\neg }\alpha )$
2. ${\mathcal{E}}_{\wedge }(\alpha ,\beta )=(\alpha \wedge \beta )$
3. ${\mathcal{E}}_{\vee }(\alpha ,\beta )=(\alpha \vee \beta )$
4. ${\mathcal{E}}_{\Rightarrow }(\alpha ,\beta )=(\alpha ⟹\beta )$
5. ${\mathcal{E}}_{\iff }(\alpha ,\beta )=(\alpha ⟺\beta )$

A construction sequence is a finite sequence $⟨{ϵ}_1,\dots ,{ϵ}_n⟩$ of expressions such that for each $i\le n$ we have at least one of:

• ${ϵ}_i$ is a proposition symbol;
• ${ϵ}_i={\mathcal{E}}_{\mathrm{\neg }}({ϵ}_j)$ for some $j<i$;
• ${ϵ}_i={\mathcal{E}}_{◻}({ϵ}_j,{ϵ}_k)$ for some $j,k<i$;

where $◻$ is one of the sentential connectives $\wedge$, $\vee$, $\Rightarrow$, or $\iff$.