Applications of Propositional Logic
Quick Reference
| Field | Value |
|---|---|
| Textbook | Rosen, Discrete Mathematics and Its Applications, 8th edition |
| Chapter | 1 (The Foundations: Logic and Proofs) |
| Section | 1.2 Applications of Propositional Logic |
| Subsections | 1.2.2 Translating English Sentences; 1.2.3 System Specifications; 1.2.5 Logic Puzzles; 1.2.6 Logic Circuits |
| Pages | 17 to 25 |
| Pages verified | Yes |
Before You Start: Prerequisite Check
📋 Can you do these? (Click to reveal self-test)
Test yourself on these prerequisite skills:
Connectives: Write the proposition “if $p$ then $q$” using a logical connective.
Check
$p \rightarrow q$ (the conditional, read “$p$ implies $q$”).
Truth value of a conditional: When is $p \rightarrow q$ false?
Check
A conditional is false in exactly one case: when the hypothesis $p$ is true and the conclusion $q$ is false. In every other case it is true.
Negation of a conjunction: If $p$ is true and $q$ is false, what is the truth value of $p \wedge q$?
Check
False. A conjunction is true only when both parts are true.
If you struggled:
- Review Propositional Logic for the connectives ($\neg$, $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$) and their truth tables.
Try This First
Before any formula, work this small case. A registration system has two rules:
- Rule A: “A student may enroll only if the prerequisite is met.”
- Rule B: “The prerequisite is not met, yet the student is enrolled.”
Let $e$ stand for “the student is enrolled” and $m$ stand for “the prerequisite is met”. Try to find truth values for $e$ and $m$ that make both rules true at the same time.
What did you find? (Click after you have tried)
Rule A says $e \rightarrow m$ (enrolling requires the prerequisite). Rule B says $\neg m \wedge e$ (prerequisite not met, but enrolled).
For Rule B to be true, you need $e$ true and $m$ false. But then Rule A becomes $\text{true} \rightarrow \text{false}$, which is false. There is no assignment that satisfies both. The two rules contradict each other. You have just checked a system specification for consistency by hand, which is the central application of this section.
What Propositional Logic Is For
The connectives and truth tables are not an end in themselves. They are a precise language. Once an English sentence, a hardware specification, or a puzzle clue is rewritten in that language, a mechanical check (a truth table or a satisfying assignment) settles questions that ordinary words leave ambiguous.
Four applications carry this section:
- Translating English into propositions, so that an ambiguous sentence becomes a single unambiguous formula.
- System specifications, where a designer lists requirements as propositions and asks whether they can all hold at once (consistency).
- Logic puzzles, where clues become propositions and the unique solution is the one assignment that makes every clue true.
- Logic circuits, where a network of AND, OR, and NOT gates computes the value of a compound proposition.
The thread running through all four is the same process: take a situation, produce a proposition, then read off truth values. A proposition behaves like a process that takes an input (an assignment of true or false to each variable) and returns an output (the truth value of the whole formula).
Prerequisite Hub
Builds on
| Skill | Why it is needed |
|---|---|
Propositional Logic (dm-propositional-logic) |
Translation and consistency checking depend on fluency with the connectives ($\neg$, $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$) and their truth tables. This is a strong prerequisite. |
Unlocks
| Skill | What comes next |
|---|---|
Propositional Equivalences (dm-propositional-equivalences) |
Once propositions model real specifications, the next step is to recognize when two different propositions always agree, which lets a specification be simplified or a circuit be reduced. |
No cross-course prerequisites apply to this node.
Quick Reference
| Property | Value |
|---|---|
| Chapter | 1.2 |
| Course | MATH301 |
| Difficulty | Intermediate |
| Time | ~30 minutes |
Translation Keywords at a Glance
| English phrase | Connective | Symbolic form |
|---|---|---|
| “and”, “but”, “yet” | conjunction | $p \wedge q$ |
| “or” (inclusive) | disjunction | $p \vee q$ |
| “if $p$, then $q$”, “$p$ only if $q$” | conditional | $p \rightarrow q$ |
| “$p$ if and only if $q$”, “exactly when” | biconditional | $p \leftrightarrow q$ |
| “not”, “it is false that” | negation | $\neg p$ |
A frequent trap sits in that table: “$p$ only if $q$” translates to $p \rightarrow q$, not $q \rightarrow p$. The misconception section returns to this.
Official Definition
Consistent system specifications:
A list of statements (system specifications) is consistent if it is possible to assign truth values to the proposition variables that occur in them so that all the statements are true.
Source: Rosen 8e, Section 1.2, p.19 (subsection 1.2.3 System Specifications, Example 3 discussion).
A specification that is not consistent is called inconsistent. Inconsistent specifications cannot be met by any system, no matter how it is built, so detecting inconsistency early prevents wasted engineering effort. The opener above produced an inconsistent two-rule specification.
No named theorem or lemma applies here. The reasoning rests on the definitions of the connectives and on the definition of consistency given above.
The Translation Procedure
Goal: Turn an English sentence into a single proposition whose truth value matches the meaning of the sentence.
Step 1: Identify the atomic (simple) statements, the ones that are either true or false on their own, and assign a variable to each.
Step 2: Locate the connecting words (“and”, “or”, “if”, “only if”, “not”) and match each to its connective using the keyword table.
Step 3: Respect the order of the words. “$p$ only if $q$” puts $q$ as the consequence; “$p$ if $q$” puts $q$ as the hypothesis.
Step 4: Assemble the compound proposition, adding parentheses so the grouping is unambiguous.
Step 5: Sanity-check by reading the symbolic form back into English and comparing it to the original sentence.
The Consistency Procedure
Goal: Decide whether a list of specifications can all be true at once.
Step 1: Translate each specification into a proposition.
Step 2: Look for an assignment of true and false to the variables that makes every proposition true. A small truth table over the variables is a reliable way to search.
Step 3: If one such assignment exists, the specification is consistent, and that assignment is a witness. If no assignment works, the specification is inconsistent.
Worked Examples
Worked Example 1: Translating “only if”
Translate “You can access the database only if you have a valid password” into a proposition.
Predict first: Before reading on, predict whether “only if” makes the password the hypothesis or the conclusion of the conditional.
Solution.
Step 1: Let $a$ stand for “you can access the database” and $v$ stand for “you have a valid password”.
Step 2 and 3: The phrase “$a$ only if $v$” means that access requires the password. Whenever access happens, the password must be present. That is exactly $a \rightarrow v$.
Step 4: The proposition is $a \rightarrow v$.
Check: Read it back. “If you can access the database, then you have a valid password.” Having access without a password would be impossible, which matches the sentence. The prediction that put $v$ as the conclusion is the correct one.
Worked Example 2: Checking consistency
A system has three specifications:
- S1: “The diagnostic message is stored if the system is in normal mode.”
- S2: “The system is in normal mode or it is in interrupt mode (or both).”
- S3: “The diagnostic message is not stored, and the system is not in interrupt mode.”
Are S1, S2, and S3 consistent?
Predict first: Read the three sentences once. Predict whether you expect to find an assignment that satisfies all three.
Solution.
Step 1: Let $d$ = “the diagnostic message is stored”, $n$ = “the system is in normal mode”, $i$ = “the system is in interrupt mode”.
Step 2: Translate. $$\text{S1}: n \rightarrow d \qquad \text{S2}: n \vee i \qquad \text{S3}: \neg d \wedge \neg i$$
Step 3: Search for a satisfying assignment. From S3, both $d$ and $i$ are false. Substitute $i = \text{false}$ into S2: $n \vee \text{false}$ forces $n = \text{true}$. Now substitute $n = \text{true}$ and $d = \text{false}$ into S1: $\text{true} \rightarrow \text{false}$, which is false.
So the only candidate forced by S2 and S3 makes S1 false. No assignment satisfies all three.
Conclusion: The specifications are inconsistent. A designer must drop or revise one of them. If the original prediction expected consistency, comparing it to this result shows where the hidden conflict is: S1 demands storage in normal mode, while S3 forbids storage and S2 forces normal mode.
Worked Example 3: A small logic puzzle
Two people each either always tell the truth (a knight) or always lie (a knave). Person X says, “I am a knave or my companion is a knight.” Determine what X and the companion are.
Predict first: Predict whether a truth-teller could ever truthfully call themselves a knave.
Solution.
Step 1: Let $x$ = “X is a knight” (so $\neg x$ means X is a knave) and $y$ = “the companion is a knight”.
Step 2: X asserts the proposition $\neg x \vee y$. A knight makes true statements and a knave makes false ones, so the statement is true exactly when X is a knight. This gives the constraint $$x \leftrightarrow (\neg x \vee y).$$
Step 3: Test the two cases for $x$.
- Suppose $x = \text{true}$ (X is a knight). Then the statement $\neg x \vee y$ must be true. Since $\neg x$ is false, $y$ must be true. So the companion is a knight. Check: $\text{true} \leftrightarrow (\text{false} \vee \text{true}) = \text{true} \leftrightarrow \text{true}$, which holds.
- Suppose $x = \text{false}$ (X is a knave). Then the statement $\neg x \vee y$ must be false. But $\neg x$ is true, so $\neg x \vee y$ is true, a contradiction.
Conclusion: X is a knight and the companion is a knight. A truth-teller cannot truthfully call themselves a knave, which is why the second case collapses.
Worked Example 4: From a circuit to a proposition
A logic circuit takes inputs $p$, $q$, $r$. It feeds $p$ and $q$ into an AND gate, sends $r$ through a NOT gate, and feeds those two results into an OR gate. Write the output as a proposition and find its value when $p = \text{true}$, $q = \text{false}$, $r = \text{true}$.
Predict first: Predict the output value before computing, just from a glance at the inputs.
Solution.
Step 1: The AND gate produces $p \wedge q$. The NOT gate produces $\neg r$. The OR gate combines them.
Step 2: The output proposition is $$(p \wedge q) \vee \neg r.$$
Step 3: Substitute $p = \text{true}$, $q = \text{false}$, $r = \text{true}$. $$(\text{true} \wedge \text{false}) \vee \neg \text{true} = \text{false} \vee \text{false} = \text{false}.$$
Conclusion: The output is false for that input. Compare to the prediction: with $q$ false the AND branch is dead, and with $r$ true the NOT branch is dead, so a quick glance already pointed to false.
Common Misconceptions
“$p$ only if $q$” translates to $q \rightarrow p$. The tempting reasoning hears “if” next to $q$ and makes $q$ the hypothesis. Test it on a concrete case. “You graduate only if you pass the final” should be false when someone graduates without passing. Under the wrong reading $q \rightarrow p$ (pass implies graduate), graduating without passing leaves $q$ false, so $q \rightarrow p$ comes out true, which contradicts the meaning. The correct reading $p \rightarrow q$ (graduate implies pass) comes out false in that case, matching the sentence. The phrase “only if” marks the consequence, not the hypothesis.
an inclusive “or” excludes the both-true case. Everyday speech often treats “or” as one-or-the-other but not both. In propositional logic the bare connective $\vee$ is inclusive: $p \vee q$ is true when $p$ is true, when $q$ is true, and when both are true. A specification that reads “the system is in normal mode or interrupt mode” is satisfied by a system in both modes unless the sentence explicitly says “but not both”. Mislabeling the both-true row as false changes which assignments count and can turn a consistent specification into an apparently inconsistent one.
consistency means every statement is true. Consistency does not assert that the specifications are true in the real world. It asks only whether some assignment of truth values makes them all true together. A consistent specification can describe a situation that never actually occurs; an inconsistent one describes a situation that cannot occur under any assignment. The question is about the existence of a satisfying assignment, not about real-world fact.
Practice Problems
Let $r$ = “it is raining” and $c$ = “the game is canceled”. Translate “it is raining and the game is canceled” into a proposition.
Let $u$ = “you may use the lab” and $k$ = “you have a key card”. Translate “you may use the lab only if you have a key card.”
A designer says: “My three specifications are consistent because each one, on its own, is true in some situation.”
What is the flaw in this reasoning?
(A) Nothing. The claim is correct.
(B) Consistency requires a single assignment that makes all three true at the same time, not three separate assignments.
(C) Consistency requires that all three specifications are true in the real world.
(D) Consistency requires that the specifications are logically equivalent.
Are these two specifications consistent? S1: “The backup runs if the disk is full.” S2: “The disk is full, and the backup does not run.” Justify your answer.
A circuit feeds $p$ and $\neg q$ into an AND gate, and feeds that result together with $r$ into an OR gate. Write the output proposition, then evaluate it for $p = \text{false}$, $q = \text{false}$, $r = \text{false}$.
On an island, each person is a knight (always truthful) or a knave (always lying). Person A says, “Both of us are knaves,” speaking about A and a companion B. Determine what A and B are.
Mastery Checklist
Novice (Level 1-2):
Competent (Level 3-4):
Proficient (Level 5):
Mental Model
Think of a proposition as a small machine: a process that takes an input (a row of true and false values, one per variable) and returns a single output (the truth value of the whole formula). Translating English builds the machine from a sentence. Checking consistency asks whether some input makes a whole bank of machines light up “true” together. Reading a circuit traces the wiring of one such machine. The same process appears in every application of this section.
Connections
Looking back:
- Propositional Logic supplies the connectives and truth tables that every translation and consistency check uses.
Looking ahead:
- Propositional Equivalences studies when two propositions always agree, which lets a specification be simplified or a circuit be reduced to fewer gates.
Real-world connections:
- Hardware and software requirement documents are system specifications; an inconsistent set cannot be implemented.
- Digital circuit design rests on reading and simplifying the propositions that gates compute.
- Constraint puzzles and scheduling problems reduce to finding an assignment that satisfies a set of clauses.
Resources
- Rosen, Discrete Mathematics and Its Applications, 8th edition, Section 1.2 Applications of Propositional Logic (p.17 to 25). The primary text for this node, covering translation, system specifications, logic puzzles, and logic circuits.
- Levin, Discrete Mathematics: An Open Introduction (open companion), Logic chapter. Open-access treatment of translation and applications: https://discrete.openmathbooks.org/dmoi3/ch_logic.html
- Existing tree node: Propositional Equivalences (the next section this unlocks).
| Previous | Up | Next |
|---|---|---|
| Propositional Logic | Skills Index | Propositional Equivalences |
Last updated: 2026-06-16