Elementary logic

Proposition

A proposition is a statement for which it makes sense to ask whether it is true or false, and which has exactly one of the two truth values. Propositions are denoted by letters such as $p$, $q$, $r$. Every mathematical statement, such as an equality or a theorem, is a proposition.

• ”$7$ is a prime number”: true proposition.
• "$2+2=5$": false proposition.
• "$x+1=3$": statement with a variable, which becomes a proposition when a value is assigned to $x$. A statement of this kind is called a predicate and is denoted by $p(x)$; predicates also become propositions through quantifiers.

1. Negation

The negation of $p$, denoted by $\neg p$ (“not $p$”), is the proposition that is true when $p$ is false and false when $p$ is true.

The negation of ”$7$ is prime” is ”$7$ is not prime”. Double negation gives back the original proposition: $\neg (\neg p)$ has the same truth table as $p$. Negation appears in counterexamples and in proofs by contradiction.

2. Conjunction and disjunction

The conjunction $p\wedge q$ (”$p$ and $q$”) is true when $p$ and $q$ are both true. The disjunction $p\vee q$ (”$p$ or $q$”) is true when at least one of $p$ and $q$ is true, including the cases in which both are.

For $x=2$: the proposition "$x>0\wedge x>3$" is false, because the second part is false; the proposition "$x>0\vee x>3$" is true, because the first part is true.