# tautology problem

• Mar 15th 2010, 01:42 PM
questionboy
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.
• Mar 15th 2010, 02:55 PM
emakarov
Edit: Are you supposed to do this without truth tables?
• Mar 15th 2010, 05:54 PM
questionboy
yes. without truth table
• Mar 16th 2010, 06:30 AM
emakarov
Check out a Java applet at izyt.com - Boolean Logic: Applet. It not only computes the simplified expression but also lists the steps done.
• Mar 16th 2010, 09:15 AM
Soroban
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}$

Quote:

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.

• Mar 17th 2010, 01:43 PM
Seppel
Hello!

Quote:

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