Truth Functional Logic for Hackers – Part One

Bob and Alice are two hackers working on an embedded system with a severe computational constraint – there is a bug in their low-cost microcontroller making OR operations significantly slower than any other operation on the chipset.

When they profiled their micropython code, they found that OR operations were up to 5x slower than any other operation.

Alice

This is a big problem! We could replace the faulty chips with better ones, if they arrive before the deadline.

Bob

I don’t think we can afford to wait – the deadline is in 3 days. A better option is to rewrite the code to avoid the OR operation.

Alice

How could we do that? We’re using the OR operation in a lot of critical places. Look:

def authorize_access(request):
    # A user is denied if they are on a blacklist OR 
    # their account is expired
    if (user_is_blacklisted(request.user_id) or 
        account_is_expired(request.account)
        return "Access denied"
    return "Access granted"

Let’s take a moment to understand the problem. The authorize_access function is used to check if a user is authorized to access a resource. The or operation is used to combine the conditions. How could we rewrite this function to avoid the OR operation?

To begin, lets take a look at the OR operation itself. OR is any case where either A or B are true (perhaps obviously).
The only time an OR is FALSE is when both inputs are themselves false.

We can express this in something called a truth table.

A truth table is a logic table used to determine the truth values of logical expressions based on their inputs. It systematically lists all possible combinations of input values and the corresponding output for each combination, allowing us to visualize how logical operations work.

Fill out this one to show which cases OR would be true:

(You can click on the table to toggle the unknown values)

Lets take the time as well to discuss some other basic operators Bob and Alice have available to them – AND and NOT.

AND requires BOTH inputs to be true for it to return true.

NOT simply “flips” the truth value of the input assigned to it.

Alice

Of course. These are the most basic operators in programming.

Bob

You’re right, they are basic. But what’s interesting is how we can combine them to create equivalent expressions. For example, we can rewrite OR using AND and NOT.

Alice

How would that work exactly?

Bob is a student of truth functional logic, which means he understands that many logical statements are equivalent. There are many, many ways to rewrite the authorize_access function without having to use the OR operation at all.

In truth functional logic (TFL), logical operators like AND, OR, and NOT can be expressed in terms of each other using logical equivalences. These equivalences are statements that have the same truth value in all possible interpretations.

For example, one of the most useful equivalences is De Morgan’s Law, which states:

• ¬(p ∨ q) ≡ (¬p ∧ ¬q)
• ¬(p ∧ q) ≡ (¬p ∨ ¬q)

Alice

What are those symbols? They look similar to the operators I know like & and ! in programming.

Bob

Good observation! In truth functional logic, we use special symbols to represent logical operations. The ‘¬’ symbol represents negation or NOT, similar to the ‘!’ in programming. The ‘∧’ is for AND, like ‘&’ in code, and ‘∨’ is for OR, similar to the ‘|’ operator. The ‘≡’ means “is equivalent to.”

Alice

I see. But why use different symbols instead of just using the programming ones?

Bob

TFL uses these symbols because they’re more precise and universal across different fields of logic and mathematics. They help logicians express complex ideas clearly without being tied to any specific programming language syntax. Plus, they make it easier to see the structure of logical formulas at a glance.

Alice

That makes sense. So how would we use these to rewrite an OR operation?

De Morgan’s Law, articulated in plain English, asserts that it is not the case that either P or Q is equivalent to the assertion that both P and Q are not true.

Let’s explore that with a truth table! This will be slightly more complicated then the prior ones, since we’re managing more operators at once.

To solve this table, we will work through each column step by step:

1. Start with the basic truth values for P and Q (columns 1 and 2)
2. Calculate ¬P by flipping the truth value of P (column 3)
3. Calculate ¬Q by flipping the truth value of Q (column 4)
4. Find P∨Q (OR) (column 5)
   • Remember, (OR) is true if either P or Q is True.
5. Calculate ¬(P∨Q) by flipping the values in column 5 (column 6)
   • Since we’re finding NOT P or Q
6. Calculate ¬P∧¬Q (AND) – true only when both ¬P and ¬Q are true (column 7)
   • Remember, (AND) is true only if P or Q is BOTH true.

Notice how columns 6 and 7 have identical values? This means they’re equivalent, demonstrating De Morgan’s Law: ¬(P∨Q) ≡ ¬P∧¬Q

Alice

That’s clever! So in our code, we could say: “it’s not the case that both cases are false” instead of “either case is true.”

Bob

Exactly! In fact, we could also express everything using only NAND operators. The NAND operation is quite powerful because it can be used to create any logical expression. For instance, we can rewrite our previous expressions using just NAND.

Alice

Really? How would that work?

Bob

Well, we can express AND, OR, and NOT using NAND. For example, NOT A can be represented as A NAND A, and A AND B can be expressed as (A NAND B) NAND (A NAND B). This means we can construct any logical operation, including our original function, using only NAND operations. With some creativity, we can derive all the necessary expressions without ever needing to use OR directly.

Using these equivalances, Bob and Alice rewrite their function:

def authorize_access(request):
    # Logically equivalent but using only NOT and AND operations
    if not (not user_is_blacklisted(request.user_id) and 
            not account_is_expired(request.account):
        return "Access denied"
    return "Access granted"

The rewritten function is logically identical, and we’ve proved it! Plus it runs significantly faster on their hardware. Bob and Alice have saved the day, with your help.

SQL queries often involve very complex logical conditions. Understanding equivalance can sometimes make queries more optimized in cases were certain logical structures take longer query times then others. For example:

SELECT * FROM transactions
WHERE NOT (customer_id = 101 AND transaction_date > '2023-01-01')

is equivalent to:

SELECT * FROM transactions
WHERE customer_id != 101 OR transaction_date <= '2023-01-01'

Cryptography

Cryptography as well is a case where strong fundamentals in logic can make or break an implementation. In homomorphic encryption (which allows computation on encrypted data), certain operations are more efficient than others due to the underlying cryptographic structures.

TFHE (Fast Fully Homomorphic Encryption over the Torus) is a widely used homomorphic encryption library where NAND gates are significantly faster than other operations. In Microsoft’s SEAL library implementation of FHE, NAND operations can be more efficient than direct OR operations.

Consider a privacy-preserving voting eligibility system where voter data is encrypted:

Original Logic:

def is_eligible_voter(encrypted_data):
    # A voter is eligible if they are a citizen OR 
    # (they are a permanent resident AND have lived here 5+ years)
    eligibility = homomorphic_or(
        encrypted_data.is_citizen(),
        homomorphic_and(
            encrypted_data.is_permanent_resident(),
            encrypted_data.lived_here_5_plus_years()
        )
    )
    return eligibility

This contains both AND and OR operations. Using De Morgan’s laws and the NAND universality property, we can rewrite it to use only NAND operations, which TFHE processes more efficiently:

Optimized for TFHE:

def is_eligible_voter(encrypted_data):
    # Step 1: Convert the OR using De Morgan: A OR B = NOT(NOT A AND NOT B)
    # Step 2: Express NOT in terms of NAND: NOT X = NAND(X, X)
    # Step 3: Express AND in terms of NAND: A AND B = NOT(NAND(A, B)) = NAND(NAND(A, B), NAND(A, B))
    
    citizen = encrypted_data.is_citizen()
    resident = encrypted_data.is_permanent_resident()
    years = encrypted_data.lived_here_5_plus_years()
    
    # NOT citizen using NAND
    not_citizen = homomorphic_nand(citizen, citizen)
    
    # resident AND years using NAND
    resident_and_years = homomorphic_nand(
        homomorphic_nand(resident, years),
        homomorphic_nand(resident, years)
    )
    
    # NOT (resident AND years) using NAND
    not_resident_and_years = homomorphic_nand(resident_and_years, resident_and_years)
    
    # NOT citizen AND NOT (resident AND years) using NAND
    not_both = homomorphic_nand(
        homomorphic_nand(not_citizen, not_resident_and_years),
        homomorphic_nand(not_citizen, not_resident_and_years)
    )
    
    # Final NOT to get: citizen OR (resident AND years)
    eligibility = homomorphic_nand(not_both, not_both)
    
    return eligibility

In production TFHE implementations, this transformation reduced computation time from minutes to seconds for complex eligibility checks on encrypted voter data, making privacy-preserving election systems practical for real-world use.

You can learn more about TFHE here.

The ability to transform logical expressions while preserving their meaning is a fundamental skill that empowers programmers to overcome constraints in virtually any computing context. It’s also just kind of neat.

The examples in this exploration merely scratch the surface of what’s possible when you deeply understand the principles of truth-functional logic.

For those interested in building a stronger foundation in logic, the Open Logic Project provides excellent free educational resources on propositional and predicate logic, formal proof systems, and other topics such as modal logic and set theory – all targetted towards a non-mathematical audience.