Beyond True or False: The Nuances of Propositional Logic (CIA Submission)

 Ever wondered how computers can understand and process human language? A fundamental concept that underpins this ability is propositional logic. It's the language of logic, a system for representing and manipulating statements.

Think of it as the grammar of reasoning. Propositional logic provides the rules and structures for combining simple statements (called propositions) into more complex ones. These rules help us to determine the truth or falsity of these statements based on the truth values of their components.

Propositions

Our discussion begins with an introduction to the basic building blocks of logic—propositions. A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both.

For example, let us take a couple of declarative sentences.

1. Washington, D.C., is the capital of the United States of America.

2. Toronto is the capital of Canada.

3. 1 + 1 = 2

4. 2 + 2 = 3

So here, Propositions 1 and 3 are true whereas 2 and 4 are false.

Now, let us take sentences which aren't propositions;

1. Read this carefully.

2. x + 1 = 2

3. x + y = z

Here, 1 isn't a proposition since the sentence is not declarative, whereas 3 and 4 aren't propositions because they are neither true nor false, but can be converted to propositions once values are assigned to the variables.

We use letters to denote propositional variables (or statement variables), that is, variables that represent propositions, just as letters are used to denote numerical variables. The truth value of a proposition is true, denoted by T, if it is a true proposition, and the truth value of a proposition is false, denoted by F, if it is a false proposition. The area of logic that deals with propositions is called the propositional calculus or propositional logic. It was first developed systematically by the Greek philosopher Aristotle more than 2300 years ago.

Negation of p (¬p or p'): The proposition ¬p is read “not p.” The truth value of the negation of p, ¬p, is the opposite of the truth value of p.

For example: We take a proposition "It is raining." So the negation of this proposition is "It is not the case that it is raining." 

This negation can be simply expressed as "It is not raining."

In propositional logic, we need to know the truth values of propositions in all possible scenarios. We can combine all the possible combination with logical connectives, and the representation of these combinations in a tabular format is called Truth table. The truth table for negation is expressed as follow:

The negation of a proposition can also be considered the result of the operation of the negation operator on a proposition. The negation operator constructs a new proposition from a single existing proposition.

We will now introduce the logical operators that are used to form new propositions from two or more existing propositions. These logical operators are also called connectives. 

Conjunction (p ∧ q): Let p and q be propositions. The conjunction of p and q, denoted by p ∧ q, is the proposition “p and q.” The conjunction p ∧ q is true when both p and q are true and is false otherwise.

Example: Rohan is intelligent and hardworking. 

It can be written as,
P= Rohan is intelligent,
Q= Rohan is hardworking.
→ P∧ Q'

The truth table for Conjunction is as follow: 

Disjunction (p ∨ q): Let p and q be propositions. The disjunction of p and q, denoted by p ∨ q, is the proposition “p or q.” The disjunction p ∨ q is false when both p and q are false and is true otherwise.

Example: "Ritika is a doctor or Engineer", 

Here P= Ritika is Doctor.
Q= Ritika is Engineer, 

so we can write it as P ∨ Q.

The truth table for Disjunction is as follow:

Exclusive-OR (p ⊕ q): Let p and q be propositions. The exclusive or of p and q, denoted by p ⊕ q, is the proposition that is true when exactly one of p and q is true and is false otherwise.

Exclusive OR (XOR) is like telling the waiter, "I want either a steak or a fish, but not both." It's a choice where only one option can be true at a time.

Here's a breakdown:

If you choose a steak: That's true.

• If you choose a fish: That's true.
• But if you choose both steak and fish: That's false because you can only have one.

In simpler terms: XOR means "one or the other, but not both."

CONDITIONAL STATEMENTS

(i) Let p and q be propositions. The conditional statement p → q is the proposition “if p, then q.” The conditional statement p → q is false when p is true and q is false, and true otherwise. In the conditional statement p → q, p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence). Implications are also known as if-then rules. The statement p → q is called a conditional statement because p → q asserts that q is true on the condition that p holds. A conditional statement is also called an implication.

For example, if we take a sentence: If it is raining, then the street is wet.
 Let P= It is raining, 

and Q= Street is wet, 

so it is represented as P → Q.

Because conditional statements play such an essential role in mathematical reasoning, a variety of terminology is used to express p → q. You will encounter most if not all of the following ways to express this conditional statement: 

“if p, then q” 

“p implies q” 

“if p, q” 

“p only if q” 

“p is sufficient for q” 

“a sufficient condition for q is p” 

“q if p” 

“q whenever p” 

“q unless ¬p” , and many more...

A useful way to understand the truth value of a conditional statement is to think of an obligation or a contract. For example, the pledge many politicians make when running for office is “If I am elected, then I will lower taxes.” If the politician is elected, voters would expect this politician to lower taxes. Furthermore, if the politician is not elected, then voters will not have any expectation that this person will lower taxes, although the person may have sufficient influence to cause those in power to lower taxes. It is only when the politician is elected but does not lower taxes that voters can say that the politician has broken the campaign pledge. This last scenario corresponds to the case when p is true but q is false in p → q.

CONVERSE, CONTRAPOSITIVE, AND INVERSE:

1. Converse (The proposition q → p is called the converse of p → q)

• Definition: A proposition formed by switching the hypothesis and conclusion of the original proposition.
• Example:
  • Original: If it rains, the ground gets wet.
  • Converse: If the ground gets wet, it rains.

2. Contrapositive (Contrapositive of p → q is the proposition ¬q → ¬p.)

• Definition: A proposition formed by negating both the hypothesis and conclusion of the original proposition and then switching them.
• Example:
  • Original: If it rains, the ground gets wet.
  • Contrapositive: If the ground does not get wet, it did not rain.

3. Inverse (¬p → ¬q is called the inverse of p → q.)

• Definition: A proposition formed by negating both the hypothesis and conclusion of the original proposition, but without switching them.
• Example:
  • Original: If it rains, the ground gets wet.
  • Inverse: If it does not rain, the ground does not get wet.

Important Note: In logic, the original proposition and its contrapositive are always equivalent. This means that if one is true, the other must be true, and if one is false, the other must be false. The converse and inverse, however, are not necessarily equivalent to the original proposition.

When two compound propositions always have the same truth value we call them equivalent, so that a conditional statement and its contrapositive are equivalent. The converse and the inverse of a conditional statement are also equivalent, as the reader can verify, but neither is equivalent to the original conditional statement.

For example, we have a statement “The home team wins whenever it is raining?”

Now to find the converse, contrapositive and inverse of the above statement,

Because “q whenever p” is one of the ways to express the conditional statement p → q, 
the original statement can be rewritten as “If it is raining, then the home team wins.” 

Consequently, the contrapositive of this conditional statement is “If the home team does not win, then it is not raining.”

 
The converse is “If the home team wins, then it is raining.”

 
The inverse is “If it is not raining, then the home team does not win.”

 
Only the contrapositive is equivalent to the original statement.

BICONDITIONALS

Let p and q be propositions. The biconditional statement p ↔ q is the proposition “p if and only if q.” The biconditional statement p ↔ q is true when p and q have the same truth values, and is false otherwise. Biconditional statements are also called bi-implications.

For example, we have a sentence "If I am breathing, then I am alive."  

P= I am breathing, Q= I am alive, 

it can be represented as P ⇔ Q. 

The truth table for biconditionals is as follow:

It is, however, to be noted that biconditionals are not always explicit in natural language. In particular, the “if and only if” construction used in biconditionals is rarely used in common language. Instead, biconditionals are often expressed using an “if, then” or an “only if” construction. The other part of the “if and only if” is implicit. That is, the converse is implied, but not stated. For example, consider the statement in English “If you finish your meal, then you can have dessert.” What is really meant is “You can have dessert if and only if you finish your meal.” This last statement is logically equivalent to the two statements “If you finish your meal, then you can have dessert” and “You can have dessert only if you finish your meal.” Because of this imprecision in natural language, we need to make an assumption whether a conditional statement in natural language implicitly includes its converse. Because precision is essential in mathematics and in logic, we will always distinguish between the conditional statement p → q and the biconditional statement p ↔ q.

Compound Propositions

A compound proposition is formed by combining two or more simple propositions using logical connectives. These connectives allow us to form more complex statements whose truth depends on the truth values of their components. For instance, the statement "It is raining and it is cold" is a compound proposition involving the logical connective "and."

Since we have now introduced four important logical connectives—conjunctions, disjunctions, conditional statements, and biconditional statements—as well as negations. We can use these connectives to build up complicated compound propositions involving any number of propositional variables. We can use truth tables to determine the truth values of these compound propositions. 

We use a separate column to find the truth value of each compound expression that occurs in the compound proposition as it is built up. The truth values of the compound proposition for each combination of truth values of the propositional variables in it is found in the final column of the table.

For example, if we have an expression p ∨ q → ¬r

So the truth table will look like as below:

PRECEDENCE OF OPERATORS

Just like arithmetic operators, there is a precedence order for propositional connectors or logical operators. This order should be followed while evaluating a propositional problem. Following is the list of precedence order for operators:

APPLICATIONS OF PROPOSITIONAL LOGIC

While it may seem abstract, propositional logic has a wide range of practical applications across various fields. By breaking down complex reasoning into simple propositions and logical connectives, it provides a systematic way to analyze and solve problems. 
For example, logic is used in the specification of software and hardware, because these specifications need to be precise before development begins. Furthermore, propositional logic and its rules can be used to design computer circuits, to construct computer programs, to verify the correctness of programs, and to build expert systems. Logic can be used to analyze and solve many familiar puzzles. Software systems based on the rules of logic have been developed for constructing some, but not all, types of proofs automatically.

We will be discussing one of many applications, and that is, Translating English sentences.

There are many reasons to translate English sentences into expressions involving propositional variables and logical connectives. In particular, English (and every other human language) is often ambiguous. Translating sentences into compound statements (and other types of logical expressions, which we will introduce later in this chapter) removes the ambiguity. Note that this may involve making a set of reasonable assumptions based on the intended meaning of the sentence. Moreover, once we have translated sentences from English into logical expressions we can analyze these logical expressions to determine their truth values, we can manipulate them, and we can use rules of inference to reason about them.

Let us look at few examples...

(I) How can this English sentence be translated into a logical expression? 

“You can access the Internet from campus only if you are a computer science major or you are not a freshman.”

Solution: The given sentence can be translated into a logical expression as follows:

Let P represent "you are a computer science major". 

Let Q represent "you are a freshman". 

Let R represent "you can access the Internet from campus".

Then, the sentence can be expressed as:

R → (P ∨ ¬Q)

This expression means that if you can access the Internet from campus (R), then it must be the case that you are either a computer science major (P) or you are not a freshman (¬Q).

(II) How can this English sentence be translated into a logical expression? 

“You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old.”

Solution: Let:

• P represent "you are under 4 feet tall."
• Q represent "you are older than 16 years old."
• R represent "you can ride the roller coaster."

Then, the given sentence can be translated into a logical expression as:

¬R → (¬P ∨ Q)

This expression means that if you cannot ride the roller coaster (¬R), then it must be the case that either you are not under 4 feet tall (¬P) or you are older than 16 years old (Q).

<endnote>

And that is all for this blogpost (which by the looks of the length, has turned into a research paper at this point...) on the topic of "Propositional Logic" for my CIA assignment submission, assigned by my Mathematics teacher, Dr. Ansa Mathew. Until next time folks, when I arrive with another anecdote of my adventures in Christ University!

- Divyabhanu Rana

</endnote>