Propositional Logic | Baeldung on Computer Science

1. Overview

In this tutorial, we’ll study the basic concepts for propositional logic and for logical operators.

At the end of the tutorial, we’ll be familiar with the concepts of proposition and logical operator, and know how to calculate the truth value of the elementary formulas in propositional logic.

2. An Introduction to Propositional Logic

Propositional logic is a branch of logic, philosophy, and discrete mathematics that focuses on the study of statements and their relationships. The discipline was developed for the purpose of formalizing logical reasoning over formal disciplines such as mathematics and was further extended into computing. The branch of machine learning that concerns itself with logical and symbolic reasoning, of which propositional logic is a part of, is called Symbolic Artificial Intelligence.

Symbolic artificial intelligence contains methodologies related to reasoning over logical propositions. These methodologies are an important component of autonomous agent systems, and an integral part of the branches of natural language processing, expert systems, Bayesian inference, and semantic representation.

Among these methodologies, we can find those related to the operation of inferential engines. Inferential engines are systems that use propositional knowledge in order to generate new knowledge algorithmically and are based upon the same theoretical foundation as that of propositional logic.

Propositional logic also allows the automatic proving of certain types of theorems in mathematics and formal logic. The first automated theorem prover that used propositional logic dates back to the 1950s, but since then the development has continued steadily. Today, there are specialized programming languages that contain automatic theorem proving procedures that under certain conditions guarantee to find proofs for theorems that are formulated in those languages.

3. Statements

3.1. Statements in Propositional Logic

Foundational to the discipline of propositional logic is the concept of a statement. Statements are the elementary conceptual units upon which we build whole logical systems that then allow us to perform logical operations.

A statement, in the context of propositional logic, is a sequence of words that conforms to the syntactical and grammatical rules of a human natural language. In this sense statements aren’t different from the common definition of sentences and the two concepts are in fact related, though not entirely coincident. Statements must in fact also conform to additional rules that are specific to propositional logic, as we’ll see shortly, and while it’s true that all statements are sentences, there are however sentences that aren’t statements.

Statements can be interpreted to obtain factual or abstract knowledge about the world. It’s also however possible to operate on them without any understanding, in an automatic manner.

By assigning semantic meaning to its syntactical structure, a human can interpret a statement and understand its content. By performing logical operations on them, instead, a program can perform inference on a set of statements and deduce new truths. Some common systems for automatic reasoning over propositions include Drools and d3web, frequently used in business management.

3.2. Notation for Propositional Logic

A proposition is normally indicated with a lowercase letter of the alphabet, in italics, as in $p$ or $q$ . When we assign specific content to a statement, though, we prefer to use the corresponding uppercase letters. Further, and this is often a source of confusion for many, sets of statements are also indicated with uppercase letters, which makes it difficult to distinguish them from sets of statements with specific content.

According to this notation, we can thus say that:

$p$ and $q$ indicate generic propositions that we can use for instance to prove theorems
$P$ and $Q$ indicate two specific statements, such as $P = \text{Mark is an engineer}$ or $Q = \text{The apple is green}$
$M = \{p, q\}$ indicates a set $M$ containing two propositions $p$ and $q$
$N = \{P, Q\}$ indicates a set $N$ containing the two specific statements defined above

The notation in the literature of propositional logic is to some degree flexible, so we must make sure to read exactly what each author means with each symbol. Regardless, all authors agree to the usage of lowercase letters for the identification of general propositions, and we’ll also do that here.

3.3. Truth Value of Propositions

We mentioned that statements are analogous to sentences in linguistics, but that there are some important differences to mention. These relate to the so-called truth value of a proposition, which we see now, and whose relationship with linguistics we discuss in the next sections.

Statements, but not necessarily sentences, have a truth value. This means that if a sentence is a proposition, then it’s possible to decide in principle about whether it’s true or not. Conversely, if we can’t decide in principle about the validity of the sentence, then that sentence isn’t a proposition.

Let’s make a few examples of both cases:

“The temperature is 24 degrees” is a proposition, because we can assess its truth by observing a thermometer and its readings
“Pigs can fly” is a proposition, because we can verify it by observing pigs flying (or not flying)
“There is a pink unicorn living on Pluto” is a proposition, because we can imagine sending a rocket to Pluto to check it
“Joe hates spaghetti” is a proposition, because we can ask Joe about his tastes and find out
“Do you like this movie?” isn’t a proposition, because we can discuss the truth of this sentence’s answer but not of the question
“Rest a bit before going” isn’t a proposition, because invitations or advice don’t have a way to be decided

3.4. Truth Values and Boolean Logic

The truth value of a proposition must be definite, and assume one and only one value. This means that, in this context, Boolean logic always applies to propositional logic. This means that statements must have one and only one of two values: true or false.

In computer science, it’s customary to indicate the truth value of a statement with the binary digits 1 and 0, for true and false respectively. We’re also going to do the same here and say that if the proposition $p$ is true it then has a value of 1, and 0 otherwise.

One last note on truth values of propositions is that Boolean logic is not intrinsically necessary, but rather a convention. There in fact exist extensions of fuzzy and also of quantum logic to propositional logic, but they’re outside of the scope of this article and we won’t treat them here.

4. Declarative Versus Non-Declarative Sentences

We’ve discussed above that propositions are sentences whose truth can be decided in principle. We’re now going to see how we call and define these sentences in linguistics. This, in turn, will allow us to convert from propositions in logic format to sentences in natural language.

We can identify at least four classes of sentences:

Declarative, which contains facts or information about the world
Interrogative, which posits questions that we can answer by means of declarative sentences
Imperative, containing orders or instructions on how things should or must be done
Exclamatory, aimed at evoking emotions in the listener but possessing no factual content

We’ll now see them here in turn.

4.1. Propositions as Declarative Sentences

Declarative sentences are those that translate into propositions. All declarative sentences have at least two components: a subject and a predicate. The predicate is always explicit and must be a recognizable word in a sentence.

The subject, not necessarily. In English, the subject of a declarative sentence is always explicit, but this isn’t valid for all languages. Declarative sentences in one of those languages containing a predicate without a subject still constitute propositions, because the subject can always be deduced by the morphology of the verb.

For example, the declarative sentence in English “we go home” is a proposition, because it contains a factual statement about the world whose truth value can be tested by observing where we are going. The sentence contains an explicit subject, but this is accidental and specific for English. The same sentence is expressed as:

“andiamo a casa” in Italian
“идем домой” in Russian
“نذهب إلى البيت” in Arabic

The subject isn’t explicit in any of these languages, but the information contained in all sentences is identical to the sample sentence in English. From this, we derive the conclusion that the information content of a sentence, and not its syntactical content, is the one upon which we decide to classify the sentence as declarative rather than not, and therefore as a proposition.

4.2. Non-Propositions and Interrogatives

A common mistake when approaching propositional logic is to erroneously identify non-declarative sentences as propositions. We’re therefore going to see them here in more detail, to understand how to spot them and not be mistaken.

The first class of non-declarative sentences is interrogatives. Interrogative sentences are often easily recognized by the question mark $?$ at their end, but the less trivial cases are those that we should mind. Let’s look at these sample sentences:

“Tell me how can I go home from here.”
“Did they tell you if the package arrived yet?”
“I’d like to know if you’re being honest.”
“I’m amazed, how come you haven’t heard!”

The four sentences all contain indirect questions. We can rewrite them and break them down in this manner, in order to highlight the interrogative:

Tell me! How can I go home from here?
Did they tell you? Did the package arrive yet?
I’d like to know. Are you being honest?
I’m amazed! How come you haven’t heard?

Of these, sentence number 3 consists of an indirect question embedded in a declarative, which at first sight could be mistakenly identified as a declarative.

4.3. Non-Propositions and Imperatives

The second class of non-declarative sentences is the imperatives, which constitute orders or instructions. The word imperative is in fact a derivation of the Latin verb impero, which means to command.

Imperatives aren’t propositions because it’s impossible in principle to decide about their truth value. They do, in fact, contain information on how the world should or must be, not about its factual status. As a general rule, if we see an exclamation mark $!$ at the end of a sentence, then the sentence is either exclamative or imperative but not declarative. The edge cases, however, make recognition harder.

Languages such as English allow formulating a rule-based system for the detection of imperative sentences in a text. The rule states that: “if the sentence has no explicit subject, then it’s an imperative”:

Go!
Come here.
Eat all the salad.

This consideration is however not valid for all languages. For some of them, we require contextual clues to discriminate between imperative and declarative sentences. In Italian, for instance, the English sentences “you go home” and “go home!” equally translate to “vai a casa”, which makes it impossible to discriminate on purely syntactical grounds.

4.4. Non-Propositions and Exclamatories

The last class of sentences that can’t form propositions is the exclamatory sentences. These are normally indicated by an exclamation mark $!$ at their end, analogously to the imperatives.

In the context of propositional logic, we’re never required to discriminate between imperative and exclamatory sentences. We can therefore generally assume that a sentence ending with an exclamation mark isn’t a logical proposition.

Exclamatory sentences aren’t propositions because their functionality in communication is to evoke or arouse emotions. Their truth value can’t be decided because they don’t hold information about the world; but rather, they serve the exclusive purpose of allowing expression of the internal dimension of affections. We talked more about this subject in our article on the detection of emotions in texts.

5. Well-Formed Formulas

Central to the discipline is also the concept of well-formed formula, often abbreviated as WFF, which are the equivalent of algebraic formulas for algebra. WFFs are sequences of symbols that hold a truth value, either true or false, in a manner analogous to that of propositions. There are special rules for operating with WFFs, which in turn constitute the subject of propositional calculus. WFFs are important because only on them can we perform inference and prove theorems.

We’ve already discussed the fact that propositions have a truth value. Therefore all propositions, individually, are well-formed formulas. Individual propositions that comprise a well-formed formula are also called atomic propositions, because of their indivisibility. There are however logical operators that let us connect two or more atomic propositions, and thus help us create a compound proposition from them.

5.1. The Negation Operator NOT

One special type of connective is the unary operator not p, also expressed as $\neg p$ and $1-p$ . This operator is special because it affects only one atomic proposition, not two, and is therefore called unary.

The negation operator is the most simple logical operator, and has this truth table:

A proposition preceded by a negation is always a well-formed formula. With the notation we defined, we can say that if $p$ is a WFF then $\neg p$ is also a WFF.

The conversion between a declarative sentence in English and its negation can be performed by adding not to the sentence, as per the appropriate syntactical rules. If $P$ is a proposition that refers to the sentence “Mark eats an apple”, then $\neg P$ refers to the sentence “Mark doesn’t eat an apple”. Notice how in English we often need to add an auxiliary verb to negate a sentence, and can’t just straight insert the word not.

Notice also that the subject of double negation is a particularly complex one. Double negation refers to the double application of the negation operator to the same proposition, such as $\neg \neg p$ . In computer science and in propositional logic we normally accept that the double negation of a proposition has the same truth as the original proposition, such that $\neg \neg p \rightarrow p$ , but there are systems of logic that disallow this.

5.2. The Conjunction Operator AND

The second operator is and, which connects two atomic propositions to one another. We normally express this operator as $p\ \text{and}\ q$ , $p \wedge\ q$ , $p \cdot q$ , or $p\ \& q$ . The and operator has the following truth table:

An intuitive way to understand this operator is to say that the conjunction of two propositions is only true if both of them are also true.

The translation between WFF containing and operators and declarative sentences in English is simple and requires only to attach the conjunction and to pairs of sentences:

$P = \text{Mark eats an apple}$
$Q = \text{Julie drinks water}$
$P \wedge Q = \text{Mark eats an apple}\ \textit{and}\ \text{Julie drinks water}$

5.3. The Disjunction Operator OR

The third operator is or, which disjoins two atomic propositions from one another. This operator is generally written as $p\ \text{or}\ q$ , $p \vee\ q$ , $p + q$ , or $p\ |\ q$ . The or operator possesses the following truth values:

We need to simply remember that the operation or returns true if any of the two propositions are true.

In order to convert a WFF containing or to a phrase in English, we simply insert the word or between the sentences:

$P = \text{Mark eats an apple}$
$Q = \text{Julie drinks water}$
$P \vee Q = \text{Mark eats an apple}\ \textit{or}\ \text{Julie drinks water}$

5.4. The Material Conditionial IF … THEN

The fourth operator is the material conditional if … then, also called implication or simply conditional. We normally express this operator as either $p \rightarrow q$ , $p ? q$ , $p \Rightarrow q$ , or $\text{if}\ p\ \text{then}\ q$ . The conditional operator has this truth table:

In the context of the conditional operator, the first proposition $p$ is called premise or antecedent of the implication, and the second proposition $q$ is called consequent or consequence.

5.5. An Intuitive Understanding of Material Conditionals

This operator is the least intuitive of all. If we look at the truth table above, we can see that WFFs containing this operator are always true except if, given the truth of the antecedent, the consequent is false.

Let’s look at what this means with an example regarding sports and leisure time:

This example is represented by the following set of propositions:

$P = \text{It's sunny outside}$
$Q = \text{I play football}$
$P \rightarrow Q = \textit{IF}\ \text{It's sunny outside}\ \textit{THEN}\ \text{I play football}$

We can then ask ourselves when is this implication false. Suppose it’s sunny outside, and we’re playing football. In this case, the implication is understandably true. Suppose however that we’re playing football while it’s night or raining:

Is in this case the implication false? The answer that we provide in propositional logic is that no, the implication isn’t false.

5.6. When Is a Material Conditional False?

One way to look at this is to imagine that the implication functions only if the condition present in the premise manifests itself, which isn’t the case for our example. If we’re indeed playing football at night, and if therefore $Q$ is true, that doesn’t tell us anything about the reasons why we’re playing, and therefore whether the implication as a whole is valid in this context.

The case in which the implication is false is instead sufficiently simple to understand. Imagine it’s sunny outside, but also that we’re not playing football but eating an apple instead:

We can then argue that the promise we made to play football if it’s sunny outside isn’t being respected, which then invalidates the implication.

One last note regarding conversion: in order to convert an implication to a phrase in English, we simply insert the words if before the antecedent and then before the consequent:

$P = \text{Mark eats an apple}$
$Q = \text{Julie drinks water}$
$P \rightarrow Q = \textit{If}\ \text{Mark eats an apple}\ \textit{then}\ \text{Julie drinks water}$

6. Conclusions

In this tutorial, we studied the foundational concepts for propositional logic, that include the idea of proposition and declarative sentences.

We’ve also studied the elementary logical operators, and learned the truth values associated with well-formed formulas containing them.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex