Syntax

In Propositional Logic, there are two types of sentences -- simple sentences and compound sentences. Simple sentences express simple facts about the world. Compound sentences express logical relationships between the simpler sentences of which they are composed.

Simple sentences in Propositional Logic are often called proposition constants or, sometimes, logical constants. In what follows, we write proposition constants as strings of letters, digits, and underscores ("_"), where the first character is a lower case letter. For example, raining is a proposition constant, as are rAiNiNg, r32aining, and raining_or_snowing. Raining is not a proposition constant because it begins with an upper case character. 324567 fails because it begins with a number. raining-or-snowing fails because it contains hyphens (instead of underscores).

Compound sentences are formed from simpler sentences and express relationships among the constituent sentences. There are five types of compound sentences, viz. negations, conjunctions, disjunctions, implications, and biconditionals.

A negation consists of the negation operator ¬ and an arbitrary sentence, called the target. For example, given the sentence p, we can form the negation of p as shown below.

A conjunction is a sequence of sentences separated by occurrences of the ∧ operator and enclosed in parentheses, as shown below. The constituent sentences are called conjuncts. For example, we can form the conjunction of p and q as follows.

A disjunction is a sequence of sentences separated by occurrences of the ∨ operator and enclosed in parentheses. The constituent sentences are called disjuncts. For example, we can form the disjunction of p and q as follows.

An implication consists of a pair of sentences separated by the ⇒ operator and enclosed in parentheses. The sentence to the left of the operator is called the antecedent, and the sentence to the right is called the consequent. The implication of p and q is shown below.

A biconditional is a combination of an implication and a reverse implication. For example, we can express the biconditional of p and q as shown below.

Note that the constituent sentences within any compound sentence can be either simple sentences or compound sentences or a mixture of the two. For example, the following is a legal compound sentence.

One disadvantage of our notation, as written, is that the parentheses tend to build up and need to be matched correctly. It would be nice if we could dispense with parentheses, e.g. simplifying the preceding sentence to the one shown below.

Unfortunately, we cannot do without parentheses entirely, since then we would be unable to render certain sentences unambiguously. For example, the sentence shown above could have resulted from dropping parentheses from either of the following sentences.

The solution to this problem is the use of operator precedence. The following table gives a hierarchy of precedences for our operators. The ¬ operator has higher precedence than ∧; ∧ has higher precedence than ∨; ∨ has higher precedence than ⇒; and ⇒ has higher precedence than ⇔.

In sentences without parentheses, it is often the case that an expression is flanked by operators, one on either side. In interpreting such sentences, the question is whether the expression associates with the operator on its left or the one on its right. We can use precedence to make this determination. In particular, we agree that an operand in such a situation always associates with the operator of higher precedence. The following examples show how these rules work in various cases. The expressions on the right are the fully parenthesized versions of the expressions on the left.

When an operand is surrounded by two ∧ operators or by two ∨ operators, the operand associates to the left. When an operand is surrounded by two ⇒ operators or by two ⇔ operators, the operand associates to the right.

Note that just because precedence allows us to delete parentheses in some cases does not mean that we can dispense with parentheses entirely. Consider the example shown earlier. Precedence eliminates the ambiguity by dictating that the sentence without parentheses is an implication with a disjunction as antecedent. However, this makes for a problem for those cases when we want to express a disjunction with an implication as a disjunct. In such cases, we must retain at least one pair of parentheses.

We end the section with two simple definitions that are useful in discussing Propositional Logic. A propositional vocabulary is a set of proposition constants. A propositional language is the set of all propositional sentences that can be formed from a propositional vocabulary.