MHB Can A∩B⊖∩C⊖ = A∩C⊖ be Equal to A∩B∩C= A∩B?

[solakis1]

Is it possible for $$A\cap B^c\cap C^c= A\cap C^c$$ to be equivalent to

$$A\cap B\cap C= A\cap B$$ ??

I think not

Is there any way to check that without a counter example??

 

[Evgeny.Makarov]

Is it possible for $$A\cap B^c\cap C^c= A\cap C^c$$ to be equivalent to

$$A\cap B\cap C= A\cap B$$ ??

It's is not only possible. For all sets $A$, $B$ and $C$ it is the case that the first equality holds iff the second one holds.

 

[solakis1]

Its is not only possible. .

you mean it is possible? If yes ,how can we know that before we even start to solve the problem.

Set theory is not a decidable theory

 

[Evgeny.Makarov]

you mean it is possible?

I am not sure what you mean by this. Usually the question "Is it possible that $P(A,B,C)$ holds?" means "Is $\exists A,B,C\;P(A,B,C)$ true?". If $P(A,B,C)$ is
\[
A\cap B^c\cap C^c= A\cap C^c\iff A\cap B\cap C= A\cap B
\]
then $\forall A,B,C\;P(A,B,C)$ is true, which implies the existential statement.

If yes ,how can we know that before we even start to solve the problem.

Nothing can be said about a problem until one starts solving it.

Set theory is not a decidable theory

First-order set theory, yes, but problem like yours can be encoded in propositional logic, which is decidable. Even if the class of problems is not decidable, it does not prevent us from solving some problems of that class.

 

[solakis1]

\[
A\cap B^c\cap C^c= A\cap C^c\iff A\cap B\cap C= A\cap B
\]

for $$A\cap B^c\cap C^c= A\cap C^c$$ to be equivalent to

$$A\cap B\cap C= A\cap B$$

but problem like yours can be encoded in propositional logic, which is decidable. .

Right. What is the corresponding propositional formula then

 

[Evgeny.Makarov]

What is the corresponding propositional formula then

\[
(A\land \neg B\land \neg C\leftrightarrow A\land \neg C)\leftrightarrow (A\land B\land C\leftrightarrow A\land B)
\]

 

[solakis1]

\[
(A\land \neg B\land \neg C\leftrightarrow A\land \neg C)\leftrightarrow (A\land B\land C\leftrightarrow A\land B)
\]

And a truth table generator from google tells me that the above is atautology, hence we have a solution.

One in propositional logic and

one in boolean ALGEBRA or in propositional algebra.

The one in propositional logic is easy

But the one in Boolean algebra is impossible .

Any suggestions??

 

[Evgeny.Makarov]

And a truth table generator from google tells me that the above is atautology, hence we have a solution.

Could you give a link to the truth table generator you are using?

One in propositional logic and

one in boolean ALGEBRA or in propositional algebra.

What exactly do you mean by Boolean algebra: a structure, a branch of algebra or something else?

But the one in Boolean algebra is impossible .

Why?

Any suggestions?

About what?

 

[solakis1]

Could you give a link to the truth table generator you are using?

https://syn-sem.appspot.com/alPropositional Logic: Truth Table Generator

¬ ∧ ∨ → ↔
( p q r s )
​

p	q	r	((((p ∧ q) ∧ r) ↔ (p ∧ q)) ↔ (((p ∧ ¬q) ∧ ¬r) ↔ (p ∧ ¬r)))
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

show instructions


https://syn-sem.appspot.com/ || Contact || Powered by NLTK and Google App Engine
​

What exactly do you mean by Boolean algebra: a structure, a branch of algebra or something else?

A Boolean algebra can be seen as a generalization of a power set algebra or a field of setsI mean a solution in Boolean Algebra is very difficult .

Have you any hints ??

 

[Evgeny.Makarov]

Thanks for the link.

A Boolean algebra can be seen as a generalization of a power set algebra or a field of sets

So you mean Boolean algebra as a structure (a complemented distributive lattice). Propositional logic is sound and complete w.r.t. Boolean algebras, i.e., $\varphi$ is a tautology iff $B\models\varphi$ for all Boolean algebras $B$. (One book where the definition of $B\models\varphi$ can be found is Heine Sorensen, Pawel Urzyczyn, "Lectures on the Curry-Howard Isomorphism", Elsevier, 2006.) So if you want to find out if a formula holds on all Boolean algebras, it is sufficient to test it on the two-element algebra.

 

[solakis1]

s, i.e., $\varphi$ is a tautology iff $B\models\varphi$ for all Boolean algebras $B$. .

No, $\varphi$ is a tautology iff $B\models\varphi=1$ for all Boolean algebras $B$

Apart from that have you any hints as to how i am going to prove :

\[
A\cap B^c\cap C^c= A\cap C^c\iff A\cap B\cap C= A\cap B
\]

By using the laws of commutativity associativity,distributivity,nutility ,indep. e.t.c e.t.c

 

[Evgeny.Makarov]

No, $\varphi$ is a tautology iff $B\models\varphi=1$ for all Boolean algebras $B$

The standard notation is $B\models\varphi$. It means that the formula $\varphi$ is true in the algebra $B$ for all valuations (values of variables).

Apart from that have you any hints as to how i am going to prove :

\[
A\cap B^c\cap C^c= A\cap C^c\iff A\cap B\cap C= A\cap B
\]

By using the laws of commutativity associativity,distributivity,nutility ,indep. e.t.c e.t.c

You should have stated from the start that you want to derive this equivalence from the axioms of Boolean algebra. It is easily derivable from $X\land Y=X\iff X\land\neg Y=0$. This equivalence, in turn, is easy to prove for sets. I'll have to think show to derive it from axioms.

 

[solakis1]

Thanks i know how to solve the problem now.

By the way have you any hints with respect to the following equivalence??

$$A\cup B=A\cap B\Longleftrightarrow A=B$$ forall non empty A,B sets.

using the Boolean axioms

 

[soroban]

Is it possible for $$A \cap B^c \cap C^c = A \cap C^c$$ to be equivalent to $$A \cap B \cap C = A \cap B $$ ?

Sketch the Venn diagrams.

The two equations hold if [math]A \cap B \cap C^c\,=\,\emptyset[/math]