Logical Expression Evaluator — Notes

1. Introduction

This project implements a complete system for the analysis, evaluation, and minimization of propositional logic expressions.

Given a textual input, for example A AND (B OR C), the system executes a pipeline composed of:

• lexical analysis (tokenizer)
• syntactic analysis (parser)
• AST construction
• logical evaluation
• truth table generation
• minterm extraction
• minimization using Quine-McCluskey and Petrick
• minimality verification
• visualization through a Karnaugh map

The goal is to provide both a structured representation and an optimized form of the expression.

---

2. System Architecture

The system is organized into independent modules, each responsible for a specific stage of the pipeline:

Input → Tokenizer → Parser → AST → Evaluator
→ Truth Table → Minterms → Minimization
→ Minimality → Karnaugh Map

This separation ensures modularity, reusability, and ease of testing.

---

3. Internal Representation: Abstract Syntax Tree

The logical expression is represented as an Abstract Syntax Tree (AST).

• Internal nodes represent logical operators (AND, OR, NOT, etc.)
• Leaves represent variables or constants (TRUE, FALSE)

Example:

A AND (B OR C)

        AND
       /   \
      A     OR
           /  \
          B    C

The file node.py defines the node structure and the supporting methods (is_variable, is_constant, etc.).

---

4. Lexical and Syntactic Analysis

Tokenizer (tokenizer.py)

It transforms the input string into a sequence of tokens:

"A AND B" → [VAR:A, AND, VAR:B]

It supports:

• operators: NOT, AND, OR, XOR, NAND, NOR, IMPLIES, IFF
• constants: TRUE, FALSE
• parentheses

---

Parser (logic_parser.py)

The parser is a recursive descent parser and respects operator precedence:

IFF < IMPLIES < OR < XOR < NOR < AND < NAND < NOT

It builds the AST while ensuring:

• correct associativity
• proper handling of parentheses
• detection of syntactic errors

---

5. Expression Evaluation

The evaluator.py module recursively evaluates the AST.

Examples:

• AND: left AND right
• NOT: NOT operand
• IMPLIES: NOT A OR B
• IFF: logical equivalence

The result is a Boolean value (True / False).

---

6. Truth Table and Minterms

Truth Table (truth_table.py)

It generates all possible combinations of the variables (2ⁿ) and evaluates the expression for each one.

It can also display the results of intermediate sub-expressions.

---

Minterms (minterms.py)

It extracts the indices of the combinations for which the function is true.

Examples:

• A OR B → [1, 2, 3]
• TRUE → [0]
• FALSE → []

This step is essential for minimization.

---

7. Boolean Minimization

Minimization is implemented through:

• Quine-McCluskey → generation of prime implicants
• Petrick’s Method → selection of the minimum cover

Main files:

• quine_mccluskey.py
• qm_*
• minimize.py

---

Minimization Output

The system produces two forms:

Verbose form

(A AND C) OR (A AND B)

Compact form (Boolean algebra)

AC + AB

The compact form is more suitable for representation through a Karnaugh map.

---

8. Minimality Verification

The main issue is that operators such as XOR or NAND are not directly comparable with the SOP form.

Adopted Solution

1. Normalization (normalize.py)

   • converts all expressions into terms of AND, OR, and NOT

2. Cost function

cost = (number of OR terms, number of literals)

3. Criterion

original_cost ≤ minimized_cost

This also allows factored forms, for example A(B + C), to be considered equivalent to or better than the SOP form.

---

9. Karnaugh Map

The kmap.py module generates Karnaugh maps for 2–4 variables.

Features:

• use of Gray code
• correct cell arrangement
• consistency with the minterms

Example:

AB\CD   00  01  11  10
-----------------------
00       1   1   0   1
01       0   0   1   0
10       1   1   1   1
11       1   1   1   1

The map is useful for visualizing the function and validating the minimization.

---

10. Main Program

The main.py file coordinates the entire process:

1. user input
2. tokenization
3. parsing
4. AST printing
5. truth table
6. minterms
7. minimization
8. minimality analysis
9. Karnaugh map

It includes handling for syntactic and runtime errors.

---

11. Testing

The test_program.py file runs automatic tests on:

• constants (TRUE, FALSE)
• basic operators
• tautologies and contradictions
• complex expressions
• syntactic errors

It verifies:

• correctness of the minterms
• consistency of the minimization
• validity of the K-map

---

12. Conclusions

The project implements a complete system for manipulating logical expressions, integrating:

• formal parsing
• semantic evaluation
• Boolean optimization
• compact representation

Strengths:

• modular architecture
• support for advanced operators
• automatic minimization
• dual representation (verbose and compact)

Limitations:

• Karnaugh maps are limited to 4 variables
• the minimality criterion is based on a structural metric

Overall, the system can be seen as a mini logic compiler, combining Boolean algebra theory with practical implementation.