5

Assuming that symmetry of equality has already been proved, you have, from the induction hypothesis about $\phi$, that $\Vert x=y\Vert\land\Vert\phi(y)\Vert\leq \Vert\phi(x)\Vert$. Take the Boolean negation of both sides, remembering that, as you said, the direction of the inequality gets reversed, you get $\neg\Vert\phi(x)\Vert\leq(\neg\Vert x=y\Vert)\lor(\...


5

Alternatively, here is a graphical proof:


5

Here is a different approach, using indicator (or characteristic) functions. If the universe is $X$ and $A\subseteq X$, then the indicator function of $A$, written $1_A$ (or sometimes $\chi_A$) is defined by $$1_A(x)=\cases{1,&$x\in A$\\0,&$x\notin A$}$$for $x\in X.$ Notice that $$\begin{align} 1_{A^c}&=1-1_A\\ 1_{A\cap B}&=1_A\cdot1_B\\ ...


4

In my opinion, the easiest way to show, for sets $A,B$, that $A=B$ is that you show $A \subseteq B$ and $B \subseteq A$. That is, to show the equality, you would show $x \in A \implies x \in B$ and $x \in B \implies x \in A$. So, we want to show that $(A\setminus B) ∪ (B\setminus C) = (A∪B)\setminus (B∩C)$. I'll show the first necessary condition, $(A\...


2

You are doing something that's very common to beginning students of logic! Distribution says that: $P \land (Q \lor R) \Leftrightarrow (P \land Q) \lor (P \land R)$ Now, what students often don't realize is that this is an equivalence. That is, you can go from left to right, but you can also go from right to left. Of course, going from right to left that ...


2

$$\begin{align} \overline{(\overline{A}\cdot\overline{B})+(A\cdot\overline{B})} &=\overline{\overline{A}\cdot\overline{B}}\cdot\overline{A\cdot\overline{B}}\tag{De Morgan's}\\ &=(A+B)\cdot(\overline{A}+B)\tag{De Morgan's}\\ &=A\cdot\overline{A}+A\cdot B+B\cdot\overline{A}+B\cdot B\tag{Expanding}\\ &=0+A\cdot B+B\cdot\overline{A}+B\\ &=B+A\...


2

All Boolean algebras have a top element. I don't have access to that Kuratowski definition, but tipically, what happens is these alternative definitions have axioms enough to define a partial order relation relative to which the complement operation is order-reversinng. Given that $0$ is the bottom element, it will follow that $0'$ is the top one.


2

First, a note on terminology: your use of the term "$\sigma$-isomorphism" doesn't really make sense. An isomorphism between two Boolean algebras always preserves all joins and meets of all sizes (it's an isomorphism!). What you mean is really whether the embedding of $\mathcal{B}$ into the power set of its Stone space is a $\sigma$-homomorphism (not a $\...


1

Recall that, $$ (A\cup B)\backslash B = (A\cup B)\cap B^{c} = (A\cap B^{c})\cup(B\cap B^{c}) = (A\backslash B)\cup X = A\backslash B, $$ where $X$ is a referencial (or universe) set. For instance, with Morgan laws you can do: $$ (A\cup B)\backslash (B\cap C) = (A\cup B) \cap (B\cap C)^{c} = (A\cup B) \cap (B^{c}\cup C^{c}) $$ $$ = \left((A\cup B)\cap B^{...


1

If there are $n$ variables $\{x_1,\cdots,x_n\}$, there are $2^n$ ways to assign values to these variables, with each one taking value $0$ or $1$. Now for each of the $2^n$ assignments of values to these variables, you could have the output of the function be $0$ or $1$. You have to choose $0$ or $1$ for each of the $2^n$ assignments of values. There are $2^{...


1

Hint: Suppose you have a circuit with three outputs $s_0,s_1,s_2$ such that $s_k$ is true iff $\sum_{i=1}^{n-1} (x_i + y_i) \equiv k \mod 3$. Use these and $x_n, y_n$ to get $s'_0, s'_1, s'_2$ such that $s'_j$ is true iff $\sum_{i=1}^n (x_i + y_i) \equiv j \mod 3$.


1

Using the algebraic approach you get for the LHS: $$(A\setminus B) \cup (B\setminus C) =$$ $$(A \cap B') \cup (B \cap C')=$$ $$((A \cap B')\cup B) \cap ((A \cap B')\cup C')=$$ $$(A \cup B) \cap (A \cup C') \cap (B' \cup C')$$ while for the RHS you get: $$(A\cup B) \setminus (B\cap C)=$$ $$(A\cup B) \cap (B\cap C)'=$$ $$(A\cup B) \cap (B' \cup C')$$ ...


1

Hint Let assume $\lnot (A \land B) \equiv \lnot A \lor \lnot B$. Then from $\lnot (A \lor B)$ using Double Negation, we get $\lnot (\lnot \lnot A \lor \lnot \lnot B) \equiv \lnot \lnot (\lnot A \land \lnot B)$.


1

Since $xy'+z+(x'+y)z'$ is $1$ when $z=1$, the factor $z'$ in the last summand can be omitted, so it becomes $$ xy'+z+x'+y. $$ By the same reasoning, the factor $x$ in the first summand can now be omitted, so it becomes $$ y'+z+x'+y. $$ Now $y'+y=1$ so the expression is $1$ always, we conclude that $$ xy'+z+(x'+y)z' = 1. $$


1

\begin{align} E&=A'B+C(A'B'+AB'+AB)\\&=A'B+C((A'+A)B'+AB)\\ &=A'B+C(B'+AB) \end{align} For boolean expressions $+$ also distributes over product, by example: $$ B'+AB = (B'+A)(B'+B)=B'+A $$ thus \begin{align} E &=A'B+C(B'+A)\\ &=A'B+CB'+CA \\ &=(A'B+C)(A'B+B')+CA \\ &=(A'B+C)(A'+B')+CA\\ &=A'B+CA'+CB'+CA \\ &=A'B+C+CB' \...


1

Are $x_i\in\{0,1\}$? Is it that when representing the input $x_3,\ldots,x_0$ in binary and call the value $n$, the $n$th bit on the right hand side represents the $0$ or $1$ result? $$f(x_3,x_2,x_1,x_0) = \left(\sum_{i=0}^3 2^ix_i\right)\text{th bit on the }RHS$$ e.g. $f(0,0,0,0) = 0000_2\text {th bit on the } RHS = 1$ $f(1,0,1,0) = 1010_2\text {th bit ...


1

By the Reverse Triangle inequality, for all $S\neq S^*$, $$ \text{dist}(f,\chi_S)\geq \text{dist}(\chi_{S^*},\chi_S)-\text{dist}(\chi_{S^*},f)=\frac{1}{2}-\delta. $$ Using the expression for Fourier coefficients that you wrote: $$ \vert \hat{f}(S^*)\vert=1-2\text{dist}(f,\chi_{S^*})\leq 1-2(1/2-\delta)=2\delta. $$


Only top voted, non community-wiki answers of a minimum length are eligible