 Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki Blog Search Turing Chat Room Members
Abit of help simplifying this boolean statement?       Author Message
Macmee Posted: Sun Sep 23, 2012 10:54 am   Post subject: Abit of help simplifying this boolean statement?

Hi!

I'm attempting to simplify this boolean function by hand (for a discrete structures course):

(P ∧ Q ∧ R) ∨ (~P ∧ Q ∧ R) ∨ (~P ∧ (~Q ∨ ~R)

I know I can turn that into:

(P ∧ Q ∧ R) ∨ (~P ∧ Q ∧ R) ∨ (~P ∧ ~Q) ∨ (~P ∧ ~R)

and then combine (P ∧ Q ∧ R) and (~P ∧ ~Q) but the problem is I then get 6 different statements and if I keep combining things I just end up with a crazy amount of statements.

I was wondering if there's a smarter way to go about simplifying large boolean statements as such then just combining everything and hoping you combined things in such a way that things cancel out. Sponsor
Sponsor   evildaddy911 Posted: Sun Sep 23, 2012 11:51 am   Post subject: RE:Abit of help simplifying this boolean statement?

can you explain what you mean by ^, v and ~? Macmee Posted: Sun Sep 23, 2012 12:10 pm   Post subject: RE:Abit of help simplifying this boolean statement?

My apologies:

~ = not / negation
^ = and / conjunction
∨ = or / disjunction Insectoid  Posted: Sun Sep 23, 2012 12:18 pm   Post subject: RE:Abit of help simplifying this boolean statement?

Well, first of all you've got (P^Q^R)v(~P^Q^R), which can be solved with common sense. The second part is a little trickier, and I don't have time to explain it right now. evildaddy911 Posted: Sun Sep 23, 2012 12:46 pm   Post subject: RE:Abit of help simplifying this boolean statement?

~X^~Y = X ~v Y; you can apply this twice right now viperfan7 Posted: Mon Mar 18, 2013 1:51 pm   Post subject: Re: Abit of help simplifying this boolean statement?

Necro post but no one posts in here as it is, so why not do something

Well using truth tables I got it down to ~P v (Q ^ R)

Table for
(P ∧ Q ∧ R) ∨ (~P ∧ Q ∧ R) ∨ (~P ∧ (~Q ∨ ~R)
 code: P | Q | R | OUT | (P ^ Q ^ R) | v | (~P ^ Q ^ R) | v | (~P | ^ | (~Q v ~R) ) ---|---|---|-----|-------------|---|--------------|---|-----|---|------------   0 | 0 | 0 |  1  |      0      | 0 |       0      | 1 |  1  | 1 |      1       0 | 0 | 1 |  1  |      0      | 0 |       0      | 1 |  1  | 1 |      1       0 | 1 | 0 |  1  |      0      | 0 |       0      | 1 |  1  | 1 |      1       0 | 1 | 1 |  1  |      0      | 1 |       1      | 1 |  1  | 0 |      0       1 | 0 | 0 |  0  |      0      | 0 |       0      | 0 |  0  | 0 |      1       1 | 0 | 1 |  0  |      0      | 0 |       0      | 0 |  0  | 0 |      1       1 | 1 | 0 |  0  |      0      | 0 |       0      | 0 |  0  | 0 |      1       1 | 1 | 1 |  1  |      1      | 1 |       0      | 0 |  0  | 0 |      0

Table for
~P ∨ (Q ∧ R)
 code: P | Q | R | OUT | ~P | v | (Q ^ R) ---|---|---|-----|----|---|---------  0 | 0 | 0 |  1  |  1 | 1 |    0  0 | 0 | 1 |  1  |  1 | 1 |    0   0 | 1 | 0 |  1  |  1 | 1 |    0  0 | 1 | 1 |  1  |  1 | 1 |    1  1 | 0 | 0 |  0  |  0 | 0 |    0  1 | 0 | 1 |  0  |  0 | 0 |    0  1 | 1 | 0 |  0  |  0 | 0 |    0  1 | 1 | 1 |  1  |  0 | 1 |    1

ALWAYS set up a truth table, they make life SO much easier

and if you expand and simplify

(P ∧ Q ∧ R) ∨ (~P ∧ Q ∧ R) ∨ (~P ∧ (~Q ∨ ~R)) ->
(~P ∧ Q ∧ R) ∨ (P ∧ Q ∧ R) ∨ (~P ∧ (~Q ∨ ~R)) ->
(~P ∧ Q ∧ R) ∨ (P ∧ Q ∧ R) ∨ (~P ∧ ~Q) ∨ (~P ∧ ~R) ->
(~P ∧ Q ∧ R) ∨ (P ∧ Q ∧ R) ∨ ~(P ∧ Q) ∨ ~(P ∧ R) ->
(~P ∧ Q ∧ R) ∨ (P ∧ Q ∧ R) ∨ ~(P ∧ Q ∧ R) ->
((P ∨ (~P ∧ Q ∧ R)) ∧ (Q ∨ (~P ∧ Q ∧ R)) ∧(R ∨ (~P ∧ Q ∧ R))) ∨ ~(P ∧ Q ∧ R) ->
(1 ∧ (P ∨ Q) ∧ (P ∨ R) ∧ (Q ∨ ~P) ∧ Q ∧ (Q ∨ R) ∧ (R ∨ ~P) ∧ (R ∨ Q) ∧ R) ∨ ~(P ∧ Q ∧ R) ->
(Q ∧ R) ∨ ~(P ∧ Q ∧ R) ->
(Q ∧ R) ∨ (~P ∧ ~Q ∧ ~R) ->
(~P ∨ (Q ∧ R)) ∧ (~Q ∨ (Q ∧ R)) ∧ (~R ∨ (Q ∧ R)) ->
(~P ∨ Q) ∧ (~P ∨ R) ∧ (~Q ∨ Q) ∧ (~Q ∨ R) ∧ (~R ∨ Q) ∧ (~R ∨ R) ->
(~P ∨ Q) ∧ (~P ∨ R) ∧ 1 ∧ (~Q ∨ R) ∧ (~R ∨ Q) ∧ 1 ->
(~P ∨ Q) ∧ (~P ∨ R) ∧ (~Q ∨ R) ∧ (~R ∨ Q) ->
(~P ∨ Q) ∧ (~P ∨ R) ∧ 1 ->
(~P ∨ Q) ∧ (~P ∨ R) ->
~P ∨ (Q ∧ R) Insectoid  Posted: Mon Mar 18, 2013 3:24 pm   Post subject: RE:Abit of help simplifying this boolean statement?

That's so much work! There's only three parts to this problem, each of which simplifies easily with a little thought.

(P ∧ Q ∧ R) ∨ (~P ∧ Q ∧ R) simplifies to Q^R, because, well, just look at it.

So now we have Q^R ∨ (~P ∧ (~Q ∨ ~R)

~Q v ~R is the inverse of Q^R (there's some identity there) so we can just negate Q^R and get the same thing.

Q^R v (~P^~(Q^R))

If Q^R evaluates to false, then ~(Q^R) is true. So we don't really need that bit. Which leaves us with (Q^R)v~P. viperfan7 Posted: Tue Mar 19, 2013 10:03 am   Post subject: RE:Abit of help simplifying this boolean statement?

Well, its meant to show to process to get the answer, so that people can learn from it.

That and I was bored.

Making that post nicely formatted took longer then solving that thing. Sponsor
Sponsor   Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First        Page 1 of 1  [ 8 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: