← Mathematics — Year 1/Discrete Mathematics: Logic, Sets and Proof

Propositional Logic

≈ 20 min

0/4 practice checks

A proposition is a statement that is either true or false — never both. We combine propositions with connectives:

NOT $\neg P$ flips the truth value.
AND $P \wedge Q$ is true only when both are true.
OR $P \vee Q$ is true when at least one is true.
IMPLIES $P \rightarrow Q$ is false only when $P$ is true and $Q$ is false.

A truth table lists every combination of truth values. With $n$ propositions there are $2^n$ rows — two choices (true or false) for each.

The implication $P\rightarrow Q$ trips people up. Read it as a promise: 'if $P$ , then $Q$ .' The promise is only broken when $P$ happens but $Q$ fails. If $P$ never happens, the promise was never tested, so it counts as true (vacuously).

Careful

$P\rightarrow Q$ is not the same as $Q\rightarrow P$ . 'If it rains, the road is wet' does not mean 'if the road is wet, it rained' — someone may have washed a taxi.

If $P$ is true and $Q$ is false, what is $P \wedge Q$ ?

True

False

Cannot be determined

Both true and false

How many rows does the truth table of a compound proposition with 3 distinct variables have?

The implication $P\rightarrow Q$ is false in exactly which case?

$P$ true, $Q$ true

$P$ true, $Q$ false

$P$ false, $Q$ true

$P$ false, $Q$ false

By De Morgan's laws, $\neg(P \wedge Q)$ is equivalent to:

$\neg P \wedge \neg Q$

$\neg P \vee \neg Q$

$P \vee Q$

$\neg P \rightarrow Q$

PreviousDeterminants and Invertibility NextSets and Set Operations