Wikipedia:Reference desk/Archives/Mathematics/2022 October 26

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 26

Boolean algebra

I have four Boolean variables, $v$, $t$, $p$ and $f$. The only thing that is known a priori about them is that $\neg v\lor \neg t\implies \neg f$. Now I want to do different things in my system depending on whether:

• $p\land f$
• $v\land t\land p\land \neg f$, or
• $\neg v\lor \neg t\lor \neg p$.

I needed to know that these three cases are mutually exclusive and that they cover all possibilities (or in other words, that exactly one of them is true, regardless of what "legal" values the variables have). Now, there are only sixteen possible values of the variables, only ten of which fulfil the requirement, so this is easily brute-forced either by hand or with a simple loop in any language. But as I'm curious, it would be satisfying to know how it could also have been solved algebraically (as I assume it could!), and I'm rusty and at a loss here. Any pointers on how to think would be appreciated. Jao (talk) 11:43, 26 October 2022 (UTC)

To show that $Y$ holds given a priori knowledge that $X$ holds is tantamount to showing that $X\Rightarrow Y,$ (or, equivalently, $\neg X\lor Y$) is a tautology. Here there are four things you want to show: the validity of the disjunction of the three bulleted formulas, and the negation of the conjunction of each of the three pairs chosen from the bulleted formulas. An algebraic version of exhaustively enumerating the possibilities to show that a given formula is a tautology is as follows:

1. Augment the formula by adding the conjunction of all formulas of the form $V\lor \neg V,$ where $V$ ranges over the $N$ variables occurring in the formula.
2. Expand the result into disjunctive normal form (DNF). Here, rather than taking the syntactic view of a formula as a linear string of symbols, we consider a conjunction in a DNF to be given as a set of literals, and a DNF itself as a set of such conjunctions. So we view $(A\land \neg B\land \neg C)\lor (\neg D\land E\land F)$ as $\bigvee \{\bigwedge \{A,\neg B,\neg C\},\bigwedge \{\neg D,E,F\}\}.$
3. Remove all conjunctions that contain both a variable and its negation.
4. Check that the cardinality of the resulting DNF is $2^{N}.$

Brute force indeed, and often overkill, but easily translated into purely algebraic operations and guaranteed to work.  --Lambiam 22:51, 26 October 2022 (UTC)

Thank you very much. Full DNF was what I was looking for, it rings a bell from the past. I have tried this out and gotten a hang of how it works. As you say, this is functionally pretty much equivalent to just jotting down and inspecting the truth table, and much more work at that, so I won't switch to this method for such tasks, but somehow this knowledge was important to me. Jao (talk) 04:45, 28 October 2022 (UTC)