Propositional Logic: Syntax and Semantics

Syntax Review (Morning Session)

Key concepts covered:

• BNF rules that define when a formula is valid
• Syntax trees and their relationship to propositional logic formulas
• Bracketing rules to minimize the number of brackets in formulas

Semantics of Propositional Logic

What is Semantics?

Semantics assigns meaning to propositional logic formulas. It determines whether a formula evaluates to true or false.

<aside> 💡

The meaning of a formula depends on the assignment of truth values to its propositional variables.

</aside>

Truth Values

• Propositional logic formulas can only have two possible values: true or false
• We define a set called the truth space: 𝔹 = {true, false}
• Semantics is a function that maps formulas to this truth space: F → 𝔹

Truth Tables for Logical Operators

Bottom (⊥)

• Always evaluates to false (constant)
• No propositional variables involved