Logic

Why is the order of applying α- and β-rules in CNF expansion irrelevant?

Consider any two expansion rules applied in any order and prove they produce the same result and because of CNF/DNF duality we shall only consider CNF.

Case 1: α + α′ in same clause. [α, α′, Z] => [α1​,α′,Z], [α2​,α′,Z] => [α1​,α′1​,Z], [α1​,α′2​,Z], [α2​,α′1​,Z], [α2​,α′2​,Z].

Case 2: α + β in same clause. [α, β, Z] => [α₁, β, Z], [α₂, β, Z] => [α₁, β₁, β₂, Z], [α₂, β₁, β₂, Z].

Case 3: β + β' in same clause. [β, β′, Z] => [β₁, β₂, β′, Z] => [β₁, β₂, β′₁, β′₂, Z].

Case 4: α + α′ in different clauses. [α, Z], [α′, Z′] => [α₁, Z], [α₂, Z], [α′₁, Z′], [α′₂, Z′].

Case 5: α + β in different clauses. [α, Z], [β, Z′] => [α₁, Z], [α₂, Z], [β₁, β₂, Z′].

Case 6: β + β′ in different clauses. [β, Z], [β′, Z′] => [β₁, β₂, Z], [β′₁, β′₂, Z′].

Argue that the secondary connective ≡ is neither an α nor β-formula?

This connective is neither an α nor β-formula because it represents mutual implication, not one of the eight basic binary connectives that define α/β forms in tableau rules.

What is the Idempotence rule?

1. X ∨ X = X.
2. X ∧ X = X.

What is the Double negation rule?

1. X = ¬¬X.

What is the Replacing implication rule?

1. X → Y = ¬X ∨ Y.

What is the Commutativity rule?

1. X ∧ Y = Y ∧ X.
2. X ∨ Y = Y ∨ X.

What is the Associativity rule?

1. (X ∧ Y) ∧ Z = X ∧ (Y ∧ Z).
2. (X ∨ Y) ∨ Z = X ∨ (Y ∨ Z).

What are De Morgan's Laws?

1. ¬(X ∨ Y) = ¬X ∧ ¬Y.
2. ¬(X ∧ Y) = ¬X ∨ ¬Y.

What is the Distributivity rule?

1. X ∧ (Y ∨ Z) = (X ∧ Y) ∨ (X ∧ Z).
2. X ∨ (Y ∧ Z) = (X ∨ Y) ∧ (X ∨ Z).

What is the Exportation rule?

1. (X ∧ Y) → Z = X → (Y → Z)

What is the Absorption Law?

1. X → Y = X → (X ∧ Y).

What is the Contradiction rule?

1. (X → Y) ∧ (X → ¬Y) = ¬X