Formal languages

Logic starts with language, and languages come in many flavors. Some languages are natural, while other languages are artificial. Natural languages like English, Hungarian, and Basque, tend to be extremely complex, and as a consequence, their structure extremely hard to capture. Unfortunately, the same goes for their logic. In fact, it is unclear whether there is such a thing as the logic of English (or Hungarian, or Basque), or if there are several distinct logics for each, or none at all. It is safe to say that even if there is such a thing, so far, nobody has managed to capture it in its entirety.

Modern logic flourished by altogether circumventing this problem. Akin to natural science, instead of trying to deal with the extreme complexity of reality all at once, logicians turned to mathematical abstraction. In particular, instead of trying to capture the logic of a particular natural language, they started developing mathematically precise artificial languages with simple and transparent structure capturing some aspects of how natural languages function. In turn, this allowed them to precisely formulate some logical notions (like validity) in those artificial languages, and to study their properties.

In this chapter, we will take the first step following in their footsteps, and introduce a number of different formal languages, from the simplest to more and more complex ones, ending with the language of zeroth-order logic. Though it is the language of zeroth-order logic that subsequent chapters of this book will be based on, working with simpler languages first will hopefully demistify the process of specifying formal languages, and formal systems in general. In fact, you can think of this process as specifying a game with a set of symbols and a precise set of instructions for playing with those symbols, and then playing the game. We will call these ‘writing games.’