• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Devaka Cooray
  • Paul Clapham
Sheriffs:
  • Tim Cooke
  • Knute Snortum
  • Bear Bibeault
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • Piet Souris
  • Ganesh Patekar
Bartenders:
  • Frits Walraven
  • Carey Brown
  • Tim Holloway

Simplifying expressions

 
Ranch Hand
Posts: 1102
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dear All,

I was revising some basic mathematics concepts, and going through MIT videos and notes.

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6_042JF10_notes.pdf

1.2 Propositional Logic in Computer Programs -

In this section they have simplified below expression with the help of truth tables -

if ( x > 0 || (x <= 0 && y > 100) )



In this expression -

if ( x > 0 || y > 100 )

Please see the truth table at the end.

I really like this way of simplifying the expressions.

My question is -

Can each expression be simplified in this way?

Thanks In Advance!


truth_table.png
[Thumbnail for truth_table.png]
 
Marshal
Posts: 64707
226
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In English‑speaking countries ¬ has a higher precedence than ∧ and that is higher than ∨ and ⇒ has a lower precedence. (It is different in France.) The bracketing confirms the English precedences.

That expression is in the form p ∨ ¬p ∧ q.
Draw a diagram with x in one direction and y in the other; you should get a square. Now shade in the area covered by p (x > 0) and later shade in the area covered by ¬p ∧ q. You will find three quarters shaded and you can reduce it to p ∨ q. You may find there is a law relating the two together.

Another way to think of it is that ¬p ∨ q ≡ p ⇒ q, so you can get your expression into the form ¬p ⇒ ¬p ∧ q. That is only false if the left part is true (i.e. the original p is false), and the right part is false, i.e. the original q is false too.
 
Campbell Ritchie
Marshal
Posts: 64707
226
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, you can simplify many expressions with a truth table, assuming they have a simpler form at all.
 
Ranch Hand
Posts: 1168
11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Yes, you can simplify many expressions with a truth table, assuming they have a simpler form at all.



But should you? Two things work into this:

1. Would simplifying the expression make the code easier for a person to understand?

2. Would it produce more efficient (in terms of space and/or speed) code?

Depending on the circumstances, it could be argued that the first version

...is closer to what the domain expert was thinking. e.g. "Having the temperature of the first solution above 0 degrees Celsius is bad, but even if the first solution is at or below 0, then having the second solution's temperature above 100 degrees is also bad." In that case, the unsimplified expression is easier to match up to the domain experts words, even though there is technically a way to simplify it.

As for the code efficiency, is the average Java compiler smart enough to recognize that the first expression is able to be simplified? If so, then the first issue, human understandability, takes precedence outright. If not, then the code efficiency has to be weighed against the understandability.

 
Campbell Ritchie
Marshal
Posts: 64707
226
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I got the impression that was an exercise in maths not programming, so p ∨ q is easier to understand than p ∨ ¬p ∧ q.
Chances are the compiler will not be programmed to do that sort of optimisation and if somebody wrote that in real life, they might not realise that there is such a simpler form. So you would have to simplify the expression yourself with the specialised carbon‑based technology which I so frequently advocate: pencil paper and eraser
I was taught to write truth tables in binary 0…2ⁿ − 1 ascending FFF…TTT (but other people write them in descending order). The expression above can be reduced to two predicates remembering that x > 0 ≡ ¬(x ≤ 0) and a two‑predicate expression can be expressed as four lines.
p q | 0 1 2 3 4 5 6 7 8 9 a b c d e f
F F | F F F F F F F F T T T T T T T T
F T | F F F F T T T T F F F F T T T T
T F | F F T T F F T T F F T T F F T T
T T | F T F T F T F T F T F T F T F T

Assuming you are using two‑valued logic where the Law of the Excluded Middle applies, those four rows comprise the entire gamut of possibilities for the values of any two‑predicate logical expression. If you replace all the Ts with 1s and the Fs with 0s, the left block reads 0‑1‑2‑3 and the right block reads 0…f if you read down the columns. The sixteen expressions can be expressed as
0 = false
1 = p ∧ q
2 = p ⇏ q i.e. p does not imply q
3 = p
4 = p ⇍ q i.e. p does not follow from q (see also line b)
5 = q
6 = p ⊕ q i.e. p xor q
7 = p ∨ q
8 = p ↓ q i.e. p nor q equivalent to ¬(p ∨ q)
9 = p ↔ q i.e. p iff q
a = ¬q
b = p ⇐ q i.e. p follows from q. This is equivalent to q ⇒ p
c = ¬p
d = p ⇒ q
e = p ↑ q i.e. p nand q equivalent to ¬(p ∧ q)
f = true
Notice there is a symmetrical pattern. If you add up two columns and get f, then one of those columns is the negation of the other.
Also two of the lines (the tautology and the contradiction) are independent of either predicate and four of the lines are independent of one predicate. So only ten lines actually require both.
Any two‑valued predicate which contains more than two terms can be simplified to one of those sixteen expressions above. If you are programming and you end up with something like this… you should be able to work out that you can simplify it toThis sort of algebra has been around for 3000 years (when I did logic I learnt that it was the oldest language anybody on the course would ever use, older than any computer language and older than English) so there are all sorts of “laws” some with names like the contrapositive law. It is a good idea to reduce the expressions to those using only these six operators if you can (and ()): ¬ ∧ ⊕ ∨ ⇒ ↔
If you are coding in Java®
¬p is !p
p ∧ q is p && q
p ⊕ q is p ^ q
p ∨ q is p || q
p ⇒ q is p ? q : true
and p ↔ q is p == q
…but the precedences are different from what one uses in logic.
 
Bartender
Posts: 2407
36
Scala Python Oracle Postgres Database Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You might enjoy Mark Chu-Carroll's book Good Math: A Geek's Guide to the Beauty of Numbers, Logic, and Computation. I did!
 
Campbell Ritchie
Marshal
Posts: 64707
226
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That looks an interesting book.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!