Problema de Lògica: Selectivitat de Tecnologia i Enginyeria

Un estudiant ha d'enfrontar-se a 4 problemes de Tecnologia i Enginyeria. Cada problema es valora amb:

• 1: Aprovat
• 0: Suspès

L'estudiant supera la selectivitat si obté 2 o més problemes aprovats.

Sigui P1, P2, P3 i P4 les notes (0 o 1) dels quatre problemes, definim la funció de decisió F tal que:

F = 1 si (P1 + P2 + P3 + P4) ≥ 2, i F = 0 en cas contrari.

Taula de Veritat

A continuació es mostra la taula de veritat per a totes les combinacions possibles de les variables P1, P2, P3 i P4:

Mapa de Karnaugh

Per representar gràficament la funció i facilitar-ne la simplificació, es construeix el mapa de Karnaugh. Aquí s’utilitzen dues variables per les files (P1P2) i dues per les columnes (P3P4) amb l'ordre de Gray (00, 01, 11, 10):

Funció Lògica i Simplificació (Pas a Pas)

1. Definició del problema: Considerem les variables P1, P2, P3, P4 amb valors binaris (0 o 1). Volem que la funció F sigui 1 si la suma de les variables és igual o superior a 2, és a dir, si almenys hi ha dues entrades a 1.
2. Funció en forma de suma de minterms: La funció es pot expressar de forma canònica incloent tots els minterms on la suma de 1s és 2, 3 o 4. És a dir, F = Σ m(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15).
3. Expressió en forma de suma de productes: Una expressió equivalent (encara que no necessàriament la més simplificada) és:
   
   F = (P1·P2) + (P1·P3) + (P1·P4) + (P2·P3) + (P2·P4) + (P3·P4)
   
   Cada terme representa una combinació en què almenys dos problemes són aprovats.
4. Construcció del mapa de Karnaugh: El mapa de Karnaugh agrupa les combinacions on F = 1. Per evitar l’ús de literals negades (que haurien d’aparèixer si un grup tingués una variable constant a 0), es seleccionen agrupacions més àmplies que abasten cel·les de diferents files o columnes on la variable en qüestió varia (és a dir, passa d’un 0 a un 1). Per exemple:
   • Grup 1 (color blau clar): Tota la fila “11” (on P1=1 i P2=1). Aquest bloc aporta el terme P1·P2.
   • Grup 2 (color verd clar): Tota la columna “11” (on P3=1 i P4=1). Aquest bloc aporta el terme P3·P4.
   • Grups 3 (color groc clar): Es formen blocs de 4 cel·les combinant parts de dues files adjacents (per mitjà del wrapping del mapa) de manera que s’elimina la variabilitat en les columnes. D’aquesta manera s’obtenen els termes:
     • Agrupant cel·les de les files “01” i “11” en les columnes “01” i “11” s'obté el terme P2·P4 (la variable P2 es manté a 1 en ambdues files i P4 a 1 en ambdues columnes).
     • Agrupant cel·les de les files “10” i “11” en les columnes “10” i “11” s'obté el terme P1·P3 (la variable P1 es manté a 1 i P3 a 1 en aquestes posicions).
     • Agrupant altres blocs similars (tenint en compte el wrapping horitzontal i vertical) es poden obtenir els termes P1·P4 i P2·P3.
     D'aquesta manera, evitant formar grups amb una variable constant a 0 (i per tant amb negació) es recupera la forma minimal simètrica.
5. Interpretació: La funció resultant indica que l'estudiant supera la selectivitat (F = 1) sempre que hi hagi almenys dues entrades amb valor 1, coincidint amb la condició establerta. Notar que, tot i que en principi podríem obtenir termes amb literals negades si agrupéssim cel·les de forma més reduïda, és possible seleccionar agrupacions (amb blocs de 4 cel·les, per exemple) que permeten eliminar aquesta necessitat i obtenir així:
   
   F = P1·P2 + P1·P3 + P1·P4 + P2·P3 + P2·P4 + P3·P4

Aquest exercici és un exemple clàssic d'aplicació de lògica booleana i d'ús de mapes de Karnaugh per simplificar funcions de variables múltiples. La clau està en seleccionar agrupacions que preservin les condicions constants (sense forçar literals negades) per arribar a la forma minimal desitjada.

Mapa de Karnaugh amb destacat de grups

En el mapa de Karnaugh, s’han identificat els següents grups:

• Grup 1 (color blau clar): Tota la fila on P1=1 i P2=1 (fila “11”). Aquest grup aporta el terme P1·P2.
• Grup 2 (color verd clar): Tota la columna on P3=1 i P4=1 (columna “11”). Aquest grup aporta el terme P3·P4.
• Grups 3 (color groc clar): A partir d'agrupacions de blocs de 4 cel·les (mitjançant el wrapping) s'obtenen els altres 4 termes:
  • Un bloc que abasta parts de les files “01” i “11” en les columnes “01” i “11” dóna el terme P2·P4.
  • Un bloc que abasta parts de les files “10” i “11” en les columnes “10” i “11” dóna el terme P1·P3.
  • Altres agrupacions similars permeten obtenir els termes P1·P4 i P2·P3.

Nota: Encara que en principis es podrien obtenir termes amb literals negades si es formessin grups més petits (perquè una variable fos constant a 0 en tot el grup), aquí s'han seleccionat agrupacions més àmplies que permeten obtenir la forma final sense negacions.

Funció Final Simplificada

Un cop seleccionades les agrupacions adequades, la funció final simplificada (en forma de suma de productes) és:

F = P1·P2 + P1·P3 + P1·P4 + P2·P3 + P2·P4 + P3·P4

Aquesta expressió és simètrica i és la forma més compacta per implementar la decisió “supera selectivitat si s'aproven 2 o més problemes”.

Resum

• S’ha utilitzat un mapa de Karnaugh per identificar agrupacions de 1s evitant la necessitat d’incloure literals negades, tot i que, en principi, si en un grup una variable fos constant a 0 hauria d’aparèixer com ¬P.
• La selecció intel·ligent dels blocs (agrupacions de 4 cel·les) permet obtenir els 6 termes minimalment necessaris.
• La funció final simplificada és:
  F = P1·P2 + P1·P3 + P1·P4 + P2·P3 + P2·P4 + P3·P4

Factorització de la Funció

Podem simplificar encara més la funció utilitzant el mètode de factor comú.

Funció inicial:

F = P1·P2 + P1·P3 + P1·P4 + P2·P3 + P2·P4 + P3·P4

Primer pas: Factor comú parcial

Agrupem els quatre darrers termes:

P1·P3 + P1·P4 + P2·P3 + P2·P4

Fem factor comú de P3 i P4:

= P3·(P1 + P2) + P4·(P1 + P2)

Segon pas: Factor comú total

Ara fem factor comú de (P1 + P2):

= (P3 + P4)·(P1 + P2)

Funció facturitzada final:

Ara podem escriure la funció de manera més compacta:

F = P1·P2 + (P3 + P4)·(P1 + P2)

Aquesta forma és funcionalment equivalent i pot resultar més eficient en alguns contextos de disseny digital.