My Math Forum Equivalence of boolean expressions
 User Name Remember Me? Password

 Applied Math Applied Math Forum

 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:
 Originally Posted by Sokrates I guess only "literals" means that there are no parentheses that are negated.
Yes. All you can have is either a single variable ("c" or "a", for example).

Quote:
 Originally Posted by Sokrates But I don't manage to get from f1 or f2 to f3 or f4.
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

Quote:
 Originally Posted by CRGreathouse Take either f3 or f4 and put it into DNF.
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
Quote:
 Originally Posted by Sokrates Ok, when I do that I get to the following: $a'c \vee b'c \vee ad'\\$
What did you derive this from?

September 12th, 2014, 09:50 AM   #8
Newbie

Joined: Sep 2014
From: Ancient Greece

Posts: 10
Thanks: 0

Quote:
 Originally Posted by CRGreathouse What did you derive this from?
From f3.

 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?

 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top