The Central Idea
A proposition is a declarative statement that has a definite truth value: it is either true or false.
For example,
7 is prime
is a proposition, and its truth value is true.
By contrast,
Close the door.
is not a proposition because it is a command rather than a statement that can be classified as true or false.
Propositional logic begins with this simple distinction and then asks: how do truth values behave when propositions are combined?
Why Logic Uses Symbols
Everyday statements can be long, detailed, and tied to a particular subject. Logic replaces complete propositions with symbols such as
\[ p,\qquad q,\qquad r. \]Suppose
\(p\): The server is online.
\(q\): The database is reachable.
The compound statement
The server is online and the database is reachable
can then be written
\[ p\land q. \]Symbolic notation makes the logical structure visible without changing the meaning of the underlying statements.
Propositions Have Truth Values
Every proposition has one of two truth values:
\[ \boxed{\text{True}}\qquad\text{or}\qquad\boxed{\text{False}}. \]These values are often abbreviated
\[ T\qquad\text{and}\qquad F. \]In digital settings, the same two-state structure is often represented by
\[ 1\qquad\text{and}\qquad 0, \]although the interpretation depends on context.
Examples of Propositions
Each of the following is a proposition:
- \(2+3=5\);
- \(10<4\);
- Paris is in France;
- the file contains exactly 100 lines;
- every square is a rectangle.
Some are true and some are false, but each has a definite truth value.
Statements That Are Not Propositions
Not every sentence qualifies as a proposition.
Commands such as
Turn off the light.
are not propositions.
Questions such as
Is the light on?
are also not propositions.
Exclamations such as
What a remarkable result!
do not ordinarily express truth-valued statements either.
Open Sentences Are Not Yet Propositions
Consider
\[ x+2=7. \]Without a specified value or condition for \(x\), this sentence does not yet have a single truth value.
If \(x=5\), it is true.
If \(x=1\), it is false.
A statement containing an unspecified variable is often called an open sentence or predicate statement.
It becomes a proposition once the variable is assigned or quantified in a way that gives the statement a definite truth value.
Atomic and Compound Propositions
A proposition treated as a single logical unit is called an atomic proposition.
For example,
\(p\): The machine is powered.
\(q\): The safety switch is engaged.
A compound proposition is built from one or more propositions using logical connectives.
Examples include
\[ \neg p,\qquad p\land q,\qquad p\lor q,\qquad p\to q,\qquad p\leftrightarrow q. \]The Five Core Connectives
Introductory propositional logic commonly uses five central operations:
- negation: \(\neg p\);
- conjunction: \(p\land q\);
- disjunction: \(p\lor q\);
- implication: \(p\to q\);
- biconditional: \(p\leftrightarrow q\).
Each connective combines or modifies truth-valued statements according to a specific rule.
Negation
The negation of \(p\) is written
\[ \neg p. \]It is read as
not \(p\)
and reverses the truth value of \(p\).
If
\(p\): 11 is prime,
then
\(\neg p\): 11 is not prime.
Since \(p\) is true, \(\neg p\) is false.
Negation Is Not Ordinary Subtraction
The symbol
\[ \neg \]is a logical operator. It does not mean numerical subtraction.
Likewise, the statement
\[ \neg p \]means that \(p\) is false, not that some quantity has become negative.
Conjunction
The conjunction of \(p\) and \(q\) is written
\[ p\land q. \]It is read
\(p\) and \(q\).
A conjunction is true only when both component propositions are true.
If
\(p\): The account is active.
\(q\): The password is correct.
then
\[ p\land q \]means that both conditions hold.
Disjunction
The disjunction of \(p\) and \(q\) is written
\[ p\lor q. \]It is read
\(p\) or \(q\).
In standard propositional logic, \(\lor\) is usually inclusive or.
This means
\[ p\lor q \]is true when \(p\) is true, when \(q\) is true, or when both are true.
Inclusive Or and Exclusive Or
Everyday language sometimes uses or exclusively.
For example,
You may choose soup or salad.
may imply that only one choice is allowed.
Standard logical disjunction,
\[ p\lor q, \]includes the possibility that both \(p\) and \(q\) are true.
When exactly one must be true, the operation is called exclusive or, often abbreviated XOR.
Implication
The implication
\[ p\to q \]is read
if \(p\), then \(q\).
The proposition \(p\) is called the antecedent or hypothesis.
The proposition \(q\) is called the consequent or conclusion.
How an Implication Can Fail
The statement
\[ p\to q \]makes a commitment: whenever \(p\) holds, \(q\) must also hold.
Therefore, the implication is false precisely in the situation where
\[ p\text{ is true} \]but
\[ q\text{ is false}. \]The next lesson will organize this rule systematically with truth tables.
An Implication Does Not Assert Its Antecedent
Suppose
\[ p\to q. \]This does not by itself claim that \(p\) is true.
It states what must follow if \(p\) is true.
This distinction is important because conditional statements describe relationships between truth values rather than simply listing facts.
Biconditional
The biconditional
\[ p\leftrightarrow q \]is read
\(p\) if and only if \(q\).
It asserts both
\[ p\to q \]and
\[ q\to p. \]A biconditional therefore expresses a two-way logical relationship.
The Phrase “If and Only If”
The phrase if and only if is often abbreviated iff.
Thus,
\(p\) iff \(q\)
means exactly
\[ p\leftrightarrow q. \]In mathematical definitions, biconditional language is especially important because it states that each condition is both necessary and sufficient for the other.
Necessary and Sufficient Conditions
In
\[ p\to q, \]\(p\) is a sufficient condition for \(q\): having \(p\) is enough to guarantee \(q\).
The proposition \(q\) is a necessary condition for \(p\): \(p\) cannot hold without \(q\).
Therefore,
\(p\) only if \(q\)
translates to
\[ p\to q. \]“If” and “Only If” Must Be Distinguished
The phrase
\(p\) if \(q\)
means
\[ q\to p. \]By contrast,
\(p\) only if \(q\)
means
\[ p\to q. \]Reversing these directions changes the logical statement.
Example: Necessary and Sufficient Language
Let
\(p\): An integer is divisible by \(4\).
\(q\): The integer is even.
Then
\[ p\to q \]is true.
Divisibility by \(4\) is sufficient for evenness, while evenness is necessary for divisibility by \(4\).
But
\[ q\to p \]is false because an even integer such as \(6\) need not be divisible by \(4\).
Translating Natural Language into Symbols
Suppose
\(p\): The package arrived.
\(q\): The customer was notified.
Then:
- The package did not arrive becomes \(\neg p\).
- The package arrived and the customer was notified becomes \(p\land q\).
- The package arrived or the customer was notified becomes \(p\lor q\).
- If the package arrived, then the customer was notified becomes \(p\to q\).
- The package arrived if and only if the customer was notified becomes \(p\leftrightarrow q\).
Logical Form Can Be Shared Across Subjects
Consider the statements
If a number is divisible by 8, then it is even.
and
If the sensor is triggered, then the alarm activates.
Their subject matter is different, but both have the form
\[ p\to q. \]Logic studies this shared form independently of the particular content.
Parentheses Show Logical Grouping
Parentheses determine which operations apply to which propositions.
Compare
\[ \neg(p\land q) \]with
\[ (\neg p)\land q. \]The first negates the entire conjunction.
The second negates only \(p\).
These are different compound propositions.
Scope of a Connective
The scope of a logical connective is the part of the expression governed by that connective.
In
\[ \neg(p\lor q), \]the negation has scope over the entire expression \(p\lor q\).
In
\[ (\neg p)\lor q, \]the negation applies only to \(p\).
Main Connective
A compound proposition usually has one connective that operates at the outermost level. This is called its main connective.
In
\[ (p\land q)\to r, \]the main connective is the implication
\[ \to. \]The conjunction \(p\land q\) forms the antecedent of that implication.
Parsing a Compound Proposition
Consider
\[ \neg p\lor(q\land r). \]The structure can be read in layers:
- form \(\neg p\);
- form \(q\land r\);
- combine those results with \(\lor\).
Reading compound propositions by structure prevents ambiguity.
Precedence Conventions
Logical notation often uses conventional precedence rules to reduce parentheses.
A common ordering is:
- \(\neg\);
- \(\land\);
- \(\lor\);
- \(\to\);
- \(\leftrightarrow\).
Under this convention,
\[ \neg p\land q \]means
\[ (\neg p)\land q. \]When any doubt exists, parentheses are preferable.
Evaluating a Compound Proposition
Once the truth values of the atomic propositions are known, the truth value of a compound proposition can be determined from its connectives.
Suppose
\[ p=T,\qquad q=F. \]Then
\[ \neg p=F, \] \[ p\land q=F, \]and
\[ p\lor q=T. \]More complicated propositions are evaluated from the inside outward.
Example: Evaluate by Structure
Suppose
\[ p=T,\qquad q=F,\qquad r=T. \]Evaluate
\[ (p\land\neg q)\to r. \]First,
\[ \neg q=T. \]Then,
\[ p\land\neg q=T\land T=T. \]Finally,
\[ T\to T=T. \]Therefore,
\[ \boxed{(p\land\neg q)\to r=T}. \]Example: A False Implication
Let
\[ p=T,\qquad q=F. \]Then
\[ p\to q \]is false.
This is the unique truth-value pattern that makes an implication false: its antecedent is true while its consequent is false.
Converse, Inverse, and Contrapositive
Starting with
\[ p\to q, \]three related statements can be formed.
The converse is
\[ q\to p. \]The inverse is
\[ \neg p\to\neg q. \]The contrapositive is
\[ \neg q\to\neg p. \]These related forms must not be treated as interchangeable merely because they use the same component propositions.
Implication and Contrapositive
A conditional statement and its contrapositive always have the same truth behavior.
Thus,
\[ p\to q \]and
\[ \neg q\to\neg p \]are logically equivalent.
This relationship will become especially transparent when truth tables and logical equivalence are studied systematically.
Converse and Inverse
The converse
\[ q\to p \]and inverse
\[ \neg p\to\neg q \]share the same truth behavior with each other.
However, neither is generally equivalent to the original implication \(p\to q\).
Example: Do Not Reverse a Conditional Automatically
Consider the true statement:
If an integer is divisible by \(6\), then it is divisible by \(3\).
The converse would be:
If an integer is divisible by \(3\), then it is divisible by \(6\).
This is false because \(9\) is divisible by \(3\) but not by \(6\).
Reversing an implication changes the logical claim.
Logic Separates Form from Factual Content
The proposition
\[ p\to q \]describes a logical form.
Whether a particular real-world instance is factually true depends on the meanings assigned to \(p\) and \(q\).
Propositional logic can analyze the structure without requiring the symbols themselves to carry subject-specific meaning.
Syntax and Semantics
Two complementary ideas appear throughout logic.
Syntax concerns how expressions are formed from symbols and rules.
Semantics concerns what those expressions mean and how truth values are assigned.
A well-formed symbolic statement is a syntactic object; determining whether it is true under a particular interpretation is a semantic question.
Well-Formed Formulas
A well-formed formula, often abbreviated WFF, is an expression constructed according to the rules of the logical language.
For example,
\[ (p\lor q)\to\neg r \]is well formed.
A string such as
\[ p\land\to q \]is not well formed because the connectives are not arranged according to the grammar of propositional logic.
Recursive Construction of Formulas
Propositional formulas can be described recursively.
- Every propositional variable such as \(p\), \(q\), or \(r\) is a formula.
- If \(A\) is a formula, then \(\neg A\) is a formula.
- If \(A\) and \(B\) are formulas, then \(A\land B\), \(A\lor B\), \(A\to B\), and \(A\leftrightarrow B\) are formulas.
This recursive viewpoint connects propositional logic to later work with formal languages, syntax trees, and automata.
Subformulas
Consider
\[ (p\land q)\to\neg r. \]Important subformulas include
\[ p,\qquad q,\qquad r,\qquad p\land q,\qquad \neg r. \]The complete formula combines these smaller formulas through its main connective.
Logical Interpretation
An interpretation or valuation assigns truth values to propositional variables.
For example,
\[ p=T,\qquad q=F,\qquad r=T \]is one possible valuation of three variables.
Once the variables are assigned truth values, every compound proposition built from them receives a truth value according to the logical connectives.
Why Several Valuations Matter
A compound proposition may behave differently under different assignments.
For example,
\[ p\land q \]is true under
\[ p=T,\qquad q=T, \]but false under
\[ p=T,\qquad q=F. \]Systematically considering all possible assignments leads directly to truth tables.
Tautologies, Contradictions, and Contingencies
Compound propositions can be classified by how they behave across all possible valuations.
A tautology is true under every valuation.
A contradiction is false under every valuation.
A contingency is true under some valuations and false under others.
These classifications will be verified systematically with truth tables.
Example of a Tautological Pattern
The expression
\[ p\lor\neg p \]says that either \(p\) is true or \(p\) is not true.
Under classical propositional logic, one of those possibilities must hold.
Therefore,
\[ p\lor\neg p \]is a tautology.
Example of a Contradictory Pattern
The expression
\[ p\land\neg p \]requires \(p\) to be both true and false simultaneously.
Under classical propositional logic, that cannot occur.
Therefore,
\[ p\land\neg p \]is a contradiction.
Logical Equivalence Is Stronger Than Matching Once
Two propositions are logically equivalent when they have the same truth value under every possible valuation of their variables.
Matching under one particular assignment is not enough.
The later lesson on logical equivalence will develop this idea in detail.
Common Error: Treating Every Sentence as a Proposition
The sentence
Please submit the report.
is not true or false.
It is a command, so it is not a proposition.
Common Error: Treating an Open Sentence as a Proposition
The expression
\[ x>5 \]does not have a definite truth value until \(x\) is specified or quantified.
It should not be treated as an ordinary proposition in isolation.
Common Error: Reading Logical Or as Always Exclusive
In standard propositional logic,
\[ p\lor q \]permits the case where both \(p\) and \(q\) are true.
If exactly one is intended, the statement must express an exclusive condition.
Common Error: Reversing “Only If”
The statement
\(p\) only if \(q\)
means
\[ \boxed{p\to q}, \]not
\[ q\to p. \]The condition following only if is necessary for the first.
Common Error: Confusing a Conditional with Its Converse
From
\[ p\to q \]we cannot automatically conclude
\[ q\to p. \]The converse is a separate statement and may have a different truth value.
Common Error: Ignoring Parentheses
The formulas
\[ \neg(p\lor q) \]and
\[ (\neg p)\lor q \]do not have the same structure.
Parentheses determine scope and must be respected.
Common Error: Evaluating in the Wrong Order
For
\[ (p\lor q)\land\neg r, \]evaluate the grouped expressions first:
- find \(p\lor q\);
- find \(\neg r\);
- combine those results with \(\land\).
Complex logical expressions should be processed layer by layer.
A Reliable Procedure for Translating Statements
- Identify the atomic propositions.
- Assign each atomic proposition a symbol.
- Locate the logical words such as not, and, or, if, and only if.
- Determine which connective is the main connective.
- Use parentheses to show grouping explicitly.
- Check that the symbolic statement preserves the direction and meaning of the original.
A Reliable Procedure for Evaluating Propositions
- Write the truth values of the atomic propositions.
- Evaluate expressions inside parentheses.
- Apply negations to their correct scope.
- Evaluate conjunctions and disjunctions.
- Evaluate implications and biconditionals.
- Record the final truth value of the compound proposition.
Example: Full Translation Workflow
Let
\(p\): The user is authenticated.
\(q\): The user has administrator privileges.
\(r\): The settings panel is accessible.
Translate:
If the user is authenticated and has administrator privileges, then the settings panel is accessible.
The antecedent contains a conjunction:
\[ p\land q. \]That conjunction implies \(r\), so the full translation is
\[ \boxed{(p\land q)\to r}. \]Example: Negated Compound Statement
Let
\(p\): The door is locked.
\(q\): The alarm is armed.
The statement
It is not the case that the door is locked and the alarm is armed
becomes
\[ \boxed{\neg(p\land q)}. \]The parentheses matter because the negation applies to the entire conjunction.
Example: “Unless”
The word unless can often be translated by rewriting the sentence into a clearer logical form.
For example,
The system will not start unless the key is present
can be understood as
If the key is not present, then the system will not start.
If
\(p\): The key is present,
\(q\): The system starts,
one valid form is
\[ \neg p\to\neg q. \]Natural-language expressions should be rewritten carefully before symbolic translation when their logical structure is not immediately transparent.
Propositional Logic in Mathematics
Mathematical reasoning constantly uses propositional structure.
Definitions frequently use biconditionals.
Theorems often take the form
\[ p\to q. \]Proof by contrapositive relies on the relationship between
\[ p\to q \]and
\[ \neg q\to\neg p. \]Logical notation therefore provides a formal language for reasoning already used throughout mathematics.
Propositional Logic in Computing
Propositional logic also appears throughout computing.
It is used in:
- conditional statements in programs;
- search filters and query conditions;
- access-control rules;
- digital circuits;
- verification systems;
- constraint solving;
- finite-state control systems.
Later lessons in this unit will connect logical expressions to Boolean algebra, circuits, finite-state machines, automata, and satisfiability.
Propositional Logic and Digital Circuits
The two-valued nature of propositions parallels the two-state behavior used in digital systems.
Logical operations such as
\[ \neg,\qquad \land,\qquad \lor \]correspond naturally to NOT, AND, and OR operations.
This relationship will be developed later when Boolean algebra and logic gates are introduced.
Propositional Logic and Constraint Systems
A collection of logical statements can describe conditions that must all be satisfied.
For example,
\[ p\lor q \]and
\[ \neg p\lor r \]can be viewed as constraints on possible truth assignments.
Determining whether some assignment satisfies all such constraints leads toward the study of satisfiability.
Practice 1: Identify Propositions
Determine which of the following are propositions:
- \(8\) is even.
- Open the window.
- Is \(12\) prime?
- \(3^2=8\).
Practice 2: Negation
Let
\(p\): The file exists.
Write the negation of \(p\) in words and symbols.
Practice 3: Conjunction and Disjunction
Let
\(p\): The battery is charged.
\(q\): The device is connected.
Translate:
- The battery is charged and the device is connected.
- The battery is charged or the device is connected.
Practice 4: Implication
Let
\(p\): An integer is divisible by \(10\).
\(q\): The integer is divisible by \(5\).
Write the statement
If an integer is divisible by \(10\), then it is divisible by \(5\)
symbolically.
Practice 5: “Only If”
Using the same \(p\) and \(q\), translate:
An integer is divisible by \(10\) only if it is divisible by \(5\).
Practice 6: Biconditional
Let
\(p\): \(n\) is even.
\(q\): \(n\) is divisible by \(2\).
Translate:
\(n\) is even if and only if \(n\) is divisible by \(2\).
Practice 7: Evaluate a Compound Proposition
Suppose
\[ p=T,\qquad q=F. \]Evaluate
\[ \neg p\lor q. \]Practice 8: Evaluate by Layers
Suppose
\[ p=T,\qquad q=F,\qquad r=T. \]Evaluate
\[ (p\lor q)\land r. \]Practice 9: Identify the Main Connective
Identify the main connective in
\[ (p\land q)\to(\neg r\lor s). \]Practice 10: Converse and Contrapositive
Starting with
\[ p\to q, \]write:
- the converse;
- the contrapositive.
Practice Answers
Practice 1
Statements 1 and 4 are propositions.
Statement 2 is a command, and statement 3 is a question.
Practice 2
In symbols,
\[ \boxed{\neg p}. \]In words:
The file does not exist.
Practice 3
\[ \boxed{p\land q} \]and
\[ \boxed{p\lor q}. \]Practice 4
\[ \boxed{p\to q}. \]Practice 5
The phrase \(p\) only if \(q\) translates to
\[ \boxed{p\to q}. \]Practice 6
\[ \boxed{p\leftrightarrow q}. \]Practice 7
Since \(p=T\),
\[ \neg p=F. \]Therefore,
\[ \neg p\lor q=F\lor F=F. \]So the answer is
\[ \boxed{F}. \]Practice 8
First,
\[ p\lor q=T\lor F=T. \]Then,
\[ (p\lor q)\land r=T\land T=T. \]Therefore,
\[ \boxed{T}. \]Practice 9
The main connective is the implication
\[ \boxed{\to}. \]Practice 10
The converse is
\[ \boxed{q\to p}. \]The contrapositive is
\[ \boxed{\neg q\to\neg p}. \]What to Remember
- A proposition is a declarative statement with a definite truth value.
- Atomic propositions can be represented by symbols such as \(p\), \(q\), and \(r\).
- Negation is written \(\neg p\).
- Conjunction is written \(p\land q\).
- Disjunction is written \(p\lor q\) and is normally inclusive.
- Implication is written \(p\to q\).
- Biconditional is written \(p\leftrightarrow q\).
- Parentheses determine scope and logical grouping.
- Compound propositions are evaluated from their component truth values.
- A conditional statement must not be confused with its converse.
The key habit is to identify the atomic propositions first and then expose the structure created by the logical connectives.
Where We Go Next
Propositional logic gives us the symbolic language for combining truth-valued statements. The next step is to organize every possible truth-value assignment systematically.
The next lesson, Truth Tables, develops a complete tabular method for evaluating compound propositions, testing logical equivalence, identifying tautologies and contradictions, and analyzing conditional structure.