Boolean algebra rules

Question

I'm starting to learn Boolean algebra in the university, but I'm having difficulties trying to fully understand some rules.

1) If this expression “$A\Rightarrow B$” which is the same as saying as “$\lnot A \lor B$”, right? So take a look at this next expression:

$$\lnot(\lnot A \Rightarrow B) = (A \Rightarrow B) = \lnot A \lor B$$

My question is, does this “$A$” become negative once again in the last expression?

What about this one:

$$\lnot A \Rightarrow B = \lnot\lnot A \lor B = A \lor B$$

Here “$A$” has already a “not” before it, do I have to put another one (because of the $\Rightarrow$) like I did in the second expression?

Finally, accordingly to DeMorgan’s Law:

$\lnot(A\lor B)=(\lnot A)\land(\lnot B)$, is this applicable in an XOR statement: $\lnot(A \oplus B)=(\lnot A)\land(\lnot B)$; or we just calculate the XOR and we put the result in the negative afterwards? Or can we do it like this: $\lnot(A \oplus B) = \lnot A \oplus \lnot B$?

I hope my questions were nonsense, if did not understand them please let me know.

Cheers :)

Answer 1

Since $A\Rightarrow B$ is the same as $\lnot A\lor B$ (and the $\lnot$ only applies to $A$, by standard convention), we have \begin{align} \lnot(\lnot A\Rightarrow B) &\equiv \lnot(\lnot(\lnot A)\lor B) &&\text{definition} \\ &\equiv \lnot(A\lor B) &&\text{double negation} \\ &\equiv \lnot A\land \lnot B &&\text{De Morgan} \\ \end{align} Note that again $\lnot$ only applies to $A$ in the formula we start with.

Similarly \begin{align} \lnot A\Rightarrow B &\equiv \lnot(\lnot A)\lor B &&\text{definition} \\ &\equiv A\lor B &&\text{double negation} \end{align}

Let's have a look at the XOR. First by informally analyzing its meaning. The statement $A\oplus B$ is true if and only if one among $A$ and $B$ is true, but not both. So the statement is false (that is, its negation is true) if and only if $A$ and $B$ are either both true or both false.

Can we say the same for $\lnot A\oplus\lnot B$? No, this is true if and only if exactly one among $A$ and $B$ is false. Thus we can see that neither $\lnot A\land\lnot B$ nor $\lnot A\oplus\lnot B$ fits the bill.

If we look at the truth tables $$ \begin{array}{cccccccccc} A & B & A\oplus B & \lnot(A\oplus B) & \lnot A\oplus \lnot B & \lnot A\land\lnot B \\ \hline T & T & F & T & F & F \\ T & F & T & F & T & F \\ F & T & T & F & T & F \\ F & F & F & T & F & T \end{array} $$ What you can say is that $$ \lnot(A\oplus B)\equiv\lnot(\lnot A\oplus \lnot B) $$ looking at the fourth and fifth columns.

---

In boolean ring terms, the XOR is denoted by $+$ and the negation of $x$ is $1+x$; so (taking into account that $1+1=0$) $$ 1+(a+b)=1+a+b=1+a+1+1+b=1+(1+a)+(1+b) $$ which confirms what the truth tables gave.

Answer 2

You are correct in saying $$A\implies B\equiv\neg A\lor B.$$

You can always use truth tables to check what you've done, e.g. for $$¬(¬ A => B) = (A => B) = ¬A V B,$$ we can write $$\left.\begin{array}{c|c} A&B& \neg A&\neg A\implies B&\neg(\neg A\implies B)&A\implies B&\neg A\lor B\\ \hline 0&0& 1&0&1&1&1\\ 0&1& 1&1&0&1&1\\ 1&0& 0&1&0&0&0\\ 1&1& 0&1&0&1&1 \end{array}\right..$$

So you can see that $\neg(\neg A\implies B)$ is not the same as $A\implies B$, but that $A\implies B$ is the same as $\neg A\lor B$.

I think it is generally accpeted that statements such as $$\neg A\lor B\equiv (\neg A)\lor B.$$

Note: I always found $\implies$ tricky to understand/remember, until I learned of the following perspective. Let $A=$"put money in vending machine," and $B=$"vending machine dispensed item."

$$\left.\begin{array}{c|c|c|l} A&B& A\implies B&\text{Interpretation}\\ \hline 0&0& 1&\text{I'm happy because I didn't pay and the machine didn't dispense.}\\ 0&1& 1&\text{I'm happy because it's my lucky day (freebie)}\\ 1&0& 0&\text{I'm not happy - the machine took my money without dispensing.}\\ 1&1& 1&\text{I'm happy - I paid and the machine dispensed.} \end{array}\right.$$

UPDATE

Exclusive or, as denoted by $\oplus$, is "one or the other but not both," (note here the use of the English word "or" which is not usually the same as the logical or $\lor$), so we have

$$\left.\begin{array}{c|c} A&B& A\oplus B&\neg(A\oplus B)&\neg A&\neg B&\neg A\land\neg B\\ \hline 0&0& 0&1&1&1&1\\ 0&1& 1&0&1&0&0\\ 1&0& 1&0&0&1&0\\ 1&1& 0&1&0&0&0 \end{array}\right..$$

So you can see that $\neg(A\oplus B)\not\equiv \neg A\land\neg B$.