A progressive collection of 20 practice problems on propositional logic, designed to develop the ability to recognize propositions, formalise statements, construct truth tables, and correctly use the main logical connectives.
Each exercise is worked through step by step, with attention paid to the meaning of the formulas and not merely to the final result. The goal is to learn to reason rigorously about the truth value of statements and the logical relationships between propositions.
Recall that a proposition is a declarative statement to which exactly one truth value can be unambiguously assigned:
\[ T \quad \text{or} \quad F \]
The main connectives of propositional logic are:
\[ \neg,\quad \land,\quad \lor,\quad \rightarrow,\quad \leftrightarrow \]
They allow compound propositions to be built from simpler ones.
Exercise 1 — level ★☆☆☆☆
Determine which of the following statements are propositions:
\[ \text{a) } 7>3 \]
\[ \text{b) } \text{Close the door.} \]
\[ \text{c) } 5+2=10 \]
\[ \text{d) } x+1=4 \]
Solution
Statements a) and c) are propositions. Statements b) and d) are not propositions.
Worked solution
To decide whether a statement is a proposition, we ask whether it has a well-determined truth value — that is, whether it is either true or false.
Consider the first statement:
\[ 7>3 \]
This is a declarative statement and we can clearly establish that it is true. It is therefore a proposition.
Now consider:
\[ \text{Close the door.} \]
This is not a declarative statement but a command. It makes no sense to call it true or false. It is therefore not a proposition.
The third statement is:
\[ 5+2=10 \]
This is a declarative statement. We can establish that it is false, since:
\[ 5+2=7 \]
A false statement can still be a proposition: what matters is that it has a definite truth value.
Finally, consider:
\[ x+1=4 \]
This statement contains a free variable, \(x\). Without specifying the value of \(x\), we cannot determine whether it is true or false.
For instance, if \(x=3\) the statement is true; if \(x=0\) it is false.
As written, it is therefore not a proposition.
In summary:
\[ \text{a) true proposition} \]
\[ \text{b) not a proposition} \]
\[ \text{c) false proposition} \]
\[ \text{d) not a proposition} \]
Exercise 2 — level ★☆☆☆☆
Determine whether each of the following propositions is atomic or compound:
\[ \text{a) } 4 \text{ is even} \]
\[ \text{b) } 4 \text{ is even and } 5 \text{ is odd} \]
\[ \text{c) } \text{It is not raining} \]
\[ \text{d) } \text{If I study, then I pass the exam} \]
Solution
a) atomic; b) compound; c) compound; d) compound.
Worked solution
A proposition is atomic when it contains no logical connectives and is not obtained by combining simpler propositions.
A proposition is compound when it contains at least one logical connective, whether explicit or implicit.
Consider:
\[ 4 \text{ is even} \]
This proposition is not formed by combining other propositions. It is therefore atomic.
Now consider:
\[ 4 \text{ is even and } 5 \text{ is odd} \]
Here we have two propositions:
\[ 4 \text{ is even} \]
and:
\[ 5 \text{ is odd} \]
joined by the word "and", which corresponds to the logical connective of conjunction:
\[ \land \]
The proposition is therefore compound.
The proposition:
\[ \text{It is not raining} \]
contains a negation. If we let \(p\) denote "it is raining", then "it is not raining" is written:
\[ \neg p \]
It is therefore compound.
Finally:
\[ \text{If I study, then I pass the exam} \]
contains a logical implication. Setting:
\[ p = \text{I study} \]
and:
\[ q = \text{I pass the exam} \]
the proposition is represented as:
\[ p \rightarrow q \]
It is therefore compound.
Exercise 3 — level ★☆☆☆☆
Translate the following proposition into logical symbols:
"Marco is studying and Laura is reading."
Use:
\[ p = \text{Marco is studying} \]
\[ q = \text{Laura is reading} \]
Solution
\[ p \land q \]
Worked solution
The proposition contains two simple statements.
The first is:
\[ \text{Marco is studying} \]
denoted by:
\[ p \]
The second is:
\[ \text{Laura is reading} \]
denoted by:
\[ q \]
The word "and" indicates that both propositions must be true simultaneously.
In propositional logic this corresponds to the conjunction:
\[ \land \]
Therefore the proposition:
"Marco is studying and Laura is reading"
translates to:
\[ p \land q \]
Exercise 4 — level ★☆☆☆☆
Translate the following proposition into logical symbols:
"If it is raining, then I stay home."
Use:
\[ p = \text{it is raining} \]
\[ q = \text{I stay home} \]
Solution
\[ p \rightarrow q \]
Worked solution
The sentence has a conditional structure:
"If ..., then ..."
In propositional logic this structure is represented by the implication:
\[ \rightarrow \]
The antecedent is the proposition following the word "if":
\[ p = \text{it is raining} \]
The consequent is the proposition following "then":
\[ q = \text{I stay home} \]
Therefore the proposition:
"If it is raining, then I stay home"
translates to:
\[ p \rightarrow q \]
It is important to note that \(p\rightarrow q\) does not assert that both \(p\) and \(q\) are true, but rather that the truth of \(p\) forces the truth of \(q\).
Exercise 5 — level ★★☆☆☆
Translate the formula:
\[ \neg p \lor q \]
into natural language, given that:
\[ p = \text{I study} \]
\[ q = \text{I pass the exam} \]
Solution
"Either I do not study or I pass the exam."
Worked solution
The formula is:
\[ \neg p \lor q \]
Let us analyse each symbol in turn.
The proposition \(p\) means:
\[ \text{I study} \]
Therefore:
\[ \neg p \]
means:
\[ \text{I do not study} \]
The proposition \(q\) means:
\[ \text{I pass the exam} \]
The connective:
\[ \lor \]
represents the inclusive disjunction, that is, "or" (in the inclusive sense).
Therefore:
\[ \neg p \lor q \]
reads:
"Either I do not study or I pass the exam."
In logic, this disjunction is true even when both propositions are true — that is, when it is the case both that I do not study and that I pass the exam.
Exercise 6 — level ★★☆☆☆
Construct the truth table for the formula:
\[ p \land q \]
Solution
| \(p\) | \(q\) | \(p \land q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Worked solution
The formula contains two propositional variables, \(p\) and \(q\). A truth table with two variables must contain \(2^2=4\) possible interpretations.
The connective \(\land\) represents the logical conjunction, which is true only when both propositions are simultaneously true.
In the first row, \(p=T\) and \(q=T\), so \(p\land q = T\). In the second row, \(p=T\) and \(q=F\): since one proposition is false, \(p\land q = F\). The same applies in the third row, \(p=F\) and \(q=T\). In the last row both are false, so the conjunction is false.
We conclude that \(p\land q\) is true exclusively when \(p=T\) and \(q=T\).
Exercise 7 — level ★★☆☆☆
Construct the truth table for the formula:
\[ p \lor q \]
Solution
| \(p\) | \(q\) | \(p \lor q\) |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Worked solution
The symbol \(\lor\) represents the inclusive logical disjunction, which is true when at least one of the two propositions is true.
With two variables there are \(2^2=4\) interpretations. In the first three rows at least one proposition is true, so \(p\lor q = T\) in each case. Only in the last row, where \(p=F\) and \(q=F\), are both propositions false, giving \(p\lor q = F\).
We conclude that the inclusive disjunction is false only when both propositions are false.
Exercise 8 — level ★★☆☆☆
Construct the truth table for the formula:
\[ p \rightarrow q \]
Solution
| \(p\) | \(q\) | \(p \rightarrow q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Worked solution
The implication \(p\rightarrow q\) is read "if \(p\), then \(q\)" and is often the most delicate connective to interpret correctly.
It is false exclusively when the antecedent is true and the consequent is false, because this is the only situation in which the logical commitment expressed by the implication is violated.
First row (\(p=T,\ q=T\)): true. Second row (\(p=T,\ q=F\)): this is the only case where \(p\rightarrow q = F\). Third row (\(p=F,\ q=T\)): true, since a false antecedent never violates the implication. Fourth row (\(p=F,\ q=F\)): true, for the same reason.
We conclude that \(p\rightarrow q\) is false only when \(p=T\) and \(q=F\).
Exercise 9 — level ★★★☆☆
Determine the truth value of the formula:
\[ (p\land q)\rightarrow r \]
under the interpretation:
\[ p=T,\qquad q=F,\qquad r=F \]
Solution
The formula is true.
Worked solution
To evaluate \((p\land q)\rightarrow r\) correctly we proceed from the inside out.
The innermost subformula is \(p\land q\). With \(p=T\) and \(q=F\) we get \(T\land F = F\).
The formula therefore reduces to \(F\rightarrow F\).
Since an implication is false only when the antecedent is true and the consequent is false, and here the antecedent is false, we have \(F\rightarrow F = T\).
We conclude that the formula is true.
Exercise 10 — level ★★★☆☆
Verify by means of a truth table that:
\[ \neg(p\land q)\equiv \neg p \lor \neg q \]
Solution
The two formulas have the same truth values under every interpretation and are therefore logically equivalent.
Worked solution
To show logical equivalence we verify that the two formulas always take the same truth value. We construct a complete truth table.
| \(p\) | \(q\) | \(p\land q\) | \(\neg(p\land q)\) | \(\neg p\) | \(\neg q\) | \(\neg p\lor \neg q\) |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F |
| T | F | F | T | F | T | T |
| F | T | F | T | T | F | T |
| F | F | F | T | T | T | T |
The last two columns agree in every row, confirming that \(\neg(p\land q)\equiv \neg p\lor\neg q\).
This equivalence is known as the first De Morgan law.
Exercise 11 — level ★★★☆☆
Verify by means of a truth table that:
\[ p\rightarrow q \equiv \neg p \lor q \]
Solution
The two formulas have the same truth values under every interpretation and are therefore logically equivalent.
Worked solution
Two formulas are logically equivalent if they take the same truth value under all possible interpretations. With two variables there are \(2^2=4\) interpretations.
| \(p\) | \(q\) | \(p\rightarrow q\) | \(\neg p\) | \(\neg p\lor q\) |
|---|---|---|---|---|
| T | T | T | F | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
The columns for \(p\rightarrow q\) and \(\neg p\lor q\) are identical (\(T,\ F,\ T,\ T\)), confirming that \(p\rightarrow q \equiv \neg p \lor q\).
This equivalence is particularly important because it allows the implication to be eliminated and rewritten using only negation and disjunction.
Exercise 12 — level ★★★☆☆
Determine whether the formula:
\[ p\lor\neg p \]
is a tautology, a contradiction, or a contingent formula.
Solution
The formula is a tautology.
Worked solution
A formula is a tautology if it is true under every interpretation; a contradiction if it is false under every interpretation; and contingent if it is true under some interpretations and false under others.
The formula contains one variable, giving \(2^1=2\) interpretations.
| \(p\) | \(\neg p\) | \(p\lor\neg p\) |
|---|---|---|
| T | F | T |
| F | T | T |
In the first row \(p\) is true, so the disjunction is true. In the second row \(\neg p\) is true, so the disjunction is again true.
The formula is true under all interpretations, hence \(p\lor\neg p\) is a tautology, known as the law of excluded middle.
Exercise 13 — level ★★★☆☆
Determine whether the formula:
\[ p\land\neg p \]
is a tautology, a contradiction, or a contingent formula.
Solution
The formula is a contradiction.
Worked solution
The formula \(p\land\neg p\) simultaneously asserts \(p\) and its negation. Let us build the truth table.
| \(p\) | \(\neg p\) | \(p\land\neg p\) |
|---|---|---|
| T | F | F |
| F | T | F |
In the first row \(p\) is true but \(\neg p\) is false, so the conjunction is false. In the second row \(p\) is false, so the conjunction is false again.
The formula is false under every interpretation, hence \(p\land\neg p\) is a contradiction, known as the law of non-contradiction.
Exercise 14 — level ★★★★☆
Determine whether the formula:
\[ p\rightarrow(p\lor q) \]
is a tautology, a contradiction, or a contingent formula.
Solution
The formula is a tautology.
Worked solution
We construct the complete truth table, evaluating the inner subformula \(p\lor q\) first.
| \(p\) | \(q\) | \(p\lor q\) | \(p\rightarrow(p\lor q)\) |
|---|---|---|---|
| T | T | T | T |
| T | F | T | T |
| F | T | T | T |
| F | F | F | T |
The final column contains only \(T\), so the formula is true under every interpretation and is therefore a tautology.
Intuitively, if \(p\) is true then \(p\lor q\) is certainly true, since an inclusive disjunction is true whenever at least one component is true.
Exercise 15 — level ★★★★☆
Determine whether the formula:
\[ (p\land q)\rightarrow p \]
is a tautology, a contradiction, or a contingent formula.
Solution
The formula is a tautology.
Worked solution
The formula contains a conjunction in the antecedent of the implication. We evaluate \(p\land q\) first, then build the complete truth table.
| \(p\) | \(q\) | \(p\land q\) | \((p\land q)\rightarrow p\) |
|---|---|---|---|
| T | T | T | T |
| T | F | F | T |
| F | T | F | T |
| F | F | F | T |
The final column is \(T,\ T,\ T,\ T\), so the formula is a tautology.
The logical meaning is straightforward: if both \(p\) and \(q\) hold simultaneously, then in particular \(p\) holds.
Exercise 16 — level ★★★★☆
Verify whether:
\[ p\land q \models p \]
Solution
Yes, \(p\) is a logical consequence of \(p\land q\).
Worked solution
The notation \(p\land q \models p\) asserts that every interpretation making the premise \(p\land q\) true also makes the conclusion \(p\) true.
A conjunction is true only when both components are true:
\[ p\land q = T \quad \Longleftrightarrow \quad p=T \ \text{and}\ q=T \]
In every such interpretation, \(p=T\) necessarily. There is therefore no interpretation in which the premise is true and the conclusion is false.
Hence \(p\land q \models p\).
Exercise 17 — level ★★★★☆
Verify whether:
\[ p \models p\lor q \]
Solution
Yes, \(p\lor q\) is a logical consequence of \(p\).
Worked solution
The notation \(p \models p\lor q\) means that every interpretation making \(p\) true must also make \(p\lor q\) true.
Suppose \(p=T\). An inclusive disjunction is true when at least one component is true. Since \(p\) is already true, \(p\lor q\) is necessarily true regardless of the value of \(q\):
\[ T\lor T=T \qquad \text{and} \qquad T\lor F=T \]
Every model of \(p\) is therefore also a model of \(p\lor q\), so \(p \models p\lor q\).
Exercise 18 — level ★★★★★
Verify whether:
\[ p\rightarrow q,\ p \models q \]
Solution
Yes, \(q\) is a logical consequence of the premises \(p\rightarrow q\) and \(p\).
Worked solution
The notation \(p\rightarrow q,\ p \models q\) means that every interpretation making both premises true must also make the conclusion \(q\) true.
Suppose both premises hold. From \(p\) we know \(p=T\). From \(p\rightarrow q\) with a true antecedent, the only way the implication can remain true is if \(q=T\) as well.
Therefore every interpretation satisfying both premises also satisfies \(q\), confirming \(p\rightarrow q,\ p \models q\).
This is the semantic form of modus ponens.
Exercise 19 — level ★★★★★
Simplify the following formula using logical equivalences:
\[ \neg(p\rightarrow q) \]
Solution
\[ \neg(p\rightarrow q)\equiv p\land\neg q \]
Worked solution
We begin by eliminating the implication using the fundamental equivalence \(p\rightarrow q \equiv \neg p\lor q\):
\[ \neg(p\rightarrow q)\equiv \neg(\neg p\lor q) \]
Applying De Morgan's law \(\neg(A\lor B)\equiv \neg A\land\neg B\) with \(A=\neg p\) and \(B=q\):
\[ \neg(\neg p\lor q)\equiv \neg\neg p\land\neg q \]
Finally, by double negation \(\neg\neg p\equiv p\):
\[ \neg(p\rightarrow q)\equiv p\land\neg q \]
This result is consistent with the semantics of the implication: \(p\rightarrow q\) is false only when \(p\) is true and \(q\) is false.
Exercise 20 — level ★★★★★
Transform the formula:
\[ p\rightarrow(q\lor r) \]
into an equivalent formula that does not contain the connective \(\rightarrow\).
Solution
\[ p\rightarrow(q\lor r)\equiv \neg p\lor q\lor r \]
Worked solution
We eliminate the implication using \(A\rightarrow B\equiv \neg A\lor B\) with \(A=p\) and \(B=q\lor r\):
\[ p\rightarrow(q\lor r)\equiv \neg p\lor(q\lor r) \]
By associativity of disjunction, the parentheses may be dropped:
\[ \neg p\lor(q\lor r)\equiv \neg p\lor q\lor r \]
The equivalent formula without implication is therefore:
\[ \neg p\lor q\lor r \]
This formula is a disjunctive clause — a disjunction of literals — and can also be viewed as a conjunctive normal form consisting of a single clause.