Propositional calculus algebra

Question

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)$$

Answer 1

$$\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$

Answer 2

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 $$

Answer 3

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:

1. Express all logical connectives expressed in XOR, AND and TRUE $: (+,\cdot,1)$
2. 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.
3. 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$