Sentential Logic and Well-Formed Formulas

In this section, you will read about how formal systems of logic work and what they are useful for. You will first be introduced to the elements of a simple system of logic called SL, and then you will learn how to construct statements, called well-formed formulas (WFFs), in SL. 

Complete the exercises and check your answers.

Sentential Logic

In formal logic, we develop different systems of symbols and rules to express ideas and carry out proofs. There are lots of such formal systems. In this module we discuss Sentential Logic (SL). It is one of the simplest formal systems of logic, and is also known as Propositional Logic.

Before you begin, please check that your browser can display the logic symbols used in this module.

These are the symbols:

≡ ∨ ↔ → ∃ ∀ ψ φ α β ⊧

They should look like the ones in this picture:

§1. Formal Systems of Logic

Sentential logic (SL) is a formal system of logic. It is a simple system of logic. When people study formal logic this is usually the first thing that they would study. Other more complicated systems include for example predicate logic (PL), and modal logic.

So what is a system of logic? Basically, it is a set of rules that tell us how to make use of special symbols to construct sentences and do proofs. To define a particular system of logic, we need to specify:

  1. The formal language of the system.
  2. The semantic rules for the formal language.
  3. The rules of proof for the language.

A formal language in a system of logic is a language with precisely specified rules that tell us how to construct grammatical sentences. Such rules are called syntactic rules. They are equivalent to the rules of grammar you find in English or Cantonese.

The semantic rules are rules for interpreting the sentences in the language. They tell us what the sentences mean and the conditions under which the sentences are true or false.

The rules of proof are rules that specify how logical proofs are to be constructed. They tell us what conclusions can be derived given certain initial assumptions.

§2. Why Study Formal Systems of Logic?

There are many reasons for creating and studying such formal systems of logic:

    • Systems of logic can be used to formalize arguments in natural languages. A natural language is a language that is used for normal everyday communication in a human society. So languages such as Japanese, Irish, and French are all natural languages. By formalization we refer to the process of translating arguments or sentences in natural languages into the notations of formal logic. The reason for carrying out formalization is that very often they can help us understand the logical structure of arguments better, by identifying patterns of valid arguments. Also, the rules of proof in a formal system of logic are precisely specified. By formalizing an argument we can use the rules of proof to check whether the argument can indeed be proved to be valid.

    • Because the rules of formal systems of logic are defined clearly, we can program them into a computer and get a computer to construct and evaluate proofs quickly and automatically. This is particularly important in areas such as Artificial Intelligence, where many researchers teach computers to use formal logic in reasoning.

    • Linguists are scientists who study natural languages. Many linguists also study formal languages and use them to compare and contrast with natural languages.

    • Many philosophers are also interested in formal systems of logic. One reason is that natural languages are sometimes not precise enough to express certain ideas clearly. So sometimes they turn to formal systems of logic instead.

    • Formal systems of logic are also interesting in their own right. Logicians and mathematicians are interested in finding out what they can or cannot prove, and also their many other logical properties. Formal systems of logic also play an important role in understanding the foundations of set theory and mathematics.

§3. The Language of SL

To define the language of SL, we need to specify the symbols or the vocabulary of SL. These are the basic building blocks out of which more complicated expressions are to be constructed. There are three kinds of symbols in SL:

1. Sentence letters: A, B, C, etc. These capital letters are used to translate sentences. If we run out of sentence letters we can always add subscripts to them to make new ones, e.g. A1, B274, etc...

2. Five sentential connectives:

      ~ (tilde, or the negation sign)
      & (ampersand, or the conjunction sign)
      ∨ (the wedge, or the disjunction sign)
      → (the arrow)

      ↔ (the double-arrow)

3. Open and close brackets: ( )

§4. Construction of WFFs

The set of sentence letters, connectives, and brackets constitutes the set of symbols of SL. An expression of SL is simply any string of one or more symbols of SL:

  1. ABCDF&&&&(())))→ABCB12356A
  2. P
  3. (P&Q)
  4. ~~(P&Q))

Now we come to syntax, the rules that tell us which of the expressions of SL are grammatical, and which are not. A grammatical expression is called a well-formed formula (WFF). A WFF of SL is any expression of SL that can be constructed according to these rules of formation:

Rules of formation for SL

  1. All sentence letters are WFFs.
  2. If φ is a WFF, then ~φ is a WFF.
  3. If φ and ψ are WFFs, then (φ&ψ), (φvψ), (φ→ψ), (φ↔ψ) are also WFFs.
  4. Nothing else is a WFF.

Some comments on these rules:

    • The first rule tells us that symbols such as "A," "B," "C" are all WFFs.

    • "φ" in rule two is a Greek symbol, which nowadays is pronounced by many English speakers as "phi" (as in "Hifi"). (Note: this is probably not the correct ancient Greek pronunciation!) It is a variable that stands for any arbitrary thing. What rule two tells us is that whatever φ is, if it is a WFF, then when you add "~" to the front of φ you will end up with a new and longer WFF. So from rule 1, we know that "A" is a WFF. Then we can apply rule two to "A" to infer that "~A" is also a WFF. If we apply rule two again, then we can see that "~~A" is also a WFF.

    • "ψ" in rule three is a Greek symbol pronounced as "psi" (as in "psychology"). It is also a variable. Consider the formula "(P&~P)". This is a WFF because "P" is a WFF according to rule 1, so "~P" is also a WFF. Combining them according to rule three then, "(P&~P)" is also a WFF.

    • However, even though "~P" is a WFF, "(~P)" is not, because as we can see from rule three, any WFF that contains a pair of brackets must have at least one of the four other connectives inside.

    • As you can see, the negation sign always connect to one single WFF to make a longer WFF, and is called a one-place connective. Whereas all other connectives connect two WFFs to make a new one and are called binary or two-place connectives. Notice that all these connectives combine with WFFs to make new WFFs. A WFF is like a sentence which is why these connectives are called “sentential connectives.”

Exercise #1

Exercise #2

§5. Grammatical Categories

Here are some useful terms for talking about WFFs and their parts. If φ and ψ are WFFs, then:

    • (φ&ψ) is a conjunction where φ and ψ are the first and second conjunct respectively.
    • (φvψ) is a disjunction where φ and ψ are the two disjuncts.
    • (φ→ψ) is a conditional sentence where φ is the antecedent and ψ the consequent. Note that it is a mistake to say that ψ is the conclusion as this conditional sentence need not be an argument.
    • (φ↔ψ) is a biconditional sentence.
    • ~φ is the negation of φ.

So for example:

    • (P&Q) is a conjunction.
    • ((P&Q)∨(R↔Q)) is a disjunction.
    • ~(P→(Q∨S)) is the negation of (P→(Q∨S)).
    • ~(P&Q) is the antecedent of (~(P&Q)→((P&S)↔Q)).

§6. Scope

By the scope of a connective α in a WFF φ we mean the shortest WFF in φ that contains α. Examples:

  1. The scope of “&” in “~(P&Q)” is “(P&Q).” “&” is of course contained in the whole WFF, but it is not the shortest WFF that contains it. “&Q” is a shorter expression that contains “&” but it is not a WFF.
  2. The scope of “&” in “(~(~P&Q)→P)” is “(~P&Q).”

§7. Main Connective

The main connective in a WFF φ is the connective that has the widest scope. Here are some examples where the main connectives are highlighted in red:

  1. ~(P&Q)
  2. ~~~(P&Q)
  3. ~(~P&(P&Q))
  4. (~(~P&Q)P)
  5. ~(~(~P&Q)↔P)
  6. ((~M&N)&R)
  7. (~(~M&N)&R)

You will probably realize that we can use the main connective of a WFF to define whether it is a negation, a biconditional or a conditional, a disjunction or a conjunction.

Exercise #3

Source: Joe Lau and Jonathan Chan,
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 License.

Last modified: Tuesday, September 10, 2019, 6:02 PM