Considerem 4 variables (P1, P2, P3, P4) on cada variable pren el valor 0 (suspès) o 1 (aprovat). La funció F és 1 si l'estudiant ha aprovat 2 o més problemes, és a dir, si la suma de 1s és ≥ 2.
F = P1·P2 + P1·P3 + P1·P4 + P2·P3 + P2·P4 + P3·P4
Aquesta expressió és simètrica i representa totes les combinacions on hi ha almenys 2 aprovacions.
Una forma de factoritzar-la és:
F = P1·P2 + P3·P4 + (P1+P2)(P3+P4)
| P1 | P2 | P3 | P4 | F |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Per a 4 variables utilitzem un mapa amb 4 files i 4 columnes. L'ordre de Gray és:
Files (P1P2): 00, 01, 11, 10.
Columnes (P3P4): 00, 01, 11, 10.
| P1P2 \ P3P4 | P3P4 | |||
|---|---|---|---|---|
| 00 | 01 | 11 | 10 | |
| 00 | 0 | 0 | 1 | 0 |
| 01 | 0 | 1 | 1 | 1 |
| 11 | 1 | 1 | 1 | 1 |
| 10 | 0 | 1 | 1 | 1 |
Aquest mètode busca agrupar el màxim nombre de 1 consecutius per reduir els termes. Es procedeix de la següent manera:
| P1P2 \ P3P4 | P3P4 | |||
|---|---|---|---|---|
| 00 | 01 | 11 | 10 | |
| 00 | 0 | 0 | 1 | 0 |
| 01 | 0 | 1 | 1 | 1 |
| 11 | 1 | 1 | 1 | 1 |
| 10 | 0 | 1 | 1 | 1 |
En aquest mètode, l'agrupament òptim ens permet extreure els termes:
• P1·P2 (Grup Blau – fila 11)
• P3·P4 (Grup Verd – columna 11)
• (P1+P2)(P3+P4) (Grup Groc – combinació de parelles)
Per tant, la funció final és:
F = P1·P2 + P3·P4 + (P1+P2)(P3+P4)
En el mapa de Karnaugh per a la funció “almenys 2 de 4”, un cop hem identificat els grups òptims per la fila completa (Grup Blau: P1·P2) i per la columna completa (Grup Verd: P3·P4), ens queda cobrir les cel·les restants que contenen 1. Aquestes cel·les es poden agrupar de manera que, en conjunt, representin les combinacions en què hi ha un 1 a una part (P1 o P2) i un 1 a l’altra part (P3 o P4). Això ens porta al terme factoritzat (P1+P2)(P3+P4).
Observem en el mapa de Karnaugh que, a més de la fila “11” i la columna “11”, hi ha cel·les amb 1 als sectors de les files “01” i “10” que no formen grups grans per si sol.
Aquestes cel·les corresponen als casos on:
- La fila “01” (on P1=0, P2=1) té 1 a les columnes “01”, “11” i “10”.
- La fila “10” (on P1=1, P2=0) té 1 a les columnes “01”, “11” i “10”.
En lloc de tractar cada cel·la de manera individual, observem que podem agrupar-les en parelles solapades, de manera que cada parella comparteixi un factor comú.
Per exemple, considerem dues parelles:
Parella 1: Una cel·la de la fila “01” juntament amb la cel·la solapada de la fila “11” a la mateixa columna on P4=1.
En la fila “01”, P2=1 i en la fila “11”, tant P1 com P2 són 1. El fet de compartir P2=1 fa que es pugui extreure el factor P2.
Parella 2: Una cel·la de la fila “10” juntament amb la cel·la solapada de la fila “11” a la mateixa columna on P3=1.
Aquí, en la fila “10”, P1=1 i en la fila “11” també, donant el factor comú P1.
Aplicant aquest procés a totes les cel·les restants, podem identificar les quatre parelles que cobreixen els 1 restants:
Aquests quatre termes poden escriure’s individualment com:
Parella A: P2·P3
Parella B: P2·P4
Parella C: P1·P3
Parella D: P1·P4
Ara, observeu que podem agrupar aquests termes per factoritzar per les parts comuns. Els termes P1·P3 i P1·P4 tenen en comú P1, mentre que P2·P3 i P2·P4 tenen en comú P2.
D'aquesta manera, podem expressar la suma d'aquests termes com:
(P1·P3 + P1·P4) + (P2·P3 + P2·P4)
= P1·(P3 + P4) + P2·(P3 + P4)
= (P1 + P2)·(P3 + P4)
Finalment, combinant els grups ja identificats:
- Grup Blau: La fila “11” dóna P1·P2.
- Grup Verd: La columna “11” dóna P3·P4.
- Grup Groc (factoritzat): Dels quatre termes solapats, hem obtingut (P1+P2)(P3+P4).
Per tant, la funció final simplificada és:
F = P1·P2 + P3·P4 + (P1+P2)(P3+P4)
Aquesta factorització és molt elegant perquè redueix la complexitat de la suma de 6 termes a una expressió amb 3 parts, aprofitant la simetria de la funció “almenys 2 de 4”.
En el mapa de Karnaugh, el grup groc es marca amb el color groc per indicar les cel·les que, a través de diferents parelles solapades, contribueixen al terme factoritzat.
Així, les cel·les marcades en groc (per exemple, a les files “01” i “10” en columnes on no s’inclou el grup complet de la fila o de la columna) són les que, en combinar-se amb les cel·les de la fila “11”, permeten extreure els termes P1·P3, P1·P4, P2·P3 i P2·P4.
És important notar que en la pràctica, la selecció dels grups grocs pot variar lleugerament en funció de com es decideixi solapar amb els altres grups (blau i verd), però el resultat final de la factorització serà el mateix.
Aquesta explicació pas a pas del grup groc mostra clarament com, mitjançant l'agrupament i la factorització de parelles, es pot arribar a una expressió simplificada que reflecteix la condició “almenys 2 de 4” de manera molt eficient.
En aquest mètode es realitza una agrupació menys eficient, on cada parella es tracta per separat sense aprofitar solapaments òptims.
L’agrupament pitjor té la desavantatge de no reduir el nombre de termes. Per això, es manté la forma:
F = P1·P2 + P1·P3 + P1·P4 + P2·P3 + P2·P4 + P3·P4
Aquesta expressió, tot i ser correcta, conté més termes i és menys intuïtiva a l’hora de veure la simetria de la funció.
A continuació es mostra com es podrien marcar els grups si es tractés cada parella per separat (sense combinar solapaments):
| P1P2 \ P3P4 | P3P4 | |||
|---|---|---|---|---|
| 00 | 01 | 11 | 10 | |
| 00 | 0 | 0 | 1 | 0 |
| 01 | 0 | 1 | 1 | 1 |
| 11 | 1 | 1 | 1 | 1 |
| 10 | 0 | 1 | 1 | 1 |
Aquí es pot observar que la mateixa cel·la pot aparèixer en diversos grups sense una combinació òptima, cosa que comporta una expressió amb més termes.
En resum, l’agrupament òptim és preferible per la seva simplicitat i per la possibilitat de factoritzar l’expressió. Així, la solució final recomanada és:
F = P1·P2 + P3·P4 + (P1+P2)(P3+P4)
Producte de Sumes:En conclusió, encara que l'expressió original no es pot simplificar més en el format de suma de productes, sí que es pot expressar de manera diferent utilitzant la forma de producte de sumes.