De Morgan Rules - Logical statements

[mathmari]

Hey!

I have proven the following properties:
(i) $(a\Rightarrow b)\iff (\neg b\Rightarrow \neg a)$
(ii) $[(a\Rightarrow b)\land (b\Rightarrow c)]\Rightarrow (a\Rightarrow c)$
(iii) $[a\land (a\Rightarrow b)]\Rightarrow b$

At the second part of the exercise we have to show the de Morgan rules:
- $C_X(A\cup B)=(C_XA)\cap (C_XB)$
- $C_X(A\cap B)=(C_XA)\cup (C_XB)$
where $A,B$ are subsets of $X$ and $C_X$ is the complement in $X$. Is the first part relevant, i.e. do we have to use the first part to show these rules? Or is this not possible and we have to show that as usual taking an element of the lft set and showing that it is in the right set and also other way around?

 

[I like Serena]

Hey mathmari!

Those first properties seem unrelated.
The relevant logical properties would be $\lnot({a\land b})=\lnot a \lor \lnot b$ respectively $\lnot({a\lor b})=\lnot a \land \lnot b$, but that is not what you have in the first part.

 

[mathmari]

Those first properties seem unrelated.
The relevant logical properties would be $\lnot({a\land b})=\lnot a \lor \lnot b$ respectively $\lnot({a\lor b})=\lnot a \land \lnot b$, but that is not what you have in the first part.

Ok... Do you suggest to show the desired properties using logical properties or to show that $y\in C_X(A\cup B)\iff y\in (C_XA)\cap (C_XB)$ ? :unsure:

 

[Evgeny.Makarov]

When you are proving the equivalence using the second option you'll be using de Morgan's logical laws implicitly anyway, so you can as well prove the equality of characteristic functions and use these laws explicitly.

 

[mathmari]

When you are proving the equivalence using the second option you'll be using de Morgan's logical laws implicitly anyway, so you can as well prove the equality of characteristic functions and use these laws explicitly.

So you mean to show that $\neg (a\land b)=\neg a\lor \neg b$ and $\neg (a\lor b)=\neg a\land \neg b$ ? Or have I misunderstood that?

If you mean this, do we show that using a truth table?

:unsure:

 

[Evgeny.Makarov]

I wrote about using de Morgan's law for logic, not about proving them.

 

[mathmari]

I wrote about using de Morgan's law for logic, not about proving them.

I got stuck right now. What exactly do you mean?

 

[Evgeny.Makarov]

Consider characteristic functions of subsets of $X$. Suppose that the codomain of those functions, whether it is $\{0,1\}$ or {true, false}, is equipped with Boolean operations $\land$, $\lor$, $\neg$, etc. Then if $x\in X$, $A\subseteq X$ and $\chi_A$ is the characteristic function of $A$, we have $x\in A\iff \chi_A(x)=1$ (or true) by definition. Next express the correspondence between operations on sets and operations on their characteristic functions. Then instead of proving equality of sets we can prove equality of their characteristic functions. And for that we can use laws of Boolean algebra, such as de Morgan's laws.

 

[I like Serena]

Ok... Do you suggest to show the desired properties using logical properties or to show that $y\in C_X(A\cup B)\iff y\in (C_XA)\cap (C_XB)$ ? :unsure:

I'd prefer to show the set properties exactly as shown.
That is, suppose $y\in C_X(A\cup B)$ and show $\implies$. After that, show $\Longleftarrow$.

 

[mathmari]

I'd prefer to show the set properties exactly as shown.
That is, suppose $y\in C_X(A\cup B)$ and show $\implies$. After that, show $\Longleftarrow$.

So do we have the following?

\begin{align*}y\in C_X(A\cup B) &\iff y\in X \ \text{ and } \ y\notin A\cup B \\ & \iff y\in X \ \text{ and } \ y\notin A \ \text{ and } \ y\notin B \\ & \iff \left (y\in X \ \text{ and } \ y\notin A\right ) \ \text{ and } \ \left (y\in X \ \text{ and } \ y\notin B \right ) \\ & \iff y\in C_XA \ \text{ and } \ y\in C_XB \\ & \iff y\in (C_XA)\cap ( C_XB )\end{align*}

\begin{align*}y\in C_X(A\cap B) &\iff y\in X \ \text{ and } \ y\notin A\cap B \\ & \iff y\in X \ \text{ and } \ \left (y\notin A \ \text{ or } \ y\notin B \right ) \\ & \iff \left (y\in X \ \text{ and } \ y\notin A\right ) \ \text{ or } \ \left (y\in X \ \text{ and } \ y\notin B \right ) \\ & \iff y\in C_XA \ \text{ or } \ y\in C_XB \\ & \iff y\in (C_XA)\cup ( C_XB )\end{align*}

:unsure:

 

[Evgeny.Makarov]

Yes, you can do that.

 

[mathmari]

Ok! Thank you! (Star)