My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Thanks Tree1Thanks
Reply
 
LinkBack Thread Tools Display Modes
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?
Sokrates is offline  
 
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.
Sokrates is offline  
September 12th, 2014, 06:26 AM   #3
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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.
Sokrates is offline  
September 12th, 2014, 08:23 AM   #5
Global Moderator
 
CRGreathouse's Avatar
 
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 View Post
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 View Post
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.
Thanks from Sokrates
CRGreathouse is offline  
September 12th, 2014, 08:37 AM   #6
Newbie
 
Joined: Sep 2014
From: Ancient Greece

Posts: 10
Thanks: 0

Quote:
Originally Posted by CRGreathouse View Post
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.
Sokrates is offline  
September 12th, 2014, 09:46 AM   #7
Global Moderator
 
CRGreathouse's Avatar
 
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 View Post
Ok, when I do that I get to the following:

$a'c \vee b'c \vee ad'\\$
What did you derive this from?
CRGreathouse is offline  
September 12th, 2014, 09:50 AM   #8
Newbie
 
Joined: Sep 2014
From: Ancient Greece

Posts: 10
Thanks: 0

Quote:
Originally Posted by CRGreathouse View Post
What did you derive this from?
From f3.
Sokrates is offline  
September 12th, 2014, 12:34 PM   #9
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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?
Sokrates is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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





Copyright © 2019 My Math Forum. All rights reserved.