Question

In this exercise we show that the meet and join operations are associative. Let A,B and C bezero-one matrices. Show that

a) $\mathbf{(}\mathit{A}\mathbf{\vee }\mathit{B}\mathbf{)}\mathbf{\vee }\mathit{C}\mathbf{=}\mathit{A}\mathbf{\vee }\mathbf{(}\mathit{B}\mathbf{\vee }\mathit{C}\mathbf{)}$ b)$\mathbf{(}\mathit{A}\mathbf{\wedge }\mathit{B}\mathbf{)}\mathbf{\wedge }\mathit{C}\mathbf{=}\mathit{A}\mathbf{\wedge }\mathbf{(}\mathit{B}\mathbf{\wedge }\mathit{C}\mathbf{)}$

Short answer

Hence, proved

a. $(A\vee B)\vee C=A\vee (B\vee C)$.

b. $(A\wedge B)\wedge C=A\wedge (B\wedge C)$

Step-by-step solution

Step 1:

Definition of matrix:

A matrix is a rectangular array of numbers. A matrix with m rows and n columns is called as $m\times n$matrix. :

Associative law for propositions:

$$\begin{gathered} (p\vee q)\vee r=p\vee (q\vee r) \\ (p\wedge q)\wedge r=p\wedge (q\wedge r) \end{gathered}$$

Step 2:

(a)

Given: A and B and C are$m\times n$ zero-one matrix

$(A\vee B)\vee C=A\vee (B\vee C)$

Proof: We can rewrite the matrix A as$\left[a_i\right]$ where$a_{ij}$represents the element in the row$i^{th}$ and in the $j^{th}$ column of A.

$A\vee B$Takes disjunction of each element of A with the corresponding element

$\begin{array}{r}(A\vee B)\vee C=\left(\left[a_{ij}\right]\vee \left[b_{ij}\right]\right)\vee \left[C_{ij}\right]\\ =\left[a_{ij}\vee b_{ij}\right]\vee \left[C_{ij}\right]\\ =\left[\left(a_{ij}\vee b_{ij}\right)\vee C_{ij}\right]\end{array}$

Use associative law

$\begin{array}{r}=\left[a_{ij}\vee \left(b_{ij}\vee c_{ij}\right)\right]\\ =\left[a_{ij}\right]\vee \left[b_{ij}\vee C_{ij}\right]\\ =\left[a_{ij}\right]\vee \left(\left[b_{ij}\right]\vee \left[C_{ij}\right]\right)\\ =A\vee (B\vee C)\end{array}$

Step 3:

(b)

Given: A and B and C arezero-one matrix

$(A\wedge B)\wedge C=A\wedge (B\wedge C)$

Proof: we can rewrite the matrix A as$\left[a_{ij}\right]$ where$a_{ij}$ represents the element in the $i^{th}$ row and in the$j^{th}$ column of A.

$A\wedge B$Takes conjunction of each element of A with the corresponding element

$\begin{array}{r}(A\wedge B)\wedge C=\left(\left[a_i\right]\wedge \left[b_{ij}\right]\right)\wedge \left[c_{ij}\right]\\ =\left[a_{ij}\wedge b_{ij}\right]\wedge \left[c_{ij}\right]\\ =\left[\left(a_{ij}\wedge b_{ij}\right)\wedge C_{ij}\right]\end{array}$

Use associative law

$\begin{array}{r}=\left[a_{ij}\wedge \left(b_{ij}\wedge c_{ij}\right)\right]\\ =\left[a_{ij}\right]\wedge \left[b_{ij}\wedge c_{ij}\right]\\ =\left[a_{ij}\right]\wedge \left(\left[b_{ij}\right]\wedge \left[c_{ij}\right]\right)\\ =A\wedge (B\wedge C)\end{array}$

Hence, the associative laws are proved.