MHB Simplifying Logical Expressions [SOLVED]

AI Thread Summary
The discussion focuses on simplifying logical expressions using DeMorgan's Law and the Distributive Property. The original expression, NOT(a < 20 AND (b < 10 OR b > 10)), is simplified correctly to a >= 20 OR b = 10 after applying DeMorgan's Law twice. Participants debate the meaning of "simplifying an expression," noting that simplification can vary based on the number of connectives and clarity of the expression. It is emphasized that while the number of connectives may decrease, the overall complexity can remain similar. Ultimately, the conversation highlights the subjective nature of simplification in logical expressions.
Valtham
Messages
3
Reaction score
0
[SOLVED] Simplifying Expressions

Hello all I am a bit confused about the laws I am learning about right now and attempted some of my own exercises to understand them a bit.

I have the problem NOT(a < 20 AND (b < 10 OR b > 10)) and I need to simplify it.

From my understanding I can use DeMorgan's Law which then gives me the expression NOT a < 20 OR NOT(b < 10 OR b > 10). I can then use the Distributive Property to create the expression (NOT a < 20 OR NOT b < 10) AND (NOT a < 20 OR NOT b > 10).

What I am confused about is after I use DeMorgan's Law the first time is it correct to use the Distributive Law next? Or should I have used DeMorgan's Law again?
 
Last edited:
Physics news on Phys.org
Valtham said:
What I am confused about is after I use DeMorgan's Law the first time is it correct to use the Distributive Law next? Or should I have used DeMorgan's Law again?
You can't use the distributive law immediately after the first De Morgan's law. Distributivity requires that the expression has both a disjunction and a conjunction. So, first you need to convert NOT(b < 10 OR b > 10) into (NOT b < 10) AND (NOT b > 10) and then use distributivity. You indeed get (NOT a < 20 OR NOT b < 10) AND (NOT a < 20 OR NOT b > 10).

If < denoted the regular order, then I believe the simplest form of this is expression is a >= 20 OR b = 10.
 
Thanks for the reply. Makes total sense that I would have to use DeMorgan's Law again. I can see how you get a >= 20 OR b = 10, but what if the expression had been (NOT a < 20 AND NOT (b <= 10 OR b >= 15)). Using that expression the "simplified" version would be a >= 20 OR b >= 10 AND b <= 15. To me that expression hardly seems simplified, and all we did was remove the "NOT" connectives pretty much. What does "simplifying an expression" mean exactly? We weren't really given a precise definition other than an example that removes as many variables and connectives as possible.
 
Valtham said:
what if the expression had been (NOT a < 20 AND NOT (b <= 10 OR b >= 15)). Using that expression the "simplified" version would be a >= 20 OR b >= 10 AND b <= 15.
It should say, "... b > 10 AND b < 15." Also, usually AND is considered to have higher priority than OR, so omitting parentheses is OK, but unless this is an explicit convention in your course, it may still make sense to put parentheses around b > 10 AND b < 15 to remove any ambiguity.

Valtham said:
To me that expression hardly seems simplified, and all we did was remove the "NOT" connectives pretty much. What does "simplifying an expression" mean exactly? We weren't really given a precise definition other than an example that removes as many variables and connectives as possible.
There are different measures with respect to which simplification can be defined. Here the answer has 2 connectives vs 4 in the original expression, so in this sense it is simpler. On the other hand, the number of atomic propositions is the same. Informally, for me it is a little easier to understand a >= 20 than NOT a < 20. Also, b > 10 AND b < 15 is often abbreviated as 10 < b < 15, which makes it even simpler.
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top