Boolean function sum-of-products expansion

[Samuel-Lubliner]

Originally, I wanted to dive into the simplification of Boolean functions. After re-watching the Colman lectures I figured there was lots to add to the Boolean Algebra. This PR aims to match the flow of the lecture videos. I didn't want to make a huge PR so I'll dive more into simplification in the next PR.

While working on this chapter, I discovered that we cannot compare truth tables for equivalence. I opened a new issue to address this in the Logic chapter.

# True
h_idempotent == h

# Why is this False?
h_idempotent.truthtable() == h.truthtable()

I have been investigating simplification of Boolean functions in Sage and I am finding the topic very interesting.

This is dated. Not all the links work. Still very informative Boolean Formulas (Propositional Calculus) in Sage by Andreas Sekine

If we look at the Sage source code: https://github.com/sagemath/sage/blob/e042294b5ed8e1cb564965079e20e4270ccde340/src/sage/logic/logic.py#L321

# TODO: implement the simplify function which calls
# a c++ implementation of the ESPRESSO algorithm
# to simplify the truthtable: probably Minilog

Sage simplify() still needs to be implemented. Although c++ ESPRESSO is the way to go, Sympy seems capable. https://stackoverflow.com/questions/68483922/creating-dnf-and-cnf-in-python-out-of-a-logictable-sympy-sagemath

Strangely, simply() still exists here, but it is commented out from this commit 15 years ago. https://github.com/sagemath/sage/blob/e042294b5ed8e1cb564965079e20e4270ccde340/src/sage/logic/boolformula.py#L1016

I'm still reviewing https://doc.sagemath.org/html/en/reference/logic/index.html and there is some promise for using currently implemented methods for simplifying Boolean expressions. While covert to Disjunctive Normal Form is not implemented, converting a Boolean formula to conjunctive normal form is implemented.

[Samuel-Lubliner]

@Zune-Ahmed I also noticed this exists source/boolean-algebra/sec-boolean-definition.ptx but it is not included anywhere in the book. Was this supposed to be deleted?

[Zune-Ahmed]

We are supposed to keep it but I didn’t get a chance to add content to it.

---

From: Samuel Lubliner @.> Sent: Sunday, September 1, 2024 2:56:05 AM To: SageMathOER-CCC/sage-discrete-math @.> Cc: Zunaid Ahmed @.>; Mention @.> Subject: Re: [SageMathOER-CCC/sage-discrete-math] Boolean function sum-of-products expansion (PR #113)

@Zune-Ahmedhttps://github.com/Zune-Ahmed I also noticed this exists source/boolean-algebra/sec-boolean-definition.ptx but it is not included anywhere in the book. Was this supposed to be deleted?

— Reply to this email directly, view it on GitHubhttps://github.com/SageMathOER-CCC/sage-discrete-math/pull/113#issuecomment-2323218747, or unsubscribehttps://github.com/notifications/unsubscribe-auth/A5KWWUQDERDKZN2MJZFJBYDZULCBLAVCNFSM6AAAAABNORKQFOVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDGMRTGIYTQNZUG4. You are receiving this because you were mentioned.Message ID: @.***>

[boughrira]

# Why is this False?
h_idempotent.truthtable() == h.truthtable()

One possible explanation is that the behavior of the equality operator has not been overridden to actually compare the content of the truthtable of each of the two instances h_idempotent and h. I think the default behavior for the == operator would be to test/check if the two objects point to the same memory address of the underlying object. You can validate this assumption with an assignment before the comparison check.

[boughrira]

One more suggestion regarding PRs: Having temporary commits/messages would be fine while still working on the changes, but could we agree to squash/clean up any temporary commits before making the PR ready for review?

Grouping relatively related and small changes into a single commit with a meaningful message helps reduce the noise and keep the repository's history clean, but more importantly, helps the reviewers to step through the changes by commits (especially helpful for large changes)

[Samuel-Lubliner]

Closes #114