Exercise 10.1 Tips for Rewriting

Master / Vertiefung Künstliche Intelligenz
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Exercise 10.1 Tips for Rewriting
I figured I’d collect a couple of “standard” rewriting techniques for those who haven’t done these kinds of formula transformations before. Many of these are usually covered in the context of Boolean Algebra (The set of all formulae over a fixed set of propositional variables is a Boolean Algebra), if you’re interested to look into those things further:

I’m using “=” to stand for "is logically equivalent, because ASCII.

  1. Conjunction and Disjunctions are commutative, i.e. (A /\ B) = (B /\ A) and (A / B) = (B / A)
  2. Conjunction and Disjunctions are associative, i.e. ((A /\ B) /\ C) = (A /\ (B /\ C)) and ((A / B) / C) = (A / (B / C))
  3. and 2. together imply that the order of conjunctive or disjunctive terms don’t matter and we can ignore brackets in conjunctive/disjunctive subformulae entirely.
  4. Absorption Laws: (A /\ (A / B)) = A and (A / (A /\ B)) = A
  5. DeMorgan’s Laws: ~(A /\ B) = (~A / ~B) and ~(A / B) = (~A /\ ~B)
  6. Implications: (A → B) = ~(A /\ ~B) = (~A / B)
  7. Distributivity Laws: (A /\ (B / C)) = ((A /\ B) / (A /\ C)) and (A / (B /\ C)) = ((A / B) /\ (A / C))
  8. Tautology / Tertium Non Datur: (A / ~A) = T and hence ~~A = A
  9. Antilogy: (A /\ ~A) = F
  10. F = ~T, T = ~F, (A /\ F) = F, (A /\ T) = A, (A / F) = A, (A / T) = T

Hope that helps :slight_smile: