3-2 OverLaps述語

ブール代数パズル

到着時間 <= 出発時間
と
公演開始 <= 公演終了
が成立しているとして、

以下の条件式を、同値変形によって、簡略化させる

    公演開始 >= 到着時間
AND 公演開始 <= 出発時間
 OR 公演終了 >= 到着時間
AND 公演終了 <= 出発時間
 OR 公演開始 <= 到着時間
AND 公演終了 >= 出発時間

こちらが元ネタ

解答

公演開始 >= 到着時間 をA
公演開始 <= 出発時間 をB
公演終了 >= 到着時間 をC
公演終了 <= 出発時間 をD
公演開始 <= 到着時間 をE
公演終了 >= 出発時間 をF
とおくと

    公演開始 >= 到着時間
AND 公演開始 <= 出発時間
 OR 公演終了 >= 到着時間
AND 公演終了 <= 出発時間
 OR 公演開始 <= 到着時間
AND 公演終了 >= 出発時間

はこう置けます。
A*B + C*D + E*F

到着時間 <= 出発時間 と
公演開始 <= 公演終了 より
以下の命題が成立

A⇒C      ... 1
D⇒B      ... 2
E⇒B      ... 3
F⇒C      ... 4
Aが偽⇒E  ... 5
Bが偽⇒F  ... 6
Cが偽⇒D  ... 7
Dが偽⇒F  ... 8
Eが偽⇒A  ... 9
Fが偽⇒D  ...10

A*B + C*D + E*F
= A*C*B + C*D*B + E*B*F*C
= B*C*(A + D + E*F)

E*Fが偽ならば、命題9と命題10より
AとDの、少なくとも1つが真
よって
A + D + E*F=1
よって
B*C*(A + D + E*F) = B*C

すなわち
    公演開始 >= 到着時間
AND 公演開始 <= 出発時間
 OR 公演終了 >= 到着時間
AND 公演終了 <= 出発時間
 OR 公演開始 <= 到着時間
AND 公演終了 >= 出発時間

と
    公演開始 <= 出発時間
AND 公演終了 >= 到着時間
は同値である

■■■■■■■■■■■■■■■■■■■■■■■■■■■■
A⇒C      ... 1
D⇒B      ... 2
E⇒B      ... 3
F⇒C      ... 4

A*B + C*D + E*F
= A*C*B + C*D*B + E*B*F*C

この変形は、
2-2 命題が成立した状態での、論理積
を使ってます