2.1 Syntax and formation rules of propositional logic

Propositional logic forms the foundation of formal reasoning. It uses symbols and connectives to represent and manipulate statements that can be true or false. Understanding its syntax is crucial for building more complex logical structures.

The syntax of propositional logic defines how formulas are constructed. It introduces propositional variables, logical connectives, and rules for combining them into well-formed formulas. This framework allows us to express and analyze complex logical relationships.

Propositional Formulas

Propositional Variables and Atomic Formulas

Top images from around the web for Propositional Variables and Atomic Formulas

• 

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

  Is this image relevant?

• 

  propositional logic define propositional symbols using sheffer stroke - 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?

• 

  propositional logic define propositional symbols using sheffer stroke - Mathematics Stack Exchange View original

  Is this image relevant?

1 of 2

Top images from around the web for Propositional Variables and Atomic Formulas

• 

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

  Is this image relevant?

• 

  propositional logic define propositional symbols using sheffer stroke - 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?

• 

  propositional logic define propositional symbols using sheffer stroke - Mathematics Stack Exchange View original

  Is this image relevant?

1 of 2

• Propositional variables are symbols that represent propositions or statements that can be either true or false (p, q, r)
• Atomic formulas consist of a single propositional variable and cannot be broken down into simpler formulas
• Serve as the basic building blocks for constructing more complex formulas in propositional logic
• Each propositional variable is considered an atomic formula (p, q, r are atomic formulas)

Compound Formulas and Well-Formed Formulas

• Compound formulas are formed by combining one or more atomic formulas using logical connectives
• Can be broken down into simpler formulas, unlike atomic formulas
• Well-formed formulas (WFFs) are formulas that are constructed according to the syntax rules of propositional logic
• WFFs are defined recursively:
  • Every atomic formula is a WFF
  • If $\phi$ and $\psi$ are WFFs, then $(\neg \phi), (\phi \land \psi), (\phi \lor \psi), (\phi \rightarrow \psi),$ and $(\phi \leftrightarrow \psi)$ are also WFFs
• Examples of well-formed formulas: $(p \land q), (\neg p \lor (q \rightarrow r))$

Logical Connectives and Notation

Logical Connectives

• Logical connectives are symbols used to combine propositional formulas to create compound formulas
• The main logical connectives in propositional logic are:
  • Negation ($\neg$): represents the negation or opposite of a proposition
  • Conjunction ($\land$): represents the logical AND, connecting two propositions that must both be true for the compound formula to be true
  • Disjunction ($\lor$): represents the logical OR, connecting two propositions where at least one must be true for the compound formula to be true
  • Implication ($\rightarrow$): represents a conditional statement, where the truth of the second proposition depends on the truth of the first proposition
  • Biconditional ($\leftrightarrow$): represents a bi-directional implication, where both propositions must have the same truth value for the compound formula to be true
• Examples of compound formulas using logical connectives: $(\neg p), (p \land q), (p \lor q), (p \rightarrow q), (p \leftrightarrow q)$

Parentheses, Infix Notation, and Precedence Rules

• Parentheses are used to group propositional formulas and specify the order of operations
• Infix notation places the logical connectives between the propositional variables or formulas they connect
• Precedence rules determine the order in which logical connectives are evaluated when parentheses are not used:
  • Negation ($\neg$) has the highest precedence
  • Conjunction ($\land$) and disjunction ($\lor$) have the next highest precedence and are evaluated from left to right
  • Implication ($\rightarrow$) and biconditional ($\leftrightarrow$) have the lowest precedence and are evaluated from right to left
• Examples demonstrating precedence rules: $p \land q \lor r$ is equivalent to $(p \land q) \lor r$, while $p \rightarrow q \lor r$ is equivalent to $p \rightarrow (q \lor r)$