0

(S or (G and not S)) or not G. How does that simplify?

((S or G) and ( S or not S )) or not G == > ( S or not S ) is a tautology so that cancels out, giving us

(S or G) or not G ==> G or not G is a tautology again so we are left only with S? Are we doing something wrong?

Improve this question
2
  • wolframalpha.com/input/?i=(S+or+(G+and+not+S))+or+not+G Commented Sep 25, 2013 at 9:12
  • Is this a programmatic situation or do you just have a problem with simplifying this one expression. If your language L contains as logical symbols or,¬,and then this is rife for any number of simplifications, possibly a normal form. Commented Sep 25, 2013 at 9:16

3 Answers 3

Reset to default
2

From boolean logic two variables S and G can take possible values as below, which the output boils down to value 1. 

S G --- 0 0 0 1 1 0 1 1

Output:

 (S || (G && !S)) || !G 0 0 1 1 = 1 0 1 1 0 = 1 1 0 0 1 = 1 1 1 0 0 = 1

Solving boolean logic

EDIT: Methods above used to derive the given expression are Truth table and Karnaugh map. Do check the link for correspondence between two and how boolean simplifications are used to solve the output function generated form K-Map.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

The second method looks promising. Could you detail how it is distinct (and if you like, how it is similar) from the truth table method you also give. Perhaps you could name the two methods of solving? An explanation of why the "output" bit works would be good too! For example, what axioms for a boolean algebra are being used at each step.
@Tom Method 1 & 2 are called Truth table approach and Karnaugh map respectively, K-map gives a pictorial representation grouping together common wanted literals. We derive a function of literals Output(S, G) as said in the answer and using algebraic Boolean Axioms we simply the function. Both approaches had a correspondence between each other, which is clearly explained in above wiki webpage.
Well add it to your answer then. You're not explaining to me, you're explaining to the OP!
Personally, I would elaborate on Kranaugh maps as that is a well established mechanism for detecting the "simplification" the OP strictly speaking asked for (although, I'm not sure the OP actually meant that).
1

Truth tables are ok for Propositional Logic (PL) (aka logic without quantifiers, relations and identity) languages with a small number of nonlogical predicates. The issue is with n non logical terms (all propositional variables with PL), you require 2^n evaluations.

Assuming classical logic, another way is to distribute into a normal form, then you can usually just "read off" that every valuation is true.

(S or (G and ¬S)) or ¬G

((S or G) and (S or ¬S)) or ¬G (by distributivity)

(((S or G) or ¬G) and ((S or ¬S) or ¬G)) (by distibutivity again)

T (by resolution of the clauses- think "reading off")

To explain what this "reading off" amounts to: all clauses in this conjunctive normal form evaluate to truly since each disjunction contains at least one pair of the form phi and ¬phi.

Improve this answer

Comments

0

Is this not just S or G?

Assume they are overlapping you want S, or G(without intersection with S) or not G. Which results in the whole of S (including the intersection with G) and G without the intersection with S which is S&G total.

Correct me if I am wrong.

Improve this answer

2 Comments

Intersection? How does this relate to this logical expression? AFAIK intersections only relate to sets?
What's the difference between logic and sets?

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.