2.2 Well-Formed Formulas and Translation

Well-formed formulas (WFFs) are the building blocks of propositional logic. They're constructed using atomic propositions, logical connectives, and parentheses, following specific rules to ensure syntactic correctness.

Translating natural language into propositional logic involves assigning atomic propositions to simple statements and using connectives to combine them. Understanding the main connective and logical structure of WFFs is crucial for evaluating truth values and constructing proofs.

Well-Formed Formulas (WFFs) in Propositional Logic

Definition of well-formed formulas

Top images from around the web for Definition of well-formed formulas

• 

  logic - Playing with propositional truth-tables - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Propositional Logic Proof using I.P. or C.P or rules of inference - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  logic - Playing with propositional truth-tables - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Propositional Logic Proof using I.P. or C.P or rules of inference - Mathematics Stack Exchange View original

  Is this image relevant?

1 of 2

Top images from around the web for Definition of well-formed formulas

• 

  logic - Playing with propositional truth-tables - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Propositional Logic Proof using I.P. or C.P or rules of inference - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  logic - Playing with propositional truth-tables - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Propositional Logic Proof using I.P. or C.P or rules of inference - Mathematics Stack Exchange View original

  Is this image relevant?

1 of 2

• Syntactically correct formula in propositional logic follows set of rules that determine structure and composition
• Constructed using:
  • Atomic propositions ($p$, $q$, $r$)
  • Logical connectives ($\neg$ negation, $\wedge$ conjunction, $\vee$ disjunction, $\rightarrow$ implication, $\leftrightarrow$ biconditional)
  • Parentheses for grouping and clarifying order of operations
• Rules for constructing:
  1. Atomic proposition is a WFF
  2. If $\phi$ is a WFF, then $\neg\phi$ is also a WFF
  3. If $\phi$ and $\psi$ are WFFs, then $(\phi \wedge \psi)$, $(\phi \vee \psi)$, $(\phi \rightarrow \psi)$, and $(\phi \leftrightarrow \psi)$ are also WFFs
  4. Only formulas constructed using above rules are considered WFFs

Well-formed vs ill-formed formulas

• Well-formed formulas follow rules for constructing WFFs in propositional logic ($p$, $\neg q$, $(p \wedge q)$, $((p \vee q) \rightarrow r)$)
• Ill-formed formulas violate one or more rules for constructing WFFs
  • May have mismatched parentheses, missing operands, or incorrect use of connectives ($\neg$, $(p \vee q$, $p \wedge \vee q$)

Translation and Logical Structure

Translation into propositional logic

• Assign atomic propositions to simple declarative sentences ("It is raining" can be $p$)
• Use logical connectives to combine atomic propositions based on relationships expressed in natural language statement
  • Negation ($\neg$): "It is not raining" can be $\neg p$
  • Conjunction ($\wedge$): "It is raining and it is cold" can be $(p \wedge q)$, where $q$ represents "It is cold"
  • Disjunction ($\vee$): "It is raining or it is cold" can be $(p \vee q)$
  • Implication ($\rightarrow$): "If it is raining, then the streets are wet" can be $(p \rightarrow r)$, where $r$ represents "The streets are wet"
  • Biconditional ($\leftrightarrow$): "It is raining if and only if there are clouds in the sky" can be $(p \leftrightarrow s)$, where $s$ represents "There are clouds in the sky"

Main connectives and logical structure

• Main connective is last connective applied when evaluating truth value of WFF, typically outermost connective not enclosed in parentheses
  • In $((p \wedge q) \vee r)$, main connective is $\vee$
• Identifying main connective helps determine logical structure of WFF
• Logical structure of WFF can be represented using parentheses and order of connectives
  • $((p \wedge q) \vee r)$ has structure: (conjunction) $\vee$ (atomic proposition)
• Understanding logical structure helps in evaluating truth value of WFF and constructing proofs