Suppose that, $(S, +, \cdot)$ is a semiring, where the operations are defined as $x\cdot y=min(x, y)$ and $x + y=max(x, y)$.
Can we further simply the expression $a\cdot b+c\cdot d$?, where $a, b, c, d\in S$ and $a\leq d$ and $c\leq b$; also note that $(S, \leq)$ is a partially ordered set.
I couldn't simply the above expression into simpler form.
This answer has been revised in the light of further information regarding the question.
If $\min$ and $\max$ are graph intersection and graph union, we also need to understand $x\leq y$ as a graph relationship.
I assume $\leq$ is defined consistently with the idea that min is a "minimum" and max is a "maximum", so $ \min(x,y) \leq x, $ $ \min(x,y) \leq y, $ $ x \leq \max(x,y), $ and $ y \leq \max(x,y). $
If by "simpler" you mean "fewer operations" then there must also be fewer variables, that is, you must eliminate at least one variable from $a\cdot b+c\cdot d$ without changing the value of the expression for any $a,b,c,d \in S.$
If you can show that the value of $a\cdot b+c\cdot d$ is independent of one of the variables then you might be able to write $a\cdot b+c\cdot d$ in terms of the three remaining variables, which might result in a simpler expression. (Or you might be able to eliminate two variables and write an expression in just the two variables remaining.)
On the other hand, if you can exhibit an example of $a,b,c,d$ in which it is impossible to know $a\cdot b+c\cdot d$ without knowing $a,$ then you have shown that $a$ cannot be eliminated. Similar statements apply to the other three variables.
So you have two possible paths, general proofs to eliminate one or more variables (followed by making sense out of the remaining variables), or specific examples that show some variables cannot be eliminated. Or maybe both.
This was the original answer, which does not hold in the context where $\min$ and $\max$ are graph intersection and graph union.
I'm assuming $\min(x,y)$ and $\max(x,y)$ are defined for all $x,y \in S$ so that for each $x$ and $y$ at least one of the following statements is true:
If we also say the first statement implies $x\leq y$ and the second implies $y \leq x,$ then either $x\leq y$ or $y\leq x$ for all $x,y\in S.$ If $\leq$ is a partial order, then we know that $x\leq y$ and $y\leq x$ cannot both be true unless $x = y.$ Moreover, $x\leq y$, $y\leq z,$ and $z\leq x$ cannot all be true for some $x,y,z\in S$ unless $x = y = z.$
The value of $a\cdot b$ then is either $a$ or $b$. The value of $c\cdot d$ is either $c$ or $d$. The value of $x + y$ (for any $x,y\in S$) is either $x$ or $y$. What does that say about the possible values of $a\cdot b+c\cdot d$?
If you can write a set that contains all possible values of $a\cdot b+c\cdot d$ (and may contain things that are not possible values of $a\cdot b+c\cdot d$), you can try, for each element in that set, to show either that it is a possible value (by exhibiting a partial order that produces that value) or is not a possible value.
That might give you some ideas about whether there is a simpler expression and (if there is) what that expression might be.
I can't think how to give more hints without spoiling the exercise.