Question

We will establish distributive laws of the meet over the join operation in this exercise. Let A, B and C bezero-one matrices. Show that

a)$A\vee (B\wedge C)=(A\vee B)\wedge (A\vee C)$ b)$A\wedge (B\vee C)=(A\wedge B)\vee (A\wedge C)$

Short answer

Hence, proved

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

b.$A\wedge (B\vee C)=(A\wedge B)\vee (A\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. :

Distributive law for propositions:

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

Step 2:

(a)

Given: A and B and C arezero-one matrix

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

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

$A\vee (B\wedge C)=\left[a_{i}j\right]\vee \left(\right[b_{i}j]\wedge [c_{i}j\left]\right)$

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

$\left[a_{i}j\right]\vee [b_{i}j\wedge c_{i}j]$

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

$[a_{i}j\vee (b_{i}j\wedge c_{i}j\left)\right]$

Use distributive law

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

Step 3:

(b)

Given: A and B and C are m x n zero-one matrix

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

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

$A\wedge (B\vee C)=\left[a_{i}j\right]\wedge \left(\right[b_{i}j]\vee [c_{i}j\left]\right)$

Takes disjunction of each element of A with the corresponding element of B

$\left[a_{i}j\right]\wedge [b_{i}j\vee c_{i}j]$

Takes conjunction of each element of A with the corresponding element of B

$[a_{i}j\wedge (b_{i}j\vee c_{i}j\left)\right]$

Use distributive law

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

Hence, the distributive laws are proved.