Logical equivalences cancellation

Question

Given a propositional term, I know we can substitute terms inside it if they are logically equivalent. Now, whenever we simplify propositional terms, whenever there is a term which is always true, i.e $(p \lor \neg p)$, or a term which is always false i.e $(p \land \neg p)$, we can just cancel it from the term. For example, in the term $$(\neg p \lor r)\land((\neg q \land \neg r) \lor (r \land \neg r))$$

We can just remove the term $(r \land \neg r)$. My lecturer justifies this by saying "because it's always $FALSE$", but it doesn't sit right with me. Why is this so? What are we replacing it with that is logically equivalent to it?

Answer 1

$p \land \neg p$ is indeed a contradiction, and in logic we use $\bot$ for that, so you can always replace $p \land \neg p$ with $\bot$

However, to completely get rid of a term, you need an equivalence like:

$$p \lor \bot \Leftrightarrow p$$

Please note though that this only works with $\lor$, because in connection with the $\land $ you have:

$$p \land \bot \Leftrightarrow \bot$$

Also, a term like $p \lor \neg p$ is a tautology, and for that we use $\top$.

And some useful equivalences for the $\top$ are:

$$p \land \top \Leftrightarrow p$$

and

$$p \lor \top \Leftrightarrow \top$$

Answer 2

Here, you can remove the term $(r \land \neg r)$ because of the $\lor$ operation in the expression $(\neg q \land \neg r) \lor (r \land \neg r)$. Since we know that $(r \land \neg r) = F$ and $F \lor x = x$, we can simply remove the term which is equivalent to $F$ in a situation like this one.

For example if it was $F \land x$, this time, we could have removed $x$ without considering its truth value because $F \land x = F$.

(Note: $F$ stands for $FALSE$ statement, i.e. contradiction. $x$ is any logical expression which has truth value $T$ or $F$)

Answer 3

Your text should have a table of "rules of boolean algebra" , "rules of propositional calculus", or such, which contains these rules and more.

$\begin{array}{r|c:c} \text{Identity} & a\wedge \top = a & a\vee\bot = a\\ \text{Annihilation} & a\wedge\bot = \bot & a\vee\top = \top\\ \text{Complementation} & a\wedge\neg a=\bot & a\vee\neg a =\top\\ \text{Idempotence} & a\wedge a=a & a\vee a=a \end{array}$

The cancelation, which your professor used, results by combining complementation and identity rules.   The pattern happens so often that the middle step is usually skipped over to save time and space. $$a\vee(b\wedge\neg b)=a\vee\bot=a\\a\wedge(b\vee\neg b)=a\wedge \top = a$$

---

The "top" symbol $\top$ is tautology (or true). $~T$ or $1$ may sometimes be used to represent this truth constant.

The "bottom" symbol $\bot$ is contradction (or false). $~F$ or $0$ may sometimes be used to represent this falsity constant.