2

From my limited understanding of logical operators, it is possible to express the more complex logical operators such as $\operatorname{xnor}$ and $\operatorname{iff}$ as a combination of just a few basic logical operators ($\operatorname{and}$, $\operatorname{or}$, $\operatorname{not}$).

Is it possible to express boolean operators (e.g. equality, subset) as a combination of logical operators too, but that yield only $true$ (tautology) or $false$ (contradiction)?

For example, I could define the $A = B$ operator (set $A$ contains the exact same elements as set $B$) as $(A \land B) \lor (\overline{A \lor B})$, which would yield $true$ when it is true. But it yields neither $true$ (set of all things) nor $false$ (empty set) when it is false, and I want it to yield $false$. Is this at all possible? And what about the boolean subset operator?

It's possible I'm combining incompatible concepts (sets, logic, boolean algebra) but please bear with me.

Andrés E. Caicedo
  • 79,201
Daniel A.A. Pelsmaeker
  • 1,099
  • 11
  • 17
  • 1
    There is a coorespondence between algebra of sets, boolean algebra and logical conncetives. When we write $A=B$ between sets, we mean : $x \in A \leftrightarrow x \in B$. Thus, the $=$ sign correspond with (logical) equivalence : $\leftrightarrow$. And we have that $P \leftrightarrow Q$ is equivalent to $(P \land Q) \lor (\lnot P \land \lnot Q)$ which in turn is : $(P \land Q) \lor \lnot (P \lor Q)$ and this one is true exactly when both $P,Q$ are true or both false. So, why you say that "it yields neither true nor false" ? – Mauro ALLEGRANZA Dec 03 '14 at 12:54
  • @MauroALLEGRANZA If I apply that to two unequal sets $P = {x, y}$, $Q = {y, z}$, it will give me ${y}$ which is not the empty set (false, contradiction, as I understand it). – Daniel A.A. Pelsmaeker Dec 03 '14 at 13:02

2 Answers2

4

Yes, you're combining different concepts in ways they don't really want to combine.

Your basic problem is that the logical operators (or "connectives" in the jargon of mathematical logic) such as $\land$ can only be applied between things that have truth values, and if $A$ and $B$ are sets, then "$A \land B$" doesn't make sense. ("$A\cap B$" does make sense, but produces a set). If you want to start with sets and get a truth value out, at some point in the expression you need to have a symbol that applies to sets and gives you a truth value -- such as $\in$ -- and this means your plan of making do with logical operations alone is dead in the water as written.

This is not to say there isn't a close connection between set algebra and logic -- indeed, the collection of subsets of some given base sets with operations $\cup$, $\cap$ and complement, and {true,false} with operations $\lor$, $\land$ and $\neg$ are the two prototypical examples of a boolean algebra, and you can translate from a formula in propositional logic to an expression in set algebra, and the same laws will hold in each case. However, the set expression will produce a set rather than a truth value.

A significant difference between the two settings is that in logic, every function from a number of truth-valued variables to a truth value can be realized as a Boolean expression, whereas in set algebra there are function from sets to sets that cannot be written in this way. One of these is the one you seem to want: $$ f(A,B) = \begin{cases} U & \text{if $A$ is the same set as $B$} \\ \varnothing & \text{otherwise} \end{cases} $$

The ones you can write using Boolean operators are exactly the one where you can determine whether $x\in f(A,B)$ by knowing only whether $x\in A$ and whether $x\in B$ (but not, for example, which particular element $x$ is or whether any other elements are in $A$ and/or $B$).

hmakholm left over Monica
  • 286,031
  • But isn't the set of everything 'true', and the empty set 'false'? Shouldn't I be able to union sets as if I'm or-ing logical sentences, and get the set of everything when it's undeniably true? – Daniel A.A. Pelsmaeker Dec 03 '14 at 13:00
  • @Virtlink: No, the universal set is not the same as "true". It corresponds to true under the standard correspondence between logic and set algebra, but that doesn't mean that the two things are the same. – hmakholm left over Monica Dec 03 '14 at 13:03
  • @Virtlink: I have expanded the answer slightly. – hmakholm left over Monica Dec 03 '14 at 13:10
  • Yes, that function $f$ is the one I'm looking for. If we have $g(A, B) = (A \land B) \lor (\lnot A \land \lnot B)$ that produces $U$ if A is the same set as B, and something else otherwise; and we think of a function $h(A, B)$ that produces $\varnothing$ if A is not the same as B, and something else otherwise, then can we combine $g$ and $h$ in $f$ to produce $U$ when $A == B$ and $\varnothing$ otherwise? Seems we'd need $f(A, B) = g(A, B) \lor h(A, B)$ in the case $A == B$ but $f(A, B) = g(A, B) \land h(A, B)$ in the case $A \neq B$. Is this the reason it's impossible? – Daniel A.A. Pelsmaeker Dec 03 '14 at 13:42
  • @Virtlink: Your expression $(A\wedge B)\vee(\not A\wedge \not B)$ still doesn't make sense when $A$ and $B$ are sets. You can write $(A\cap B)\cup(\overline A\cap \overline B)$, which does what you describe here, however. The basic reason why what you want is impossible is that the Boolean operators work element-by-element. Whenever you have a set-algebraic expression $f(A,B)$, there is no way for $x\in f(A,B)$ to depend on which elements other than $x$ belong or don't belong to $A$ and $B$. Thus in particular the $h(A,B)$ you specify is impossible. – hmakholm left over Monica Dec 03 '14 at 13:57
0

Just consider the definition of $x\in (A \star B)$ for any of the operators $\star$ we are considering. You can notice that they all are defined in the form

$A \star B \iff \forall x\in U, L$

Where U is theUniverse , and L is some logical expression defined in terms of the logical primitives $(x\in A)$ and $(x\in B)$.

for example

$A \subseteq B\iff ((x\in A) \implies (x\in B))$

Where in this case $L=((x\in A) \implies (x\in B))$. So essentially there is a duality between logical expressions over $(x\in A)$ and $(x\in B)$, and the set relations on $A$ and $B$. From there, we notice that we can represent $L$ "as a combination of just a few basic logical operators", and by passing through the duality, represent the set relations as the combination of a few basic dual operations.

For example

$A = B\iff ((x\in A) \iff (x\in B))$

$A = B\iff (((x\in A) \implies (x\in B)) \wedge ((x\in B) \implies (x\in A)))$

$A = B\iff (A\subseteq B \wedge B\subseteq A)$

which I think is the sort of simplification you were asking about.

Jeremy Salwen
  • 683
  • Not quite. The subset operator itself is a boolean one, but my question is whether it is at all possible to write all such boolean operators (both equality and subset) as a collection of logical operators or set operations. – Daniel A.A. Pelsmaeker Dec 03 '14 at 13:23