Truth Tables and Logical Connectives

Introduction

Welcome to the first lesson in our new module, "Logic and Computational Thinking." In the previous module, you built a strong practical foundation in Python, learning to manipulate data with pandas and create insightful visualizations with Matplotlib. You now have the tools to work with data effectively.

Your goal is to build transformative AI, much like Tony Stark builds his technology. This requires more than just coding; it requires understanding the fundamental principles that make computation possible. At its core, a computer, and by extension any AI system, operates on a simple binary principle: true or false, on or off, 1 or 0. Formal logic is the language we use to reason about these states with absolute precision.

In this lesson, you will achieve the learning outcome: Identify propositions and construct truth tables for logical connectives (AND, OR, NOT, IF-THEN). We will start with the most basic atom of logic—the proposition—and learn how to combine propositions into more complex statements whose truth we can systematically evaluate. This is the first step toward building the rigorous mental framework needed to design and understand complex algorithms and AI systems.

1. What is a Proposition?

Before we can reason logically, we need to define the basic statements we're reasoning about. In logic, these are called propositions.

A proposition is a declarative sentence that has a single, unambiguous truth value: it is either true or false, but not both.

Let's read a formal definition and see some examples.

1.1. Propositional Logic — Discrete Structures for Computing

This resource provides a clear definition of a proposition with excellent examples of what is, and what is not, a proposition.

Read the first part of the page, from the beginning down to the heading "Constructing Propositions". Pay close attention to the examples of propositions and the examples of statements that are not propositions.

To summarize the key points:

Propositions:
- "The Earth is the third planet from the sun." (True)
- " $1 + 1 = 3$ ." (False)
- "It is raining outside right now." (Either true or false, depending on the current weather)
Not Propositions:
- "What is your name?" (This is a question, not a statement with a truth value.)
- "Go to your room." (This is a command.)
- " $x + 5 = 10$ ." (This is a statement whose truth depends on the variable $x$ . It is not a proposition on its own.)

In logic, we use lowercase letters like $p$ , $q$ , and $r$ to represent propositions. For example, we could define:

$p$ : "The server is online."
$q$ : "The database is connected."

2. Combining Propositions: Logical Connectives

The real power of logic comes from combining simple propositions into more complex ones. We do this using logical connectives (also called logical operators). For this lesson, we will focus on the four most important ones: NOT, AND, OR, and IF-THEN.

A truth table is a tool that shows us the truth value of a complex proposition for every possible combination of truth values of its simple components.

The following video provides an excellent introduction to these connectives and how their truth tables are constructed.

An Introduction to Propositional Logic

This animated video from Spanning Tree clearly explains the core logical connectives and introduces the concept of a truth table to visualize their behavior.

Please watch the video in two parts: Watch from 00:36 to 04:12. This section covers propositions, NOT, AND, and OR, and introduces truth tables. Then, skip ahead and watch from 04:37 to 07:11. This part covers the very important but sometimes tricky IF-THEN connective. Don't worry about 'Exclusive OR' or 'Biconditional' for now; we'll focus on the main four.

3. A Closer Look at Each Connective

Let's formalize what you just saw in the video. We will use the symbols $p$ and $q$ as our propositions. We'll denote True as T and False as F.

a) Negation (NOT)

Negation simply flips the truth value of a proposition.

Symbol: $\neg$ (you may also see $\sim$ or ! in programming)
Reads as: "not $p$ "
Example: If $p$ is "It is sunny," then $\neg p$ is "It is not sunny."

Truth Table for Negation:

$p$	$\neg p$
T	F
F	T

b) Conjunction (AND)

Conjunction is true only when both propositions are true. This is analogous to the and operator in programming.

Symbol: $\land$ (you may also see & or &&)
Reads as: " $p$ and $q$ "
Example: If $p$ is "The file is open" and $q$ is "The file is writable," then $p \land q$ is "The file is open and the file is writable."

Truth Table for Conjunction:

$p$	$q$	$p \land q$
T	T	T
T	F	F
F	T	F
F	F	F

c) Disjunction (OR)

Disjunction is true if at least one of the propositions is true. This is an inclusive OR, meaning it's also true if both are true. This is the standard or in most programming languages.

Symbol: $\lor$ (you may also see | or ||)
Reads as: " $p$ or $q$ "
Example: "To get a discount, you are a student or you are a senior citizen." You still get the discount if you happen to be both.

Truth Table for Disjunction:

$p$	$q$	$p \lor q$
T	T	T
T	F	T
F	T	T
F	F	F

d) Implication (IF... THEN...)

Implication, or the conditional statement, is often the most confusing for newcomers. It represents a contract or a promise. The statement $p \to q$ is only false when the first part ( $p$ ), called the antecedent or hypothesis, is true, and the second part ( $q$ ), the consequent or conclusion, is false. In all other cases, the promise is not broken.

Symbol: $\to$ (you may also see $\Rightarrow$ )
Reads as: "if $p$ , then $q$ " or " $p$ implies $q$ "
Example: Let's use the statement from the video: "If it is my birthday, then I will eat cake."
- T $\to$ T: It's my birthday and I eat cake. (Promise kept)
- T $\to$ F: It's my birthday and I don't eat cake. (Promise broken - this is the only false case!)
- F $\to$ T: It's not my birthday, but I eat cake anyway. (Promise not broken. The promise only applies if it's my birthday.)
- F $\to$ F: It's not my birthday and I don't eat cake. (Promise not broken.)

Cases where the antecedent ( $p$ ) is false are called vacuously true. The implication is true because the condition didn't apply in the first place.

Truth Table for Implication:

$p$	$q$	$p \to q$
T	T	T
T	F	F
F	T	T
F	F	T

This image provides a great summary of the truth tables for all the standard connectives.

Comprehensive Truth Table for Logical Connectives — A compact reference showing the truth tables for negation (~p), conjunction (p & q), disjunction (p or q), exclusive or, implication (p -> q), and biconditional (p <-> q).

4. Constructing Larger Truth Tables

The real utility of truth tables is in analyzing more complex propositions. The process is systematic.

Identify atomic propositions: Find all the simple propositions ( $p, q, r, \dots$ ).
Determine the number of rows: If there are $n$ atomic propositions, you will need $2^{n}$ rows to cover all possible truth combinations.
Create columns: Make a column for each atomic proposition, then for each intermediate sub-expression, and finally for the entire expression.
Fill the table: Fill in the truth values for the atomic propositions. Then, use the basic truth table rules to fill in the columns for the sub-expressions, working from the inside out.

Let's look at an example for the expression $p \lor q \to \neg r$ . Since there are three variables ( $p, q, r$ ), we need $2^{3} = 8$ rows.

Example Truth Table for p ∨ q → ¬r — This truth table breaks down the evaluation of $p \lor q \rightarrow \neg r$. It first evaluates the sub-expressions $p \lor q$ and $\neg r$, and then uses those results to evaluate the final implication.

5. Practice Exercise

Now, let's put this theory into practice. Please solve the following problems.

Task (15 minutes):

Identify Propositions: Which of the following sentences are propositions?
a) "The moon is made of green cheese."
b) "He is a student."
c) "Are you logged in?"
d) " $2 \times 3 = 6$ ."
e) "This statement is false." (This is a tricky one! Think about it.)
Evaluate Truth Values: Let $p$ be the proposition "It is cold" and let $q$ be "It is raining." Suppose $p$ is True and $q$ is False. What are the truth values of the following?
a) $p \land q$
b) $p \lor q$
c) $\neg p \to q$
Construct a Truth Table: Construct the complete truth table for the compound proposition: $(p \land \neg q) \to p$

Click to see the solutions

Identify Propositions:
- a) Proposition. It is a declarative statement that is definitively false.
- b) Not a proposition. The truth value depends on who "he" is. It's not self-contained.
- c) Not a proposition. It's a question.
- d) Proposition. It is a declarative statement that is true.
- e) Not a proposition. This is a paradox (a liar's paradox). If it's true, then it must be false. If it's false, then it must be true. It does not have a single, non-contradictory truth value.
Evaluate Truth Values (Given $p = T$ , $q = F$ ):
- a) $p \land q$ $\equiv T \land F \equiv$ False.
- b) $p \lor q$ $\equiv T \lor F \equiv$ True.
- c) $\neg p \to q$ $\equiv \neg T \to F \equiv F \to F \equiv$ True.
Construct a Truth Table for $(p \land \neg q) \to p$ :

$p$ $q$ $\neg q$ $p \land \neg q$ $(p \land \neg q) \to p$

T T F F T

T F T T T

F T F F T

F F T F T

Notice something interesting? The final column is always true, regardless of the inputs for $p$ and $q$ . This type of statement is called a tautology, a concept we will explore later in this module.

$p$	$q$	$\neg q$	$p \land \neg q$	$(p \land \neg q) \to p$
T	T	F	F	T
T	F	T	T	T
F	T	F	F	T
F	F	T	F	T

Conclusion

In this lesson, you took your first step into the world of formal logic. You learned how to define and identify the fundamental building blocks of logical statements and how to combine them in precise ways.

Key Takeaways:

A proposition is a statement that is either true or false.
We use logical connectives like NOT ( $\neg$ ), AND ( $\land$ ), OR ( $\lor$ ), and IF-THEN ( $\to$ ) to build complex propositions.
A truth table is a powerful tool to systematically evaluate the truth value of any compound proposition for all possible scenarios.
The implication $p \to q$ is only false when a true premise leads to a false conclusion.

You have started building the mental toolset to think with the same precision as a computer. This foundation is not just an academic exercise; it's the basis for everything from designing database queries and writing bug-free code to understanding how the most advanced AI models make decisions.

Preview of the Next Lesson:
Now that you understand the symbols and rules of propositional logic, the next step is to apply them. In the next lesson, we will focus on the learning outcome: "Translate natural language statements into propositional logic." You will learn how to take ambiguous English sentences and convert them into the clear, unambiguous language of logic that you learned today.

Recommended resources