import itertools
from typing import List, Tuple, Set
def nand(a: bool, b: bool) -> bool:
"""NAND gate implementation"""
return not (a and b)
def evaluate_original_function(B: bool, C: bool, D: bool, E: bool) -> bool:
"""Evaluate F = B'C + CE' + CD"""
term1 = (not B) and C
term2 = C and (not E)
term3 = C and D
return term1 or term2 or term3
def generate_truth_table() -> List[Tuple]:
"""Generate truth table for the original function"""
truth_table = []
for B, C, D, E in itertools.product([False, True], repeat=4):
output = evaluate_original_function(B, C, D, E)
truth_table.append((B, C, D, E, output))
return truth_table
def evaluate_nand_circuit(inputs: Tuple[bool, bool, bool, bool], gates: List[Tuple]) -> bool:
"""
Evaluate a NAND circuit given inputs and gate connections.
gates format: [(input1_idx, input2_idx), ...] where idx refers to:
0-3: original inputs (B, C, D, E)
4+: outputs of previous gates
"""
B, C, D, E = inputs
values = [B, C, D, E] # indices 0-3 are inputs
for gate in gates:
input1_idx, input2_idx = gate
if input1_idx >= len(values) or input2_idx >= len(values):
return False # Invalid circuit
result = nand(values[input1_idx], values[input2_idx])
values.append(result)
return values[-1] if values else False # Return last gate output
def test_circuit_equivalence(gates: List[Tuple], truth_table: List[Tuple]) -> bool:
"""Test if a NAND circuit produces the same truth table as original function"""
for row in truth_table:
B, C, D, E, expected = row
actual = evaluate_nand_circuit((B, C, D, E), gates)
if actual != expected:
return False
return True
def generate_circuit_candidates(max_gates: int) -> List[List[Tuple]]:
"""Generate all possible NAND circuit configurations up to max_gates"""
candidates = []
def generate_recursive(current_gates: List[Tuple], remaining_gates: int, max_inputs: int):
if remaining_gates == 0:
if current_gates: # Don't include empty circuits
candidates.append(current_gates.copy())
return
# Generate all possible connections for the next gate
for i in range(max_inputs):
for j in range(i, max_inputs): # j >= i to avoid duplicate gates like (0,1) and (1,0)
new_gates = current_gates + [(i, j)]
generate_recursive(new_gates, remaining_gates - 1, max_inputs + 1)
for num_gates in range(1, max_gates + 1):
generate_recursive([], num_gates, 4) # Start with 4 inputs (B, C, D, E)
return candidates
def find_minimal_nand_implementation(max_gates: int = 6) -> Tuple[List[Tuple], int]:
"""Find minimal NAND gate implementation"""
print("Generating truth table for F = B'C + CE' + CD...")
truth_table = generate_truth_table()
print("\nTruth Table:")
print("B C D E | F")
print("-" * 9)
for B, C, D, E, F in truth_table:
print(f"{int(B)} {int(C)} {int(D)} {int(E)} | {int(F)}")
print(f"\nSearching for minimal NAND implementation (up to {max_gates} gates)...")
# Generate and test circuits in order of increasing complexity
for num_gates in range(1, max_gates + 1):
print(f"\nTesting {num_gates}-gate circuits...")
candidates = generate_circuit_candidates(num_gates)
tested = 0
for gates in candidates:
tested += 1
if tested % 1000 == 0:
print(f" Tested {tested} circuits...")
if test_circuit_equivalence(gates, truth_table):
return gates, num_gates
return None, -1
def print_circuit_description(gates: List[Tuple]):
"""Print human-readable description of the circuit"""
input_names = ['B', 'C', 'D', 'E']
print("\nCircuit Description:")
for i, (in1, in2) in enumerate(gates):
gate_num = i + 1
# Get input names
if in1 < 4:
input1_name = input_names[in1]
else:
input1_name = f"G{in1-3}" # Gate output
if in2 < 4:
input2_name = input_names[in2]
else:
input2_name = f"G{in2-3}" # Gate output
if i == len(gates) - 1: # Last gate is output
print(f"F = NAND({input1_name}, {input2_name})")
else:
print(f"G{gate_num} = NAND({input1_name}, {input2_name})")
def verify_solution(gates: List[Tuple]):
"""Verify the solution by testing all input combinations"""
print("\nVerification:")
print("B C D E | Original | NAND Circuit | Match")
print("-" * 41)
all_match = True
for B, C, D, E in itertools.product([False, True], repeat=4):
original = evaluate_original_function(B, C, D, E)
circuit = evaluate_nand_circuit((B, C, D, E), gates)
match = original == circuit
all_match &= match
print(f"{int(B)} {int(C)} {int(D)} {int(E)} | {int(original)} | {int(circuit)} | {'✓' if match else '✗'}")
print(f"\nAll outputs match: {'✓' if all_match else '✗'}")
return all_match
# Main execution
if __name__ == "__main__":
print("=== NAND Gate Minimization for F = B'C + CE' + CD ===\n")
# Find minimal implementation
solution, num_gates = find_minimal_nand_implementation(max_gates=8)
if solution:
print(f"\n🎉 Found minimal implementation with {num_gates} NAND gates!")
print(f"Gate connections: {solution}")
print_circuit_description(solution)
verify_solution(solution)
# Analyze the boolean expression equivalent
print(f"\nThe minimal NAND implementation uses {num_gates} gates.")
print("Each NAND gate implements: NAND(A,B) = (AB)'")
else:
print("\n❌ No solution found within the specified gate limit.")
print("Try increasing max_gates parameter.")
# Additional analysis
print(f"\n=== Additional Analysis ===")
print("Original function: F = B'C + CE' + CD")
print("This can be factored as: F = C(B' + E' + D)")
print("Using De Morgan's laws and NAND equivalencies:")
print("F = C · (B' + E' + D)")
print("F = C · ((BE)' + D) [since B' + E' = (BE)']")
print("F = C · (BED')' [since (BE)' + D = (BED')']")
# Show systematic approach
print(f"\n=== Systematic Search Results ===")
print("The algorithm systematically tests all possible NAND gate configurations")
print("starting from 1 gate up to the specified maximum, ensuring the")
print("minimal solution is found first.")