My Math Forum Equivalence of boolean expressions

 Applied Math Applied Math Forum

 September 15th, 2014, 06:41 AM #11 Member   Joined: Aug 2014 From: Somewhere between order and chaos Posts: 44 Thanks: 5 Math Focus: Set theory, abstract algebra, analysis, computer science The fail-proof way to show that two Boolean expressions are equivalent is to construct truth tables for both of them. If the truth tables are the same, then they are equivalent. EDIT: Sorry, missed the part about doing it algebraically.
September 15th, 2014, 07:08 AM   #12
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 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?
If they're different it's not possible. Trick question, typo in the problem, you typed it out wrong, or I made a mistake -- take your pick. I did give a way to verify that the two are different, and you should check that to your satisfaction.

 September 17th, 2014, 09:29 AM #13 Newbie   Joined: Sep 2014 From: Ancient Greece Posts: 10 Thanks: 0 I discovered a solution, so I thought that I would share it here, maybe someone else will also find it useful. Starting with $f_{3} = (a \vee c')(b' \vee c')(a' \vee d)$ Using the distributive law $a\vee (bc)=(a\vee b)(a\vee c)$ We get $(a \vee c')(b' \vee c')(a' \vee d)= (c' \vee ab')(a' \vee d)$ Then multiplying out the parantheses, we get $(c' \vee ab')(a' \vee d)=a'c' \vee c'd \vee aa'b' \vee ab'd$ In the above expression we have the term $aa'b'$ and since $aa'=0$ it can be removed. So then we have left $a'c' \vee c'd \vee ab'd$ Which equals $f1$. Last edited by Sokrates; September 17th, 2014 at 09:35 AM.
September 18th, 2014, 11:47 AM   #14
Newbie

Joined: Sep 2014
From: Ancient Greece

Posts: 10
Thanks: 0

Quote:
 Originally Posted by CRGreathouse So f3 and f1 are not the same
CRGreathouse: Care to comment?

Last edited by Sokrates; September 18th, 2014 at 11:59 AM.

September 18th, 2014, 12:55 PM   #15
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 CRGreathouse: Care to comment?
I gave conditions under which f1 and f3 differ. Anyone interested can check the functions at those points. If the functions are the same at those points then I was mistaken (in proof if not conclusion). If they differ then the simplification is wrong. It doesn't mean much to me either way, this is just a 1-off problem.

 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