Propositional Operators

Chapter 3 41 mins

Learning outcomes:

  1. What are logical operators
  2. Negation (::\neg::)
  3. Disjunction (::\vee::)
  4. Exclusive disjunction (::\oplus::)
  5. Conjunction (::\wedge::)
  6. Implication (::\to::)
  7. Biconditional (::\leftrightarrow::)

Introduction

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.

What is a logical operator

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

A logical operator is something that can be used to create compound propositions from atomic propositions.

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.

Negation

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

C++ is easy.

..what would you write as the negation?

Well, we'd just write this:

C++ is not easy.

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.

London is in Australia.

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

London is not in Australia.

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}::.

So if we are given a proposition ::p::, it's negation would symbolically be represented as ::\pmb{\neg p}::.
Other symbols also exist for negation. One of them is ::\sim:: which was also used in the famous book Principia Mathematica, by Bertrand Russell and Alfred North Whitehead. The other symbol is ::!::. Sometimes, the word ::{\sim}p::, ::\rm{NOT}:: is used directly as well. So other ways to express the negation of a proposition ::p:: are ::\neg p::, ::{\sim}p::, ::\rm{NOT} \space \mathnormal p::.

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.

A truth table explores all possible truth values for the constituent propositions and then showcases the truth values of the compound proposition.

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:

::p::::\neg p::
::\bold T::::\bold F::
::\bold F::::\bold T::
::\bold T:: stands for true, while ::\bold F:: stands for false.

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!

Given the following propositional variables and expressions, convert the expression into equivalent English sentences.

  1. ::p:: : Ali is playing outside.
    ::\neg p::
  2. ::e:: : 2 is an even integer.
    ::\neg e::
  3. ::a:: : ASP stands for Active Server Pages.
    ::\neg a::
  4. ::easy:: : Python is easy.
    ::\neg easy::
  1. Ali is not playing outside.
  2. 2 is not an even integer.
    Note that this statement could also be expressed as '2 is an odd integer', since we know that any integer can either be even or odd, nothing else. Likewise, if an integer is not even, then it must be odd.
  3. ASP does not stand for Active Server Pages.
  4. Python is not easy.

Given the following English sentences, express each one symbolically using a propositional variable and the negation operator.

  1. Icecream is not delicious.
  2. C++ is not object-oriented.
  3. Elementary logic is not easy to understand.
  4. Jupiter is bigger than Earth.
  1. ::i:: : Icecream is delicious.
    ::\neg i::
  2. ::o:: : C++ is object-oriented.
    ::\neg o::
  3. ::e:: : Elementary logic is easy to understand.
    ::\neg e::
  4. ::j:: : Jupiter is not bigger than Earth.
    ::\neg j::

Disjunction

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

Java was created in the 1990s or Java was created in the 1970s.

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:

Java was created in the 1990s or Java is an OOP language.

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:

Java was created in the 1960s or Java was created in the 1970s.

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.

Precision of logic vs. ambiguity of natural languages

Now before we move on, notice one thing in the sentences above. The second statement in each of the compound propositions above has explicitly mentioned the respective fact about Java. However, as we know, when we are working in English and referring to the same thing, we could skip the step of writing it again in words, since it is automatically, implicity implied.

For instance, instead of saying 'Java was created in the 1960s or Java was created in the 1970s', we could simply say 'Java was created in the 1960s or 1970s'.

This works in English — in fact, one should write this way in English, otherwise he/she would be uselessly dragging the length of his/her sentences.

However, logic is not English, or any other natural language. It may be influenced by natural languages but it is a language on its own. And it is precise — everything ought to be specified precisely.

Logic is meant to remove the ambiguities of natural languages so reasoning could be unified.

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::.

The disjunction of two propositions ::p:: and ::q:: is denoted as ::\pmb{p \vee q}::.
The symbol ::\vee:: comes from the Latin word 'vel' which means 'or'.

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.

::p::::q::::p \vee q::
::\bold T::::\bold T::::\bold T::
::\bold T::::\bold F::::\bold T::
::\bold F::::\bold T::::\bold T::
::\bold F::::\bold F::::\bold F::

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

A disjunction can be denoted using ::\pmb{|}:: (::p \space \pmb{|} \space \mathnormal{q}::), or even the word ::\rm{OR}:: (::p \space \rm{OR} \space \mathnormal{q}::).

Given the following propositional variables and expressions, convert the expression into equivalent English sentences.

  1. ::a:: : Ali is playing outside;   ::s:: : Sara is playing outside.
    ::a \vee s::
  2. ::o:: : Java is object-oriented;   ::i:: : Java is imperative.
    ::o \vee i::
  3. ::today:: : Today is a rainy day;   ::tomorrow:: : Tomorrow is a rainy day.
    ::today \vee tomorrow::
  4. ::g:: : Google CodeJam is easy
    ::g \vee \neg g::
  1. Ali is playing outside or Sare is playing outside.
  2. Java is object-oriented or Java is imperative.
  3. Today is a rainy day or tomorrow is a rainy day.
  4. Google CodeJam is easy or Google CodeJam is not easy.

Given the following English sentences, express each one symbolically using propositional variables and logical operators.

  1. Branding takes months or years to learn.
  2. Pizza dough is made with improvers or without improvers.
  3. Alex loves donuts or pasta.
  4. JavaScript was made by Brendan Eich or James Gosling.
  1. ::m:: : Branding takes months to learn;   ::y:: : Branding takes years to learn.
    ::m \vee y::
  2. ::i:: : Pizza dough is made with improvers
    ::i \vee \neg i::
    This expression represents one of the three laws of thought — the law of excluded middle. It states that anything is either true or not true. It is a tautology. We'll learn more in Propositional Equivalences.
  3. ::d:: : Alex loves donuts;   ::p:: : Alex loves pasta.
    ::d \vee p::
  4. ::b:: : JavaScript was made by Brendan Eich;   ::j:: : JavaScript was made by James Gosling.
    ::b \vee j::

Exclusive disjunction

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:

Pay $10 fine or take a chance.

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.

The exclusive disjunction of two propositions ::p:: and ::q:: is denoted as ::\pmb{p \oplus q}::.

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:::

::p::::q::::p \oplus q::
::\bold T::::\bold T::::\bold F::
::\bold T::::\bold F::::\bold T::
::\bold F::::\bold T::::\bold T::
::\bold F::::\bold F::::\bold F::

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::.

Another way to represent this operation is using the word ::\rm{XOR}:: (::p \space \rm{XOR} \space \mathnormal{q}::).

Given the following propositional variables and expressions, convert the expression into equivalent English sentences.

  1. ::f:: : Sara has paid a $10 fine;   ::c:: : Sara has taken a chance.
    ::f \oplus c::
  2. ::c:: : The boys are playing cricket;   ::t:: : The boys are playing table tennis.
    ::c \oplus t::
  3. ::r1:: : Auditions are happening in Room 1;   ::r2:: : Auditions are happening in Room 2.
    ::r1 \oplus r2::
  1. Sara has paid a $10 fine or taken a chance, but not both.
  2. The boys are playing cricket or table tennis, but not both.
  3. Auditions are happening in Room 1 or Room 2, but not both.

Given the following English sentences, express each one symbolically using propositional variables and logical operators.

  1. With a large pizza, you get garlic bread or chocolate brownie, for free.
  2. I will go to London or I will go to Toronto, but not both.
  3. The code will solve the question or exceed the time limit, but not both.
  1. ::g:: : With a large pizza, you get garlic bread for free;   ::b:: : With a large pizza, you get a chocolate brownie for free.
    ::g \oplus b::
  2. ::l:: : I will go to London;   ::t:: : I will go to Toronto.
    ::l \oplus t::
  3. ::s:: : The code will solve the question;   ::e:: : The code will exceed the time limit.
    ::s \oplus e::
  4. In statement 1, it's implicitly understood that we will either get a garlic bread for free, or a chocolate brownie for free, with a large pizza, but not both.

Conjunction

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:

Python is statically-typed and Python is object-oriented.

..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:

A pound cake requires cloves and a pound cake requires garlic.

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:

A pound cake requires sugar and a pound cake requires flour.

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.

The conjunction of two propositions ::p:: and ::q:: is denoted as ::\pmb{p \wedge q}::.

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

::p::::q::::p \wedge q::
::\bold T::::\bold T::::\bold T::
::\bold T::::\bold F::::\bold F::
::\bold F::::\bold T::::\bold F::
::\bold F::::\bold F::::\bold F::
Other symbols used are ::\rm{\&}:: (::p \space \rm{\&} \space q::), and ::\rm{AND}:: (::p \space \rm{AND} \space \mathnormal{q}::).

Given the following propositional variables and expressions, convert the expression into equivalent English sentences.

  1. ::b:: : I have ordered burgers;   ::f:: : I have ordered fries.
    ::b \wedge f::
  2. ::c:: : COVID-19 is a virus;   ::s:: : Salmonella is a bacteria.
    ::c \wedge s::
  3. ::p:: : I know Python;   ::c:: : I know C++.
    ::p \wedge c::
  4. ::b:: : Principia Mathematica was written by Bertrand Russell;
    ::a:: : Principia Mathematica was written by Alfred North Whitehead.
    ::b \wedge a::
  1. I have ordered burgers and fries.
  2. COVID-19 is a virus and Salmonella is a bacteria.
  3. I know Python and C++.
  4. Principia Mathematica was written by Bertrand Russell and Alfred North Whitehead.

Given the following English sentences, express each one symbolically using propositional variables and logical operators.

  1. The window is old and broken.
  2. Auditions are happening in Room 1 and Room 2.
  3. Megan plays guitar and Charlie plays drums.
  4. I love cricket and football.
  1. ::o:: : The window is old;   ::b:: : The window is broken.
    ::o \wedge b::
  2. ::r1:: : Auditions are happening in Room 1;   ::r2:: : Auditions are happening in Room 2.
    ::r1 \wedge r2::
  3. ::m:: : Megan plays guitar;   ::c:: : Charlie plays drums.
    ::m \wedge c::
  4. ::c:: : I love cricket;   ::f:: : I love football.
    ::c \wedge f::

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.

Implications

Statements of the following nature:

If it is raining, I go out with an umbrella.

..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:::

Given the premise ::p:: and conclusion ::q::, the implication is represented as ::\pmb{p \to q}::.

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.

::p::::q::::p \to q::
::\bold T::::\bold T::::\bold T::
::\bold T::::\bold F::::\bold F::
::\bold F::::\bold T::::\bold T::
::\bold F::::\bold F::::\bold T::

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.

Other ways to express ::p \to q::

Often times, implications in English aren't written in the straightforward way: 'if ::p::, then ::q::'. Implications can be expressed in numerous other ways, such as by adding in other words in this simpler statement, or by switching the premise and the conclusion, or by proposing completely different statements.

Shown below are a couple of ways to express the conditional statement ::p \to q:::

  1. ::q::, if ::p::
    Means that: ::q:: is true if ::p:: is true.
  2. ::q::, when ::p::
    Means that: ::q:: is true when ::p:: is true.
  3. ::p:: only if ::q::
    Means that: ::p:: is true only if ::q:: is true. Otherwise ::p:: is not true.
  4. ::p:: is sufficient for ::q::
    Means that: if ::p:: is true, then it is sufficient for ::q:: to be true as well.
  5. ::q:: is necessary for ::p::
    Means that: ::q:: being true, is necessary for ::p:: to be true.
  6. ::\neg p:: unless ::q::
    Means that: ::p:: won't be true, unless ::q:: is true.
  7. ::q:: unless ::\neg p::
    Means that: ::q:: would be true, unless ::p:: is false.

Given the following propositional variables and expressions, convert the expression into equivalent English sentences.

  1. ::r:: : It is raining;   ::u:: : I go out with an umbrella.
    ::r \to u::
  2. ::e:: : Quantum physics is easy;   ::s:: : I will study quantum physics.
    ::e \to s::
  3. ::o:: : Python is object-oriented;   ::s:: : Python supports classes.
    ::o \to s::
  4. ::p:: : I am in Paris;   ::b:: : I will buy perfume.
    ::\neg p \to b::
  1. If it is raining, then I go out with an umbrella
  2. If quantum physics is easy, then I will study quantum physics.
  3. If Python is object-oriented, then Python supports classes.
  4. If I am not in Paris, then I will buy perfume.

Given the following English sentences, express each one symbolically using propositional variables and logical operators.

  1. If Java supports dynamic arrays, then I will learn Java
  2. I won't be selected in the competition unless I make a really beautiful design.
  3. Alex can fly to London only if he has an airline ticket.
  4. If the item is above $2, then I won't buy it.
  5. The program gives a message when it's sharply 8pm.
  1. ::d:: : Java supports dynamic arrays;   ::l:: : I will learn Java.
    ::d \to l::
  2. ::s:: : I would be selected in the competition;   ::b:: : I make a really beautiful design.
    ::\neg s:: unless ::b::
    ::\neg b \to \neg s::
  3. ::f:: : Alex can fly to London;   ::t:: : Alex has an airline ticket.
    ::f:: only if ::t::
    ::f \to t::
  4. ::a:: : The item is above $2;   ::b:: : I will buy the item.
    If ::a::, then ::\neg b::
    ::a \to \neg b::
  5. ::m:: : The program gives a message;   ::s:: : It's sharply 8pm.
    ::m:: when ::s::
    ::m \to s::

Biconditionals

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:

If I know computing, then I have a computer.

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:

The program will finish on time if, and only if, the Euclidean algorithm is used.

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.

The biconditional of two propositions ::p:: and ::q::, is given as ::\pmb{p \leftrightarrow q}::
The double-headed arrow means that the proposition on either side implies the other one. Hence the two arrows.

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

::p::::q::::p \leftrightarrow q::
::\bold T::::\bold T::::\bold T::
::\bold T::::\bold F::::\bold F::
::\bold F::::\bold T::::\bold F::
::\bold F::::\bold F::::\bold T::

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!

Moving on

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.