Not logged in. · Lost password · Register

Jazzpirate
Member since Oct 2016
770 posts
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: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen