5.1 Propositions

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, lit_l1, 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

    ¬p “not p negation of p
    pq p and q conjunction of p and q
    pq p or q disjunction of p and q
    pq p implies q implication of q from p
    pq p if q implication of p from q
    pq p if and only if q equivalence of p and q

    where p and q are propositions.

The operators ¬, , , , and 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,

¬abcd¬ef

is an abbreviation for

((¬a)(bc))((d(¬e))f).