Propositional calculus algebra Can somebody explain me the following equivalence in propositional algebra(by the use of the laws of algebra):
$$\lnot(p \lor q) \lor (\lnot p \land q) \equiv \lnot p$$
I get stuck after $$\lnot(p \lor q) \lor (\lnot p \land q) \equiv (\lnot p \land \lnot q) \lor (\lnot p \land q)$$
 A: $$\begin{align} \underbrace{\lnot(p \lor q)}_{\large \equiv \;\lnot p \land \lnot q} \lor (\lnot p \land q) & \equiv (\color{blue}{\lnot p} \land \lnot q) \lor (\color{blue}{\lnot p} \land q) \tag{1} \\  
&\equiv \color{blue}{\lnot p} \land (\underbrace{\lnot q \lor q}_{\large\top}) \tag{2}  \\
&\equiv \lnot p \land \top\tag{3}\\ \\
&\equiv \lnot p \tag{4}
\end{align}$$
In $(1)$, we use DeMorgan's Law.
In $(2)$, we use the Distributive Law ("in reverse").
In $(3)$, we recognize that $\lnot q \lor q$ is a tautology: necessarily true, whatever the truth value of $q$.
In $(4)$, we invoke the identity: $\lnot p \land \top \equiv \lnot p$
A: First note that
$$ \lnot p\equiv 1-p $$
$$ p\land q\equiv pq $$
$$ p\lor q \equiv p+q-pq $$
So now let's start by simplifying the left side
$$ 1-(p+q-pq)\equiv 1-(p+q(1-p)) $$
$$ \equiv 1-p-q(1-p) \equiv (1-p)(1-q) $$
The right side is just $(1-p)q$, therefore 
$$ (1-p)(1-q)+ (1-p)q- (1-p)(1-q)(1-p)q $$
$$ \equiv (1-p)(1-q)+ (1-p)q- (1-p)(1-q)q $$
$$ \equiv (1-p)(1-q)+ (1-p)q- (1-p)0 $$
$$ \equiv (1-p)(1-q)+ (1-p)q $$
$$ \equiv (1-p)((1-q)+q) $$
$$ \equiv (1-p)(1) $$
$$ \equiv 1-p $$
A: There's sometimes a smart human solution but it could also be very difficult to find a solution for a general logical expression with several variables. However, there is an algorithm that almost always works but that sometimes is tedious:


*

*Express all logical connectives expressed in XOR, AND and TRUE $: (+,\cdot,1)$

*Use the algebraic laws (commutativity, associativity, distributivity, additive and multiplicative units, idempotence $X\cdot X=X$, and the additive inverse $X+X=0$) in Boolean rings to simplify almost like for numbers.

*Eventually try to simplify by substitute back to other connectives as below.


\begin{array}{l|l}
connective & substitute \\
\hline
\neg X& 1+X\\
X\wedge Y& XY\\
X\vee Y& X+Y+XY\\
X\oplus Y&X+Y\\
X\Rightarrow Y&1+X+XY\\
X\Leftrightarrow Y&1+X+Y
\end{array}
Your case in a straight forward manner:
$\lnot(p \lor q) \lor (\lnot p \land q)\Leftrightarrow$
$\neg(p+q+pq)\vee((1+p)q)\Leftrightarrow$
$(1+p+q+pq)\vee(q+pq)\Leftrightarrow$
$(1+p+q+pq)+(q+pq)+(1+p+q+pq)(q+pq)\Leftrightarrow$
$1+p+q+pq+q+pq+q+pq+pq+ppq+qq+qpq+pqq+pqpq\Leftrightarrow$
$1+p+q+q+q+q+pq+pq+pq+pq+pq+pq+pq+pq\Leftrightarrow 1+p\Leftrightarrow \neg p$
