De Morgan Rules - Logical statements

  • MHB
  • Thread starter mathmari
  • Start date
  • Tags
    Rules
In summary, the conversation discusses the properties of logical operations and the use of de Morgan's laws to prove set properties. The relevant logical properties are $\lnot({a\land b})=\lnot a \lor \lnot b$ and $\lnot({a\lor b})=\lnot a \land \lnot b$. To prove set properties, one can either show the desired properties using logical properties or show the equality of characteristic functions and use de Morgan's laws explicitly.
  • #1
mathmari
Gold Member
MHB
5,049
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
  • #2
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. 🤔
 
  • #3
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:
 
  • #4
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.
 
  • #5
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:
 
  • #6
I wrote about using de Morgan's law for logic, not about proving them.
 
  • #7
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?
 
  • #8
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.
 
  • #9
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)
 

Related to De Morgan Rules - Logical statements

1. What are De Morgan's Laws?

De Morgan's Laws are a set of rules that describe how logical statements can be simplified by negating or inverting the terms within the statement. They are named after mathematician Augustus De Morgan and are commonly used in logic and computer science.

2. What are the two De Morgan Rules?

The two De Morgan Rules are the De Morgan's Law of Negation and the De Morgan's Law of Conjunction. The Law of Negation states that the negation of a disjunction is the conjunction of the negations, while the Law of Conjunction states that the negation of a conjunction is the disjunction of the negations.

3. How do De Morgan Rules work?

De Morgan Rules work by simplifying logical statements by negating or inverting the terms within the statement. This can help to reduce the complexity of the statement and make it easier to understand and analyze.

4. What is the purpose of De Morgan Rules?

The purpose of De Morgan Rules is to provide a set of rules that can be used to simplify logical statements. This can be especially useful in fields such as mathematics, computer science, and philosophy, where logical statements are frequently used.

5. Are De Morgan Rules always applicable?

Yes, De Morgan Rules are always applicable. They are based on fundamental principles of logic and can be used to simplify any logical statement, regardless of its complexity. However, it is important to use them correctly and carefully in order to avoid errors in reasoning.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
841
  • Set Theory, Logic, Probability, Statistics
Replies
16
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
919
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
Replies
1
Views
518
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Back
Top