# Math Help - tautology problem

1. ## tautology problem

Determine weather (not p^(p->q))-> not p.

I don't know where to start. The only way I know is use truth table.

2. Edit: Are you supposed to do this without truth tables?

3. yes. without truth table

4. Check out a Java applet at izyt.com - Boolean Logic: Applet. It not only computes the simplified expression but also lists the steps done.

5. Hello, questionboy!

I made up names for these rules:

. . $\begin{array}{cccc}(p \to q) \;=\;\sim\!p \vee q && \text{ADI} & \text{(Alternate De{f}inition of Implication)}\\ \\

p \:\vee \sim\!p \;=\;T && \text{Rule [1]} \\ \\

T \vee p \;=\;T && \text{Rule [2]} \end{array}$

Tautology? . $\bigg[\sim\!p \wedge (p\to q)\bigg]\;\to\;\sim\! p$

$\begin{array}{ccc}\bigg[\sim\!p \wedge (\sim\!p \vee q)\bigg] \;\to\;\sim\!p && \text{ADI} \\ \\ \sim\bigg[\sim\!p \wedge (\sim\!p\vee q)\bigg] \:\vee\:\sim\!p && \text{ADI} \\ \\ \bigg[p \;\vee \sim(\sim\!p \vee q)\bigg]\:\vee\:\sim\!p && \text{DeMorgan} \end{array}$

$\begin{array}{cccc} p \;\vee \bigg[\sim(\sim\!p \vee q) \;\vee \sim\!p\bigg] && \quad\text{Assoc.} \\ \\
p \;\vee \bigg[\sim\!p \;\vee \sim(\sim\!p \vee q)\bigg] && \quad\text{Comm.} \\ \\ \bigg[p \;\vee \sim\!p\bigg] \;\vee \sim(\sim\!p \vee q) && \quad\text{Assoc.} \\ \\ T \;\vee \sim(\sim\!p \vee q) && \quad\text{Rule [1]} \end{array}$

. . . . . . $\begin{array}{cccc} T & \qquad\qquad\qquad\quad\;\;\text{Rule [2]}\end{array}$

It is a tautology.

6. Hello!

Originally Posted by questionboy
Determine weather (not p^(p->q))-> not p.

I don't know where to start. The only way I know is use truth table.
1) $\neg p\wedge (p\rightarrow q)$...................assumption to start a conditional proof
2) $\neg p$..........................1, by using Conjunction Elimination
3) $[\neg p\wedge (p\rightarrow q)]\rightarrow \neg p$.................1-2, by using the rule of conditional proof

Best wishes,
Seppel