Propositional Calculus – the basics

Let’s see if we can build this from ground up. We first define a statement (or sometimes, a proposition) to be a meaningful assertion that is either true or false. Well, meaningful means we should be able to say for sure if a statement is true or false. So, something like “Hello, there!” is not counted as a statement but “the sun is made of butter” is. The latter is evidently false but the former is neither true nor false. Now, it can get quite cumbersome after a while if we keep using statements such as “the sun is made of butter” every time we need to use them. Thus, it is useful to have variables, or to be precise, propositional variables, to denote all statements. We usually prefer to use and so on for such variables.

Now, all of this would be rather boring if we had just symbols such as etc. to denote statements. Thus, a statement like “Archimedes was a philosopher” is not that interesting in itself. In fact, all the statements (in our formal system) would be “isolated” ones in the sense that we wouldn’t be able to logically “connect” one statement to another. We want to be able to express sentences like “ and “, “ implies ” and so on. So, we add something called logical connectives (also called operator symbols) to the picture. There are four basic ones: (conjunction), (disjunction), (material implication), which are all of arity 2 and (negation) which is of arity 1. Using these logical connectives, we can now form compound statements such as (i.e. and ), (i.e. or ), (i.e. ), and (i.e. implies .) Note that each of and requires two propositional variables in order for it to make any sense; this is expressed by saying their arity is 2. On the other hand, has arity 1 since it is applied to exactly one propositional variable.

We also introduce another logical operator called logical equivalence (,) which has arity 2. It is really convenient to have logical equivalence on hand, as we shall see later. We say if and only if ““. What this basically means is, if is true then so is and if is true then so is . Another equivalent way of saying this is, if is true then so is and if is false then so is .

Before we proceed further, we make a few observations. First, if and are propositional variables, then by definition each of those is either true or false. Formally speaking, the truth value of or is either true or false. This is equally true of the compound statements and . Of course, the truth values of these four compound statements depend on and . We will delve into this in the next post.

Second, we don’t really need all the four basic operators. Two of those, viz. and suffice for all logical purposes. This means all statements involving and/or can be “converted” to ones that involve only and . However, we can also choose the “minimal” set , instead, for the purpose for which we chose the minimal set . In fact, there are lots of other possible combinations of operators that can serve our purpose equally well. Which minimal set of operators we choose depends sometimes on personal taste and at other times on practical considerations. So, for example, while designing circuits in the field of computer hardware, the minimal operator set that is used is . In fact, all that’s really needed is this particular operator set. Here .

So, what have we got so far? Well, we have a formal notion of a statement (or proposition.) We have access to propositional variables (, etc.) that may be used to denote statements. We know how to create the negation of a given statement using the logical connective. We also know how to “connect” any two statements using conjunction, disjunction and material implication that are symbolically represented by the logical connectives and , respectively. And, lastly, given any two statements and , we have defined what it means for the two to be logically equivalent (which is symbolically represented by ) to each other. Indeed, if and only if ().

We shall see in the later posts that the above “small” formal system (for propositional calculus) we have built thus far is, in fact, quite powerful. We can, indeed, already employ quite a bit of it in “ordinary” mathematics. But, more on this, later!

Propositional Calculus

I wish to use this part of the blog to quickly go through the basic elements of propositional calculus, and then later move on to predicate calculus in another part of the blog, followed by the fundamentals of relational algebra in yet another part. I might then go through the problem of query optimization in RDBMS after that. Let’s see how far this goes.