Propositional Operators

In the previous chapter, we saw the distinction between atomic and compound propositions. As we considered two connectives in the given compound sentences — 'and' and 'or' — we stated that they'll be explained in detail in the next chapter.

Likewise, now it's time to unveil the idea of logical connectives and how they enable composing compound propositions from simpler ones.

Let's start by formally defining what a logical connective/operator really is:

Some other terms commonly used to refer to logical operators are: logical connectives, sentential operators, sentential connectives, propositional operators, propositional connectives.

In propositional logic, there are a handful of logical operators used to create new propositions from the ones already given. Let's check them all out one-by-one.

We all are pretty familiar with the idea of negating statements. For instance, if you were to negate the sentence below:

..what would you write as the negation?

Well, we'd just write this:

To negate the original statement, we just put the word 'not' in there.

Now let's suppose that we say that C++ is actually very challenging i.e C++ is actually not easy, what could we then say about the first statement — 'C++ is easy'?

Would it be true or false?

Clearly, it would be false. However, its negation, which is the second sentence 'C++ is not easy', would be true.

Uptil this point, note that we've not shown anything formal. This is just how we interpret negations in natural language.

Recall the fact that mathematical logic has completely been built upon ideas from natural language. So one would expect natural intuition behind every operator used, and indeed there is.

Anyways, let's consider another statement.

From general knowledge, we know that this sentence is clearly false. But let's reason about its negation:

Now what?

Well, the negation is true. The original proposition was false, so if we negate it, we'd surely arrive at a true statement.

In mathematical logic, negations are represented using the symbol ::\pmb{\neg}::.

To show formally how an operator forms new propositions i.e what is the status of the new compound statement that it forms based on the truth values of the constituent propositions, we could use something called a truth table.

This cleanly shows the behavior of the given operator.

In formal terms. we call this the semantics of the operator.

Anyways, coming back to truth tables, let's create a truth table for the negation operation. First, let's construct the simplest proposition using the negation operator which is the following: ::\neg p::.

Since this proposition has just one atomic proposition (represented by a variable), we need to consider all the possible truth values that single proposition could have. They are true or false.

First the atomic proposition goes in the first column of the table. After this, we explore the compound proposition in the second column.

Altogether, this is the truth table we arrive at:

When ::p:: is ::\bold T::, ::\neg p:: is ::\bold F::. Similarly, when ::p:: is ::\bold F::, ::\neg p:: is ::\bold T::. Simple, as it can be!

Akin to 'not', the word 'or' is also very common in natural language. Imagine if we said:

What could you say about the truth value of this sentence?

If you look it up, Java was created in 1995, so this means that the first atomic statement over here i.e 'Java was created in the 1990s' is true, however the second one is false.

But nonetheless, we would say that the statement altogether is true. Simply because one of the simpler statements is true.

Let's take another example:

Once again, if you look it up, you'll see that Java is indeed an OOP language i.e the second atomic proposition is true. And we already know that the first one is true as well — Java was certainly created in the 1990s (1995 specifically).

What would you say about the truth value of this sentence?

Well, pretty logically, since both the simpler statements are true, who would deny the whole statement anyway. It would surely be true.

One more example to go:

This time, very clearly, we can right away say that the whole statement is false. Why?

Because neither of the simpler statements 'Java was created in the 1960s' and 'Java was created in the 1970s' is true. Both are false, and hence the compound sentence is false.

To sum up, the word 'or' creates a compound proposition that is true when at least one of the constituent propositions is true. When both are false, the compound proposition is false.

In logic, 'or' is commonly known as a disjunction. It also has a symbolic representation, just like negation. It is denoted via the symbol ::\vee::.

Let's consider the semantics of ::\vee:: via a truth table.

Since, disjunction is a binary operation, it takes two propositions, we'd need to have two columns to represent each of the two constituent propositions.

If at least one proposition is ::\bold T::, the disjunction is ::\bold T::, otherwise ::\bold F::.

The word 'or' in English generally does not always imply an 'inclusive or'.

That is, it does not always include the case of both the constituent propositions being true and then making the disjunction true as well. In some cases, the word 'or' implies what is known as an 'exclusive or'.

Let's consider a classic example from the board game Monopoly:

First of all, from the definition of a proposition, we know that this sentence over here is not a proposition — it's an imperative.

But we're not interested in this right now. We're rather interested in the way the word 'or' is being used. So what does this sentence mean? Does it say that you need to both pay $10 fine and take a chance, or only do one of them?

Clearly we have to do either one, but not both.

The 'or' used here is an 'exclusive or', in that it excludes the case where you could do both: pay the fine and draw a chance card as well.

Logicians conceived of bringing this mere distinction, between the meaning of 'or' based on the context of the sentence, into logic and guess what — it's called an exclusive disjunction and has its own symbol.

It means that either ::p:: is true or ::q:: is true, but not both. So when both are true, then by definition, the exclusive disjunction becomes false.

Below shown are the semantics of ::\oplus:::

It's similar to an inclusive or, except for that when both the propositions ::p:: and ::q:: are ::\bold T::, then their exclusive disjunction is ::\bold F::.

Just like the word 'or', we use the word 'and' quite often in our day-to-day conversations. It's so common that it has found its way all the way into logic.

Let's explore its behavior in natural language.

Given the statement:

..what do you think its truth value will be?

Well, if you've taken our Python course, you'll know that Python is not statically-typed; but yes, it is object-oriented.

That is, the first atomic proposition is false, but the second one is true. Since one atomic proposition is false, the whole statement is false. This is because in the given statement, with the word 'and', we assert that both the given propositions are true, not just one.

This follows from the way we interpret 'and' in natural language.

As another example, consider the following:

Seriously — cloves, garlic? Are we making a cake, or a broth? Without any doubt and second thought, both the atomic propositions are false. And since both are false, the whole statement is, pretty intuitively, also false.

It's only when both the statements are true, that we could say that their 'and' is true, as follows:

Indeed, a pound cake requires sugar (the irresistable sweetness) and flour (for texture) i.e. both the atomic propositions are true; and hence the whole sentence is true as well.

The 'and' operation is formally known as conjunction in logic.

Shown below is the truth table for ::p \wedge q:::

One thing worth mentioning over here is that, often times, conjunctions in English aren't just represented using the word 'and'. Sometimes other words, such as 'but', 'while' etc. are also used, and they mean the same thing.

For instance, instead of saying 'Megan loves guitars and Charlie loves drums', we could say 'Megan loves guitars but Charlie loves drums'. Both the sentences are effectively the same — it's just that they are read differently.

Statements of the following nature:

..are very common in natural language. Even more so, they are really useful in computer programming. As a consequence, they've shown up in logic as well. They are known as implications.

If it is raining, then you'd expect me to go out with an umbrella. But what if I don't?

Well, if it's raining and I do go out with an umbrella, then the given statement would be true. But if it's raining and I go out without an umbrella, then the given statement would be false.

Notice that there are two more possibilities.

1. It is not raining and I go out with an umbrella.
2. It is not raining and I go out without an umbrella.

In both these cases, since the condition of the statement i.e. 'If it is raining' is not fulfilled, we can't strictly claim that the whole statement is false. For the statement to be false, the condition should be met and the following assertion should be false — only then can we say that the whole statement is false.

If the condition is false, the compound statement still technically holds.

Formally, the condition of an implication statement is known as the premise, or the hypothesis, or the antecedent; while the following, implied, statement is called the conclusion, or consequent.

In short, an implication can be refuted in only one case and that is when the premise is true but the conclusion is false.

Implications are denoted using the symbol ::\to:::

The arrow points towards the conclusion, analagous to how the premise takes to the conclusion. Let's have a look over the semantics of implications.

When the premise ::p:: is ::\bold T::, but the consequent is ::\bold F::, only then we say that the original statement is ::\bold F::. Otherwise, it is ::\bold T::.

The following snippet shows some other ways to express ::p \to q:: in English.

Often times, when we use the word if...then in a sentence, we mean that the consequent can only occur if the condition holds. If the condition doesn't hold, then our conclusion has to be false.

For instance, read the following:

Here, we see that the use of 'if' implies that if I know computing then I have a computer, and conversely, if I don't know computing then I don't have a computer. The 'if' is implicity guaranteeing the falsity of the conclusion when the premise is false.

In other words, this type of an implication says that if the premise is false, then the conclusion is also false. This is the only difference it has as compared to a normal implication.

This special kind of if was studided by logicians and ultimately formalised into logic. We call it a biconditional, or a bi-implication, or bidirectional impliciation.

In words it is written as 'if and only if', or simply as 'iff' in abbreviated form.

Here's an example of using iff in plain English:

This sentence is merely saying that if the Euclidean algorithm is used, then the program will definitely finish on time; and if it's not used then it definitely won't finish on time.

Talking about its notation, it's denoted using a double-headed arrow.

Time for the semantics of ::p \leftrightarrow q:::

Everything here is the same as for a normal implication except for one thing that when the premise is ::\bold F::, then the conclusion must also be ::\bold F::, for ::p \leftrightarrow q:: to be ::\bold T::. However, if the premise is ::\bold F::, but the conclusion is ::\bold T::, then this refutes the compound proposition and hence we get the value ::\bold F::.

Simple!

In this chapter, we got an introduction to the most common logical operators in PL. In the next chapter, we'll construct compound propositions by using a mixture of these operators; and then see their possible truth values by drawing out truth tables.