libro no 463 eso que llamamos lógica macluskey colección e o agosto 10 de 2013

Por una Cultura Nacional, Cientfica y Popular!

Coleccin Emancipacin Obrera IBAGU-TOLIMA 2013

GMM


Libro No. 463. Eso que llamamos Lgica. Macluskey. Coleccin E. O. Agosto 10 de 2013. Ttulo original: 2011-2012 Macluskey, excepto donde se indique lo contrario. 2011-2012 Javier J Sedano, Apndices II y III. Versin Original: Eso que llamamos Lgica. 2011-2012

Macluskey, excepto donde se indique lo contrario. 2011-2012

Javier J Sedano, Apndices II y III.

Licencia Creative Commons: Emancipacin Obrera utiliza una licencia Creative Commons, puedes copiar, difundir o remezclar nuestro contenido, con la nica condicin de citar la fuente. La Biblioteca Emancipacin Obrera es un medio de difusin cultural sin fronteras, no obstante los derechos sobre los contenidos publicados pertenecen a sus respectivos autores y se basa en la circulacin del conocimiento libre. Los Diseos y edicin digital en su mayora corresponden a Versiones originales de textos. Este libro en particular fue extraido de las pginas: Autora-atribucin: Respetar la autora del texto y el nombre de los autores No comercial: No se puede utilizar este trabajo con fines comerciales No derivados: No se puede alterar, modificar o reconstruir este texto. Portada E.O. de Imagen: http://collection.openlibra.com.s3.amazonaws.com/covers/2013/03/Eso-que-llamamos-Logica-OpenLibra-350x459.gif


Eso que llamamos

Lgica

Macluskey


Resumen de los apuntes de la asignatura Metodologa, del Segundo Curso de Informtica, curso 1973-74

Recopilacin de artculos publicados en El Cedazo

Macluskey, 2012

con la colaboracin de Javier J Sedano

2011-2012 Macluskey, excepto donde se indique lo contrario. 2011-2012 Javier J Sedano, Apndices II y III.

Distribuido segn la licencia Creative Commons Reconocimiento- NoComercial-SinObraDerivada 2.5 Espaa [http://creativecommons.org/licenses/by-nc-nd/2.5/es/] Usted es libre de copiar, distribuir y comunicar pblicamente la obra bajo las condiciones siguientes:

Reconocimiento. Debe incluir esta pgina completa en la

reproduc- cin de la obra, sin alteracin alguna. No comercial. No puede utilizar esta obra con fines comerciales.

Sin obras derivadas. No se puede alterar, transformar o

generar una obra derivada a partir de esta obra. Al reutilizar o distribuir la obra, tiene que dejar bien claros los

trminos de licencia de esta obra. Alguna de estas condiciones puede no aplicarse si obtiene el

per- miso del titular de los derechos de autor. Nada en esta licencia menoscaba o restringe los derechos

morales del autor.

Estas pginas estn dedicadas a Jos Pepe Cuena Bartolom, quien, en los albores de la informtica, nos ense no solamente Lgica, sino tambin a pensar

Tus alumnos nunca Te lo agradeceremos lo suficiente.

ndice

Prefacio............................................................................ 7 Introduccin ..................................................................... 9

I- El lgebra de Boole .......................................................19

II- La Forma Normal Disyuntiva en el lgebra de Boole .........35 III- lgebra de Circuitos ....................................................47

IV- El lgebra de Conjuntos, revisitada ................................63

V- El Clculo Proposicional .................................................79 VI- La escurridiza Implicacin Lgica ...................................95

VII- El proceso de deduccin lgica ................................... 117

VIII- El clculo de predicados ........................................... 137 IX- La inferencia lgica .................................................... 149

Apndice I: Solucin al Problema del Maquinista. ............... 167

Apndice II: La reduccin de Karnaugh, por J ..................... 173 Apndice III - Lgica digital, por J..................................... 183

Prefacio

Querido lector: tienes en tus manos, o mejor, en tu ordenador, un no s cmo llamarlo: un libro electrnico, un documento, un estudio arqueolgico, unas apostillas, un... qu s yo, un conjunto de pginas, en definitiva, donde he recopilado los artculos de la serie Eso que llamamos Lgica que se fueron publicando en El Cedazo (es decir, el blog comunitario de El Ta- miz: www.eltamiz.com/elcedazo) entre octubre de 2011 y mayo de 2012.

Podis acceder al contenido de la serie completa en esta direc- cin de internet: www.eltamiz.com/elcedazo/eso-que-llamamos- logica.

Adems de los artculos publicados por m, he recopilado tambin los dos artculos relacionados con la serie que public nuestro amigo Javier J Sedano, otro editor de El Cedazo: uno, sobre el mtodo de reduccin de Karnaugh, y el otro, sobre lgica digital, donde explicaba cmo se disean las puertas lgicas que forman la circuitera de todos los artilugios electrnicos. Estos dos artculos se publicaron como Anexos, y los encontraris como Apndices (II y III, respectivamente) al final del libro.

Todos estos artculos, publicados cada pocas semanas, estn escritos con la tnica lgica y esperable en una serie de artculos publicados a lo largo de varios meses en un blog. Ahora, para esta recopilacin en un nico documento, he intentado ade- cuar la estructura y el discurso al hecho de que la serie est ya completamente escrita, y por tanto no tienen sentido frases muy normales en el blog, como Dentro de unos das veremos tal y tal cosa o Si tenis dudas, no dudis en preguntar en los comentarios, etc.

Sin embargo, a pesar de esta adecuacin, en los diferentes captulos del libro se sigue notando claramente su origen blogue- ro. Eliminarlo hubiera sido tanto como reescribirlo de arriba abajo, y no

creo que merezca la pena hacer tal cosa, pues adems as, en caso de duda, siempre se puede buscar en las entradas originales publicadas en el blog, ver los comentarios que los lectores hicieron, etc.

Algo parecido ocurre con las notas al pie de pgina de los artculos originales: al convertirlos a formato libro he preferido incluir- las en el texto principal, pero no todas, slo las que no se des- viaban en exceso del discurso principal. Lo que tiene todo el sentido en el mundo de Internet no tiene por qu ser lo ms adecuado en un texto completo. Espero que no se haya perdido mucho con el cambio.

En fin: ojal que estas pginas os sean de utilidad y que, leyn- dolas, aprendis mucho, pero mucho, mucho, sobre Eso que llamamos Lgica.

Macluskey, 2012

Introduccin

Como buen informtico del Neoltico que soy, soy bastante bueno en Lgica. De veras, bastante bueno, y yo nunca miento. Nunca, jams... Bueno, casi nunca, al menos.

Soy bueno quiz no en la lgica aristotlica, por llamarla de algn modo, pero s, al menos, en la lgica que se debe usar en los algoritmos informticos de la lgica o lo que sea por la que se rigen los humanos en sus acciones reconozco que entiendo ms bien poco. Aunque, para ser precisos, era bueno en lgica: con el paso de los aos cada vez entiendo menos mi profesin, mi pueblo, mi pas, mi mundo seguro que soy yo, claro, que son mis neuronas las que han perdido capacidad con el tiempo y ya no entienden montones de cosas que antes comprendan bien. Pero el caso es que en los aos 70 y 80 del siglo pasado haba que ser bueno en lgica informtica si queras prosperar en mi profesin. Y yo lo era.

Jos Cuena Bartolom, delante de su amada pizarra, en 1973

O sea, que, adems de tener una rara habilidad para desarrollar algoritmos eficacsimos para resolver complicados problemas de todo tipo, resulta que tambin soy bastante bueno en lgica formal. Y no es que lo sea por ciencia infusa, no, sino ms bien porque disfrut en mi ya lejana carrera, all por el principio de los setenta del siglo pasado, de las lecciones de uno de los mejores profesores que he tenido a lo largo de mi vida: Don Jos Cuena Bartolom. El hecho de que cuarenta aos despus re- cuerde perfectamente su nombre, mientras que he olvidado el de la mayora de los dems profesores que tuve antes y despus, ya significa algo.

Aunque, por alguna oscura razn, su asignatura no se denomi- naba Lgica, como sera lgico, sino Metodologa, vaya Vd. a saber las razones de tal nombre, l nos ense la lgica formal de una manera tal que jams la olvidaramos ninguno de los alumnos que asistimos a sus lecciones.

Nos ense que la lgica formal era sencilla. Sencillsima. Con cuatro conceptos bsicos bien aprendidos (y esta vez son, literalmente, cuatro) estabas ya preparado para enfrentarte al ominoso mundo de los silogismos y del clculo proposicional sin el menor problema.

En definitiva: No hay nada ms lgico que la Lgica, valga la redundancia

En este librito intitulado Eso que llamamos Lgi- ca intentar, antes simplista que incomprensible, hacer a los amables lectores de El Cedazo y a aquellos en cuyas manos cai- ga partcipes de estos conocimientos, siguiendo a rajatabla el mtodo de Don Jos, apoyndome en mis tal vez maravillosos (aunque obviamente amarillentos, emborronados y encima escritos con una letra infame) apuntes de Segundo de Carrera que conservo como oro en pao.

Don Jos Cuena, despus de haberme enseado todo lo que s sobre Lgica, a m y a los compaeros que me siguieron en cursos subsiguientes, escribi un libro de culto para los informticos de

pro: Lgica Informtica, publicado en 1985 por Alianza Editorial y en la actualidad debidamente agotado. Luego se de- dic al desarrollo de la Inteligencia Artificial, public artculos, ms libros Y Don Jos nos dej un mal da de 1999. All donde te encuentres, Pepe, pues era as, Pepe, como todo el mundo le conoca, este humilde librillo est dedicado a ti.

En realidad, al principio de mi desempeo profesional yo no saba que lo que yo saba sobre lgica era rara avis. Ingenuo como soy, pensaba que todo buen informtico dominaba sus misterios al menos igual que yo.

Pero poco a poco me di cuenta de que no, no todo el mundo en mi mundo saba lo que yo saba. Es ms, me di cuenta de que en realidad pocos colegas saban lo que yo saba de la forma que lo saba. Que yo era un caso raro, vaya.

Luego, mucho tiempo ms tarde, hace slo cuatro o cinco aos, me ocurri un sucedido que definitivamente me convenci de que mi acervo lgico era como era simplemente por lo bien es- tructurado que estaba desde el principio (mrito de Pepe Cuena, desde luego). Un compaero de trabajo, ms joven que yo (cosa que no es muy difcil), pero ya con sus aitos, ante ciertos cambios drsticos en su vida decidi, entre otras cosas, comen- zar la Carrera de Filosofa. Vocacin tarda, pero intensa.

En Primero de Filosofa las asignaturas eran algo as como Histo- ria Histrica de la Filosofa, tica Rimbombante, Ontologa Cre- puscular, Epistemologa de la Semntica Asinttica y otros arca- nos similares (supongo que se nota mucho que yo, de Filosofa, entiendo ms bien poco). Y Lgica.

Parece que la Lgica era (y seguramente sigue siendo) el coco de Primero en Filosofa. En realidad, a poco que lo pen- semos, es lgico. En un sistema educativo como el espaol, los alumnos deciden cursar estudios de Ciencias o de Letras (se llamen como rayos se llamen ahora; en mis tiempos era as y, con matices, as sigue siendo), y esa decisin la han de tomar muy pronto, algo as como con catorce aos o quince.

Disculpad que no sepa cmo se llaman ahora las diferentes eta- pas educativas espaolas; tenemos aqu la sabia costumbre de cambiarlo todo, casi siempre para peor, cada tres o cuatro aos, as que hace tiempo, desde que mi hija pas por el proceso, que no sigo estos procelosos asuntos.

En los estudios de Ciencias se ensean Matemticas, Trigono- metra, Fsica, Qumica y todas esas cositas; en los de Letras se da

Literatura, Historia, Latn, Griego clsico, Filosofa, y cosas as. En los currcula de cada tipo de estudios hay alguna asignatura del otro tipo (por ejemplo, los de Ciencias dan un poco de Literatura y Filosofa, y los de Letras algo de Matemticas, etc), pero por lo que he podido ver esas asignaturas del lado oscuro son consideradas como maras, por lo que los conocimientos de matemticas que tienen los alumnos que llegan a Primero de Filosofa son, por decirlo de una forma caritativa, escasos.

Aclaro que en Espaa llamamos maras a las asignaturas que, aunque haya que darlas y aprobarlas para pasar el curso, no son muy importantes para lo que se denomina el tronco del currculo. Por ejemplo, la Gimnasia, la Religin, la Educacin para la Ciudadana o como se llame ahora y cosas as son maras. A menudo tienen fama de ser asignaturas fciles, aunque no siempre sea el caso.

Pero no es lo peor que sean escasos, es que adems estn cmo lo dira mal vistos. Si vas a ser filsofo (o juez, o histo- riador, o acadmico de la Real Academia de la Lengua, igual da), da la sensacin de que cuanto menos sepas de lgebra o de clculo diferencial, mejor. Y lo mismo pasa al revs, desde luego: si estudias fsica, o una ingeniera naval o de caminos, puentes y autopistas, o de lo que sea, est poco menos que prohibido que sepas una palabra de latn o griego clsico, o que sepas quin fue Ciro el Grande, Pedro el Cruel o el mismsimo Platn As nos va.

Volviendo a mi colega, el filsofo de tarda vocacin No re- cuerdo qu estudios tena antes de decidirse a estudiar Filosofa, probablemente algunos de la rama de ciencias, pero en cualquier caso seguro que con el tiempo los tena satisfactoriamente olvidados. Se encontr, obviamente, en un curso donde sus compaeros eran en su gran mayora adolescentes recin sali- dos del Bachillerato, que haban cursado por la rama de Letras y que, por tanto, haca tiempo que no vean en serio nada que tuviera ver con matemtica de ningn tipo.

Cuando empezaron las clases en la asignatura de Lgica fue el desparrame. Nadie entenda nada. Lo que all se contaba pareca chino capuchino para todos, incluido mi colega. No tenan armas ni bagajes como para entender la asignatura y, desde luego (y conste que hablo de odas, pero no creo equivocarme), el profesor tampoco ayudaba, con explicaciones seguramente muy filo- sficas pero muy poco didcticas.

Primer examen parcial, al final del primer trimestre. Suspenso general, o casi. Incluyendo a mi amigo. Un desastre, vaya.

Conste aqu que mi opinin es que cuando nadie en una clase entera de varias decenas (o centenares!) de alumnos es capaz de aprobar la asignatura, la culpa es exclusivamente del profesor, y esto es extensivo a si slo aprueban dos o tres: siempre hay fieras que se buscan la vida para aprender la asignatura como sea. Un tipo que, tras esforzarse en ensear su asignatura, consigue semejante marca de suspensos, no merece dar clase ni en un parvulario. Y ste es un tipo de profesor que abunda muchsimo, sobre todo en la Universidad.

Pero lo peor de todo es que esta gente, encima se jacta de que su asignatura es taaan difcil que no la aprueba nadie! Se pavo- nean: Ja, ja Mira qu duro soy y qu importante es mi asignatura, que slo aprueban el 2% de mis estudiantes. Por fa- vor...

INTIL, que eres un intil, hombre ya!! A ver si te enteras de que t ests all nica y exclusivamente para ensear a tus alumnos todo lo que sabes, y nada ms. Si no lo consi- gues, no ests haciendo tu trabajo, aquello por lo que te pagan. Por lo que te pagamos. Todos, pues de nuestros impuestos sa- len tus emolumentos. Pero no, claro, no le echan. En realidad, luego, en vez de echarle a patadas de la docencia, que es lo nico que se merece, encima el tipo est casi siempre bien con- siderado por sus superiores. As nos va, ya digo.

Me vuelvo a ir por las ramas ya vuelvo, ya.

Bien, el caso es que tomando un caf con mi colega, y tras co- mentar debidamente el tiempo y el resultado del partido de tur- no, le pregunt educadamente por su experiencia universitaria, y me

dice: la Epistemologa, bien; la tica, muy bien; la Histo- ria de la Filosofa, muy de hincar codos y aprendrsela de memoria lo que me va fatal es la Lgica: no entiendo nada! .

Yo me extrao: la Lgica? Pero si es sencillsima! . Y l se extraa ms: SENCILLSIMA?? Tu caf es alucingeno, o qu? Pero si no la entendemos ni uno.

Evidentemente se trataba de una discusin completamente ba- lad. Por mucho que yo le contara y porfiara, agarrado a mi va- sito de plstico con el brebaje que la mquina de la oficina hace pasar por caf, que la Lgica formal era en realidad muy sencilla, no iba a convencerle a l, que la estaba sufriendo en sus carnes.

Se me ocurri entonces una idea feliz (ya dije alguna vez que lo mo son las ideas felices): busqu en el desvn mis semiapoli- llados apuntes de Lgica de Segundo, los fotocopi tal cual, y le pas el tocho de fotocopias, disculpndome por mi mala letra, la que tena entonces.

Aunque intent pagarme las fotocopias, no se lo permit bastante tena el hombre con descifrar mis aejas cagadas de mos- ca. Acept las disculpas de hecho me asegur que mi letra es ahora mucho peor que hace casi cuarenta aos, y tiene razn. En fin. Tampoco le di muchas ms indicaciones: slo los viejos apuntes manuscritos, emborronados y amarillentos.

Aprob. Con notable alto. Parece que los apuntes corrieron como la plvora entre sus colegas estudiantes. Y parece que el profesor casi se suicida cuando, al final del curso, tuvo que aprobar a la mayor parte de la clase. Con lo bien que lo llevaba el buen hombre

al acabar el primer trimestre, con prcticamente todos sus alumnos suspensos!

Posteriormente charlamos, con otro caf en la mano, al que esta vez invit mi colega (aunque, eso s, estaba igual de malo que

el primero) (el caf, quiero decir), y me corrobor que, efectivamente, la Lgica es sencilla siempre que se enseara de la forma correcta, con la orientacin correcta, y dando las bases apropiadas a los alumnos para ir comprendiendo lo que va vi- niendo a continuacin.

El caso es que, conociendo cmo funciona la Universidad espa- ola, a m no me extraa nada que en la Facultad de Filosofa siguieran contando la Lgica con silogismos y dems, como en el Siglo XVII, pero al menos estaba seguro de que en las carre- ras de ciencias, y particularmente en las de ingeniera de informtica, la enseanza de Lgica formal (cuyo dominio es bsi- co para poder ser un buen ingeniero informtico, o al menos lo era), se hara con todos los predicamentos de calidad, al menos igual de bien como a m me lo contaron cuarenta aos ha.

Ja! Pues va a ser que no.

Mi hija, estudiante de ingeniera informtica, me cont una ancdota lamentable cuando el profesor (o profesora, no re- cuerdo) de alguna asignatura sobre Lgica fue incapaz de explicar a la concurrencia por qu la implicacin lgica tiene la frmula que tiene cosa que veremos con detalle dentro de unos cuantos captulos.

Les vena a decir que esto es as porque es as es como la suma, por qu dos ms dos son cuatro?, pues porque s, es as, y punto.

Y punto. S, s, habis ledo bien: Y punto!!!! Toma ya. Na- da menos que en tercero o cuarto de Carrera!

En fin.

Es completamente inadmisible que cualquier profesor universita- rio, y ms en una asignatura que tiene que ver con la matemtica, es ms: con la lgica!, diga que las cosas son as porque

son as! En dos palabras: Impresionante. Espero que Jesuln de Ubrique no me cobre derechos de autor por usar su mejor frase As nos va. Naturalmente, me sent con mi hija exactamente cinco minutos, le cont por qu la implicacin lgica es como es (de veras: es una deduccin completamente lgica), lo comprendi perfectamente y se indign porque toda una profesora universitaria que, se supone, se gana la vida enseando

su asignatura, no fuera capaz de explicar algo tan sencillo. Repi- to: As nos va!

En definitiva, mi intencin es ir repasando con vosotros, amables lectores, esos prodigiosos apuntes de Metodologa (o sea, Lgica y adlteres) de mi Segundo Curso de Informtica, impartidos hace cerca de cuarenta aos por ese gran profesor y gran profesional que fue Don Jos Cuena Bartolom.

No esperis un curso completo de Lgica; para eso habr que ir a alguna Universidad y aprenderla all; ms bien os conta- r lo mismo que a m me ha servido para ganarme la vida todos estos aos. Y antes simplista que incomprensible, siempre.

Pero aviso, y el que avisa no es traidor: Habr frmulas. Frmulas matemticas. No una, ni dos. Un puao. En ninguno de los prrafos anteriores dije que el libro se llamara Lgica sin frmulas. Eso s, aseguro que todas y cada unas de las frmulas y pasos de clculo que iremos viendo son sencillos, lgicos, casi inevitables en muchos casos.

No veris ms operaciones que sumas y multiplicaciones. No habr integrales, ni derivadas, ni races cuadradas, ni series de Taylor, ni nmeros imaginarios, ni numero e, ni PI, ni n de n. Con slo los signos + y (pues ni siquiera restar o dividir nos har falta) nos apaaremos para descifrar cualquier intrngulis lgico que nos echen. En una palabra: Creo que podris seguir bien las frmulas. Si os ponis a ello, claro.

Si os ponis.

Y dicho esto, he de hacer igualmente una precisin: si sois lgicos, filsofos, matemticos o, incluso, informticos de carrera, igual esta forma de contar algo tan lgico como la Lgica os parece, cuando menos, naf, ingenua, poco formal y escandalosa- mente simplista, incluso en algunos casos, errnea.

Quiz. Es ms: Seguramente.

Hay que tener en cuenta que estoy contando una historia en buena parte olvidada basada en engorrinados apuntes de hace casi 40 aos (y, diga lo que diga el tango, veinte aos s que son algo, y cuarenta mucho ms!) de una carrera sobre una disciplina, la informtica, que por entonces se estaba definiendo da a da, y en la que la experiencia profesional de los profesores y su capacidad didctica contaba mucho ms que ctedras, programas, currcula y otros diversos rollos tpicos de la excesi- vamente procedimentada Universidad actual

Perdonad, pues, estas carencias evidentes del relato, todas ellas culpa ma y no de D. Jos Cuena, a cambio de poder observar por una mirilla algo sucedido 40 aos atrs es seguramente un raro privilegio que pocas veces se puede tener.

Aprovechadlo, pues, si gustis.

Y como todas las cosas bien hechas, este libro sobre Eso que llamamos Lgica empieza, lgicamente, por el principio, por la base fundamental en que todo lo dems se asienta. El primer captulo tratar, como no puede ser de otro modo, de lo que pa- s aquel lejano primer da de clase. Tratar del lgebra de Boole.

I- El lgebra de Boole

Tras la breve (bueno, vale, no tan breve) introduccin, hoy empezar a destripar cmo es la Lgica por el principio, siguiendo los apuntes de la asignatura de Segundo de Carrera que impar- ti D. Jos Cuena all por 1973 Y empezar, como es lgico, por sus bases ms fundamentales. Por lo que es imprescindible conocer para poder seguir el resto de captulos y para poder razonar mnimamente. Por el lgebra de Boole.

Primer da de clase. Octubre de 1973. A la hora en punto aparece el profesor de la asignatura (muy mal sntoma: el primer da y llegar puntual a la hora dnde se ha visto eso?) y se pre- senta: Soy Jos Cuena, y aunque el nombre de la asignatura sea Metodologa, en realidad lo que yo voy a ensearles a Vds. es Lgica.

Pues vale, ningn problema. Total, slo un par de horas antes se haba presentado el profesor de otra asignatura de nombre Informtica Bsica II, y nos dijo algo similar: Como no tengo ni idea de qu es lo que hay que dar en esta asignatura, yo les contar de arriba abajo las tripas del ordenador que yo conozco, que a la sazn es el UNIVAC 1110

Estbamos en 1973, se trataba de una Carrera nueva, los profesores, que tambin eran nuevos, eran todos, sin excepcin, pro- fesionales que trabajaban en las incipientes empresas informti- cas de la poca (IBM, Bull, NCR, UNIVAC, Iberia, RENFE, etc), y los temarios de las asignaturas se iban construyendo sobre la marcha.

Menuda diferencia con lo que pasa ahora, donde prcticamente ni uno solo de los profesores de las facultades de informtica espaolas ha trabajado jams en la empresa privada

Y s muy bien que esta frase es injusta para algunos profesores, desgraciadamente pocos, que son la excepcin que confirma la regla. Mis disculpas para todos ellos: eso es lo que tiene genera- lizar, que en ocasiones hace confundir churras con merinas

George Boole. El caso es que D. Jos (en realidad Pepe para todo el mundo), tras presentarse, comenz inmediatamente a explicar el lgebra de Boole, lo que fue el mal sntoma definitivo: empezar a explicar la asignatura el primer da? As, por las buenas? Eso s que no se haba visto nunca hasta entonces. Todos mis profesores de todos los cursos anteriores nos haban instruido acerca del axioma que reza: La primera clase no se da, y la ltima se perdona. Pues resulta que no era un axioma, mire usted.

Rpidamente todos sacamos, nuestros cuadernos/folios/papeles de tomar apuntes muy aplicadamente, y comenzamos a copiar lo que nos iba explicando. He dicho alguna vez que, en 1973, no haba ni un solo libro que pudiramos usar para estudiar una asignatura de informtica? Pues lo digo.

Seguramente s existan libros sobre ciertas disciplinas en ingls! O sea, como si fuese chino o arameo : el idioma moder- no que estudi mi generacin en el Colegio o en el Instituto era franais, bien sr. Y el ingls? Non, non, pas danglais. El poco ingls que yo saba lo aprend en una Academia privada, en cursos de verano, obligado por mi madre (a quien nunca se lo agradecer lo suficiente, pues mis preferencias iban ms por holgazanear, jugar mal- al ftbol e ir a hacer el burro a la pis- cina). Los dems, ni eso.

Como consecuencia, los apuntes tomados de las explicaciones de los profesores y sus grficos y frmulas escritos en la pizarra eran oro molido, casi el nico medio de poder seguir y aprobar la asignatura.

S, en las pizarras, esas aejas pizarras hechas de autntica pizarra, normalmente de color verde oscuro, en las que se escri- ba con tiza y se borraba con unos artilugios que, ms que bo- rrar, lo que hacan era esparcir los trazos de tiza, en forma de yeso pulverizado, por toda la clase. Todos mis recuerdos de mis aos de estudiante estn difuminados por una nube blanca de polvo de tiza

Cedamos, pues, la palabra a Don Jos:

El lgebra de Boole

Se trata de un sistema [S,+,] compuesto de un conjunto (S), y dos operaciones definidas sobre l (+,), en el que se verifican unas ciertas propiedades. Las operaciones deben ser cerradas, es decir, aplicadas a dos elementos pertenecientes a S, su resultado es otro elemento perteneciente a S.

Atencin: aunque esto mismo lo repetir varias veces a lo largo del libro, aviso aqu por primera vez que los signos (+,) no representan la suma o la multiplicacin tal como estamos acos- tumbrados. Tommosles simplemente como un par de garaba- tos que representan un par de operaciones que se aplican a los elementos del conjunto S, y ya veremos cmo se comportan.

Las propiedades del conjunto se definen exclusivamente mediante unos ciertos axiomas de entrada; una vez definidos estos axiomas, todos los teoremas resultantes sern demostrados a partir de ellos.

Los axiomas del lgebra de Boole fueron postulados por Edward Vermyle Huntington en 1904. Como sabris, un axioma es un postulado indemostrable, que se toma como cierto siempre y en toda ocasin y que sirve de base para cualquier demostracin posterior de un determinado teorema. As como los axiomas de Peano son la base formal de la aritmtica, del mismo modo los de Huntington son la base del lgebra de Boole.

Y estos axiomas de Huntington son solamente cuatro, aunque, como son duales, como veremos en un momento, podramos decir que en realidad son ocho.

Unos aos ms tarde, en 1933, Huntington revis esos axiomas, simplificndolos, pero Pepe Cuena nos cont los de 1904 y esos son

tambin los que voy a contar yo aqu a continuacin.

Axiomas de Huntington (1904)

Axioma 1: Ambas operaciones son conmutativas (Ley conmutativa).

a+b = b+a ab = ba

Axioma 2: Ambas operaciones, (+,), tienen un elemento neutro.

a+0 = 0+a = a a1 = 1a = a

Axioma 3: Ambas operaciones son distributivas respecto de la otra operacin (Ley distributiva).

a(b+c) = ab+ac

(b+c)a = ba+ca

a+(bc) = (a+b)(a+c) (bc)+a = (b+a)(c+a)

Axioma 4: Para cada elemento existe su complementario.

Todo elemento a perteneciente a S tiene un complementario a, tambin perteneciente a S, tal que:

a+a = 1 aa = 0

Y esto es todo, amigos.

Aviso para navegantes: Si habis detectado algo raro eso no es nada. Esperad y ved.

Bien, esto es todo lo que necesitamos para definir un l- gebra de Boole (y para que los informticos podamos ganar- nos la vida: nunca estaremos lo bastante agradecidos a Mr. Boole y a Mr. Huntington). No hace falta nada ms.

Si nos fijamos bien, vemos que el conjunto de propiedades definidas por los axiomas se dividen en dos subconjuntos simtri- cos, pues el lado izquierdo es idntico al lado derecho tras una simple transformacin, cambiando + por y viceversa, y cambiando 0 por 1 y viceversa. Entonces, usando exclusivamente estos axiomas, comenzaremos a demostrar una serie de teoremas que nos harn la vida ms fcil en el futuro.

En cada transformacin que hagamos en las frmulas identifica- remos debido a qu axioma concreto podemos hacer esa transformacin, marcando el nmero de Axioma utilizado (A1, A2, A3 o A4) y de qu lado (Izquierdo o Derecho).

Comencemos.

Teoremas bsicos

Teorema 1: Idempotencia. a+a = a; aa = a

a+a = a

aa = a

a = a+0 = a+(aa) = (a+a)(a+a) = (a+a)1 = (a+a)

A2 Izq. A4 Der. A3 Der. A4 Izq. A2 Der.

a = a1 = a(a+a) = (aa)+(aa) = (aa)+0 = (aa)

A2 Der. A4 Izq. A3 Izq. A4 Der. A2 Izq.

Teorema 2: a+1 = 1; a0 = 0

a+1 = 1

a0 = 0

1 = a+a = a+(a1) = (a+a)(a+1) = 1(a+1) = a+1

A4 Izq. A2 Der. A3 Der. A4 Izq. A2 Der.

0 = aa = a(a+0) = (aa)+(a0) = 0+(a0) = a0

A4 Der. A2 Izq. A3 Izq. A4 Der. A2 Izq.

Teorema 3: Ley de absorcin.

a+(ab) = a; a(a+b) = a

Para demostrar este teorema usaremos no slo los cuatro axiomas iniciales, sino tambin el recin demostrado Teorema 2, cosa que podemos hacer porque ya hemos demostrado dicho Teo- rema 2 a partir de los axiomas del lgebra.

De aqu en adelante, siempre que use un teorema ya demostrado, lo marcar como Tx en vez de Ax, indicando como siempre si se usa su parte izquierda o su parte derecha.

a+(ab) = a

a(a+b) = a

a+(ab) = (a1)+(ab) = a(1+b) = a1 = a

A2 Der. A3 Izq. T2 Izq. A2 Der.

a(a+b) = (a+0)(a+b) = a+(0b) = a+0 = a

A2 Izq. A3 Der. T2 Der. A2 Izq.

Teorema 4: Propiedad asociativa.

a+(b+c) = (a+b)+c; a(bc) = (ab)c

Para demostrar este teorema es preciso demostrar antes dos lemas independientes.

Lema 1:

a(a+(b+c)) = a((a+b)+c)

a+(a(bc)) = a+((ab)c)

a(a+(b+c)) = a = a+(ac) = (a(a+b))+(ac) = a((a+b)+c)

T3 Der. T3 Izq. T3 Der. A3 Izq.

a+(a(bc)) = a = a(a+c) = (a+ab)(a+c) = a+((ab)c)

T3 Izq. T3 Der. T3 Izq. A3 Der.

Lema 2:

a(a+(b+c)) = a((a+b)+c)

a+(a(bc)) = a+((a.b)c)

a(a+(b+c))=(aa)+(a(b+c)) = 0+(a(b+c)) = a(b+c) = (ab)+(ac) = (0+(ab))+(ac) = ((aa)+(ab))+(ac) = (a(a+b))+(ac) = a((a+b)+c)

A3 Izq. A4 Der. A2 Izq. A3 Izq. A2 Izq. A4 Der. A3 Izq. A3 Izq.

a+(a(bc))=(a+a)(a+(bc))= 1(a+(bc)) = a+(bc) = (a+b)(a+c) = (1(a+b))(a+c) = ((a+a)(a+b))(a+c) = (a+(ab))(a+c) = a+((ab)c)

A3 Der. A4 Izq. A2 Der. A3 Der. A2 Der. A4 Izq. A3 Der. A3 Der.

Bien: teniendo convenientemente demostrados ambos lemas, ahora aplicamos a cada lado respectivamente las operaciones + y (que, ojo, no tenemos por qu saber que se llaman suma o multiplicacin) miembro a miembro, el primer miembro de ambos lemas por un lado, y el segundo, por el otro. Ambas ecuaciones sern iguales, pues aplican la misma operacin + o a los dos lados de la igualdad.

Para que quede claro: si tenemos dos igualdades (los dos lemas) que son, por ejemplo, a=b y c=d, evidentemente es cierto que se cumple ac=bd, y por supuesto ocurre lo mismo con el signo +: a+c=b+d.

Exactamente eso es lo que haremos ahora.

Lema 1: a(a+(b+c)) = a((a+b)+c) Lema 2: a(a+(b+c)) = a((a+b)+c)

Lema 1: a+(a(bc)) = a+((a.b)c) Lema 2: a+(a(bc)) = a+((a.b)c)

Lado izquierdo [a(a+(b+c))]+[a(a+(b+c))] = (a+a)(a+(b+c)) = 1(a+(b+c)) = a+(b+c) Lado derecho [a((a+b)+c)]+[a((a+b)+c)] = (a+a)((a+b)+c)) = 1((a+b)+c) = (a+b)+c Igualando ambos lados: a+(b+c) = (a+b)+c

A3 Izq. A4 Izq. A2 Der. A3 Izq. A4 Izq. A2 Der.

Lado izquierdo [a+(a(bc))][a+(a(bc))] = (aa)+(a(bc)) = 0+(a(bc)) = a(bc) Lado derecho [a+((ab)c)][a+((ab)c)] = (aa)+((ab)c)) = 0+((ab)c) = (ab)c Igualando ambos lados: a(bc) = (ab)c

A3 Der. A4 Der. A2 Izq. A3 Der. A4 Der. A2 Izq.

Nota de Macluskey en 2012: Sinceramente, nunca pens que costara tanto definir algo tan obvio como la propiedad asociativa para que veis lo que cuesta establecer las bases formales de cualquier disciplina.

Teorema 5: Para cada elemento a de S existe un complementario a y slo uno.

Atencin: Este teorema no dice lo mismo que el axioma A4, aunque en una visin apresurada podra parecerlo. All estable- camos que existe la nocin de complementario, es decir, que cada elemento

de S tiene elementos complementarios, al menos uno, mientras que este Teorema 5 afirma que el complementario de cada elemento de S es uno y slo uno, exactamente uno y ni ms ni menos que uno. O sea: uno.

Supongamos que existieran dos complementarios de a, por ejemplo x e y. Se cumpliran las siguientes 4 ecuaciones:

Por x complementario de a: 1) a+x = 1 2) ax = 0

A4 Izq. A4 Der.

Por y complementario de a: 3) a+y = 1 4) ay = 0

A4 Izq. A4 Der.

x=1x = (a+y)x = (ax)+(yx) = 0+(yx) = (ay)+(yx) = (ya)+(yx) = y(a+x) = y1 = y Luego ambos complementarios, x e y, son iguales. Por tanto hay un nico complementario de a, que es a.

A2 Der. (3) A3 Izq. (2) (4) A1 Der. A3 Izq. (1) A2 Der.

Teorema 6: El complementario del complementario de un elemento a de S es igual al propio a.

Es decir: (a)=a

Sabemos por el Axioma 2 que: a+a=1 y tambin que aa=0. Suponiendo que (a)=x, ocurrir que: a+x=1, y ax=0, dado que ese x es el complementario de a. Igualando los unos y los ceros de

ambas ecuaciones (de stas y de las de arriba) tenemos que: a+a = a+x, y que aa = ax; el nico valor que cumple ambas ecuaciones es x=a, luego a es el complementario del complementario de a.

Y no es un trabalenguas, que conste.

Teorema 7: Los dos trminos neutros de las dos operaciones +, son complementarios entre s, es decir: 0=1 y 1=0

Segn el Axioma 2: a+a=1 y aa=0.

Suponiendo a=0, queda 0+a=1; luego a=1; por tanto 0=1

Suponiendo a=1, queda 1.a=0; luego a=0; por tanto 1=0

Teorema 8: Leyes de De Morgan.

(a+b) = ab ; (ab) = a+b

Los informticos usamos muy a menudo las leyes de De Morgan para simplificar una frmula lgica. O, al menos en mis tiempos, las usbamos a menudo...

He aqu su demostracin:

(a+b) = ab

(ab) = a+b

Sea x = (a+b) Entonces: 1) (a+b)x=0 y 2) (a+b)+x=1 Probamos x=(ab) en 1): (a+b)(ab) = (aab)+(bab) = (aab)+(bba) = (0b)+(0a) = 0+0 = 0 Probamos x=ab en 2): (a+b)+(ab) = a+(b+(ab)) = a+(b+a)(b+b) = a+(b+a)1 = a+b+a = a+a+b = 1+b = 1 Luego x = (a+b) = ab

A4 Der. A4 Izq. A3 Izq. A1 Der. A4 Der. T2 Der. T1 Izq. T4 Izq. A3 Der. A4 Izq. A2 Der. A1 Izq. A4 Izq. T2 Izq.

Sea x = (ab) Entonces: 1) (ab)x=0 y 2) (ab)+x=1 Probamos x=(a+b) en 1): (ab)(a+b) = (aba)+(abb) = (aab)+(bba) = (0b)+(0a) = 0+0 = 0 Probamos x=(a+b) en 2): (ab)+(a+b) = (a+b)+(ab) = a+(b+(ab)) = a+(b+a)(b+b) = a+(b+a)1 = a+b+a = a+a+b = 1+b = 1 Luego x = (ab) = a+b

A4 Der. A4 Izq. A3 Izq. A1 Der. A4 Der. T2 Der. T1 Izq. A1 Izq. T4 Izq. A3 Der. A4 Izq. A2 Der. A1 Izq. A4 Izq. T2 Izq.

En fin: al llegar a este punto, Don Jos mir satisfecho la pizarra toda llenita de frmulas, mir el reloj y nos dijo: Hasta la semana que viene. Buenos das., y se fue rpidamente, dejndo- nos hechos un autntico lo, mirando incrdulos las tres pginas escasas de apuntes donde, aunque nosotros no lo sabamos, acababa de plantar los mejores cimientos sobre los que cons- truir nuestra futura vida profesional.

No entendamos casi nada, claro, porque, consecuencia de no- s-cuntos aos de estudios reglados de matemticas-como- Dios-manda, no podamos evitar ver el signo + como una suma, y el signo como un producto, por mucho que hubira- mos sido advertidos y aquel amasijo de frmulas no tena el menor sentido.

Lo de que a+0=a lo veamos claro y nos pareca muy bien y muy lgico, y lo de que a1=a, tambin, pero Cmo que 1+a=1? Qu es eso de que a+a=a? No ser 2a, como toda la vida? Y, para ms escarnio, cmo es que de pronto existe la propiedad distributiva de la suma respecto de la multiplicacin? Y como axioma, nada menos!

El caso es que nadie interrumpi a Don Jos ese da. Nos limi- tamos a tomar apuntes como si nos los hubiera dictado un extraterrestre y a un extraterrestre no se le discute cuando te cuenta su conocimiento superior, y menos an en la poca de Franco.

Yo me fui a mi casa. Repas los apuntes. Tres veces (ya digo, hasta aqu son slo tres pginas escasas). Nada. Al da siguiente, en lugar de ir a la sacrosanta cafetera en los descansos entre clases, nos quedamos unos pocos recalcitrantes para descifrar aquello Y al da siguiente Y de pronto a alguien (creo que fue a m, que siempre he sido muy listo ejem, pero no estoy seguro) se le ocurri proponer: Oye, digo yo y si cambiamos el + por la Unin de Conjuntos y el por la Interseccin? Qu pasara?

Pues lo que pas es que de pronto, instantneamente, se nos hizo la luz a todos. Evidentemente, naturalmente, ciertamente todo tena sentido entonces.

Tengo que decir aqu que todos nosotros habamos estudiado Conjuntos en el Bachillerato, como una cosa nueva que se haba incorporado recientemente al currculum y que no se saba muy bien para qu serva. As eran las cosas en aquella Espa- a El caso es que todos conocamos el rollo se de los conjuntos, las uniones y las intersecciones y tal, aunque nadie saba para qu serva, y entonces todo nos cuadr. Ahora s que tena sentido que algo Unin el conjunto universal diera siempre el conjunto universal. Etc, etc.

En aquel momento nos acordamos de los ancestros de Don Jos Cuena, por no habernos puesto en la pista y facilitarnos la vida Pero hacindolo de esta forma nos hizo pensar, razonar y buscar analogas hasta comprender todo el asunto. No slo nos ense lgica: nos ense a pensar. Menudo era Don Jos!

Y uno se ha tirado toda su vida pensando, analizando, critican- do no s si me ha servido de mucho, pero, qu le vamos a hacer, no voy a cambiar a estas alturas.

Ha sido ste un captulo denso. Muy denso. Pero en l estn las bases de toda la Lgica y de mucho ms.

No es necesario que lo aprendis de memoria, creo yo, sino ms bien tenerlo de referencia para cuando haga falta. Si el captulo es en definitiva un rollo soberano, es mi culpa. Pero si ha resultado un buen captulo, quiz excepcional, no es mrito mo, pues me he limitado a descifrar mis viejos apuntes y ponerlos en un formato inteligible Y eso s que ha tenido mrito!

A partir de aqu seguiremos escuchando, va el tnel del tiempo, a Pepe Cuena en 1973, ensendonos a seguir pensando.

II- La Forma Normal Disyuntiva en el

lgebra de Boole

En el espeso y lleno de formulas, aunque tremendamente didc- tico (espero), captulo anterior de este libro dedicado a algo parecido a la lgica, vimos cmo en dos patadas Don Jos Cuena se despach toda la definicin del lgebra de Boole.

Al da siguiente (en realidad a la semana siguiente, porque las clases eran semanales, de dos horas cada una), a mediados de octubre de 1973, nuestro profesor apareci, nuevamente a la hora en punto, para seguir iluminndonos.

Sigamos con l, pues.

Bien, lo que Don Jos nos cont ese da fue cmo se defina una determinada relacin en el lgebra de Boole, introduciendo para ello el signo , que relaciona dos elementos del conjunto S.

Evidentemente, esa relacin se llama Menor o igual que, hasta ah podamos llegar

En un lgebra de Boole se puede definir esta relacin mediante la siguiente ecuacin:

Como ya nos habamos dado cuenta los de clase, o al menos la mayora, que para algo el descubrimiento de la semana pasada haba corrido como la plvora, de que el lgebra de Boole era la que regulaba la Teora de Conjuntos, rpidamente nos dimos cuenta de que la relacin en conjuntos era exactamente la relacin Contiene que estudiamos en dicha teora.

Mejor dicho, puesto que aqu es menor o igual que y no mayor o igual que, en realidad se trata de la relacin Es Conteni- do por.

Y claro, a partir de aqu todo fue coser y cantar. Si el conjunto A es contenido por B, esto implica que la interseccin de A y el complementario de B es el conjunto vaco ergo implica que .

Naturalmente. Evidentemente. Claro. Qu tontera!

En la figura siguiente queda claro. B contiene a A, as que A es menor o igual que B, es decir, . Por tanto, la interseccin de A (el conjunto azul) con B (la zona gris clarita), que es el complementario de B (la parte amarilla), es el conjunto vaco, pues no tienen ningn elemento en comn, luego es evidente que .

Toda la clase estuvo dedicada a demostrar las diferentes propiedades de tal relacin, en demostrar que es una relacin de orden, y, dentro de las de orden, de orden parcial, puesto que la relacin Menor o Igual no abarca a todos los elementos del conjunto S.

Por muy intimidante que parezca el prrafo anterior, en realidad es una tontera, es muy sencillo de entender: La relacin en los nmeros naturales o en los reales, por ejemplo, es de orden total: cada uno de todos los nmeros es o menor o mayor (o igual) que todos los dems, pero tratando, por ejemplo, con conjuntos no tiene por qu ser as: pueden existir conjuntos que ni contienen ni son contenidos por otros conjuntos.

El ejemplo ms claro es lo que ocurre entre un conjunto y su complementario, por ejemplo, los espaoles con los extranje- ros (los no espaoles, vaya): ninguno de los dos conjuntos contiene al

otro, es ms, es que en ese caso no comparten ni uno slo de sus elementos.

Como toda buena relacin de orden, cumple con las tres conoci- das propiedades: es Reflexiva (es decir, , pues todo elemento es menor o igual que s mismo, en este caso estrictamente igual) es Transitiva (lo que quiere decir que si

y , entonces , cosa que es bastante evidente), y es Antisimtrica (es decir, que si y simultneamente

, entonces necesariamente , lo que es tambin sencillo de entender).

En realidad, como supongo os habis dado cuenta, la cosa funciona al revs: como en esta relacin se cumplen las tres propiedades, entonces la relacin es de orden. Ahora s.

Esta relacin Menor o igual que, como consecuencia de ser una relacin de orden, cumple un par de propiedades adiciona- les:

Por un lado, si entonces . Y por el otro, si entonces . No voy a demostrar estas frmulas: no son muy complicadas, por no decir que son intuitivas. Pensando en conjuntos se ve muy fcilmente: si x est contenido en y, tambin estar contenido en la Unin de y con cualquier otra cosa; y si x est contenido en y, entonces los complementarios cumplan la relacin opuesta: el complementario de y est contenido en el de x. Muy evidente, como veis.

Quedmonos finalmente con esto: la relacin en un lgebra de Boole es de orden parcial, y con eso nos sirve.

Le bamos cogiendo el tranquillo a esto de la Lgica

Siguiente da, siguiente semana. Hora en punto, nuevamente. Esto ya se est convirtiendo en todo un sntoma Hoy D. Jos nos hablar de La Forma Normal Disyuntiva de las expresiones (funciones) en un lgebra de Boole.

Mmmm. La qu? S, la Forma Normal Disyuntiva, qu pasa? Ser algo importantsimo para lo que sigue ms adelante, as que hagamos menos chiribitas con los ojos, y vayamos al grano.

Primero habr que definir qu es una funcin booleana. Toda aplicacin de que venga dada por una expresin en lgebra de Boole es una funcin booleana. Fcil, no?

Venga, que es sencillo: dado que las dos operaciones definidas para el lgebra (+,) son cerradas, es decir, que aplicadas a dos elementos de S dan como resultado otro elemento de S, el resultado de toda funcin f(x,y,z,) expresada en lgebra booleana tambin pertenece a S.

Bueno, vale, ya voy.

Sea, por ejemplo, la siguiente funcin definida en un sistema que obedece al lgebra de Boole:

, .

Como tanto x como y como z son elementos de S (y, por tanto, sus complementarios tambin lo son), cualquier operacin (+,) realizada sobre ellos (y entre ellos) y sus complementarios dar obligatoriamente un resultado que ser tambin un elemento de S.

Truco: Pensad nuevamente en conjuntos y lo veris claro. Da- dos varios conjuntos cualesquiera y unidos e intersecados entre s y sus complementarios como nos venga en gana, el resultado ser siempre s, otro conjunto. Eso es una aplicacin de .

Tericamente, las expresiones del lgebra de Boole podran lle- var constantes; de hecho hay dos constantes de oficio: los dos elementos neutros, 0 y 1. Pero las constantes en el sentido al- gebraico habitual no tienen mucho sentido. Qu sera 6a, por ejemplo? Pues a, claro, dado que 6a=a+a+a+a+a+a. Y como sabemos que a+a=a, entonces 6a=a, obviamente. Y qu sera

, entonces? Pues (a+b), naturalmente, dado que (a+b)(a+b)=(a+b). En definitiva, nunca aparecern constantes en

las expresiones que usaremos aqu (ni en las que usaremos normalmente en nuestra vida cotidiana de relacin con el lgebra de Boole).

Como dira Forrest Gump: Mejor, una cosa menos!.

Pues bien, si tenemos una funcin booleana cualquiera en la que no aparecen constantes, ( , por ejemplo), entonces dicha funcin se puede representar como una suma de productos , tales que:

1) En todo trmino aparecen reflejadas todas las variables que aparecen en la frmula original (bien complementadas, bien sin complementar).

2) Todos los productos son distintos entre s.

Cabe decir aqu que a partir de ahora har lo mismo que Don Jos hizo hace casi cuarenta aos, simplificando la notacin de las frmulas de la misma manera que lo hacemos en el lgebra normal, la numrica: no escribiendo el signo , salvo en los casos donde su uso sea preciso para hacer ms descriptiva la frmula.

Es decir, la frmula del ejemplo de arriba (y todas las dems) la escribir preferentemente a partir de ahora del siguiente modo:

Se entiende, no? Pero recordad que + no es suma ni es multiplicacin en el sentido numrico habitual, sino que son sumas booleanas o productos booleanos, que ya veremos cmo se definen en segn que sistemas En conjuntos, por ejemplo, + es Unin y es Interseccin, como ya sabis. En otros sistemas, sern otras cosas Paciencia.

Volviendo a la afirmacin de hace un ratito (eso de que toda funcin se puede descomponer en sumas de productos), veremos cmo se llega a esto, procediendo a la reduccin sistemti- ca de las expresiones en tres pasos:

Paso 1: Quitar sistemticamente toda complementacin a frmulas entre parntesis. Para ello usaremos extensivamente las Leyes de De Morgan. stas fueron demostradas en el Teorema 8 que vimos en el captulo anterior.

Y no, no son las Leyes de Morgan, como las llama casi todo el mundo que habla en espaol, sino Leyes de De Morgan, puesto que son debidas al matemtico indio-britnico Augustus De Mor- gan

Por ejemplo, si tenemos , quedara, aplicando la Ley de De Morgan, .

Al final de este paso slo estn complementadas las variables individuales, no operaciones con ellas.

Paso 2: Quitar sistemticamente el signo entre parntesis, aplicando la propiedad distributiva. As, quedara .

Por ejemplo, quedara .

En realidad, se es el resultado final, tras dos pasos. El primero de ellos dejara , y en un segundo paso quedara

; reordenando los trminos queda la frmula del texto.

Por supuesto, si algn trmino tiene simultneamente una variable x y su complementaria, x, al estar ambas multiplicndose entre s, el resultado de esta multiplicacin es cero, por lo que podemos eliminar sin pudor alguno el trmino completo. As, si, por ejemplo, resultara un trmino , al ser , queda , y podemos eliminar el trmino completo, pues sabemos que . Adems, si quedan dos o ms trminos exactamente iguales, se pueden eliminar todos menos uno, puesto que sabemos tambin que .

Bien, ahora tenemos ya la expresin reducida a una suma de productos distintos pero no es suficiente, porque es posible que no en todos los productos estn representadas todas las variables, lo que era uno de los requisitos iniciales.

De hecho, en el ejemplo anterior son 4 las variables y ningn

trmino tiene ms que dos Hay que hacer algo para que todos los trminos tengan todas las variables, bien complementadas, bien sin complementar, que era el requisito pre- vio, si os acordis.

Para solucionarlo:

Paso 3: Multiplicar los trminos a los que les falte alguna variable x por (x+x), que, como es igual a 1, no cambia el resultado.

Por ejemplo, si son tres las variables de una cierta funcin f(x,y,z), y tenemos un trmino xy (sin z), entonces ste se multiplica por (z+z), quedando entonces .

Nuevamente, si como consecuencia de todas estas operaciones resultan dos o ms trminos iguales, se eliminan todos ellos menos uno, debido a la consabida idempotencia:

En fin, tras la aplicacin secuencial de estos tres pasos tenemos la misma frmula original, bien masajeada, vale, pero la misma original, expresada de la forma pedida.

A esta forma de organizar las frmulas booleanas se le denomina Forma Normal Disyuntiva (FND), y veremos que nos ser de gran utilidad ms adelante y hasta aqu puedo contar de momento.

Veamos un ejemplo: Sea . Con tres variables, como podemos ver: x,y,z. Cul es su Forma Normal Disyuntiva?

Aconsejo a los que os interese todo esto que intentis realizar el proceso vosotros solos, tenis conocimientos y argumentos ms que suficientes para hacerlo y es fcil.

Segn el paso 1, se eliminan los complementos en parntesis (por Ley de De Morgan).

queda, en primer lugar,

, que a su vez queda

. Reordenando los productos (gracias a la

propiedad conmutativa) queda, por fin:

. Ahora aplicamos la distributiva (paso 2). Primero, sacamos en los dos primeros trminos como sumando comn a x (mira que resulta raro lo de sacar sumando comn ms vale acostum- brarse), y entonces queda:

. Ahora aplicamos de nuevo la distributiva en el

primer parntesis, y queda:

; zz es cero, as que lo eliminamos, y queda: . Otra vez la distributiva, y queda:

, y otra vez ms y queda, finalmente: .

Como xx es igual a cero, lo mismo que yy, queda finalmente: .

Ya est? Pues no, an queda el ltimo paso.

Uno de los dos trminos (xy) no tiene la variable z, as que lo multiplicamos por (z+z), que es, obviamente, 1 (paso 3), y tenemos que la frmula original, sa tan fea de ah arriba, es equivalente a

, mucho ms bonita, dnde va a parar, que ya est en Forma Normal Disyuntiva.

Si os lo estabais preguntando, s, efectivamente, tambin hay una Forma Normal Conjuntiva, que es parecida a la FND, pero sustituyendo los + por y viceversa, as que lo que resulta es un producto de trminos tal que cada uno de ellos es una suma que contiene todas las variables, complementadas o no, en vez de una suma de productos

La demostracin es idntica, en realidad, a la de la Forma Nor- mal Disyuntiva, cambiando, en los pasos 2 y 3, el 1 por el 0 y el + por el , y viceversa. Ya lo sabis: todo en lgebra de Boole es dual.

Podramos ahora definir una Forma Normal Disyuntiva Com- pleta, que es, para n variables, la suma de todos los productos posibles de esas n variables complementadas y sin complemen-

tar, que, como es fcil comprobar, son en total : las permuta- ciones de 2 elementos (los dos estados: complementado-sin complementar) tomados de n en n.

Se demuestra fcilmente que esta Forma Normal Disyuntiva Completa es igual a la unidad (a 1, en realidad: es algo muy in- tuitivo, yo no voy a hacerlo aqu).

Por otra parte, se demuestra tambin fcilmente que, suponiendo como conjunto de valores posibles slo 0 y 1, y dando a las variables valores arbitrarios entre estos valores 0 1, en la Forma Normal Disyuntiva Completa slo habr un nico trmino que valdr 1 y todos los dems, 0 (y su suma, 1, claro, al sumar muchos ceros y un nico 1).

Esto es as porque para que un trmino (producto) cualquiera valga 1 en estas condiciones, todas las variables que lo compo- nen tienen que valer 1, por lo que habr slo una combinacin plausible: cualquier otra combinacin variar en al menos un valor de una variable, que ser entonces 0 y anular al trmino completo, al estar esa variable que es igual a cero multiplicando al resto.

Y lo mismo ocurre con la Forma Normal Conjuntiva, pero al revs, claro: la Forma Normal Conjuntiva Completa ser siempre cero, por los mismos argumentos, aunque cambiando el 0 por el 1 y la suma por la multiplicacin, y viceversa. Ah, la dualidad, siempre la dualidad en el lgebra de Boole.

Un pequeo ejemplo para fijar las ideas (recordad que en este caso concreto los valores permitidos de las variables slo pueden ser 0 y 1):

Mirando la Forma Normal Disyuntiva Completa de un conjunto de tres variables, x,y,z, uno de los trminos que la forman es, necesariamente, .

Este trmino slo puede valer 1 para los valores siguientes de las

variables: x=1; y=0; z=1. Si los valores de las variables fue- ran exactamente estos, qu les ocurrir al resto de trminos de la FNDC, por ejemplo al ?

Pues que variarn en al menos la complementacin de una variable, en nuestro ejemplo en dos: x e y. Y al variar en alguna variable, quiere decir que alguno de los trminos del producto ser 0, por lo que el producto completo ser cero.

Efectivamente, siendo x=1; y=0; z=1, el producto es cero. Y todos los dems tambin, salvo el que cit al principio, el , que valdr 1.

Luego la FNDC se compone de la suma de un nico trmino que vale 1 y otros siete que valen todos 0, por lo que la suma final es 1. Siempre 1.

Vale, todo esto est muy bien, pero Para qu diablos sirve esta dichosa Forma Normal Disyuntiva?

Pues para saber si dos funciones son en realidad la misma, puesto que toda funcin que sea igual a otra tendr su misma Forma Normal Disyuntiva (y tambin su misma For- ma Normal Conjuntiva, claro).

Esto nos ser de gran utilidad ms adelante, porque podemos representar la FND de cualquier funcin booleana en forma de tabla y esto ser crucial para comprender segn qu sistemas. Habr que esperar a los siguientes captulos del libro para irlo descubriendo.

Paciencia.

Veamos entonces cmo quedara la frmula que habamos visto antes, aquella tan fea en la que, tras operar convenientemente, habamos visto que su Forma Normal Disyuntiva era finalmente la

siguiente: . Para rellenar la dichosa tabla, representamos todos los valores posibles de la Forma Normal Disyuntiva Completa (en este caso sern ), y entonces marcamos con un 0 los trminos que no estn en su FND, y con un 1 los que s estn, proceso que convendris conmigo que es bastante sencillo.

Y el resultado es:

V: x

V: y

V: z

f(x,y,z)

x

y

z

0

x

y

z

0

x

y

z

1

x

y

z

1

x

y

z

0

x

y

z

1

x

y

z

0

x

y

z

0

Las cosas empiezan a tener sentido, no?

Aqu se acab la clase, aquel fro otoo de 1973. Y el captulo con ella. En los captulos que vienen a continuacin usaremos continuamente estas tablas de valores, as que mejor compren- derlas muy bien

III- lgebra de Circuitos

En el captulo anterior trasteamos con la definicin de la Forma Normal Disyuntiva en un lgebra de Boole. Dije all que sera importante para todo lo que vendra ms adelante; aqu comenzaremos a ver cul es esa importancia.

Repito una vez ms que uso para confeccionar este pequeo libro los apuntes de Lgica de mi Segundo de Carrera, all por 1973-74, impartidos por D. Jos Cuena, Pepe para casi todo el mundo.

Nueva semana, nueva clase. Don Jos Cuena aparece con cinco minutos de retraso (Pardiez, l tambin es humano!) y comien- za su clase, definiendo qu es un interruptor un interruptor elctrico. Bueno, no es que nos describiera fsicamente dicho artilugio infernal (materiales, tamaos, tolerancias, etc), no, sino para qu sirve.

Un interruptor es, definido de este modo, un artefacto elctrico que sirve para dejar pasar la corriente en un circuito o para cortarla, segn que est en estado Cerrado o Abier- to, respectivamente. Es decir, la llave de la luz, vaya.

Un interruptor elctrico, y su

diagrama

Un interruptor puede estar en dos posiciones, mediante el accionamiento del mecanismo, que lo pone bien en estado A (y la corriente se corta), bien en estado C (y la corriente sigue su curso). O sea, mismamente una llave de la luz, sin ir ms lejos.

Entonces, tras esta ingenua definicin, comenz Don Jos a modelizar cmo son los circuitos elctricos, compuestos de cables e interruptores Veamos qu es lo que pasa. Qu es lo que pas, en realidad.

En primer lugar, un determinado interruptor puede ser modeli- zado por una variable, digamos x por ser originales, que slo puede adoptar dos valores, que denotaremos como x y x, ya que el interruptor puede estar en uno u otro de los estados, pero no al mismo tiempo: Abierto(A)/Cerrado(C).

Por convencin asignamos el valor 1 al estado Cerrado (pasa la corriente) y 0 al estado Abierto (no pasa la corriente), aunque nada nos impedira hacerlo al revs. Asimismo, ambos estados son complementarios entre s: lo contrario a Abierto es Cerrado, y viceversa, como es evidente.

Representado en una tabla, queda algo tan soso como:

x

x

A

C

C

A

En cuanto a cmo podemos conectar cables e interruptores, o sea, qu operaciones es posible realizar con ellos, hay dos ma- neras, y slo dos:

En serie: Dos interruptores x e y estn conectados en serie si estn conectados uno a continuacin del otro sobre la misma lnea.

La corriente slo pasa si ambos interruptores estn simultneamente cerrados.

En paralelo: Dos interruptores x e y estn conectados en paralelo si estn conectados cada uno en un ramal de la lnea, volviendo a unirse ambos inmediatamente despus. La corriente

pasa si cualquiera de los interruptores (o los dos) estn cerrados.

El esquema de ambos casos es el siguiente:

Entonces, el esquema de funcionamiento puede establecerse mediante las siguientes tablas, recordando siempre que 0 significa Abierto y 1 significa Cerrado. Y s, evidentemente, aqu estamos usando la Forma Normal Disyuntiva!, la que vimos en el captulo anterior.

Empezamos ya a vislumbrar cul es su enorme utilidad.

Serie

()

x

y

xy

Paralelo

(+)

x

y

x+y

1

1

1

1

1

1

1

0

0

1

0

1

0

1

0

0

1

1

0

0

0

0

0

0

Es evidente por su comportamiento que podemos llamar a la operacin conectar en serie y + a la operacin conectar en paralelo, dado que tiene como representacin su misma tabla. Entonces, a partir de este momento usar esta notacin: cuando

ponga + significa conectar en paralelo, y cuando diga , significa conectar en serie.

Ahora lo que corresponde es comprobar qu es el Conjunto (S,+,) siendo S un conjunto de variables (interruptores) que admiten slo dos valores (Abierto = 0 y Cerrado = 1, porque

para algo son interruptores y slo pueden estar en esas dos posiciones) y las operaciones +,, es decir, las conexiones en paralelo y en serie, respectivamente.

Ser acaso este conjunto una hermosa lgebra de Boo- le? Para que ello fuera cierto debera cumplir los cuatro axiomas de Huntington que vimos en el primer captulo del libro, pero si lo fuera entonces no tendramos que calcular nada ms: todos los axiomas y hallazgos que hicimos para un lgebra de Boole cualquiera serviran automticamente para el clculo de circuitos Y eso seguramente sera una buena cosa.

Veamos, pues:

Son, quiz, conmutativas las operaciones + y ?

Si escribimos la tabla anterior como tabla de doble entrada, po- niendo cada variable x,y una en abscisas y otra en ordenadas, tenemos:

y

y

x

+

0

1

x

0

1

0

0

1

0

0

0

1

1

1

1

0

1

Si nos fijamos bien, ambas tablas son simtricas respecto a la diagonal ngulo superior izquierdo ngulo inferior derecho;

podemos deducir, por tanto, que ambas son conmutativas, pues. Adems, el sentido comn nos dice que si tenemos dos interruptores a y b conectados en serie, es indiferente que est fsicamente antes el a o el b el resultado es el mismo, pues s- lo pasa la corriente si ambos estn cerrados, y lo mismo, o mejor dicho, lo contrario, si estn en paralelo.

Por lo tanto, s, los circuitos elctricos cumplen con el axioma 1 del lgebra de Boole. Sigamos.

Existirn, tal vez, elementos neutros para ambas operaciones, + y ? Estos elementos neutros sern 0 (abierto), para la suma (conexin en paralelo) y 1 (cerrado), para la multiplicacin (conexin en serie).

Dado un interruptor cualquiera, si le conectamos un interruptor Abierto (0) en paralelo (operacin +), el resultado del circuito, si circula o no corriente por l, depende exclusivamente del estado (Abierto-0 o Cerrado-1) del interruptor original.

A su vez, dado un interruptor cualquiera, si le conectamos un interruptor Cerrado (1) en serie (operacin ), el resultado del circuito, si circula o no corriente por l, depende exclusivamente del estado (Abierto-0 o Cerrado-1) del interruptor original (de hecho este ltimo caso es equivalente a alargar el cable conectando un nuevo trozo al trozo original).

Una imagen que vale ms que mil palabras:

En trminos algebraicos, pues: x+0 = 0+x = x, por un lado, y x1 = 1x = x, por el otro.

Por tanto, existe un elemento neutro de cada operacin, y se cumple el Axioma 2 del lgebra de Boole.

No va mal la cosa. Prosigamos.

Sern, por ventura, distributivas las operaciones + y respecto de la otra?

Si nos acordamos, la propiedad distributiva de un lgebra de Boole obligaba a que se cumplieran las siguientes ecuaciones:

x(y+z) = xy+xz, por un lado, y por el otro:

x+(yz) = (x+y)(x+z).

Para ver si, por ventura, se cumplen estas propiedades distributivas, construimos una tabla de valores, con la que comproba- remos si el circuito resultante tiene o no corriente al final.

Primero, para la distributiva de la multiplicacin respecto de la suma, con la FND completa, de nuevo!, que tendr 8 filas, es decir, , dado que son tres las variables: x,y,z.

x

y

z

y+z

x(y+z)

xy

xz

xy+xz

1

1

1

1

1

1

1

1

1

1

0

1

1

1

0

1

1

0

1

1

1

0

1

1

1

0

0

0

0

0

0

0

0

1

1

1

0

0

0

0

0

1

0

1

0

0

0

0

0

0

1

1

0

0

0

0

0

0

0

0

0

0

0

0

Esta tabla la hemos construido, paso a paso, fijndonos siempre en si la corriente circula o no en cada uno de los 8 casos repre- sentados por la combinacin de las tres primeras columnas.

El esquema de construccin es el siguiente:

La quinta columna de la tabla, x(y+z), muestra el resultado del circuito mostrado en el primer dibujo; mientras que la ltima columna, xy+xz, muestra el comportamiento del representado en el segundo dibujo.

Se ve con claridad que ambos son perfectamente equivalentes, pues con cada posible posicin de todos los interruptores, siempre que la corriente circula en el primer circuito, circula tambin en el segundo circuito, luego ambos circuitos son equivalentes, y por consiguiente cumplen esta propiedad.

Slo queda comprobar la propiedad distributiva equivalente, es decir, si la propiedad distributiva de la suma respecto de la multiplicacin se cumple tambin, y lo haremos de la misma forma, construyendo tambin su correspondiente tabla de valores.

En este caso, el esquema de construccin es el siguiente:

Veamos la tabla de valores correspondiente:

x

y

z

Yz

x+(yz)

x+y

x+z

(x+y)(x+z)

1

1

1

1

1

1

1

1

1

1

0

0

1

1

1

1

1

0

1

0

1

1

1

1

1

0

0

0

1

1

1

1

0

1

1

1

1

1

1

1

0

1

0

0

0

1

0

0

0

0

1

0

0

0

1

0

0

0

0

0

0

0

0

0

Esta tabla la hemos construido tambin paso a paso, fijndonos siempre en si la corriente circula o no en cada caso.

La quinta columna, x+(yz), muestra el resultado del circuito del primer dibujo, cundo circula la corriente y cundo no circula, mientras que la ltima columna, (x+y)(x+z), muestra el comportamiento del circuito del segundo dibujo. Idnticas.

Por tanto, podemos asegurar que en los circuitos se cumplen ambas propiedades distributivas, es decir, cumplen tambin el axioma 3 del lgebra de Boole.

Bien, bien, vamos bien Sigamos con el ltimo axioma que nos

queda por comprobar. Existir, por una afortunada coincidencia, un elemento complementario para cada elemento de S, es decir, para cada conmutador?

sta s que es fcil, pues refleja la caracterstica ms caracterstica (valga la redundancia) de un interruptor: que puede estar

abierto o cerrado y nada ms: no puede estar casi abierto y medio cerrado a la vez, al menos si no tenemos en considera- cin efectos cunticos y dems y aqu no encontraris ni una palabra sobre cuntica, que para eso ya est la prodigiosa serie de Pedro en El Tamiz.

Y dado que un interruptor puede estar Abierto (0) o Cerrado (1), estados que, si al interruptor lo llamamos x, denominaremos x y x, respectivamente, por convencin (es decir, un interruptor puede estar en estado x, cerrado, o x, abierto), entonces cumplen que x+x=1 y que xx=0.

Los siguientes dibujos representan ambas situaciones, donde se puede comprobar fcilmente el cumplimiento de ambas suposi- ciones.

En el primero, en serie, sea cual fuera el valor de x, Abierto o Cerrado, su complementario x tiene el valor contrario. Por tan- to, uno de los dos est siempre Abierto y como consecuencia no hay corriente en el final del circuito. Lo contrario pasa si estn conectados en paralelo; uno de los dos estar necesariamente Cerrado, lo que garantiza que al final del circuito haya siempre corriente.

Por lo tanto, los circuitos cumplen tambin el Axioma 4 del l- gebra de Boole. Y como ste postulado era el ltimo que queda- ba, eso quiere decir que los circuitos cumplen todos los axiomas del lgebra de Boole.

Estupendo. Y entonces?

Pues que vamos a poder representar circuitos elctricos con funciones booleanas. Ni ms, ni menos. As que lo primero que haremos es denominar lgebra de Circuitos a las operaciones que podemos hacer con circuitos, aadiendo o qui- tando interruptores Y el lgebra de Circuitos es un lgebra de Boole, una vulgar y nada especial lgebra de Boole, un l- gebra de Boole monda y lironda.

Como consecuencia, todas las transformaciones, teoremas y cositas varias (como la Forma Normal Disyuntiva) que hemos encontrado y demostrado para el lgebra de Boole son inmediata y directamente aplicables al diseo de circuitos.

Casi nada! Ya habis aprobado el primer curso de Electricis- ta. Hala. Ya slo os queda aprender todas esas tonteras de la Ley de Ohm, los voltajes y los amperios y cundo no conviene tocar con los deditos un cable pelado para no tener que bailar claqu sin pretenderlo, pero eso, leyendo el libro que sobre Electricidad escribi Pedro en El Tamiz, es pan comido. Bueno o no.

Algunos electricistas me he topado yo a lo largo de mi vida que si tuvieran algn conocimiento de lgebra de Boole hubieran mucho mejor su trabajo, porque tengo cada chapuza de conexiones de cables en mi casa!, como, por ejemplo, que la luz del pasillo est simultneamente conectada a dos diferenciales diferentes, o que cuando se va una zona determinada, la de la cocina, porque salta el diferencial al enchufar la plancha, la la- vadora y el horno a la vez, entonces el saln, que no tiene nada que ver en teora, se queda a media luz Misterios de las conexiones escondidas en tubos, cajas y empalmes. Escondidas, s, pero mal hechas.

Volviendo a lo nuestro, Don Jos Cuena estuvo varios das dando vueltas a la teora de Circuitos; hablando sobre Diseo de Circuitos, o viendo, por ejemplo, el mtodo de Karnaugh para simplificar circuitos. Esto de simplificar circuitos es til cuando te dan un circuito embarullado, como los de mi casa sin ir ms lejos, y tienes que buscar un circuito equivalente ms sencillo que haga lo mismo Ojo, lo mismo, no lo correcto, que eso es otra cosa.

No voy a entrar en detalle en esta parte, sin duda muy interesante, pues a m me ha servido muchas veces ante el dilema de cmo conectar de la mejor manera posible algn cacharro en casa, pero que se escapa del alcance de este libro. No quiero entrar en conflicto con ningn sindicato de electricistas.

Adems, Javier J Sedano public un magnfico artculo sobre el mtodo de Karnaugh dentro de la propia serie Eso que llamamos Lgica en El Cedazo, artculo que encontraris como Apn- dice II al final de este libro.

Slo voy a poner un nico ejemplo de cmo disear un circuito que probablemente sea de los ms tiles que necesitaremos en nuestras mansiones: cmo instalar un foco, lmpara o simple bombilla desnuda regulada por dos conmutadores.

Un conmutador es parecido a un interruptor, tan parecidos como que por fuera son igualitos, pero con dos salidas en vez de una; por lo tanto lo que hace en realidad es enviar (conmutar) la corriente por uno u otro camino, en vez de simplemente interrum- pir o no la corriente.

Su diagrama es el siguiente:

Fijaos que en realidad el conmutador no interrumpe nada, tan slo deriva (conmuta) la corriente elctrica por uno u otro cable, segn que su mecanismo est situado en una u otra posicin. O sea, siempre tiene un lado abierto y el otro cerrado (salvo los

nanosegundos en que el mecanismo en movimiento, en que no est en contacto con ningn borne pero mejor vamos a obviar esto, no?).

En realidad, bien se podra usar un conmutador como mero interruptor, simplemente no conectando nada a una de las dos salidas. De hecho la mayora de aparatos comerciales que se venden hoy por ah son todos conmutadores, pues el pequeo sobrecoste de la circuitera adicional no compensa comercial- mente fabricar y distribuir varios tipos de mecanismo.

Son cosas de la economa moderna: en mis tiempos eso no pa- saba, haba conmutadores e interruptores, que eran bastante ms baratos, aunque hay que reconocer que los interruptores eran redondos, con una especie de palomillas giratorias que, en una posicin, por ejemplo en vertical, estaban abiertos, mientras que en la otra, en horizontal, estaban cerrados a ver quin es el artista que disea un conmutador con semejantes caractersticas.

Volviendo a nuestro caso, lo que tenemos es una habitacin normal y corriente en la que hay dos llaves de la luz (conmutadores en este caso), una en cada extremo de la habitacin, y queremos que cualquiera de las llaves encienda/apague la luz independientemente de la posicin de la otra, es decir, que si la luz est encendida, al accionar cualquier conmutador se apague, y viceversa, si est apagada, que se encienda cuando accione- mos cualquiera de los dos. Lo mismito que tenemos en el saln o el dormitorio, vaya.

Lo primero de todo es modelizar el comportamiento de nuestro sistema, teniendo en cuenta que llamaremos a los dos conmutadores x e y, para variar. Para ello crearemos la tabla de estados, en la que modelizaremos nuestro sistema de dos conmutadores.

Cmo hacemos eso?

Mediante la Forma Normal Disyuntiva, desde luego. La tabla resultante es la siguiente:

x

y

Hay luz?

1

1

1

1

0

0

0

1

0

0

0

1

El primer valor (un 1) lo ponemos arbitrariamente, pues en principio igual nos da que en este caso haya luz o no en la habitacin salvo que seis unos frikis como yo y os empeis en que cuando todos los interruptores o conmutadores de la casa estn hacia abajo, est toda la casa apagada Ese truco permi- tira dejar todas las luces de la casa apagadas incluso cuando no hubiera electricidad. En fin, cosas mas.

Lo importante, digo, es que una vez fijado este caso inicial, con una nica pulsacin sobre cualquier conmutador la luz se apague, y una vez apagada, con una nica pulsacin sobre cualquier conmutador la luz se encienda. Eso quiere decir que, desde el estado inicial (1,1), una nica variacin en cualquiera de los dos conmutadores (0,1) (1,0), debe apagar la luz; mientras que a partir de cualquiera de estos dos estados, un nico cambio en cualquier variable, o sea, una pulsacin en cualquier conmutador, encienda la luz. Esos dos estados son el (1,1) original o el (0,0).

Se ve claro? Espero que s.

Pues ahora podemos darnos cuenta de una pequea sutileza: si sumamos (ojo: esta vez, y sin que sirva de precedente, utiliza- remos una suma numrica normal, no booleana) los valores 0

1 de cada fila, si la suma da un valor cero o par ( (1,1) suma 2, y (0,0) suma 0), el sistema debe estar encendido; mientras que si el resultado de la suma es impar ( (0,1), (1,0), que ambos suman 1), el sistema debe estar apagado. Interesante, no?

Bien, ahora escribamos la funcin booleana que describe el sistema a partir de la tabla de funcionamiento, que ya sabis que es la Forma Normal Disyuntiva de la Variable. La funcin Bom- billa encendida se representa por la funcin f(x,y)=xy+xy. Es decir, ambos conmutadores pueden estar o bien hacia arriba o hacia abajo para que la corriente transite por la bombilla y podamos leer a su luz algn buen libro

Cmo se implementa esta funcin xy+xy con los conmutadores? Fcil; mediante su conexin de la forma siguiente:

Ahora, sabiendo esto, podemos disear circuitos donde no haya dos conmutadores para encender/apagar un sistema, sino que haya tres, cuatro Se crea la tabla de valores de todos los estados posibles de todos los conmutadores ( posibilidades), y se marca cules de ellos deben dar como resultado de la funcin Apagado (0) Encendido (1). Para no equivocarse al asignar valores, se puede uno ayudar por el truco de sumar todos los valores (con una suma numrica normal) y asegurarse que todos los valores impares tengan el mismo valor final (0 1, igual da), y los valores pares o cero, el contrario. Este truco garantiza que desde cualquier posicin, el cambio de una nica variable (o sea, el accionamiento de un conmutador cualquiera) cambia el resultado de la suma en 1, en ms o en menos, y eso cambia la paridad del resultado final, y por tanto, el valor Encendi- do/Apagado de nuestra bombilla.

As que, si os viene en gana y queris practicar, podis disear cmo sera el circuito para tener tres conmutadores que go-

biernen el encendido de una bombilla: uno en la entrada de la habitacin, otro al lado de la cama y el tercero al lado de la me- sita. No deberais tener ningn problema en llegar a la funcin.

Pero quiz s lo tengis al disear el circuito porque necesita- ris de un nuevo mecanismo que llamaremos conmutador de cruce, conmutador/cruzador, o simplemente cruzador, cuyo diagrama de actuacin es el siguiente:

En la imagen no slo est el diagrama del cruzador, sino tambin el diagrama tcnico de un cruzador comercial, para mayor informacin.

En una de sus posiciones, el conmutador-cruzador permite el paso directo de corriente, de a a c y de b a d, mientras que en la otra permite el paso cruzado de la corriente, de a a d, y de b a c.

Como veis, este conmutador no interrumpe nunca la corriente, sino que deriva ambas entradas por un camino o por su contrario, dependiendo de su posicin. Ya slo os queda disear el circuito

Para terminar el captulo, uno de los problemas que nos puso Don Jos en el examen sobre circuitos, all por las navidades del 73, aunque lo he tuneado un poco No es muy difcil, pero s muy divertido. No voy a dar la solucin para no chafaros el disfrute de hacerlo y aprender un poco ms sobre circuitos elctricos. Dice as:

Pedro, J y Mac, como no tienen otra cosa que hacer, estn ju- gando a cara o cruz con una moneda cada uno y un dispositivo elctrico con tres botones, cada uno de ellos asociado a cada uno de los jugadores, que denominaremos p, j y m.

Cada jugador lanza su moneda y pulsa el botn correspondiente si sale cara y no lo pulsa si sale cruz.

Gana el juego el jugador que tenga un valor en su moneda dis- tinto al de los otros dos. Por ejemplo, si Pedro tiene cara y J y Mac tienen cruz, gana Pedro. O si J tiene cruz y Pedro y Mac tienen cara, gana J. Si los tres valores son iguales, no gana nadie.

Se pide disear un circuito con un origen (una toma nica de corriente) y cuatro bombillas que se iluminan: la bombilla 1, si gana Pedro; la bombilla 2, si gana J; la bombilla 3, en el alta- mente improbable caso de que gane Mac; y, por fin, la bombilla 4 si no gana nadie.

Que sepis que aqul que logre resolverlo (no es tan difcil) no va a poder patentarlo Ya lo hice yo, je, je! Incluso me sirvi para aprobar el primer parcial de la asignatura.

Hasta aqu lo que voy a contar sobre circuitos elctricos. En la red podis encontrar mucho ms y mejor que esta breve introduccin. Y, desde luego, en cualquier curso sobre electricidad.

Pero no contado de esta manera, me temo.

En el prximo captulo, una vez bien sentadas las bases, empezar a hablar (mejor dicho: Pepe Cuena empezar a hablar), de una vez por todas, de algo parecido a la Lgica.

IV- El lgebra de Conjuntos, revisitada

En el captulo anterior de este libro dedicado ms o menos a la Lgica dimos un vistazo necesariamente rpido al lgebra de Circuitos. Me dej por contar bastantes cosas sobre simplifica- cin de circuitos, diseo, etc, sobre todo por el mtodo de Karnaugh (en realidad se supona que muchos de nosotros nos tendramos que dedicar al diseo de hardware, as que se contaban todas estas cosas; luego, el 95% o ms de nosotros nos dedicamos al software) pero creo que no aportaba gran cosa a lo que quera contar.

Adems, en la red se encuentra bastante documentacin al respecto para los electricistas en ciernes, incluyendo el estupendo artculo de J en El Cedazo que encontraris en el Apndice II de este librito.

As que seguir con la asignatura de Metodologa de mi Segundo de Carrera, impartida por Don Jos Cuena Bartolom en el Insti- tuto de Informtica (antes de que se convirtiera en Facultad), all por finales del ao 1973

Bueno, pues tras contar teora sobre al lgebra de Boole y su inmediata aplicacin a los Circuitos elctricos, Pepe Cuena entr a saco a la Teora de Conjuntos (sa que conocamos malamen- te desde el Bachillerato, con sus diagramas de Venn y todo eso), pero con una orientacin bastante diferente de la que habamos visto entonces, con una orientacin muy lgica, si se me permite la expresin.

Enseguida veris por qu digo esto

Los conjuntos, definidos de la forma clsica, es decir, todos aquellos

grupos de elementos dentro del Conjunto Universal que son factibles de agruparse por cualquier criterio, ms las operaciones Union (+) e Interseccin (), forman un lgebra de Boole, eso es algo bastante claro. De hecho, fue este conocimiento (al que llegamos tras horas de frustrantes especulacio- nes, como cont en el primer captulo del libro) el que nos libr de ser ingresados en un frenoptico cuando nos enfrentamos

por vez primera con el lgebra de Boole, as que lo dbamos por descontado.

Aviso: A lo largo de este captulo dedicado al lgebra de conjuntos, y en contra de lo normalmente aceptado, usar siempre y + en vez de y . Con ello pretendo afianzar la idea de que el lgebra de conjuntos es un lgebra de Boole de lo ms nor- malita.

Para aquellos de vosotros que tengis un poco oxidados los conjuntos, justo a continuacin tenis un par de ellos para vuestro uso y disfrute, A (azul) y B (rojo), inmersos en un Conjunto Universal verde que te quiero verde

Dos conjuntos tpicos en un Diagrama de Venn

La interseccin entre A y B es la parte gris rayada; la unin entre A y B es todo lo que no es verde; el complementario de A es lo que le falta para ser el Universal, es decir, lo que no es azul (y el complementario de B, lo que no es rojo), etc, etc. Pa- ra fijar ideas, suponed, por ejemplo, que el conjunto A son los rubios y el conjunto B, los que tienen ms de cincuenta aos, y rpidamente podis poner cara y ojos a todos y cada uno de los grupitos que aparecen en el dibujo.

Tambin os acordaris de que un conjunto puede contener a otro. Por ejemplo, el conjunto de los europeos contiene al conjunto de los espaoles, y a su vez el conjunto de los espaoles est contenido en el conjunto de los europeos, y decimos que los espaoles son un subconjunto de los europeos Hasta aqu no creo que haya descubierto nada nuevo.

Entremos, pues, en materia:

Es evidente que, lidiando con conjuntos:

1- Las dos operaciones (+,, es decir, Unin e Interseccin) son conmutativas.

2- Existe un elemento neutro para cada operacin: el Conjunto Vaco, o 0, para la unin (+) y el Conjunto Universal, o 1, para la interseccin ().

3- Ambas operaciones cumplen la propiedad distributiva respec- to de la otra ( A(B+C) = AB+AC; y A+(BC) = (A+B)(A+C) ).

4- Todo Conjunto A tiene su complementario A tal que A+A=1 y AA=0, es decir, el Conjunto Universal menos el propio conjunto A.

As que, al cumplir con los axiomas de Huntington, no queda duda de que los conjuntos, con la Unin y la Interseccin, forman un lgebra de Boole.

En teora de conjuntos, una cierta informacin aplicada a un cierto conjunto permite determinar un subconjunto de l. Por ejemplo, si tenemos el conjunto de todas las ovejas de un reba- o, aplicando una cierta informacin, un cierto atributo de ellas (el de ser negras, por ejemplo) define un subconjunto del anterior, el que forman las ovejas negras del rebao, o sea, aquellas ovejas que, perteneciendo al rebao, son negras, es decir, aquellas ovejas en las que se cumple que la frase ser negra es verdadera, siendo una oveja negra la interseccin entre las ovejas y las cosas que son negras... o algo as.

Como no todas las ovejas del rebao son negras (o s, quin sa- be, pero en principio esto es irrelevante), se define la relacin Estar contenido en ( ) por la que denotamos que todos los elementos de un determinado conjunto pertenecen tambin a otro conjunto de

rango superior. Estrictamente, un conjunto A es contenido por uno B ( ) cuando todos los elementos de A estn tambin en B, pero el conjunto B puede tener ms elementos que no estn contenidos en A o no, en cuyo caso A y B seran iguales ( ). En este caso, tanto A contiene a B como B contiene a A.

Si os acordis del segundo captulo del libro, dedicado funda- mentalmente a definir la Forma Normal Disyuntiva, comenzaba explicando qu era la relacin , y cmo esta relacin menor o igual que defina en un lgebra de Boole una relacin de orden parcial. Pues bien, tratndose de conjuntos, la relacin es contenido por es equivalente a la relacin , y, por tanto, es tambin de orden parcial.

Como consecuencia, slo queda decir que es lo mismo que decir que . O sea, en espaol corriente, que si un conjunto A est contenido en otro conjunto B, entonces la interseccin de A con el complementario de B es el conjunto vaco.

No no pongis caras raras, que es algo evidente. Echad una ojeada al siguiente dibujo (que ya sali hace un par de captulos), y lo entenderis.

Si A est contenido en B, entonces la interseccin de A (la zona azul) con el complementario de B (B, o sea, la zona gris) es el conjunto vaco, pues no comparten ni un solo elemento Fcil.

Bien, pues ya tenemos todo lo que necesitamos para operar con conjuntos. Porque al saber que el lgebra de conjuntos es un lgebra de Boole, sabemos que en la relacin de orden se cumple la propiedad transitiva, es decir, si y , entonces

y eso nos lleva probablemente a entender de una forma nueva (o, bueno, quiz no tan nueva) las implicaciones de la teora de conjuntos

Veamos un ejemplo.

Supongamos que tenemos una serie de afirmaciones que se su- ponen ciertas referidas a un cierto entorno, un pas, pueblo o a toda la humanidad, tanto da:

1 Un hombre que no es feliz no es dueo de s mismo.

2 Todo hombre casado tiene responsabilidades.

3 Todo hombre, o bien est casado o es dueo de s mismo o ambas cosas.

4 Ningn hombre con responsabilidades puede pescar todos los das.

Qu podemos decir de esta comunidad de vecinos, aplicando lo que sabemos de teora de conjuntos y del lgebra de Boole?

En primer lugar, definimos un Conjunto Universal, que engloba a todos los hombres de ese entorno al que se refiere el enun

libro no 463 eso que llamamos lógica macluskey colección e o agosto 10 de 2013

Documents