# Discrete Math: Compound Propostions

So this is another practice problem I have for discrete math, this time involving compound propositions, with the book my campus uses is Discrete Mathematics with Applications, 7th Edition by Ken Rosen. The problem goes "Let p and q be two given propositions. Use equivalence laws shown in Table 6 and example 3 of section 1.3 to simplify compound propostion $\lnot [p \land (p \to q)]$. Indicate what law(s) you are using in each step."

After trying it on my own, here's what I came up with:

$$\lnot[p \land \lnot(\lnot p \lor \lnot q)]$$ $$\lnot [p \land \lnot(p \land q)]$$ $$\lnot p \lor \lnot [\lnot(p \land q)]$$ $$\lnot p \lor p \land q$$ $$(\lnot p \lor p)\land(\lnot p \lor q)$$ $$T \land(\lnot p \lor q)$$ $$\lnot p \lor q$$

Is this even close to accurate?

• In the first step you have misapplied De Morgan : $\lnot(\lnot p \lor \lnot q)$ is $(p \land q)$. Jan 6, 2017 at 8:12

$\neg[p\land (p\rightarrow q)]\equiv \neg[p\land (\neg p\vee q)] \ \$(by the definition of $p\rightarrow q$)$\ \ \equiv [\neg p \vee\neg(\neg p\vee q)] \ \$(DeMorgan's Law) $\ \ \equiv [\neg p\vee (p\land \neg q)]\equiv (\neg p\vee p)\land (\neg p\vee \neg q))\equiv \neg(p\land q)$ (by the distributivity property.)

where I am also using the fact that $\neg p\vee p$ is a tautology.

It's close, but the first two steps are wrong. $p\to q$ is equivalent to $\neg(p\wedge\neg q)$, not $\neg(p\wedge q)$. (The first two lines aren't consistent either since $\neg(\neg p\vee\neg q)$ simplifies to $(p\wedge q)$.)

$p\wedge(p\rightarrow q)\equiv p\wedge(\neg p \vee q) \equiv (p \wedge \neg p) \vee (p\wedge q) \equiv (p \wedge q)$

Hence,$\neg\left(p\wedge(p\rightarrow q)\right)\equiv \neg(p \wedge q)$