Created by Turbolearn AI

Propositional Logic: The Basics

Let's dive into propositional logic, its applications, and why it's relevant to us. Here’s what
we'll cover:

Propositional logic
Negation
Compound propositions (conjunctions, disjunctions)
Conditionals and biconditionals
Truth tables
Notation
Logical equivalence
Circuit reduction

The goal is to learn how to construct correct mathematical arguments. We'll convert English
sentences into equations, run them through a proof process, and determine if something is
correct or incorrect.

Uses for Propositional Logic

Designing circuits: Discovered long after propositional logic's inception.
Creating programs: Ensuring programs function as intended. Validating
programs: Verifying the correctness of programs.

What is a Proposition?
A proposition is a statement that can be either true or false.

Let's consider some examples:

St. George is the capital of Utah.

7-3=9I
have 12
puppies.
Pigeons are reptiles.
4 + 6 = 10

All of the above are propositions.

A proposition is a statement that can be proven true or false.

Page 1
 Created by Turbolearn AI

Based on the statements above, let's identify their truth values:

St. George is the capital of Utah: False

7 - 3 = 9: False
I have 12 puppies: False (Assuming the speaker does not have 12 puppies)
Pigeons are reptiles: False
4 + 6 = 10: True

More Examples
Consider these statements:

How many kids do you have?

Eat an apple every day.
x+5
=8y
-x=
z
Let a = 12. a + 5 = 19

Which of the above are propositions?

"How many kids do you have?" is not a proposition because it's a question, not a
declarative statement.
"Eat an apple every day" is not a proposition because there is nothing to prove. "x
+ 5 = 8" and "y - x = z" are technically not propositions because the values of the
variables are unknown.
"a + 5 = 19" is a proposition because it can be proven false.

The truth value of "a + 5 = 19" is False.

Notation
Propositional calculus, which has been around since Aristotle's time, involves using symbols to
represent statements.

In algebra, we use variables like x, y, and z to represent numbers. Similarly, in propositional

logic, we use p, q, r, s, and so forth to represent propositions.

Page 2
 Created by Turbolearn AI

True or false values are typically represented as T or F. However, in the context of computers,
binary, and circuits, we often use 1 and 0.

Negation
Negation means the opposite of a statement.

For example, if p is the statement "St. George is the capital of Utah," then "not p" (¬p) means
"St. George is not the capital of Utah."

The negation symbol can be represented as a sideways L (¬) or a line over the variable.

Propositional Logic

Propositional Variables
We can assign a proposition, a statement that can be either true or false, to a variable. For
example:

P = "St. George is the capital of Utah."

Then using P is the same as saying "St. George is the capital of Utah."

Negation
If P is a proposition, then "not P" is its negation. If P is true, then "not P" is false, and vice
versa. The symbol for negation is ∼, although a tilde (~) is often used since the negation
symbol is not a standard keyboard character.

Instead of saying "not" we can say

It is not the case that P.

Compound Propositions
A compound proposition is the creation of a new proposition based on old ones.

Page 3
 Created by Turbolearn AI

Boolean Logic
George Boole
In the 1800s, George Boole wrote "The Laws of Thought" and realized that propositional
calculus could be applied to binary logic.

Conjunction (AND)
The conjunction of two propositions P and Q is denoted as P ∧ Q, which means "P and Q."
Both P and Q must be true for P ∧ Q to be true.

Example:

P = "Alex has three dogs."

Q = "Alex has two cats."

P ∧ Q = "Alex has three dogs and Alex has two cats."

Disjunction (OR)
The disjunction of two propositions P and Q is denoted as P ∨ Q, which means "P or Q." In
the context of Aristotle's logic and programming, this "or" is inclusive, meaning that P, Q, or
both can be true for P ∨ Q to be true.

Example:

P = "Alex has three dogs."

Q = "Alex has two cats."

P ∨ Q = "Alex has three dogs or Alex has two cats."

Programming Implications
In programming, "and" is often represented by && and "or" by ||.

Page 4
 Created by Turbolearn AI

if (x == 9 || y == 7) {
// Code to execute if x is 9 or y is 7 or both
}

if (P && Q) {
//Both P and Q must be true
}

Truth Table
P Q P ∧Q P ∨Q

True True True True

True False False True
False True False True
False False False False

Logic Gates & Truth Tables

Exclusive OR (XOR)
The exclusive OR, often represented by a circled plus sign (⊕) or the acronym XOR in some
programming languages, is a logical operator that yields true if and only if one of the
operands is true, and the other is false.

Exclusive OR: Alex either has three dogs or Alex has two cats, implying one or the
other, but not both.

In everyday language, "or" often implies exclusive or. However, in formal logic, we usually
mean the inclusive "or," where both can be true. We will hardly use exclusive OR in this class.

Boolean Algebra
Boolean algebra allows representing logical statements mathematically.
P and Q can be written as:
P×Q
P⋅Q
PQ (placing them next to each other)

Page 5
 Created by Turbolearn AI

Truth Tables
Truth tables are a straightforward method to determine if a statement is true or
false.

Truth Table Example

Let's consider two variables:

P: Alex has three

dogs. Q: Alex has two
cats.

The possible combinations of truth values for P and Q are:

P Q not P not Q P and Q P or Q P XOR Q

true true false false true true false

true false false true false true true
false true true false false true true
false false true true false false false

Explanation:

not P: The negation of P (opposite of P).

not Q: The negation of Q (opposite of Q).
P and Q: Both P and Q must be true for the expression to be true.
P or Q: At least one of P or Q must be true for the expression to be true.
P XOR Q: Exactly one of P or Q must be true for the expression to be true.

Conditional Statements
Conditional statements can be tricky but are essential.
A conditional statement has the basic idea: Let P be the statement "I won the
lottery." Let Q be the statement "I will give you a dollar." "Let P therefore Q" is how
you say it. One way to say it is "If I won the lottery, I will give you a dollar."

Ways to Express Conditionals

Several ways to express "if P then Q":

Page 6
 Created by Turbolearn AI

If P, then Q
P implies Q
If P, Q
P only if Q
P is sufficient for Q
Q if P
Q whenever P

Let's hold off on formally defining the last few until we examine the truth table to clarify
them.

Truth Table for Conditional Statements

Consider the statement "If I win the lottery (P), then I will give you a dollar (Q)."

P Q P therefore Q

true true true

true false false
false true true
false false true

Explanation:
Row 1 (True, True): If I win and give you a dollar, the statement is true.
Row 2 (True, False): If I win but don't give you a dollar, I lied, so the statement is
false.
Row 3 (False, True): If I didn't win but still give you a dollar, the statement is
considered true, because the condition of winning (P) was never met.
Row 4 (False, False): If I didn't win and didn't give you a dollar, the statement is
true because I didn't violate the condition.

Conditionals Deep Dive

Truth Values of Conditionals

Let's dissect conditional statements, particularly those that might seem counterintuitive at
first glance.

Consider the claim: "If I win the lottery, I'll give you a dollar."

Page 7
 Created by Turbolearn AI

If I give you a dollar and then win the lottery 10 years later, the statement holds
true.
If I give you a dollar and never win the lottery, the statement can't be proven false
because the condition of winning the lottery was never met.

The key takeaway is this: a conditional statement $P \implies Q$ is only challenged when P is
true. If P is false, the statement stands, regardless of the truth value of Q.

Conjectures vs. Theorems

Many of our mathematical understandings start as conjectures, which are essentially
educated guesses based on observation or experimentation.

Conjecture: A statement believed to be true but not yet proven.

If a conjecture is proven true through a mathematical process, it earns the title of a theorem.
Think of the Pythagorean theorem as a prime example. Theorems come with proofs,
solidifying their truth.

The process of proving something often starts with the assumption that P is true to show that
if P occurs, then Q will occur.
P only if Q
When we say "P only if Q," we're saying that for the entire statement to be true, P being true
necessitates that Q is also true. In other words, $P \implies Q$ must hold.

Here's what $P$ only if $Q$ is saying: P must be true only if Q is true.

Various Ways to Express $P \implies Q$

There are multiple ways to phrase $P \implies Q$:

P is sufficient for Q.
A sufficient condition for Q is P.
Q if P.
Q whenever P.
Q when P.

Page 8
 Created by Turbolearn AI

Q follows from P. Q
unless not P.

Necessary Conditions
Q is necessary for P: Q being true is necessary for P to be true.
A necessary condition for P is Q: For P to be true, Q must be true.

To solidify these concepts, try creating your own propositions for P and Q and then rephrase
them using the expressions above.

Vacuous Truths
In the realm of proofs, there exists the concept of vacuous truth. A statement is vacuously
true if it doesn't really say anything because its condition is never met.

Imagine someone claiming, "Every research paper I've ever published was featured in a
distinguished scientific journal." If they've never published a paper, the statement is vacuously
true because there are no papers to disprove the claim.

Propositional Logic Table

Statement Meaning

P⟹ Q If P, thenQ. Only challenged when

P is true, but
Q is false.
P only ifQ For $P \implies P must be true only
to be true,
Q$ Q isiftrue.
P is sufficient for
If P is true, then
Q is true.
Q
Q is necessary
If P is true,Q must be true.
forP
A statement that is true because the condition for it to be false can't
Vacuously True
be met (e.g., claiming all published papers are in a journal when no
Statement
papers have been published).

In scenarios where the condition P is always false, the statement "P therefore Q" is considered
vacuously true. This is because the left side of the implication is never satisfied.

Page 9
 Created by Turbolearn AI

Logical Equivalences
Logical equivalences are useful in proofs. Two statements are logically equivalent if, for any
given truth values of their variables, they always evaluate to the same truth value.

Logical equivalence means that for any specific truth value combinations of P and
Q, whatever one statement evaluates to, the other will also evaluate to.

For example:

P therefore Q is logically equivalent to not Q therefore not P.

Let's prove this with a truth table:

P Q P ⇒Q ¬Q ¬P ¬Q ⇒¬P

False False True True True True

False True True False True True
True False False True False False
True True True False False True
As you can see, the columns for P ⇒ Q and ¬Q ⇒ ¬P match exactly, showing they are logically
equivalent.

The Contrapositive
The logical equivalence between P ⇒ Q and ¬Q ⇒ ¬P is called the contrapositive.

The contrapositive of a conditional statement is formed by both reversing and

negating the original statement.

Like in algebra, where you can perform the same operation on both sides of an equation
without changing its validity, in logic, you can swap a statement for its contrapositive in a
proof without changing its validity.

Converse and Inverse

The converse of P ⇒ Q is Q ⇒ P.
The inverse of P ⇒ Q is ¬P ⇒ ¬Q.

Page 10
 Created by Turbolearn AI

The converse and inverse are logically equivalent to each other, but they are NOT logically
equivalent to the original statement or its contrapositive.

In summary:

Statement Logical Form

Original P ⇒ Q

Contrapositive ¬Q ⇒ ¬P

Converse Q ⇒ P

Inverse ¬P ⇒ ¬Q

Biconditional Statements
A biconditional statement (denoted P ⇔ Q) is pronounced "P if and only if Q." It is true only if
both P ⇒ Q and Q ⇒ P are true.

A biconditional statement is true only when both the conditional statement and
its converse are true.

Truth Table:

P Q P ⇔Q

False False True

False True False
True False False
True True True

A biconditional statement is essentially an "and" statement of the conditional and converse.

Example: "You can drive my car if and only if you have a driver's license." This means:

If you can drive my car, then you must have a license.

If you have a license, then you can drive my car.

Determining Truth Values for Formulas

To determine all possible truth values for a complex formula, construct a truth table that
includes all the necessary components.

For example, to determine the truth values of P ∧ (Q ⇔ R), you would need columns for P, Q,
R, Q ⇔ R, and finally P ∧ (Q ⇔ R).

Page 11
 Created by Turbolearn AI

Truth Tables and Logical Operations

When evaluating logical statements, we need to determine if each part is true or false. This
often involves breaking down the statement into its components and evaluating each one.

Building Truth Tables

1. Identify all variables: List all unique variables that make up your statement.
2. List all combinations: Create columns for each variable and list all possible true/false
combinations.
3. Evaluate negations: Create a column for each negation (like 'not Q') and fill it based on
the original variable.
4. Evaluate compound statements: Evaluate 'or', 'and', etc., using the truth values of the
components.
5. Determine the final result: The last column shows the truth value of the entire
statement for each combination.
Order of Operations
Just like in math, logical operations have an order:

1. Negations
2. Conjunctions and Disjunctions
3. Conditionals and Biconditionals

However, it's best practice to use parentheses to clarify the order, so you don't have to
remember the order of operations!

Conditional Example
Let's walk through creating a truth table for $P \implies Q$:

P Q ¬Q P ∨¬Q P ∧Q (P ∨¬Q) → (P ∧Q)

True True False True True True

True False True True False False
False True False False False True
False False True True False False

Page 12
 Created by Turbolearn AI

Remember that a conditional statement is only false when a true statement implies a false
conclusion. Also remember that a conditional statement that has a false premise is "vacuously
true".

Conditional statement: A statement that is vacuously true when its premise is

false.

Page 13