Simplificación de fórmulas lógicas

Leyes utilizadas

Se aplican principalmente la doble negación, De Morgan, identidad, dominación, complemento, absorción, distributiva, conmutativa, asociativa, equivalencia de la implicación y definición de la bicondicional.

a) \begin{aligned} \neg[(p\to q)\land\neg(p\lor\neg q)] &=\neg[(\neg p\lor q)\land(\neg p\land q)]\\ &=\neg(\neg p\land q)\\ &=p\lor\neg q. \end{aligned}

b) \begin{aligned} [(p\to q)\lor(q\to p)]\land\neg p &=[(\neg p\lor q)\lor(\neg q\lor p)]\land\neg p\\ &=V\land\neg p\\ &=\neg p. \end{aligned}

c) \begin{aligned} (p\to\neg q)\lor(\neg q\lor p) &=(\neg p\lor\neg q)\lor(\neg q\lor p)\\ &=(\neg p\lor p)\lor\neg q\\ &=V. \end{aligned}

d) \begin{aligned} \neg[\neg(p\land q)\land\neg q]\leftrightarrow p &=\neg[(\neg p\lor\neg q)\land\neg q]\leftrightarrow p\\ &=\neg(\neg q)\leftrightarrow p\\ &=q\leftrightarrow p. \end{aligned}

e) \begin{aligned} [(p\to q)\land p]\lor(\neg q\to\neg p) &=[(\neg p\lor q)\land p]\lor(q\lor\neg p)\\ &=(p\land q)\lor q\lor\neg p\\ &=q\lor\neg p. \end{aligned}

f) \begin{aligned} [(p\lor\neg q)\land q]\to p &=(p\land q)\to p\\ &=\neg(p\land q)\lor p\\ &=(\neg p\lor\neg q)\lor p\\ &=V. \end{aligned}

g) \begin{aligned} \neg[\neg(p\land q)\to\neg q]\lor q &=\neg[(p\land q)\lor\neg q]\lor q\\ &=\neg(p\lor\neg q)\lor q\\ &=(\neg p\land q)\lor q\\ &=q. \end{aligned}

h) \begin{aligned} \neg[(\neg p\to q)\leftrightarrow\neg p] &=\neg[(p\lor q)\leftrightarrow\neg p]\\ &=\neg(\neg p\land q)\\ &=p\lor\neg q. \end{aligned}

a) Doble negación.

b) Identidad.

c) Distributiva de la conjunción respecto de la disyunción.

d) Complemento o tercero excluido: q\lor\neg q=V.

e) Definición de la implicación: p\to q\equiv\neg p\lor q.

f) Asociativa de la disyunción.

g) Conmutativa y asociativa de la disyunción.

h) Absorción: p\lor(p\land q)=p; luego, identidad de la conjunción.

Aplicando las leyes proposicionales:

\begin{aligned} a)&\quad\neg\neg p\equiv p\\ b)&\quad\neg(p\land\neg q)\equiv\neg p\lor q\\ c)&\quad\neg(\neg p\lor q)\equiv p\land\neg q\\ d)&\quad\neg(\neg p\land\neg q)\equiv p\lor q\\ e)&\quad[p\land(q\land F)]\lor(r\lor V)\equiv V\\ f)&\quad p\land[(q\land F)\lor(r\lor V)]\equiv p\\ g)&\quad p\land(p\to F)\equiv F\\ h)&\quad p\land(p\to V)\equiv p\\ i)&\quad\neg(p\land q)\lor(p\to q)\equiv V\\ j)&\quad\neg(p\lor q)\land(p\lor q)\equiv F\\ k)&\quad(\neg p\lor\neg q)\lor(p\land q)\equiv V\\ l)&\quad\neg(p\lor q)\lor\neg(\neg p\land\neg q)\equiv V. \end{aligned}

Las leyes aplicadas en cada paso son:

1. Definición de la bicondicional: A\leftrightarrow B\equiv(A\to B)\land(B\to A).
2. Definición de la implicación: A\to B\equiv\neg A\lor B.
3. De Morgan para la negación de una conjunción: \neg(A\land B)\equiv\neg A\lor\neg B.
4. De Morgan y doble negación: \neg(q\lor\neg p)\equiv\neg q\land p y \neg\neg p\equiv p.
5. Absorción: p\lor(p\land q)\equiv p.
6. Idempotencia: \neg p\lor\neg p\equiv\neg p.
7. De Morgan: \neg(\neg p\lor q)\equiv p\land\neg q.
8. Distributiva: \neg p\lor(p\land\neg q)\equiv(\neg p\lor p)\land(\neg p\lor\neg q).
9. Complemento y dominación: (\neg p\lor p)\land(\neg p\lor\neg q)\equiv V\land(\neg p\lor\neg q).
10. Identidad: V\land(\neg p\lor\neg q)\equiv\neg p\lor\neg q.

a) \begin{aligned} (p\lor p)\land(\neg p\lor q\lor q) &=p\land(\neg p\lor q)\\ &=(p\land\neg p)\lor(p\land q)\\ &=p\land q. \end{aligned}

b) \begin{aligned} (\neg p\land q)\land[(p\lor q)\lor p] &=(\neg p\land q)\land(p\lor q)\\ &=[(\neg p\land q)\land p]\lor[(\neg p\land q)\land q]\\ &=F\lor(\neg p\land q)\\ &=\neg p\land q. \end{aligned}

El símbolo \downarrow representa la operación NOR: p\downarrow q\equiv\neg(p\lor q).

Entonces: \begin{aligned} [(p\downarrow q)\lor\neg q]\lor\neg q &=[\neg(p\lor q)\lor\neg q]\lor\neg q\\ &=[(\neg p\land\neg q)\lor\neg q]\lor\neg q\\ &=\neg q. \end{aligned}