September 11th, 2014, 12:34 PM  #1 
Newbie Joined: Sep 2014 From: Ancient Greece Posts: 10 Thanks: 0  Equivalence of boolean expressions
How can we algebraically show that these boolean expressions are equivalent? $f_{1} = a'c' \vee c'd \vee ab'd\\ f_{2} = ((a'c')'(c'd)'(ab'd)')'\\ f_{3} = (a \vee c')(b' \vee c')(a' \vee d)\\ f_{4} = ((a\vee c')'\vee (b'\vee c')'\vee (a'\vee d)')'$ The following laws might help: $ab=ba\\ a(b\vee c)=ab\vee ac\\ a\vee ab=a\\ a\vee b=b\vee a\\ a\vee (bc)=(a\vee b)(a\vee c)\\ a(a\vee b)=a$ I've been trying to manipulate these expressions using these laws for hours but I'm quite stuck. Could someone please help? 
September 12th, 2014, 06:02 AM  #2 
Newbie Joined: Sep 2014 From: Ancient Greece Posts: 10 Thanks: 0 
I don't know why I posted this in "Applied Math", maybe it would suit better in another forum. If so, please move it. Anyway, help is appreciated. I managed to see that f3 and f4 are equivalent, so it remains to show how one of them is equivalent to f1 and f2. 
September 12th, 2014, 06:26 AM  #3 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms 
Use DNF. Expand all the NOTs with the DeMorgan laws until they appear only on literals (a, b, c, d) and then expand until all you have is (strings of literals or negated literals ANDed together) which are ORed together. $f_1$ is already in this form, so you need only do this to the others. If you get stuck, show how far you got in the process. 
September 12th, 2014, 08:08 AM  #4 
Newbie Joined: Sep 2014 From: Ancient Greece Posts: 10 Thanks: 0 
Ok, following your instructions it was quite easy to show that f1 and f2 are equivalent. And as I said before I also saw how f3 and f4 are equivalent. The rest seems harder though. I guess only "literals" means that there are no parentheses that are negated. I know how to remove those. But I don't manage to get from f1 or f2 to f3 or f4. They just seem to have different structure altogether. For example we have a'c', c'd and ab'd "together" in f1 and f2, while in f3 and f4 it's rather aVc', b'Vc' and a'Vd that are together. I don't see how they can be made equal when they are so different. Last edited by Sokrates; September 12th, 2014 at 08:13 AM. 
September 12th, 2014, 08:23 AM  #5  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Quote:
Take either f3 or f4 and put it into DNF.  
September 12th, 2014, 08:37 AM  #6 
Newbie Joined: Sep 2014 From: Ancient Greece Posts: 10 Thanks: 0  Ok, when I do that I get to the following: $a'c \vee b'c \vee ad'\\$ Do you mean like this? What's next? Last edited by Sokrates; September 12th, 2014 at 09:35 AM. 
September 12th, 2014, 09:46 AM  #7 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  
September 12th, 2014, 09:50 AM  #8 
Newbie Joined: Sep 2014 From: Ancient Greece Posts: 10 Thanks: 0  
September 12th, 2014, 12:34 PM  #9 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms 
So f3 and f1 are not the same, since you can't get from one to the other by reordering terms or factors. (That's the nice thing about DNF.) A quick check shows that they differ when a, b, and d are false and c is true. 
September 12th, 2014, 12:43 PM  #10 
Newbie Joined: Sep 2014 From: Ancient Greece Posts: 10 Thanks: 0 
Hm? In the task it says "Show (algebraically, using the that the laws that I wrote in the first post) that the following function expressions f1 to f4 are equivalent". How is that possible then?


Tags 
boolean, equivalence, expressions 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Boolean conjunction  calvinleeabc  Algebra  1  October 23rd, 2013 03:14 AM 
Boolean Questions  rhymin  Applied Math  0  April 17th, 2013 08:48 AM 
Boolean Algebras  Hooman  Abstract Algebra  1  December 18th, 2012 12:38 PM 
Simple boolean expressions  gregnolan  Applied Math  2  October 13th, 2009 10:23 PM 
Boolean Algebra  MoZ  Applied Math  8  January 28th, 2009 05:29 PM 