Prompt:
create python script to solve logical minimization with quine mc cluskey algorithm.
parameters:
number_of_bits = 5
minterms = [4, 5, 7, 12, 15, 20, 21, 23, 28, 30]
xterms = [6, 14, 22, 26, 31]Hasil: https://claude.ai/share/c0418058-d739-488b-bd63-ddc09af78091
Output dari program python:
# python qq.py
QUINE-MCCLUSKEY ALGORITHM
==================================================
Starting Quine-McCluskey Algorithm
Number of bits: 5
Minterms: [4, 5, 7, 12, 15, 20, 21, 23, 28, 30]
Don't cares: [6, 14, 22, 26, 31]
--------------------------------------------------
Step 1: Initial grouping by number of ones
Group 1: [('00100', [4])]
Group 2: [('00101', [5]), ('01100', [12]), ('10100', [20]), ('00110', [6])]
Group 3: [('00111', [7]), ('10101', [21]), ('11100', [28]), ('01110', [14]), ('10110', [22]), ('11010', [26])]
Group 4: [('01111', [15]), ('10111', [23]), ('11110', [30])]
Group 5: [('11111', [31])]
Step 2.1: Combining terms
New Group 1: [('0010-', [4, 5]), ('0-100', [4, 12]), ('-0100', [4, 20]), ('001-0', [4, 6])]
New Group 2: [('001-1', [5, 7]), ('-0101', [5, 21]), ('-1100', [12, 28]), ('011-0', [12, 14]), ('1010-', [20, 21]), ('1-100', [20, 28]), ('101-0', [20, 22]), ('0011-', [6, 7]), ('0-110', [6, 14]), ('-0110', [6, 22])]
New Group 3: [('0-111', [7, 15]), ('-0111', [7, 23]), ('101-1', [21, 23]), ('111-0', [28, 30]), ('0111-', [14, 15]), ('-1110', [14, 30]), ('1011-', [22, 23]), ('1-110', [22, 30]), ('11-10', [26, 30])]
New Group 4: [('-1111', [15, 31]), ('1-111', [23, 31]), ('1111-', [30, 31])]
Step 2.2: Combining terms
New Group 1: [('-010-', [4, 5, 20, 21]), ('001--', [4, 5, 6, 7]), ('--100', [4, 12, 20, 28]), ('0-1-0', [4, 6, 12, 14]), ('-01-0', [4, 6, 20, 22])]
New Group 2: [('-01-1', [5, 7, 21, 23]), ('-11-0', [12, 14, 28, 30]), ('101--', [20, 21, 22, 23]), ('1-1-0', [20, 22, 28, 30]), ('0-11-', [6, 7, 14, 15]), ('-011-', [6, 7, 22, 23]), ('--110', [6, 14, 22, 30])]
New Group 3: [('--111', [7, 15, 23, 31]), ('-111-', [14, 15, 30, 31]), ('1-11-', [22, 23, 30, 31])]
Step 2.3: Combining terms
New Group 1: [('-01--', [4, 5, 6, 7, 20, 21, 22, 23]), ('--1-0', [4, 6, 12, 14, 20, 22, 28, 30])]
New Group 2: [('--11-', [6, 7, 14, 15, 22, 23, 30, 31])]
Step 2.4: Combining terms
Step 3: Prime Implicants Found
PI1: 11-10 covers [26, 30]
PI2: -01-- covers [4, 5, 6, 7, 20, 21, 22, 23]
PI3: --1-0 covers [4, 6, 12, 14, 20, 22, 28, 30]
PI4: --11- covers [6, 7, 14, 15, 22, 23, 30, 31]
Step 4: Coverage Table and Essential Prime Implicants
Coverage Table:
Minterm Binary Covered by PIs
-------------------------
4 00100 PI2, PI3
5 00101 PI2
7 00111 PI2, PI4
12 01100 PI3
15 01111 PI4
20 10100 PI2, PI3
21 10101 PI2
23 10111 PI2, PI4
28 11100 PI3
30 11110 PI1, PI3, PI4
Essential Prime Implicants:
PI2: -01-- (covers [4, 5, 6, 7, 20, 21, 22, 23])
PI3: --1-0 (covers [4, 6, 12, 14, 20, 22, 28, 30])
PI4: --11- (covers [6, 7, 14, 15, 22, 23, 30, 31])
FINAL RESULT:
==============================
Minimized Boolean Expression:
F = B'C + CE' + CD
Term breakdown:
Term 1: -01-- → B'C
Term 2: --1-0 → CE'
Term 3: --11- → CD
Tahap selanjutnya membuat dengan NAND gates:
Create iterative python code to find minimal implementation of the following boolean equation with 2 input NAND gates only .
F = B'C + CE' + CDHasil: https://claude.ai/public/artifacts/99ce4712-ab81-4f9e-8ead-2a25bee86cda
Output program python:
# python min.py
BOOLEAN FUNCTION IMPLEMENTATION WITH 2-INPUT NAND GATES
======================================================================
Function: F = B'C + CE' + CD
Step-by-Step Conversion to NAND Gates
==================================================
Original: F = B'C + CE' + CD
Step 1: Apply De Morgan's law
F = ((B'C + CE' + CD)')'
F = ((B'C)' · (CE')' · (CD)')'
Step 2: Convert each product term to NAND form
For any product AB: AB = (A NAND B)' = (A NAND B) NAND (A NAND B)
B'C where B' = B NAND B:
B'C = ((B NAND B) NAND C) NAND ((B NAND B) NAND C)
CE' where E' = E NAND E:
CE' = (C NAND (E NAND E)) NAND (C NAND (E NAND E))
CD:
CD = (C NAND D) NAND (C NAND D)
Step 3: Convert the sum to NAND form
A + B + C = ((A)' · (B)' · (C)')'
Where A', B', C' are complements of our product terms
This gives us the final NAND-only implementation.
NAND Gate Circuit Implementation
==================================================
F = B'C + CE' + CD
Gate connections:
1. G1 = B NAND B (generates B')
2. G2 = E NAND E (generates E')
3. G3 = G1 NAND C (intermediate for B'C)
4. G4 = G3 NAND G3 (generates B'C)
5. G5 = C NAND G2 (intermediate for CE')
6. G6 = G5 NAND G5 (generates CE')
7. G7 = C NAND D (intermediate for CD)
8. G8 = G7 NAND G7 (generates CD)
9. G9 = G4 NAND G4 (generates (B'C)')
10. G10 = G6 NAND G6 (generates (CE')')
11. G11 = G8 NAND G8 (generates (CD)')
12. G12 = G9 NAND G10 (intermediate)
13. G13 = G12 NAND G12 (generates (G9·G10))
14. G14 = G13 NAND G11 (intermediate)
15. G15 = G14 NAND G14 (generates (G13·G11))
16. G16 = G15 NAND G15 (final output F)
Total NAND gates required: 16
Truth Table Verification
============================================================
B | C | D | E || Original | NAND Impl | Match
------------------------------------------------------------
0 | 0 | 0 | 0 || 0 | 0 | ✓
0 | 0 | 0 | 1 || 0 | 0 | ✓
0 | 0 | 1 | 0 || 0 | 0 | ✓
0 | 0 | 1 | 1 || 0 | 0 | ✓
0 | 1 | 0 | 0 || 1 | 1 | ✓
0 | 1 | 0 | 1 || 1 | 1 | ✓
0 | 1 | 1 | 0 || 1 | 1 | ✓
0 | 1 | 1 | 1 || 1 | 1 | ✓
1 | 0 | 0 | 0 || 0 | 0 | ✓
1 | 0 | 0 | 1 || 0 | 0 | ✓
1 | 0 | 1 | 0 || 0 | 0 | ✓
1 | 0 | 1 | 1 || 0 | 0 | ✓
1 | 1 | 0 | 0 || 1 | 1 | ✓
1 | 1 | 0 | 1 || 0 | 0 | ✓
1 | 1 | 1 | 0 || 1 | 1 | ✓
1 | 1 | 1 | 1 || 1 | 1 | ✓
------------------------------------------------------------
Implementation CORRECT
✓ Implementation verified successfully!
The NAND gate circuit correctly implements F = B'C + CE' + CD
(base) root@ubuntu24:/home/waskita# python z.py
=== NAND Gate Minimization for F = B'C + CE' + CD ===
Generating truth table for F = B'C + CE' + CD...
Truth Table:
B C D E | F
---------
0 0 0 0 | 0
0 0 0 1 | 0
0 0 1 0 | 0
0 0 1 1 | 0
0 1 0 0 | 1
0 1 0 1 | 1
0 1 1 0 | 1
0 1 1 1 | 1
1 0 0 0 | 0
1 0 0 1 | 0
1 0 1 0 | 0
1 0 1 1 | 0
1 1 0 0 | 1
1 1 0 1 | 0
1 1 1 0 | 1
1 1 1 1 | 1
Searching for minimal NAND implementation (up to 8 gates)...
Testing 1-gate circuits...
Testing 2-gate circuits...
Testing 3-gate circuits...
Tested 1000 circuits...
Tested 2000 circuits...
Tested 3000 circuits...
Testing 4-gate circuits...
Tested 1000 circuits...
Tested 2000 circuits...
Tested 3000 circuits...
Tested 4000 circuits...
Tested 5000 circuits...
Tested 6000 circuits...
Tested 7000 circuits...
Tested 8000 circuits...
Tested 9000 circuits...
Tested 10000 circuits...
Tested 11000 circuits...
Tested 12000 circuits...
Tested 13000 circuits...
Tested 14000 circuits...
Tested 15000 circuits...
Tested 16000 circuits...
Tested 17000 circuits...
Tested 18000 circuits...
Tested 19000 circuits...
Tested 20000 circuits...
Tested 21000 circuits...
Tested 22000 circuits...
Tested 23000 circuits...
Tested 24000 circuits...
Tested 25000 circuits...
Tested 26000 circuits...
Tested 27000 circuits...
Tested 28000 circuits...
Tested 29000 circuits...
Tested 30000 circuits...
Tested 31000 circuits...
Tested 32000 circuits...
Tested 33000 circuits...
🎉 Found minimal implementation with 4 NAND gates!
Gate connections: [(0, 3), (1, 2), (1, 4), (5, 6)]
Circuit Description:
G1 = NAND(B, E)
G2 = NAND(C, D)
G3 = NAND(C, G1)
F = NAND(G2, G3)
Verification:
B C D E | Original | NAND Circuit | Match
-----------------------------------------
0 0 0 0 | 0 | 0 | ✓
0 0 0 1 | 0 | 0 | ✓
0 0 1 0 | 0 | 0 | ✓
0 0 1 1 | 0 | 0 | ✓
0 1 0 0 | 1 | 1 | ✓
0 1 0 1 | 1 | 1 | ✓
0 1 1 0 | 1 | 1 | ✓
0 1 1 1 | 1 | 1 | ✓
1 0 0 0 | 0 | 0 | ✓
1 0 0 1 | 0 | 0 | ✓
1 0 1 0 | 0 | 0 | ✓
1 0 1 1 | 0 | 0 | ✓
1 1 0 0 | 1 | 1 | ✓
1 1 0 1 | 0 | 0 | ✓
1 1 1 0 | 1 | 1 | ✓
1 1 1 1 | 1 | 1 | ✓
All outputs match: ✓
The minimal NAND implementation uses 4 gates.
Each NAND gate implements: NAND(A,B) = (AB)'
=== Additional Analysis ===
Original function: F = B'C + CE' + CD
This can be factored as: F = C(B' + E' + D)
Using De Morgan's laws and NAND equivalencies:
F = C · (B' + E' + D)
F = C · ((BE)' + D) [since B' + E' = (BE)']
F = C · (BED')' [since (BE)' + D = (BED')']
=== Systematic Search Results ===
The algorithm systematically tests all possible NAND gate configurations
starting from 1 gate up to the specified maximum, ensuring the
minimal solution is found first.
Leave a Reply