Swipe to navigate through the chapters of this book
Propositional logic is the basis for any study of logic. The sentences of propositional logic are built from a set of unstructured atomic propositions that are combined using a number of logical connectives. Logical connectives are Boolean operators whose names come from natural language, such as “not”, “and”, “or” and “implies”, and they are given a formal meaning that mimics its usage in natural language.
This chapter is devoted to the study of classical propositional logic. The chapter starts with a presentation of both the syntax and the semantics of propositional logic. In other words, we describe both the set of sentences of the language of propositional logic, and characterise the meaning of those sentences (i.e. which sentences are valid or not). The notion of proof derivation is then introduced as a syntactic characterisation of logical inference, and the interplay between provability and validity is established. The chapter concludes with a discussion of the decision problem of checking whether a propositional formula is valid or not.
Please log in to get access to this content
Aczel, P.: Schematic consequence. In: Gabbay, D.M. (ed.) What Is a Logical System? Studies in Logic and Computation, pp. 261–272. Springer, Berlin (1994)
Hoos, H.H., Stutzle, T.: Satlib: an online resource for research on sat. In: Walsh, T., Gent, I.P., v. Maaren, H. (eds.) SAT 2000, pp. 283–292. IOS Press, Amsterdam (2000)
Prasad, M.R., Biere, A., Gupta, A.: A survey of recent advances in sat-based formal verification. Int. J. Softw. Tools Technol. Transf. (STTT) 7(2), 156–173 (2005) CrossRef
- Propositional Logic
Dr. José Bacelar Almeida
Dr. Maria João Frade
Dr. Jorge Sousa Pinto
Dr. Simão Melo de Sousa
- Springer London
- Sequence number
- Chapter number
- Chapter 3