MHB De Morgan Rules - Logical statements

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Rules
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
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?
 
Physics news on Phys.org
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. 🤔
 
Klaas van Aarsen said:
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:
 
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.
 
Evgeny.Makarov said:
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:
 
I wrote about using de Morgan's law for logic, not about proving them.
 
Evgeny.Makarov said:
I wrote about using de Morgan's law for logic, not about proving them.

I got stuck right now. What exactly do you mean?
 
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.
 
mathmari said:
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$.
 
  • #10
Klaas van Aarsen said:
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:
 
  • #11
Yes, you can do that.
 
  • #12
Ok! Thank you! (Star)
 

Similar threads

Replies
6
Views
1K
Replies
5
Views
1K
Replies
16
Views
2K
Replies
4
Views
2K
Replies
5
Views
1K
Replies
3
Views
5K
Replies
8
Views
2K
Back
Top