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

• I did not know that reverse Distributive law has been applied. It has been made clear by @amWhy Commented Oct 13, 2014 at 6:26

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

• OH! Distributive law has been used in reverse? That is the point, I was unable to understand. Thanks a ton! Commented Oct 12, 2014 at 12:42
• Yes, as a rule of replacement, we have $\lnot p \land (\lnot q \lor q) \overset{\leftrightarrow}{\equiv} (\lnot p \land \lnot q) \lor (\lnot p \land q)$, and the equivalence goes both directions. Commented Oct 12, 2014 at 12:48
• I am new to this site. can you tell me a source to learn the markup language for writing logic symbols? Commented Oct 12, 2014 at 12:59
• For some basic information about writing math at this site see e.g. here, here, here and here. You can also click on "edited..." in the lower center part of the post to view the formatting of posts that use the markup in which you are interested. Commented Oct 12, 2014 at 13:05

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

• You make a mismatch of logical expressions and numerical expressions. If you write $T(\neg p)=1-T(p)$ I will agree.
– Lehs
Commented Oct 12, 2014 at 13:39
• @Lehs, it's called Boolean Algebra. Look it up.
– k170
Commented Oct 12, 2014 at 13:54
• No it doesn't. It's called mismatch.
– Lehs
Commented Oct 12, 2014 at 14:07
• @Lehs, okay, so where exactly is this "mismatch" in my post? Please enlighten me.
– k170
Commented Oct 12, 2014 at 14:12
• LHS is logical values and RHS is corresponding arithmetical values. There are no - + x etc defined for logical values. You should look at it as a function from logical expressions/values to the set $\mathbb Z$. Doing so everything works OK in your calculation.
– Lehs
Commented Oct 12, 2014 at 14:25

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$