A proposition is a sentence, written in a language, that has a truth value (i.e., it is true or false) in a world. A proposition is built from atomic propositions using logical connectives.

An atomic proposition, or just an atom, is a symbol. We use the convention that propositions consist of letters, digits and the underscore (_) and start with a lower-case letter.

For example, ai_is_fun, ${\text{lit\_l}}_1$, live_outside, mimsy and sunny are all atoms.

Propositions can be built from simpler propositions using logical connectives. A proposition or logical formula is either

• •

  an atomic proposition or

• •

  a compound proposition of the form

  $\mathrm{\neg }p$	“not $p$”	negation of $p$
  $p\wedge q$	“$p$ and $q$”	conjunction of $p$ and $q$
  $p\vee q$	“$p$ or $q$”	disjunction of $p$ and $q$
  $p\to q$	“$p$ implies $q$”	implication of $q$ from $p$
  $p\leftarrow q$	“$p$ if $q$”	implication of $p$ from $q$
  $p\leftrightarrow q$	“$p$ if and only if $q$”	equivalence of $p$ and $q$

  where $p$ and $q$ are propositions.

The operators $\mathrm{\neg }$, $\wedge$, $\vee$, $\to$, $\leftarrow$ and $\leftrightarrow$ are logical connectives.

Parentheses can be used to make logical formulae unambiguous. When parentheses are omitted, the precedence of the operators is in the order they are given above. Thus, a compound proposition can be disambiguated by adding parentheses to the subexpressions in the order the operations are defined above. For example,

is an abbreviation for