Atomic Formulae and Logical Connectives

• Two categories:

  • Atomic formulae: sentences with no logically relevant internal structure. They don't contain a connector.

  • Logical connectives: they serve to connect formulae in order to create new and more complex formulae. They correspond to logical operators.

    • Conjunction: and

    • Disjunction: or

    • Conditional: if... then...

    • Negation: not

• The logical connectives represent logical idealizations of the corresponding words in English.

• Logical operators are truth-functional.

• A non-atomic sentence is called a logically compound sentence, it contains atomic sentences and logical operators.

Conjunction

• "And"

  • Represented by & or ∧

• Two atomic sentences connected by a conjunction are called conjuncts.

  • A single capital letter represents each conjunct.

  • It is traditional (and purely conventional) to pick a letter that has some relationship to the corresponding sentence.

  • (J & M)

  • They must be placed inside parenthesis.

• Types of conjunctions:

  • Non-sentential conjunctions: paraphrase two sentences that are joined in order to recognize the conjunctions.

    • The cat nd the dog have been fed - The cat has been fed and the dog has been fed

  • Non-truth-functional conjunction: even if we paraphrase the two sentences, they don't make sense on their own, so the atomic sentence is the whole sentence.

    • Vanilla ice cream and chocolate syrup make a great sundae - Vanilla ice cream makes a great sundae and chocolate syrup makes a great sundae.

  • Not-just-truth-functional conjunction: the symbolizations only capture part of the overall meaning of the sentence. If the order is changed, the meaning (but not the truth-value) changes.

    • The villain jumped on the train and the villain yelled - The villain yelled and the villain jumped on the train.

• Conjuncts can be joined by other words than "and"

  • Mary likes dogs, whereas John likes cats - Mary likes dogs and John likes cats.

• &-introduction: adding the ampersand to two conjuncts.

Disjunction

• "or"

  • Represented by ∨

• The two atomic sentences joined by a disjunction are called disjuncts.

  • (J∨M)

• Types of disjunctions

  • Non-sentential disjunction: paraphrase two sentences that are joined in order to recognize the disjunts.

    • Either John or Mary laughed - Either John laughed, or Mary laughed.

  • Disjunction is always truth-functional: the paraphrase does have the same meaning as the original sentence, even though the original sentence is obviously false.

  • Ambiguity of disjunction: there can be an inclusive (one but not both) or an exclusive (true if only one of them is, false if both are true) interpretation.

• Disjunctions will only use "or", and sometimes "either... or..."

Conditional

• "If... then..."

  • Represented by →

  • Connects two sentential clauses to form a conditional sentence.

  • (J→M)

• The "if" clause is called the antecedent, the "then" clause is called the consequent.

• →-elimination or modus ponens

  • If we know that a conditional is true, and its antecedent is as well, then we can infer the truth of the consequent.

Negation

• "Not"

  • Represented by ~ or ¬

  • ¬J

• Negation is a unary connective, as it only connects one formula, while the other connectives are binary.

• Types of negation:

  • Non-sentential negations: the word "not" doesn't appear explicitly.

    • The cat is unhappy - The cat is not happy - It is not the case that the cat is happy

  • Non-truth-functional negatives: when we can't remove the prefix.

    • The cat is disturbed.

Combination of connectives

• Main connective: the top-level structure of the sentence.

  • (D∨(F&G))

  • The main connective here is a disjunction.

• The scope, or the influence, of the connector is contained within the parenthesis.

  • Scope of the conjunction: (F&G)

  • Scope of the disjunction: (D∨(F&G))

• We paraphrase sentences to reformulate them.

  • If Bob gathers eggs, then either he won't feed the chickens or he won't feed the ducks.

  • (G→(¬C∨¬D))

• Sometimes, a sentence will be ambiguous and it is impossible to tell what the structure should be.

  • It will rain and it will hail or it will snow.

  • Which can be ((R&H)vO) or (R&(HvO)).

• The word unless can also be hard to interpret.

Formal syntax

• Basic symbols of sentential logic

  • The capital letters we use to symbolize atomic sentences, called atomic formulae or occasionally sentential letters: A, B, C, and so on (possibly with numeric subscripts).

  • The symbols for the logical connectives: &, ∨, →, and ¬.

  • The parentheses used to disambiguate the scope of the connectives: ( and ).

• Expressions of sentential logic

  • Any finite sequence or string of basic symbols is an expression of sentential logic.

• We can use variables to range over expressions and not mistake them for sentential letters.

• Formulae (rules) of sentential logic

  • Every atomic formula φ is a formula of sentential logic.

  • If φ is a formula of sentential logic, then so is ¬φ.

  • If φ and ψ are formulae of sentential logic, then so are each of the following:

    • (φ&ψ)

    • (φ∨ψ)

    • (φ→ψ)

  • An expression φ of sentential logic is a formula only if it can be constructed by finitely many applications of the first three rules.

Parse trees

• A parse tree graphically represents the internal structure of an expression of sentential logic.

  • It helps to test whether or not the expression is well-formed.

• Steps to construct a parse tree

  1. Write down the entire expression. It must only contain basic symbols.

  2. Identify the general form of the expresion.

     • A sentential letter

     • A negation symbol followed by a subexpression

     • A conjunction (φ&ψ).

     • A disjunction (φ∨ψ).

     • A conditional (φ→ψ).

  • Find the top-level structure.

    • Ignore everything inside the embedded parenthesis

      • ((P∨Q)&¬(R→S)) can be seen as (()&¬()).

    • If it appears to have multiple top-level structures, it is not well-formed.

      • (()&∨())

  • Create a branch for each subexpression.

  • Continue until each branch ends in a sentential letter.

• Subformula: a formula ψ is a subformula of a formula φ if and only if ψ appears (as a node) in the parse tree of φ.

Conventions

• A convention governs a practice of doing something in one particular way, if that practice could have been done another way and still achieve its implicit goal.

  • For example, & represents a conjunction, but it could have been ∧

• Procedure for reinserting omittes parenthesis

  1. 1First, insert parentheses around every occurrence of & and its two conjuncts, starting with the rightmost & and ending with the leftmost,

  2. Next, insert parentheses in the same fashion for each ∨ and its two disjuncts, from rightmost occurrence first, to the leftmost occurrence last,

  3. Finally, insert parentheses for each →, and its antecedent and consequent, from rightmost occurrence first, to the leftmost occurrence last.

  • Parentheses are never inserted around negations

  • You should never break up existing pairs of parentheses.

Summary

• The building blocks of the language are atomic formulae and logical connectives. Atomic formulae or sentential letters are capital letters used to represent logically simple sentences.

• The logical connectives, conjunction, disjunction, the conditional, and negation, serve to join sentences together to create logically compound formulae.

• Conjunction is the connective that corresponds to the word ‘and’.

• Disjunction is the connective that corresponds to the word ‘or’.

• The conditional is the connective that corresponds to the phrase ‘if...then...’.

• Negation is the connective that corresponds to the word ‘not’.

• More complicated sentences and combinations of connectives are considered.

• The formal rules that define the syntax of sentential logic are presented.

• The notion of a parse tree is introduced, and a procedure for constructing a parse tree is provided that allow us to decide (in finitely many steps) whether or not an expression is a formula.

• Syntactic conventions, including choices of symbols and omission of parentheses, are discussed.

Must-know definitions

• Basic symbols of sentential logic

• Expressions of sentential logic

• Formulae of sentential logic

• Parse tree construction rules

• Subformula

• Procedure for reinserting omitted parenthesis

New terms