Propositional Logic

This chapter provides an introduction to propositional logic. Its main emphasis is on describing how formal logical reasoning in terms of statements, arguments and deductions can be obtained from natural language; on discussing the advantages of this formalisation by looking at ambiguities of natural languages; and on clarifying the important role of logic in computer science and computational modelling through a number of examples. The first section introduces, in a light-weight way, the syntax or language of propositional logic and its semantics, which explains the truth of logical statements. The connectives of propositional logic (negation, disjunction, conjunction, implication and equivalence) are presented together with conditions for the truth and falsity of statements that contain them. Their use in natural language is illustrated by examples. In a more formal approach, the syntax of propositional logic is then introduced, including formation rules and well-formedness checks for formulae, precedences for connectives and syntax trees. The semantics of propositional logic is formally defined via truth tables. Semantic concepts such as satisfiability, logical equivalence and validity of statements, tautologies and contradictions are defined as well. Finally, algebraic laws of logical equivalences, similar to those of Boolean algebra, are presented.