Leyes booleanas

CLASE XVIII. Leyes Booleanas-Simplificación de formulas

Las álgebras booleanas, estudiadas por primera vez en detalle por George Boole constituyen un área de las matemáticas que ha pasado a ocupar un lugar prominente con el advenimiento de la computadora digital. Son usadas ampliamente en el diseño de circuitos de distribución y computadoras, y sus aplicaciones van en aumento en muchas otrasáreas. En el nivel de lógica digital de una computadora, lo que comúnmente se llama hardware, y que está formado por los componentes electrónicos de la máquina, se trabaja con diferencias de tensión, las cuales generan funciones que son calculadas por los circuitos que forman el nivel. Éstas funciones, en la etapa de diseña del hardware, son interpretadas como funciones de boole.
Teoremas básicosde Ss: Leyes Booleanas.
A través de estas leyes se puede simplificar una formula del Lenguaje Ss llevándola a una mínima expresión y de esta forma poder realizar una derivación mas simple, estas leyes también son utilizadas en conjuntos y algebra.
Las leyes booleanas establecen cuando dos proposiciones son equivalentes. Se dice que dos proposiciones P y Q son equivalentes si la tabla de verdadde P ↔ Q es uma tautologia.
A continuación se enuncia algunas de las más importantes leyes booleanas:
a) Conmutativa (Conm): permite cambiar de posiciones a las subformulas
p & q ↔ q & p
p v q ↔ q v p

b) Asociativa (As): permite reagrupar subformulas
p & ( q & r ) ↔ ( p & q ) & r
p v ( q v r ) ↔ ( p v q ) v rDEMOSTRACIÓN

1 p & ( q & r ) H
2 p 1 EC
3 q & r 1 EC
4 q 3 EC
5 r 3 EC
6 p & q 2,4 IC
7 ( p & q ) & r 5,6 IC

8 ( p & q ) & r H
9 p & q 8 EC
10 p 9 EC11 q 9 EC
12 r 8 EC
13 q & r 11,12 IC
14 p & ( q & r ) 10,13 IC Por lo tanto A es un teorema

15 p & ( q & r ) ↔ ( p & q ) & r 1,7,8,14 IE

c) Distributivas (Dist): permite simplificar una formula dederecha a izquierda y transformarla de izquierda a derecha
p & ( q v r ) ↔ ( p & q ) v ( p & r )
p v ( q & r ) ↔ ( p v q ) & ( p v r )
d) Idempotencia (Idem): permite absorver una formula cuando existen dos iguales
p v p ↔ p
p & p ↔ p
De absorción (Abs): SIMPLIFICA
p & ( p v q ) ↔ pp v ( p & q ) ↔ p
DEMOSTRACION
U ={1,2,3,4,5}, P ={1,2,3} y Q ={4,5}
P ( ( P ( Q) ↔ P
{1,2,3} ( ({1,2,3}( {4,5} ) ↔ {1,2,3}
{1,2,3} ( U ↔ {1,2,3}
{1,2,3} ( {1,2,3,4,5} ↔ {1,2,3}
{1,2,3} ↔ {1,2,3}

e) De de Morgan (DeM): TRANSFORMA
( ( p & q ) ↔ ( p v ( q
( ( p v q ) ↔ ( p & ( q

f)Traducción de La equivalencia (TE) SIMPLIFICA
( p -> q ) & ( q -> p ) ↔ ( p ↔ q)
( p ↔ q ) ↔ (( p & q ) v (( p & ( q ))
g) Negación de la implicación (NI) ( ( p -> q ) ↔ p & ( q
h) Traducción de la implicación (TI) ( p -> q ) ↔ ( p v q
i) Involución ( ( p ↔ p
j) Contrareciproca (CR): ( p -> q ) ↔ (( q -> ( p )
k) Negación de la dobleimplicación (NI) ( ( p ↔ q ) ↔ ( p ↔ ( q )
( ( p ↔ q ) ↔ (( p ↔ q )

l) Ley Inversa (F) p & ( p ↔ F
m) Ley de la Verdad (V) p v ( p ↔ V
n) Ley de Identidad:
p v F = p
p & V = p
o) Ley de exportación-importación (LEI):
(p -> (q -> r )) ↔ ( p & q -> r)
p) Leyes de...