- 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

posted 4 years ago

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 -

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!

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.

Can each expression be simplified in this way?

Thanks In Advance!

truth_table.png

posted 4 years ago

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.

That expression is in the form

Draw a diagram with

Another way to think of it is that ¬

Campbell Ritchie

Marshal

Posts: 64707

226

posted 4 years ago

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

posted 4 years ago

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 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

posted 4 years ago

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.

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.

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 =

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 =

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.

posted 4 years ago

You might enjoy Mark Chu-Carroll's book Good Math: A Geek's Guide to the Beauty of Numbers, Logic, and Computation. I did!

No more Blub for me, thank you, Vicar.

Campbell Ritchie

Marshal

Posts: 64707

226

posted 4 years ago

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!