# 5.1.1 Syntax of Propositional Calculus

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, $\mbox{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

$\neg p$ “not $p$ negation of $p$
$p\wedge\mbox{}q$ $p$ and $q$ conjunction of $p$ and $q$
$p\vee\mbox{}q$ $p$ or $q$ disjunction of $p$ and $q$
$p\rightarrow q$ $p$ implies $q$ implication of $q$ from $p$
$p\leftarrow\mbox{}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 $\neg$, $\wedge\mbox{}$, $\vee\mbox{}$, $\rightarrow$, $\leftarrow\mbox{}$ 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,

 $\neg a\vee b\wedge c\rightarrow d\wedge\neg e\vee f$

is an abbreviation for

 $((\neg a)\vee(b\wedge c))\rightarrow((d\wedge(\neg e))\vee f).$