Let A and B represent two linear inequalities:
$A : a_1 x_1 + ... + a_n x_n \geq k_1$
$B : b_1 x_1 + ... + b_n x_n \geq k_2$
If A and B is unsatisfiable (does not have solution), does the following hold in general (the conjunction of two inequalities implies the summation of them )? If so, I am looking for a formal proof?
$A \land B \implies A + B$
$𝑎_1𝑥_1+...+𝑎_n𝑥_n \geq𝑘1 \;\; \land \;\; 𝑏_1𝑥_1+...𝑏_n𝑥_n\geq 𝑘_2 \implies 𝑎_1𝑥_1+...+𝑎_n𝑥_n + 𝑏_1𝑥_1+...𝑏_n𝑥_n \geq 𝑘_1+𝑘_2 $
and then I would like to generalize the above theorem to summation of several inequalities.
My attempt:
My intuition is that if A and B be unsatisfiable, there is a matrix of Farkas coefficient C such that the weighted sum of A + B would be zero, and leads to -1 > 0 contradiction. Since A and B are unsatisfiable, the conjunction would be false. Therefore $\bot \implies \bot$
which is a correct statement.
My question is how to generalise this proof for a system of linear inequalities
$A : \bigwedge \Sigma_{i=1}^{n} a_i x_i\leq k_i \;\; \wedge \;\; \bigwedge \Sigma_{i=1}^{n} b_i y_i\leq l_i $
and
$B: \bigwedge \Sigma_{j=1}^{n} a_j x_j\leq w_j \;\; \wedge \;\; \bigwedge \Sigma_{j=1}^{n} b_j y_j\leq z_j $
No comments:
Post a Comment