• Post Reply Bookmark Topic Watch Topic
  • New Topic

can this expression be simplified any further?  RSS feed

 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have looked at a set of simplification laws for boolean expressions and I can't find one to simply it any further. I managed to simplify !(!B && (A || B)) down to B && (!A || !B). However, I can't find any simplification rules to further simplify it. I saw the rule for A && (A || B) = A, but it's not the same rule (since both A and B are negative in the expression I'm working on. Thanks!
 
Paul Clapham
Sheriff
Posts: 22509
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't think that is correct. I do think that DeMorgan's laws would be useful here:

! (A & B) = !A | !B


! (A | B) = !A & !B

 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul Clapham wrote:I don't think that is correct. I do think that DeMorgan's laws would be useful here:

! (A & B) = !A | !B


! (A | B) = !A & !B



Well I used DeMorgan's laws here and the way I did it was as follows:

!(!B && (A || B)) becomes
!!B && (!A && !B) however 2 'nots' become a positive so that becomes
B && (!A && !B) please correct me if I'm wrong // That is where I went wrong I originally put !A || !B

 
Junilu Lacar
Sheriff
Posts: 11165
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're not applying DeMorgan's Laws properly. Look at your work again and don't take shortcuts this time. Do one substitution at a time so you don't confuse yourself.
 
Paul Clapham
Sheriff
Posts: 22509
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Naziru Gelajo wrote:Well I used DeMorgan's laws here and the way I did it was as follows:

!(!B && (A || B)) becomes
!!B && (!A || !B) ...


Then that's definitely wrong. The law says !(X & Y) = !X | !Y, and you didn't apply it right.
 
Fred Kleinschmidt
Bartender
Posts: 560
9
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
!(!B && (A || B))

You should simplify the interior before applying DeMorgan's law.

Look at !B && (A || B)
This is true if "(B is false) and (either A is true or B is true)". It is then easy to see that this breaks down to "B is false, and A is true".
So then the original becomes !(!B & A). Then apply DeMorgans law on this simpler expression.
 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul Clapham wrote:
Naziru Gelajo wrote:Well I used DeMorgan's laws here and the way I did it was as follows:

!(!B && (A || B)) becomes
!!B && (!A || !B) ...


Then that's definitely wrong. The law says !(X & Y) = !X | !Y, and you didn't apply it right.


Yah I edited my original comment. I mean to put !!B && (!A && !B) which becomes B && (!A && !B) but I can't find a means to get past that. Now I'm looking at another boolean logic expression and this time it has to do with (C || B || A) && B. I can't find any laws that apply to this particular scenario. But from what I can see, There are rules that apply to two variables and definitely not 3 that have a similar structure. Please kindly correct me if I'm wrong.
 
Paul Clapham
Sheriff
Posts: 22509
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Naziru Gelajo wrote:Yah I edited my original comment. I mean to put !!B && (!A && !B) which becomes B && (!A && !B) but I can't find a means to get past that.


That was the second step in the process. It's correct, but your first step was wrong so it isn't helpful.
 
Junilu Lacar
Sheriff
Posts: 11165
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Naziru Gelajo wrote:
!(!B && (A || B)) becomes
!!B && (!A || !B) ...
...
Yah I edited my original comment. I mean to put !!B && (!A && !B) which becomes ...

!(!B && (A || B)) does NOT become !!B && (!A && !B)

You are taking shortcuts. To avoid confusion, you can do this:

Let X = !B
Let Y = (A || B)

Therefore,

!(!B && (A || B)) ==> !(X && Y)

Now, apply DeMorgan's Laws to !(X && Y). Once you have done that, substitute (!B) for X and (A || B) for Y. Then you can proceed.
 
Stephan van Hulst
Saloon Keeper
Posts: 7817
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In this case I would find it easier to first use the distributive, negation and identity laws:
P ∧ (Q ∨ R) ≡ (P ∨ Q) ∧ (P ∨ R)
P ∨ ¬P      ≡ T
P ∧ T       ≡ P

Applying DeMorgan's law afterwards becomes much simpler.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!