Propositional Logic

By Daniel Machado Updated: 10/02/2026

Propositional logic, also known as sentential logic or propositional calculus, is the branch of mathematical logic that studies propositions and the ways they are combined using logical connectives.

Unlike predicate logic, propositional logic does not analyze the internal structure of propositions, which makes it a zero-order logic system. Within this framework, each statement is treated as an atomic, indivisible block; it does not distinguish between subjects, predicates, or quantifiers, focusing exclusively on the truth value of the complete sentence and how it relates to others.

The primary goal of propositional logic is to analyze the validity of arguments. An argument is valid when, whenever all of its premises are true, its conclusion must also be true. To this end, rules of inference are used, which are basic deductive patterns that allow one to derive valid conclusions from given premises.

In this article, we will cover the core concepts of propositional calculus: propositions, logical connectives, truth tables, and rules of inference, among others.

Table of Contents

Propositions

A proposition (or statement) is a declarative sentence that is either true or false, but not both at the same time. Propositions serve as the fundamental building blocks of propositional logic and are represented by lowercase letters such as p, q, r, s, etc., known as propositional variables.

Some examples of propositions include:

"The Sun is a star." (True proposition).
"The Earth is flat." (False proposition).
"2 + 2 = 4." (True proposition).
"Water boils at 30°C at sea level." (False proposition).

In contrast, sentences such as "Stop!", "What time is it?", or "Good morning!" are not propositions, because it is impossible to determine whether they are true or false; commands, exclamations, and questions fall into this non-declarative category.

The truth value of a proposition has one of two possible states: true (T) or false (F). This dichotomy is founded on the principle of bivalence (or the law of the excluded middle), a cornerstone of classical logic. While the primary interest of propositional logic is not to establish the empirical truth of a claim about the physical world (which belongs to empirical sciences or specific factual knowledge), it does require assigning a definite truth value (T or F) to each atomic proposition to operate.

The process of converting expressions from everyday natural language into formal logical syntax is known as translating statements into symbolic form.

Propositions are divided into two main types:

Simple or atomic propositions: basic statements that cannot be broken down into smaller propositions; they represent the minimal units of meaning within the system. The examples listed above are atomic propositions.
Compound or molecular propositions: formed by combining two or more atomic propositions using logical connectives (which we will examine next).

Logical Connectives

Logical connectives (or logical operators) are symbols used to build compound propositions from existing propositions. Each connective has a specific symbol, a natural language reading, and well-defined truth conditions, summarized in the table below.

For the following examples, consider the atomic propositions p: "The door is open" and q: "The light is on".

Connective	Symbol	Expression (reading)	Example	Truth value
Negation	¬	"not", "it is not the case that", "it is false that"	¬p: "The door is not open" ¬q: "It is not the case that the light is on"	True when the original proposition is false. False when the original proposition is true.
Conjunction	∧	"and", "but"	p ∧ q: "The door is open and the light is on"	True only when both propositions joined are true; false in all other cases.
Inclusive disjunction	∨	"or" (inclusive)	p ∨ q: "The door is open or the light is on"	True when at least one of the propositions is true. False only if both are false.
Exclusive disjunction	⊻	"either… or…, but not both"	p ⊻ q: "Either the door is open or the light is on, but not both"	True when exactly one proposition is true and the other is false. False if both share the same truth value.
Conditional (implication)	→	"if…, then…"	p → q: "If the door is open, then the light is on"	False only when the antecedent (first proposition) is true and the consequent (second proposition) is false. True in all other cases.
Biconditional (equivalence)	↔	"if and only if"	p ↔ q: "The door is open if and only if the light is on"	True when both propositions share the same truth value (both T or both F). False if their truth values differ.

The logical behavior of each connective—that is, the conditions under which a compound proposition formed by it is true or false—can be summarized in a truth table. A truth table lists all possible combinations of truth values for the underlying atomic propositions and, for each combination, determines the result of applying the connective. Below are the individual truth tables for each operator.

Negation

p	¬p
T	F
F	T

Conjunction

p	q	p ∧ q
T	T	T
T	F	F
F	T	F
F	F	F

Inclusive disjunction

p	q	p ∨ q
T	T	T
T	F	T
F	T	T
F	F	F

Exclusive disjunction

p	q	p ⊻ q
T	T	F
T	F	T
F	T	T
F	F	F

Conditional

p	q	p → q
T	T	T
T	F	F
F	T	T
F	F	T

Biconditional

p	q	p ↔ q
T	T	T
T	F	F
F	T	F
F	F	T

Compound propositions can, in turn, be combined with others using logical connectives to produce more complex propositional formulas. This nesting capacity makes it possible to construct formal logical expressions that model extensive chains of deductive reasoning. For instance, given the atomic propositions p, q, r, some formulas that can be constructed are:

(p ∧ q) → r
¬(p ∨ q) ↔ (¬p ∧ ¬q)
(p → q) ∧ (q → p)
[(p ∧ q) ∧ r] → p

Truth Tables

Truth tables are systematic tabular tools used to determine the truth value of compound propositions. They list every possible combination of truth values for the component atomic propositions and compute the resulting truth value of the compound proposition for each case.

For example, the truth table for the formula (p → q) ∧ (q → p) is:

p	q	p → q	q → p	(p → q) ∧ (q → p)
T	T	T	T	T
T	F	F	T	F
F	T	T	F	F
F	F	T	T	T

Each row in the table represents a single truth assignment (or interpretation). To evaluate the truth value of the compound proposition across all circumstances, the table is read row by row.

Examining the first row, if both p and q are true, then the compound proposition (p → q) ∧ (q → p) is true. In the second and third rows, where p and q have opposing truth values, the compound statement evaluates to false. Finally, in the fourth row, where both p and q are false, the compound statement is true.

Once a truth table is evaluated, any propositional formula can be classified into one of three fundamental categories based on its truth value distribution:

Tautology: a formula that evaluates to true under every possible combination of truth values of its propositional variables. A standard example is the law of excluded middle: p ∨ ¬p.
Contingency: a formula that evaluates to true under some interpretations and false under others. For example, the statement (p ∧ q) → r.
Contradiction: a formula that evaluates to false under every possible combination of truth values of its variables. A standard example is p ∧ ¬p.

Logical Equivalences

In propositional logic, two statements are said to be logically equivalent if they yield the same truth value across all possible interpretations. When this holds, the two statements can be substituted for one another in any logical context without altering the validity of an argument.

Formally, two propositional formulas A and B are logically equivalent, denoted by A ≡ B, if and only if their truth tables match across every row.

Logical equivalences are essential in mathematical logic and computer science because they provide the means to simplify complex Boolean expressions, prove theorems, and rewrite arguments into equivalent canonical forms without compromising validity.

The most important logical equivalences (or laws of logic) are presented in the following table:

Law	Formula
Double negation law	¬(¬p) ≡ p
Commutative laws	p ∧ q ≡ q ∧ p p ∨ q ≡ q ∨ p
Associative laws	(p ∧ q) ∧ r ≡ p ∧ (q ∧ r) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
Distributive laws	p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Absorption laws	p ∧ (p ∨ q) ≡ p p ∨ (p ∧ q) ≡ p
De Morgan's laws	¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q

To verify that two formulas are logically equivalent, one can construct their corresponding truth tables and confirm that the final columns are identical.

Arguments

An argument is an ordered sequence of statements known as premises, intended to provide rational justification or evidence for asserting a final statement called the conclusion.

In formal logic, an argument is valid when its logical structure guarantees that whenever all premises are true, the conclusion must necessarily be true as well. Validity depends entirely on the logical form of the argument, rather than the factual content of the statements it contains.

Consider the following argument:

If the server is down, then the website does not load.
The server is down.
Therefore, the website does not load.

The deductive structure of this argument matches a fundamental rule of inference known as modus ponens (MP). Modus ponens establishes that from a conditional premise p → q and the affirmation of its antecedent p, one can validly infer the consequent q.

Another classic valid argument form is:

If an internet connection is active, then the email is sent.
The email is not sent.
Therefore, an internet connection is not active.

In this case, the underlying rule is modus tollens (MT). Modus tollens states that from a conditional premise p → q and the denial of its consequent ¬q, one can validly infer the denial of its antecedent ¬p.

A frequent invalid argument is the formal error known as the fallacy of denying the antecedent. Consider this example:

If it rains, then the street is wet.
It does not rain.
Therefore, the street is not wet.

Even though in a specific real-world scenario the street may indeed be dry, logical validity is not determined by empirical happenstance, but by formal structure. In fact, there are conditions under which the premises are true while the conclusion is false.

The falsity of the antecedent does not logically imply the falsity of the consequent, as the consequent could be true for an entirely independent reason (such as a street cleaning truck or a sprinkler system). Consequently, this argument is a formal fallacy: a pattern that may appear intuitively sound, but fails to guarantee the truth of the conclusion from the truth of the premises.

In addition to standard natural language expressions, an argument can be written in several formal formats to highlight its logical anatomy. In propositional logic, a standard vertical layout lists each premise on an individual line, places a horizontal line underneath the final premise, and presents the conclusion at the bottom.

For example, modus ponens is represented as:

\(\begin{array}{l} p \to q \\ p \\ \hline \therefore q \end{array}\)

And modus tollens is represented as:

\(\begin{array}{l} p → q \\ ¬q \\ \hline \therefore ¬p \end{array}\)

The symbol ∴ is read as "therefore".

An argument can also be represented compactly as a single propositional formula. Under this representation, all premises are linked together using conjunction (∧), grouped within parentheses or brackets, and connected to the conclusion using a conditional (→). Thus, an argument with premises P₁, P₂,..., P_n and conclusion C is formulated as:

(P₁ ∧ P₂ ∧... ∧ P_n) → C

Difference between Validity, Truth, and Soundness

Propositional logic evaluates the validity of arguments, not the empirical truth of their assertions. These concepts belong to separate domains and must be kept distinct.

Truth refers to the empirical state of an individual proposition: whether its claim corresponds to reality. For instance, "Paris is the capital of France" is a true statement, whereas "2 + 2 = 5" is a false statement.
Validity, on the other hand, is a purely structural property of deductive arguments. An argument is valid if the truth of its premises necessitates the truth of its conclusion, meaning it is impossible for all premises to be true while the conclusion is false.

This distinction means that an argument can be entirely valid even when its premises and conclusion are patently false or absurd in the real world. Validity concerns structural consistency, not factual accuracy. For example:

If pigs have wings, then elephants sing opera.
Pigs have wings.
Therefore, elephants sing opera.

This argument is structurally valid (it is an instance of modus ponens), despite being completely divorced from reality. Propositional logic evaluates the mechanical validity of the inference, not the plausibility of the assertions.

However, relying solely on formal validity can lead to accepting deductive arguments whose conclusions, although formally derived, fail to hold in practice because one or more premises are false. This motivates the distinction between a valid argument and a sound argument.

An argument is sound if and only if it satisfies two conditions simultaneously: first, it must be valid (its formal structure ensures that if the premises are true, the conclusion must follow); and second, all of its premises must actually be true in reality.

Consider the following argument:

If 4 is an even integer, then it is divisible by 2.
4 is an even integer.
Therefore, 4 is divisible by 2.

This argument is valid (its structure is modus ponens). Furthermore, both premises are mathematically true. Because it satisfies both criteria, it is a sound argument. Conversely, the argument "If 5 is even, then it is divisible by 2; 5 is even; therefore, 5 is divisible by 2" is valid in form, but unsound because the premise "5 is even" is false.

Rules of Inference

Rules of inference are valid argument forms used as templates for establishing the truth of an assertion by deriving a conclusion from given premises. Their validity can be verified via truth tables by showing that the conditional statement representing the entire argument is a tautology.

The most widely applied rules of inference are:

Rule of inference	Formula
Modus ponens	[(p → q) ∧ p] → q
Modus tollens	[(p → q) ∧ ¬q] → ¬p
Syllogism	(p → q) → [(q → r) → (p → r)]
Disjunctive syllogism	[(p ∨ q) ∧ ¬p] → q [(p ∨ q) ∧ ¬q] → p
Hypothetical syllogism (transitivity)	[(p → q) ∧ (q → r)] → (p → r) [(p ↔ q) ∧ (q ↔ r)] → (p ↔ r)
Simplification	p ∧ q → p p ∧ q → q
Addition	p → p ∨ q q → p ∨ q
Simple constructive dilemma	[( p ∨ q) ∧ ( p → r) ∧ (q → r)] → r
Constructive dilemma	[(p → q) ∧ (r → s) ∧ (p ∨ r)] → (q ∨ s)
Destructive dilemma	[(p → q) ∧ (r → s) ∧ (¬q ∨ ¬s) ] → (¬p ∨ ¬r)
Proof by cases	[(p → q) ∧ (¬p → q)] → q

Limitations of Propositional Logic

Although propositional logic provides a solid framework for analyzing argument validity, it has an inherent limitation: it cannot inspect the internal structure of atomic propositions. The system treats every declarative statement as an undifferentiated unit. As a result, arguments that depend on the internal semantic relationships between constituents (such as subjects, predicates, or quantifiers) fall outside its analytical scope.

The standard demonstration of this limitation is the classical syllogism:

All men are mortal.
Socrates is a man.
Therefore, Socrates is mortal.

In propositional logic, this argument consists simply of three unrelated atomic propositions, represented as p, q, and r. Its formal structure is modeled as: (p ∧ q) → r.

When evaluated with a truth table, this formula is contingent rather than a tautology, which would indicate that the argument is invalid. Intuitively, however, the conclusion clearly follows from the premises. This failure occurs because propositional logic is blind to internal structures: it cannot determine that "Socrates" belongs to the set "men", nor that "all" denotes universal quantification.

Accounting for these structural relationships requires a more expressive framework: predicate logic (or first-order logic). First-order logic extends formal language by decomposing propositions into individual terms (objects, such as "Socrates") and predicates (properties or relations, such as "is mortal"), and introducing quantifiers such as ∀ ("for all") and ∃ ("there exists"). Under this richer system, the classical syllogism is formally proven valid using inference rules that operate directly on internal predicates and quantifiers.

Logic Circuits

Logic circuits are graphical models that use standard diagrams and symbols to represent the logical relationships between propositions and their truth values. These diagrams provide an intuitive visualization of logical connectives, showing how truth values determine signal paths, directly analogous to electric current flowing through a network of switches.

In digital electronics, these circuits process binary signals (0 and 1, representing false and true, respectively) to carry out logical computations. Logic circuits form the foundational building blocks of digital hardware, including microprocessors, embedded systems, and mobile devices.

The primary elements of a logic circuit are:

1) Propositions (input variables): represent the inputs to the circuit. Each variable takes on one of two discrete binary states: 0 (false) or 1 (true).

2) Logical connectives (logic gates): execute logical operations on input signals. The elementary logic gates include:

AND (conjunction): outputs 1 only when all inputs are 1.
OR (disjunction): outputs 1 when at least one input is 1.
NOT (inverter / negation): outputs the inverted state of its input (0 becomes 1, and 1 becomes 0).
NAND (negated conjunction): outputs 0 only when all inputs are 1.
NOR (negated disjunction): outputs 0 when at least one input is 1.
XOR (exclusive disjunction): outputs 1 when exactly one input is 1.
XNOR (equivalence): outputs 1 when both inputs are identical.

Example: the logic circuit corresponding to the compound proposition p ∧ (q ∨ r) is:

Logic circuit diagram example in propositional logic

Applications of Propositional Logic

Propositional logic has numerous applications in various fields due to its ability to formalize and analyze arguments. Some of the main applications of propositional logic include:

Digital circuits: They are the foundation of computers and other electronic devices and are based on Boolean algebra, which is a direct application of propositional logic.
Mathematics: Propositional logic is fundamental to the axiomatization and development of mathematics. It is used to define mathematical concepts, and to formulate and prove theorems.
Computer Science: Programming languages are based on principles of propositional logic to evaluate conditions and control program flow.
Philosophy: In philosophical analysis, propositional logic is used to study the nature of truth, meaning, and argumentation.
Law: Propositional logic is used in legal analysis to evaluate the validity of legal arguments and to identify potential fallacies in legal reasoning.
Education: Teaching propositional logic in primary and secondary education helps develop students' critical thinking and logical reasoning skills.

References

Epp, S. (2020). Discrete Mathematics with Applications (5th ed.). Cengage.
Gallier, J., & Quaintance, J. (2025). Mathematical foundations and aspects of discrete mathematics.
Haggard, G., Schlipf, J., & Whitesides, S. (2006). Discrete mathematics for computer science. Thomson Brooks/Cole.
Hunter, D. (2017). Essentials of discrete mathematics (3rd ed.). Jones & Bartlett Learning.
Johnsonbaugh, R. (2018). Discrete Mathematics (8th ed.). Pearson.
Levin, O. (2024). Discrete mathematics: An open introduction (4th ed.).
Lipschutz, S., & Lipson, M. (2007). Theory and problems of discrete mathematics (3rd ed.). McGraw-Hill.