Intereting Posts

Show $\sum\limits_{d|n}\phi(d) = n$.
Prove: $ \frac{1}{\sin 2x} + \frac{1}{\sin 4x } + \cdots + \frac{1 }{\sin 2^n x} = \cot x – \cot 2^n x $
Let $u:\mathbb{C}\rightarrow\mathbb{R}$ be a harmonic function such that $0\leq f(z)$ for all $ z \in \mathbb{C}$. Prove that $u$ is constant.
Equality of two notions of tensor products over a commutative ring
Number of Squares in a circle
Strategies for Factoring Expressions with Four Terms
Calculating $\sum_{k=0}^{n}\sin(k\theta)$
Homology Group of Quotient Space
Uncountable product of separable spaces is separable?
Subset of natural numbers such that any natural number except 1 can be expressed as sum of two elements
Some way to integrate $\sin(x^2)$?
If $E_P(X) \in $ span($E_{P_i}(X)$), $1 \leq i \leq n$, for all integrable $X$, then is $P$ a convex combination of the $P_i$?
Multiples of an irrational number forming a dense subset
Products and Stone-Čech compactification
show $\frac{1}{15}< \frac{1}{2}\times\frac{3}{4}\times\cdots\times\frac{99}{100}<\frac{1}{10}$ is true

I am currently working through Velleman’s book *How To Prove It* and was asked to prove the following

$(P \leftrightarrow Q) \equiv (P \wedge Q) \vee (\neg P \wedge \neg Q)$

This is my work thus far

- Can someone explain consensus theorem for boolean algebra
- If $B$ is an infinite complete Boolean algebra, then its saturation is a regular uncountable cardinal
- Power set representation of a boolean ring/algebra
- how many semantically different boolean functions are there for n boolean variables?
- If $\phi$ is a tautology then dual $\phi$ is a contradiction.
- Prove XOR is commutative and associative?

$(P \to Q) \wedge (Q \to P)$

$(\neg P \vee Q) \wedge (\neg Q \vee P)$ (since $(P \to Q) \equiv (\neg P \vee Q)$)

$\neg[\neg(\neg P \vee Q) \vee \neg (\neg Q \vee P)]$ (Demorgan’s Law)

$\neg [(P \wedge \neg Q) \vee (Q \wedge \neg P)]$ (Demorgan’s Law)

At this point I am little unsure how to proceed.

Here are a few things I’ve tried or considered thus far:

I thought that I could perhaps switch some of the terms in step 3 using the law of associativity however the $\neg$ on the outside of the two terms prevents me from doing so (constructing a truth table for $\neg (\neg P \vee Q) \vee (\neg Q \vee P)$ and $\neg (\neg P \vee \neg Q) \vee \neg (P \vee Q)$ for sanity purposes)

I can’t seem to apply the law of distribution since the corresponding terms are negated.

Applying demorgans law to one of the terms individually on step 2 or 3 doesnt seem to get me very far either.

Did I perhaps skip something? Am I even on the right track? Any help is appreciated

- What is the exact definition of a reflexive relation?
- Prove $\langle \mathbb{N}, x \mapsto x +1, 1 \rangle$ is a Peano system without circular reasoning
- Show that $p \Rightarrow (\neg(q \land \neg p))$ is a tautology
- Are axioms assumed to be true in a formal system?
- Prove that $\beta \rightarrow \neg \neg \beta$ is a theorem using standard axioms 1,2,3 and MP
- State of the progess of the automated proof checking
- Entailment relations that are not partial orders
- DNF form ( $ \neg ((p \wedge q) \equiv (r \vee s)) $ )
- How can you pick the odd marble by 3 steps in this case?
- A *finite* first order theory whose finite models are exactly the $\Bbb F_p$?

$$(P \leftrightarrow Q) \equiv (P \wedge Q) \vee (\neg P \wedge \neg Q)$$

I’ll start with your initial work, but instead of employing DeMorgan’s as you did, we’ll use the Distributive Law (DL), in two “steps”:

$$\begin{align} (P \leftrightarrow Q) &\equiv (P \to Q) \wedge (Q \to P) \tag{correct}\\ \\

&\equiv (\color{blue}{\bf \lnot P \lor Q}) \land (\color{red}{\bf \lnot Q \lor P})\tag{correct} \\ \\

&\equiv \Big[\color{blue}{\bf \lnot P} {\land} \color{red}{\bf(\lnot Q \lor P)}\Big] \color{blue}{\lor} \Big[\color{blue}{\bf Q} \land \color{red}{\bf (\lnot Q \lor P)}\Big]\tag{DL}\\ \\

& \equiv \Big[(\color{blue}{\bf \lnot P} \land \color{red}{\bf\lnot Q)} \lor (\color{blue}{\bf\lnot P} \land \color{red}{\bf P})\Big] \lor \Big[(\color{blue}{\bf Q} \land \color{red}{\bf \lnot Q}) \lor (\color{blue}{\bf Q} \land \color{red}{\bf P})\Big]\tag{DL} \\ \\

&\equiv \Big[({\lnot P}\land \lnot Q) \lor \text{False}\Big] \lor \Big[\text{False} \lor (Q \land P)\Big]\tag{why?} \\ \\

&\equiv (P \land Q) \lor (\lnot P \land \lnot Q)\tag{why?}\end{align}$$

That’s a great book. You’ll learn a lot from it.

Justify the following: $$\begin{align} (\neg P \lor Q) \land (\neg Q \lor P) &\equiv[(\neg P\lor Q) \land \neg Q] \lor [(\neg P\lor Q)\land P] \\

&\equiv [(\neg P \land \neg Q) \lor (Q\land \neg Q)]\lor [(\neg P\land P)\lor (Q\land P)] \\

&\equiv (\neg P\land \neg Q) \lor (Q\land P).\end{align}$$

You can also “reverse” amWhy solution, starting with :

$(P \land Q) \lor ( \lnot P \land \lnot Q)$

you can use the distributivity laws to obtain :

$$[(P \land Q) \lor \lnot P] \land [(P \land Q) \lor \lnot Q]$$

and again :

$$(P \lor \lnot P) \land (Q \lor \lnot P) \land (P \lor \lnot Q) \land (Q \lor \lnot Q]$$

i.e.

$$T \land (Q \lor \lnot P) \land (P \lor \lnot Q) \land T$$

i.e.

$$(Q \lor \lnot P) \land (P \lor \lnot Q)$$

Now we use the equivalence between $(\lnot A \lor B) \quad$ and $\quad (A \rightarrow B)$, and get :

$$(P \rightarrow Q) \land (Q \rightarrow P)$$

that is

$P \leftrightarrow Q$.

- Solving higher order logarithms integrals without the beta function
- About Euclid's Elements and modern video games
- What is meant with unique smallest/largest topology?
- Prove lower bound $\sum\limits_{k=1}^{n}\frac{1}{\sqrt{n^2+k^2}}\ge\left(1-\frac{1}{n}\right)\ln{(1+\sqrt{2})}+\frac{\sqrt{2}}{2n}$
- Prove that $0 \leq ab + ac + bc – abc \leq 2.$
- Inner Product Spaces – Triangle Inequality
- Every finite abelian group is the Galois group of of some finite extension of the rationals
- Evaluate $\int_0^{2\pi}\frac{1}{1 + A\sin(\theta) + B\cos(\theta)}\, \mathrm{d}\theta \ \text{ for }\ A,B <<1$
- Composition of measurable function and continuous function
- Construction of uncountably many non-isomorphic linear (total) orderings of natural numbers
- Jacobson radical of a ring finitely generated over $\mathbb Z$
- Why are maximal ideals prime?
- Give me such a $“3n±Q”$ problem that we do not know a counter-example
- Help with $\int\frac{1}{1+x^8}dx$
- On critical points of a large function