• Sep 18th 2008, 02:31 PM
olenka
How to prove that this below argument is valid, using established Rules of reasoning and Logical Equivalences (using vertical statement -reason format.)

{[(¬p ˅ q ) → r ] ˄ [ r →(s v t)] ˄ (¬s ˄ ¬u)˄(¬u → ¬t)}→ p ??????

p.s For those who don't see the symbols I will put this argument in words:
{[( not p v q) --> r] and [r --> (s v t)] and (not s and not u) and ( not u --> not t)} -->p
• Sep 18th 2008, 03:51 PM
hwhelper
Ummm - keep simplifying using
a -> b = !a + b
!(a + b) = !a * !b
!(ab) = !a + !b
where ! means "not", + means "or", and * or multiplication means "and".

To prove that
{[( not p v q) --> r] and [r --> (s v t)] and (not s and not u) and ( not u --> not t)} -->p
= ((!p + q) -> r)(r -> (s+t))(!s)(!u)(!u -> !t)) -> p
= (p(!q)+r)(!r+s+t)(!s)(!u)(u+!t)) -> p
Now (!u)(u+!t) = !u !t
(!r+s+t)(!s)(!t) = !r !s !t
So LHS = (p !q + r)(!r)(!s)(!t)(!u) =
p(!q)(!r)(!s)(!t)(!u)
SO
To prove that
p(!q)(!r)(!s)(!t)(!u) -> p or
!p + q + r + s + t + u + p
which is true since it has !p + p
• Sep 19th 2008, 07:00 AM
triclino
Quote:

Originally Posted by olenka
How to prove that this below argument is valid, using established Rules of reasoning and Logical Equivalences (using vertical statement -reason format.)

{[(¬p ˅ q ) → r ] ˄ [ r →(s v t)] ˄ (¬s ˄ ¬u)˄(¬u → ¬t)}→ p ??????

p.s For those who don't see the symbols I will put this argument in words:
{[( not p v q) --> r] and [r --> (s v t)] and (not s and not u) and ( not u --> not t)} -->p

We want to prove that all the statements logically imply p

We notice that the statement having p is the statement (~pvq)--->r but in the proof that it will follow the way it is written down it will not help us to get p out of it.So through contrapositive law we can convert it to:

........................~r-----> ~(~pvq)..........................................1

Now we convert r---->(svt) by contrapositive law again to:

.........................~(svt)----->~r............................................. .2

we are also given as assumptions :

...........................~u..................... .........................................3

..............................~s.................. ............................................4

From ....~u----> ~t and 3 and using M.Ponens we get :

...............................~t................. ............................................5

From 4 and 5 and using the law of logic called addition introduction we get :

..............................~s^~t............... ..........................................6

From ...6 and using the law called De Morgan we get:

................................~(svt)............ .............................................7

Now from 2 and 7 and using the law called M.Ponens we get:

.................................~r............... ...............................................8

And from 1 and 8 and using again M.Ponens we get :

.........................................~(~pvq )...........................................9

From 9 and using again De Morgan we get :

.........................................p^~ q..............................................10

And finally from 10 and using addition elimination we get :

...........................................p...... ..............................................11

NOTE the above logically implies ~q as well.

The above can be written in amore tabular form, like the following:

1) (~pvq)------>r................................................ ......assumption

2) r----->(svt)............................................ ...............assumption

3) ~s................................................ ........................assumption

4) ~u................................................ .......................assumption

5) ~u------>~t............................................... ...........assumption

6) ~r-----~(~pvq).................................... 1, contra positive

7) ~(svt)------>~r......................................2,contr a positive

8) ~t................................................ .......4,5 M.Ponens

10) ~(svt)............................................ .....9, De Morgan

11) ~r................................................ .......7,10 M.Ponens

12) ~(~pvq)........................................... .....6,11 M.Ponens

13) p^~q.............................................. .....12, De Morgan

The laws use are:

a) contra positive:........(P----->Q) ------>(~Q----->~P) and also (~Q------>~P)-------->(P------>Q)

b) M.Ponens :..........(P----->Q AND P)------>Q

c) De Mrgan...........~(P ^Q) <-------> ~P v ~Q

d) addition introduction ...... P,Q --------> P^Q

THERE may be other shorter or longer proofs the above only shows the way

Also as hwhelper mentioned there can be a Boolean proof by substituting "a---->b" with ~avb.

Finally by the use of true tables there can be a semantical proof in which we must show that:

The conditional:

{[(¬p ˅ q ) → r ] ˄ [ r →(s v t)] ˄ (¬s ˄ ¬u)˄(¬u → ¬t)}→ p

IS A tautology
• Sep 19th 2008, 02:30 PM
olenka
Thank you so much guys ! U R the best!!!!(Clapping)
• Sep 19th 2008, 03:22 PM
Plato
Quote:

Originally Posted by olenka
Thank you so much guys ! U R the best

I for one am not so sure about that. It is not standard.
$\displaystyle \begin{gathered} 1.\,\left( {\neg p \vee q} \right) \to r \hfill \\ 2.\,r \to \left( {s \vee t} \right) \hfill \\ 3.\,\neg s \wedge \neg u \hfill \\ 4.\,\neg u \to \neg t \hfill \\ \therefore \,p \hfill \\ \end{gathered}$

$\displaystyle \begin{gathered} 5.\,\left( {\neg p \vee q} \right) \to \left( {s \vee t} \right)\;\left[ {1\,\& \,2} \right] \hfill \\ 6.\,\neg u\;\left[ 3 \right] \hfill \\ 7.\,\neg t\;\left[ 4 ,\& \,6\right] \hfill \\ 8.\,\neg s\;\left[ 3 \right] \hfill \\ 9.\,\neg s \wedge \neg t\left[ {7\,\& \,8} \right] \hfill \\ \end{gathered}$
$\displaystyle \begin{gathered} 10.\,\neg \left( {s \vee t} \right)\left[ 9 \right] \hfill \\ 11.\,\neg \left( {\neg p \vee q} \right)\left[ {10\,\& \,5} \right] \hfill \\ 12.\,p \wedge \neg q\left[ {11} \right] \hfill \\ \therefore \,p\left[ {12} \right] \hfill \\ \end{gathered}$

I will leave it to you to supply the reasons by name. Names of the rules differ from text to text and author to author. That is the reason I don’t trust what you have handed. I have taught this material for years in North America. I can tell you that I got confused each time we changed textbooks.
Notations and rules names are simply not standard.

However, the layout of the proof that I have given you is fairly standard.
• Sep 19th 2008, 04:19 PM
triclino
Here is ashorter proof by contradiction:

Let assume ~p and start a contradiction,then by the law called disjunction introduction we have :

...........................~pvq................... ...........................................1

from the assumption ~pvq----> r and 1 and using M.Ponens we get:

...................................r.............. ................................................2

from the assumption r----->(svt) and 2 and using M.Ponens we get :

.........................................(svt).... ..............................................3

from the assumptions ~u------>~t and ~u and using M.Ponens we get:

...............................................~t. ...............................................4

from the assumption ~s and 4 and using addition introduction we get:

.......................................~s^~t...... ...........................................5

from 5 and using De MORGAN we get :

.....................................~(svt)....... ...........................................6

from 3 and 6 and using addition introduction we get :

....................................(svt) and ~(svt)......................................7

HENCE .........................P........................ ..................................
• Sep 19th 2008, 04:47 PM
triclino
Quote:

Originally Posted by Plato
I for one am not so sure about that. It is not standard.
$\displaystyle \begin{gathered} 1.\,\left( {\neg p \vee q} \right) \to r \hfill \\ 2.\,r \to \left( {s \vee t} \right) \hfill \\ 3.\,\neg s \wedge \neg u \hfill \\ 4.\,\neg u \to \neg t \hfill \\ \therefore \,p \hfill \\ \end{gathered}$

$\displaystyle \begin{gathered} 5.\,\left( {\neg p \vee q} \right) \to \left( {s \vee t} \right)\;\left[ {1\,\& \,2} \right] \hfill \\ 6.\,\neg u\;\left[ 3 \right] \hfill \\ 7.\,\neg t\;\left[ 4 ,\& \,6\right] \hfill \\ 8.\,\neg s\;\left[ 3 \right] \hfill \\ 9.\,\neg s \wedge \neg t\left[ {7\,\& \,8} \right] \hfill \\ \end{gathered}$
$\displaystyle \begin{gathered} 10.\,\neg \left( {s \vee t} \right)\left[ 9 \right] \hfill \\ 11.\,\neg \left( {\neg p \vee q} \right)\left[ {10\,\& \,5} \right] \hfill \\ 12.\,p \wedge \neg q\left[ {11} \right] \hfill \\ \therefore \,p\left[ {12} \right] \hfill \\ \end{gathered}$

I will leave it to you to supply the reasons by name. Names of the rules differ from text to text and author to author. That is the reason I don’t trust what you have handed. I have taught this material for years in North America. I can tell you that I got confused each time we changed textbooks.
Notations and rules names are simply not standard.

However, the layout of the proof that I have given you is fairly standard.

The names may vary from book to book but the structure of the law is still the same .

for addition elimination for example you can write Q^P------> P e.t.c ,e.tc

And since you taught logic i suppose you will be able to give us a stepwise proof like the above where the laws of logic are explicitly mentioned of the following:

$\displaystyle \forall x$$\displaystyle \forall y( x\displaystyle \geq 0 and y\displaystyle \geq 0-------->\displaystyle \sqrt{xy}=\displaystyle \sqrt{x}$$\displaystyle \sqrt{y}$)

Also any theorems axioms definitions involved i.e justification of each step

......................................here and now............................................... .........................
• Sep 19th 2008, 05:26 PM
triclino
Quote:

Originally Posted by Plato
That is the reason I don’t trust what you have handed. .

IN propositional calculus you check each and every exercise if it s provable by using the true tables.

If the exercise is a TAUTOLOGY then it is provable.

Propositional calculus is

........................................ a DECIDABLE THEORY......................................

SO if youdo not trust what she handed out simply go to the true tables and see if what she handed out is a Tautology or not.
• Sep 19th 2008, 05:38 PM
Plato
Triclino, If you had any idea of what is really going on here, I would take offence at your response.
But the fact is, you know so little about what you are talking about it is not worth the time a logician to response to your elementary errors.
While I applaud your efforts to understand the basics of logical arguments, I must tell you that your limited experience in this area can be a real determent to those who hope to learn from your posts. Actually your own confusion is a determent to the understanding you hope to contribute by your postings.
• Sep 19th 2008, 07:41 PM
Soroban
Hello, olenka!

I forgot the name of this rule: .$\displaystyle \bigg[(p \vee q) \wedge (\sim p)\bigg] \to q$
. . I'll call it "Detchment", okay?

Quote:

How to prove that this below argument is valid,
using established Rules of reasoning and Logical Equivalences
(using vertical statement - reason format.)

$\displaystyle \bigg\{ [(\sim p \vee q) \to r] \wedge [r \to (s \vee t)] \wedge (\sim s \wedge \sim u) \wedge (\sim u \to \sim t)\bigg\} \:\to\:p$

On the left side, we have:

. . $\displaystyle \bigg[(\sim p \vee q) \to r\bigg] \wedge \bigg[r \to (s \vee t)\bigg] \wedge (\sim s) \wedge (\sim u) \wedge \bigg[(\sim u) \to (\sim t)\bigg] \qquad\text{Given}$

. . $\displaystyle \bigg[\sim(\sim p \;\vee\; q) \;\vee\; r\bigg] \wedge \bigg[\sim r \;\vee (s \;\vee \;t)\bigg] \wedge \;(\sim s)\; \wedge\; (\sim u) \wedge\; \bigg[u \vee \sim t\bigg] \qquad \text{Equiv. of impl'n}$

. . $\displaystyle \bigg[(p \wedge \sim q) \vee r\bigg] \wedge \bigg[\sim r \vee(s \vee t)\bigg] \wedge (\sim s) \wedge (\sim u) \wedge \bigg[u \vee \sim t\bigg] \qquad \text{DeMorgan}$

. . $\displaystyle \bigg[r \vee (p \wedge \sim q)\bigg] \wedge \bigg[(s \vee t) \vee \sim r \bigg] \wedge (\sim s) \wedge \underbrace{(\sim u) \wedge \bigg[u \vee \sim t\bigg]} \qquad \text{Commutative}$
. . $\displaystyle \bigg[r \vee (p \wedge \sim q)\bigg] \wedge \bigg[(s \vee t) \vee \sim r\bigg] \wedge (\sim s)\quad \wedge\quad (\sim t)\qquad \text{Detachment}$

. . $\displaystyle \bigg[r \vee (p \vee \sim q)\bigg] \wedge \underbrace{\bigg[\sim(\sim s \wedge \sim t) \vee \sim r\bigg] \wedge \bigg[\sim s \wedge \sim t\bigg]} \qquad\text{ DeMorgan}$

. . . . . . $\displaystyle \underbrace{\bigg[r \vee (p\; \wedge \sim q)\bigg] \qquad\wedge \qquad \sim r} \qquad\qquad\text{ Detachment}$

. . . . . . . . . . . . . $\displaystyle p\; \wedge \sim q\qquad\qquad\text{ Detachment}$

And: .$\displaystyle (p \:\wedge \sim q) \to p\quad\hdots$ . Forgot the name of this rule, too

• Sep 21st 2008, 08:03 PM
olenka
Thanks to all of you for your effort(Rofl)(Clapping)t!!!!!!!