Propositional Logic: Syntax and Semantics

• A proposition is a declarative statement that can be either true or false.
• Examples of propositions include "The earth is a planet" and "The sun is a star."
• Propositions that cannot be broken down into simpler propositions are called elementary or atomic.
• A proposition can be affirmative or negative, such as "The earth is round" versus "The earth is not round."
• Complex propositions combine elementary propositions, with the truth value determined by the truth values of each elementary proposition.
• Paradoxes are declarative statements whose truth cannot be determined.
• Example: "This sentence is false".

Propositional Language

• A language, whether formal or natural, is characterized by its syntax and semantics.

Syntax of Propositional Language

• Formulas are written using symbols from an alphabet according to well-defined writing rules.

The Alphabet

• The propositional language alphabet includes:
  • Propositional variables represented by capital letters (e.g., P, Q, P1, P2).
  • Logical connectives: ¬ (negation), ∧ (conjunction), ∨ (disjunction), → (implication), ↔ (biconditional).
  • Parentheses: "(", ")".

Writing Rules

• In the following rules, Greek letters are used to represent formulas.
  • Any propositional variable is a formula (atomic).
  • If α is a formula, then (α) is a formula.
  • If α is a formula, then ¬α is a formula.
  • If α and β are formulas, then α ∧ β, α ∨ β, α → β, α ↔ β are formulas.
  • No other expression is a formula.

Definitions

• An atomic formula denotes a propositional variable.
• A literal denotes an atomic formula or its negation (e.g., P, ¬P).
• Two literals are complementary if one is the negation of the other.

Precedence of Connectives

• Formulas are simplified by introducing precedence rules between connectives.
• The order of application is: ¬, ∧, ∨, →, ↔, from left to right.
• E.g., P → Q → R is interpreted as (P → Q) → R, and P ∧ Q ∨ R as (P ∧ Q) ∨ R.

Subformulas

• Subformulas can be derived from writing rules.
• The set S(α) of subformulas of a formula α can be defined as follows:
  • If α is a formula, then α ∈ S(α).
  • If α = ¬β, then β ∈ S(α).
  • If α = β1 op β2 where op ∈ {∧, ∨, →, ↔}, then β1, β2 ∈ S(α).
• ExamplE:
  • For α = P ∨ ¬Q → P,
  • S(α) = {P ∨ ¬Q → P, P ∨ ¬Q, P, ¬Q, Q}.

Semantics of Propositional Language

• The semantics aims to assign a truth value to formulas in a propositional language, using a truth function or valuation v: {V, F}n → {V, F} for a formula α with n propositional variables.

• The function v can be defined as follows:

  • v(P) = V or F for any propositional variable P.
  • The valuation of ¬β depends on the valuation of β
    • V if v(β) = F
    • F if v(β) = V

• The valuation of α and β depends on the valuation of both independantly - V if both v(α) = V and v(β) = V - F otherwise

• The valuation of α or β depends on the valuation of both independantly - F if both v(α) = F or v(β) = F - V otherwise

• The valuation of α -> β depends on the valuation of both independantly - V if either v(α) = F or v(β) = V - F otherwise

• The valuation of α <-> β depends on the valuation of both independantly - V if ν(α) = ν(β) - F otherwise

• For a formula α with n distinct propositional variables, there are 2n valuation functions, represented in a truth table.

• The table indicates the truth value of α for each valuation vi.

Satisfiability of a Formula and a Set of Formulas

• A valuation v satisfies a formula α if, after assigning truth values to the propositional variables of α, the truth value of α is V (v(α) = V).
• Written as v |= α. If v does not satisfy α, it is written as v |≠ α.
• A formula α is satisfiable if there exists at least one valuation v such that v |= α; otherwise, it is unsatisfiable.
• A valuation v satisfies a set of formulas Γ = {α1, ..., αn} if v satisfies all formulas in Γ (v |= α1 and v |= α2 and ... and v |= αn); in this case, v corresponds to a row in the truth table where the truth values of α1, ..., αn are all V.
• EXample The set { P ∧ Q, P ∨ Q, P → Q, P ↔ Q } is satisfiable, while the set { P ∧ Q, P ∨ Q, P → Q, P ↔ Q, ¬P } is unsatisfiable.

Tautology

• A formula α is a tautology (denoted |= α) if v |= α for every valuation v.

Logically Equivalent Formulas

• Two formulas α and β are logically equivalent if v(α) = v(β) for every valuation v; in this case, α ↔ β.

Properties of Logical Connectives

• Commutativity of ∨ and ∧:
• α ∨ β = β ∨ α
• α ∧ β = β ∧ α
• Associativity of ∨ and ∧:
• (α ∨ β) ∨ γ = α ∨ (β ∨ γ)
• (α ∧ β) ∧ γ = α ∧ (β ∧ γ)
• Distributivity of ∨, ∧, etc.:
  • α ∨ (β ∧ γ) = (α ∨ β) ∧ (α ∨ γ)
  • α ∧ (β ∨ γ) = (α ∧ β) ∨ (α ∧ γ)
• Idempotence:
  • α ∨ α = α
  • α ∧ α = α
• De Morgan's Laws:
  • -(α ∨ β) = -α ∧ -β
  • -(α ∧ β) = -α ∨ -β
• α = - - α

Logical Consequence

• A formula β is a logical consequence of a formula α (denoted α |= β) if for every valuation v, if v |= α, then v |= β. In the truth table, the truth value of β is V in all rows where the truth value of α is V.
• More generally, a formula β is a logical consequence of a set of formulas Γ = {α1, α2, ..., αn} (denoted α1, ..., αn |= β or simply Γ |= β) if: for every v, if v |= α1 and v |= α2 and ... and v |= αn, then v |= β.
• EXample: P → Q, ¬Q |= ¬P.
• EXAMPLE negation isn't always a logical consequence P→Q, ¬P, therefore is not |= ¬Q

Theorems

• Γ |= β if and only if Γ ∪ {¬β} is not satisfiable.

• If Γ |= β and Γ |= ¬β, then Γ is not satisfiable.

Theorem of Substitution

• If β is a formula containing the propositional variable P, and β' is obtained by substituting a formula α for all occurrences of P in β, then if |= β, then |= β'.

Theorem of Replacement

• If α is a formula containing β, and α' is obtained by replacing one or more occurrences of β by β', then if |= β' ↔ β, then |= α' ↔ α.

Complete System of Connectives

• A set S of connectives is complete if for every formula α, there exists a formula α' using only connectives from S such that |= α' ↔ α.

Connectives of Sheffer

• There exist two complete sets of connectives, each formed by a single connective.

Disjunctive and Conjunctive Normal Forms

• A formula α is in disjunctive normal form (DNF) if it is of the form M1 ∨ M2 ∨ ... ∨ Mn, where each M is of the form L1 ∧ L2 ∧ ... ∧ Ln, and each Li is either a literal Pi or ¬Pi.
• A formula α is in conjunctive normal form (CNF) if it is of the form C1 ∧ C2 ∧ ... ∧ Cn, where each Ci is of the form L1 ∨ L2 ∨ ... ∨ Ln.
• For every formula α, there exists a formula α' in DNF (or CNF) such that |= α'↔α.