tautology problem

**questionboy** · March 15th 2010, 01:42 PM

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

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

**emakarov** · March 15th 2010, 02:55 PM

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

**questionboy** · March 15th 2010, 05:54 PM

yes. without truth table

**emakarov** · March 16th 2010, 06:30 AM

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

**Soroban** · March 16th 2010, 09:15 AM

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.

**Seppel** · March 17th 2010, 01:43 PM

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

Thread: tautology problem

LinkBack

Thread Tools

Display

tautology problem

Similar Math Help Forum Discussions

tautology

Tautology problem

Having problem with these 2 Tautology? (This is due today at 9am)

Tautology

tautology

Search Tags