Social Question

LostInParadise's avatar

Can you solve this simple problem in logic?

Asked by LostInParadise (31904points) September 9th, 2022
6 responses
“Great Question” (2points)

If you are given the birth and death dates of two historical figures, you would have no trouble determining if their lives overlapped.

Suppose the birth and death dates for two people are b1 and d1, and b2 and d2. Can you give a statement of the form w>=x and y>=z that will be true if and only if the two lives overlapped?

I found the answer to this to be non-intuitive. The way I tackled it was to find a logical condition for the lives to be non-overlapping, which seemed rather obvious, and then use that to solve the problem.

Observing members: 0
Composing members: 0

Answers

gorillapaws's avatar

This is easy with set theory. You’re talking about the intersection of two different sets of the days lived of two individuals.

Zaku's avatar

Yes, I can.

LostInParadise's avatar

The answer is:
overlap = (d1 >= b2) and (d2 >= b1)

This may not be obvious. It is much more obvious that there will be non-overlap if either person is born after the other dies, giving:
non-overlap = (b2 > d1) or (b1 > d2)
We then get overlap = not non-overlap = not ((b2 > d1) or (b1 > d2))

There is a law of logic, which I hope you will find self-evident, that says not(A or B) = not A and not B

Applying this law gives overlap = not(b2 > d1) and not (b1>d2) = (d1>=b2) and (d2>=b1)

gorillapaws's avatar

@LostInParadise “There is a law of logic, which I hope you will find self-evident, that says not(A or B) = not A and not B”

That’s De Morgan’s laws.

LostInParadise's avatar

I did not want to mention De Morgan’s laws to keep thing from getting too technical.

I finally figured out how to make sense of the answer. Instead of births and deaths, let’s talk about beginnings and endings of intervals, b1,e1 and b2 and e2. We know that e1 > b1 and e2>b2. Having e1 > b2 and e2 > b1, means that all the e values are greater than all the b values. Imagine putting these values on a number line. Going from left to right, each time you pass a b value, you join its interval and each time you pass an e value you leave an interval. Having all the b values first, regardless of which b value matches with which e value, means that the region between the last b value and the first e value must belong to both intervals.

This generalizes easily. For any number of intervals, the only way to have the intersection of all of them to be non-null is to have all the beginning points precede all the end points. Which end point matches to which beginning point does not matter. The region between the last beginning point and the first end point belongs to all the intervals.

LostInParadise's avatar

One last comment. If there is a computer program to handle the generalized case from tables of beginning and end points, it can easily tell if all the intervals intersect by checking whether the maximum beginning point is less than the minimum end point.

Answer this question

Login

or

Join

to answer.

Mobile | Desktop


Send Feedback   

`