Proposition

Proposition is a statement which is either true or false, e.g., "$\sqrt{2}$ is irrational" or "$1+1=3$". According to this definition, statements like $x = 3$ is not a proposition (since the truth depends on the value of $x$).

Connectives: Propositions can be composed together via connectives (conjunction, disjunction, and negation).

• (Conjunction:) $P \land Q$ is true if and only if both $P$ and $Q$ are true.

• (Disjunction:) $P \lor Q$ is true if and only if at least one is true.

• (Negation:) $\neg P$ is true if and only if $P$ is false.

• (Implication:) $P \Rightarrow Q$ is false if and only if $P$ is true and $Q$ is false. It is easy to check that $P\Rightarrow Q$ is equivalent to $\neg P \lor Q$. We encounter this kind of statement very often in mathematics, and there are several ways to say this statement, e.g,

  1. If $P$, then $Q$
  2. $Q$ if $P$
  3. $P$ only if $Q$
  4. $P$ is sufficient for $Q$
  5. $Q$ is necessary for $P$
  6. $P$ implies $Q$
  7. $Q$ is implied by $P$

The converse of the proposition "$P\Rightarrow Q$" is written as $Q\Rightarrow P$, and the contrapositive is $\neg Q \Rightarrow \neg P$.

See the following table for more detail.

$P$	$Q$	$P\land Q$	$P\lor Q$	$P\Rightarrow Q$
$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$	$F$
$F$	$T$	$F$	$T$	$T$
$F$	$F$	$F$	$F$	$T$