Not logged in. · Lost password · Register

 Member since Oct 2016 803 posts 2019-01-11, 11:43   #1   Subject: 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)) 1. 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. 3. Absorption Laws: (A /\ (A \/ B)) = A and (A \/ (A /\ B)) = A 4. DeMorgan's Laws: ~(A /\ B) = (~A \/ ~B) and ~(A \/ B) = (~A /\ ~B) 5. Implications: (A -> B) = ~(A /\ ~B) = (~A \/ B) 6. Distributivity Laws: (A /\ (B \/ C)) = ((A /\ B) \/ (A /\ C)) and (A \/ (B /\ C)) = ((A \/ B) /\ (A \/ C)) 7. Tautology / Tertium Non Datur: (A \/ ~A) = T and hence ~~A = A 8. Antilogy: (A /\ ~A) = F 9. F = ~T, T = ~F, (A /\ F) = F, (A /\ T) = A, (A \/ F) = A, (A \/ T) = T Hope that helps
Close Smaller – Larger + Reply to this post:
Verification code: Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys:
Special characters:
Go to forum
Datenschutz | Kontakt