Logical Connectives and Their Truth Tables

Logical Connectives: Introduction

In the previous sections, we learned about simple mathematical statements (propositions) and how to form their negation. However, complex arguments and mathematical theorems are built by combining multiple simple statements. This is achieved using logical connectives, which act as the glue binding propositions together to form compound statements.

What are Logical Connectives?

Logical connectives (or logical operators) are symbols or words used to connect two or more simple statements, or to modify a single statement, to form a new, compound statement. The truth value of this new compound statement is determined solely by the truth values of its component statements and the specific connective used.

Think of them like mathematical operators ($+, -, \times, \div$) but for logic. Just as '$2 + 3$' produces a value based on the numbers 2 and 3 and the '+' operator, a compound statement like '$p$ and $q$' produces a truth value based on the truth values of $p$ and $q$ and the "and" connective.

Primary Logical Connectives

The main logical connectives, along with their corresponding English terms and symbols, are:

1. Conjunction: Corresponds to the word "and". Symbol: $\land$.
2. Disjunction: Corresponds to the word "or". Symbol: $\lor$.
3. Negation: Corresponds to the word "not". Symbols: $\sim$ or $\neg$. (As noted before, this is a unary operator, acting on a single statement).
4. Conditional (Implication): Corresponds to the phrase "if... then...". Symbols: $\implies$ or $\rightarrow$.
5. Biconditional (Equivalence): Corresponds to the phrase "if and only if". Symbols: $\iff$ or $\leftrightarrow$.

The meaning of each connective is formally defined by its truth table, which lists the resulting truth value of the compound statement for every possible combination of truth values of its component statements.

In the following sections, we will delve into the truth tables and properties of Conjunction and Disjunction, and we have already covered Negation.

Competitive Exam Pointer: Basic Connectives

Conjunction (AND, $\land$) and its Truth Table

The conjunction is one of the simplest ways to combine two statements. It corresponds to the English word "and". When we connect two statements with "and", we are asserting that both statements are true.

Definition of Conjunction

Let $p$ and $q$ be two simple statements. The conjunction of $p$ and $q$ is the compound statement formed by connecting $p$ and $q$ with the word "and".

• Symbol: The symbol for conjunction is $\land$.
• Notation: The conjunction of $p$ and $q$ is written as $p \land q$.
• Read as: "$p$ and $q$".

The truth value of the conjunction $p \land q$ is defined as follows: $p \land q$ is True if and only if both $p$ is true and $q$ is true. In all other cases (if $p$ is false, or $q$ is false, or both are false), the conjunction $p \land q$ is False.

Truth Table for Conjunction ($\land$)

The truth table for conjunction systematically lays out the truth value of $p \land q$ for every possible combination of truth values for $p$ and $q$. Since there are two component statements, and each can be either True or False, there are $2 \times 2 = 4$ possible combinations of truth values for the pair $(p, q)$.

This table clearly shows that the only time the conjunction $p \land q$ is True is when both $p$ and $q$ are True (the first row). Any instance of a False component statement makes the entire conjunction False.

Answer:

Competitive Exam Pointer: Conjunction

Disjunction (OR, $\lor$) and its Truth Table (Inclusive and Exclusive OR)

Disjunction is another common logical connective, corresponding to the English word "or". However, the word "or" can have two different meanings in English: inclusive or exclusive. In mathematical logic, "or" is almost always used in the inclusive sense unless explicitly stated otherwise.

Definition of Disjunction (Inclusive OR)

Let $p$ and $q$ be two simple statements. The disjunction of $p$ and $q$ is the compound statement formed by connecting $p$ and $q$ with the word "or".

• Symbol: The symbol for disjunction is $\lor$.
• Notation: The disjunction of $p$ and $q$ is written as $p \lor q$.
• Read as: "$p$ or $q$".

In the standard (inclusive) sense, the disjunction $p \lor q$ is considered True if $p$ is true, or if $q$ is true, or if both $p$ and $q$ are true. The disjunction $p \lor q$ is False only when both $p$ is false and $q$ is false.

Think of a common example: "You will pass the exam if you study hard or you are lucky." The promise holds true if you study hard, or if you are lucky, or if you are both studied hard and lucky. The promise is broken only if you neither study hard nor are lucky.

Truth Table for Disjunction ($\lor$, Inclusive OR)

The truth table for inclusive disjunction shows the truth value of $p \lor q$ for all 4 possible combinations of truth values for $p$ and $q$:

This table shows that $p \lor q$ is True in three out of four cases. It is False only in the last row where both $p$ and $q$ are False.

Answer:

Exclusive OR (XOR)

Sometimes in everyday language, "or" is used to mean "one or the other, but not both". This is called the exclusive OR. For example, "You can have tea or coffee" usually implies you choose only one.

The statement "$p$ exclusive or $q$" is true if exactly one of $p$ or $q$ is true. It is false if $p$ and $q$ are both true or both false.

Symbol: Exclusive OR is often denoted by $\oplus$ or sometimes XOR.

Truth Table for Exclusive OR ($\oplus$):

Notice the difference in the first row compared to the inclusive OR truth table. In inclusive OR, T $\lor$ T is T; in exclusive OR, T $\oplus$ T is F.

Note: Unless a problem explicitly mentions "exclusive or" or uses the symbol $\oplus$, always interpret "or" ($\lor$) in the inclusive sense in mathematical logic.

Answer:

Competitive Exam Pointer: Disjunction (Inclusive vs. Exclusive)

Truth Table for Negation ($\neg$)

Negation is the simplest logical operation as it applies to a single statement. As previously defined, the negation of a statement $p$ is a new statement that asserts the opposite of $p$. The truth value of the negation is always the reverse of the truth value of the original statement.

Understanding the Negation Operator

The negation operator takes one statement as input and produces another statement as output. Its effect on the truth value is direct and absolute:

• If the input statement $p$ is True, the output statement $\sim p$ (or $\neg p$) is False.
• If the input statement $p$ is False, the output statement $\sim p$ (or $\neg p$) is True.

This behavior is precisely captured by its truth table.

Truth Table for Negation ($\sim$ or $\neg$)

The truth table for negation systematically lists all possible truth values for the input statement $p$ and shows the corresponding truth value for the negated statement $\sim p$. Since there is only one input statement $p$, which can be either True (T) or False (F), the truth table has only two rows (excluding the header row).

This truth table is the fundamental definition of logical negation. It shows that the truth value of $\sim p$ is False when $p$ is True, and True when $p$ is False.

Negation is a unary operator because it operates on a single operand (one statement). Other connectives like "and" ($\land$) and "or" ($\lor$) are binary operators because they operate on two operands (two statements).

Competitive Exam Pointer: Truth Table for Negation

Constructing Truth Tables for Simple Compound Statements

Truth tables are indispensable tools in propositional logic. They provide a systematic way to determine the truth value of any compound statement for every possible combination of truth values of its simple component statements. Constructing truth tables allows us to analyze the logical structure of statements and understand their behavior under different conditions.

Steps for Constructing a Truth Table

Follow these steps to construct a truth table for any compound statement:

1. Identify All Simple Statements: List all the distinct simple propositional variables (usually denoted by $p, q, r, ...$) that appear in the compound statement.
2. Determine the Number of Rows: If there are $n$ distinct simple statements, then there are $2^n$ possible combinations of their truth values (since each statement can be either True or False). The truth table will require $2^n$ rows, in addition to the header row. For example:
   • 1 simple statement ($p$): $2^1 = 2$ rows.
   • 2 simple statements ($p, q$): $2^2 = 4$ rows.
   • 3 simple statements ($p, q, r$): $2^3 = 8$ rows.
3. Set Up Columns for Simple Statements: Create the first $n$ columns for each of the simple statements identified in step 1. Fill these columns with all $2^n$ possible combinations of Truth (T) and False (F). A standard way to do this is to make the rightmost column alternate T, F, T, F, ...; the column to its left alternate TT, FF, TT, FF, ...; the next column alternate TTTT, FFFF, ...; and so on, until the leftmost simple statement column has $2^{n-1}$ T's followed by $2^{n-1}$ F's.

Example for 2 variables ($p, q$):

$p$	$q$
T	T
T	F
F	T
F	F

Example for 3 variables ($p, q, r$):

$p$	$q$	$r$
T	T	T
T	T	F
T	F	T
T	F	F
F	T	T
F	T	F
F	F	T
F	F	F

4. Add Columns for Sub-expressions: If the compound statement contains parenthetical expressions or negations of simple statements, create separate columns for these intermediate logical steps. This helps in breaking down the calculation. Calculate the truth values for these columns row by row, using the truth values from the simple statement columns and the definitions of the connectives/operators involved ($\sim, \land, \lor$, etc.).
5. Add the Final Column: Create the last column for the entire compound statement. Using the truth values from the simple statement columns and any necessary intermediate columns, calculate the truth value of the final statement for each row based on the definition of the main logical connective.

Let's apply these steps to construct truth tables for some simple compound statements.

Answer:

Answer:

Constructing truth tables might seem tedious for simple statements, but it is a systematic and foolproof method that can be extended to compound statements of any complexity. It is the basis for verifying logical equivalences and checking the validity of arguments.

Competitive Exam Pointer: Truth Table Construction