OLI - 2. Syntax and symbolization

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