Proof for Tautologies uisng equations

Hi all,

I looking for some explanation on how to prove a equation a tautolgies. I can quite easl do this using turth table. But when i try to do this using equation i get a bit stuck.

So for example if i had a problem like as follow

(r ⇒ (p ∧ q)) ⇔ ((r ⇒ p) ∧ (r ⇒ q))

I know this is not tautology but what am i suppose to prove to be tautoloy. Should the end verdict be

(r ⇒ (p ∧ q)) ⇔ ((r ⇒ p) ∧ (r ⇒ q)) <-> TRUE.

Is this is what am i need to show using rule of inference? Please point me to the right direction.

thanks

ssharish

Re: Proof for Tautologies uisng equations

Since (r ⇒ (p ∧ q)) ⇔ ((r ⇒ p) ∧ (r ⇒ q)) is a biconditional (i.e., equivalence), one way is to rewrite (r ⇒ (p ∧ q)) until you get ((r ⇒ p) ∧ (r ⇒ q)), or vice versa. This is because A ⇔ A is a tautology for any formula A. Alternatively, which also works not only for biconditionals, you can rewrite the formula until you get TRUE.

Re: Proof for Tautologies uisng equations

Hey many thanks for the reply. So what your saying is, if take the LHS of the expression and try work my way through until i get to RHS using rule of inference I should prove that the whole expression is tautology as A<=>B is nothing but tautology?

I also understand your senond approch and I quite find it hard to prove until i get true, for such a huge expression. It might take few pages before i can prove the whole expression is TRUE? Isn't it?

Thanks very much

ssharish

Re: Proof for Tautologies uisng equations

If you rewrite the left-hand side so that it coincides with the right-hand side, you have A ⇔ A, and

(A ⇔ A) ⇔

(A ⇒ A) ∧ (A ⇒ A) ⇔

(¬A ∨ A) ∧ (¬A ∨ A) ⇔

TRUE ∧ TRUE ⇔

TRUE

Re: Proof for Tautologies uisng equations

Hey thanks very much for that. And can you also clarify is this is true. If I do the following?

( (P ^ Q) => (P ^ R) )

<=> ( ¬(P ^ Q) v (P ^ R) )

<=> ( ¬(P ^ (Q v R) ) << Can I do this using associative?

<=> ( ¬p v ¬(Q v R)

Thanks

Harish

Re: Proof for Tautologies uisng equations

Quote:

Originally Posted by

**ssharish** <=> ( ¬(P ^ Q) v (P ^ R) )

<=> ( ¬(P ^ (Q v R) ) << Can I do this using associative?

No, because P ∧ Q is under negation. This is equivalent to ¬P v ¬Q v (P ∧ R).

You can use LaTeX, e.g., [TEX]\neg P\lor\neg Q\lor (P\land Q)[/TEX] gives $\displaystyle \neg P\lor\neg Q\lor (P\land Q)$, but be sure to use [TEX] and not [tex] tags. Above the edit text box, this is the second icon with the emblem $\displaystyle \TeX$.

Re: Proof for Tautologies uisng equations

Hey thanks very emakarov and i'm sorry about the post on not using latex i'm still a newbie and trying to lean. I understand your approch and I hence i asked if i was doing that right. If that is the case I feel like i'm stuck a bit. So for exaple

( ( A ^ B ) => ( A ^ C ) <=> ( ( A ^ B ) => C )

> ( ¬( A ^ B ) v ( A ^ C ) )

> ( ¬A v ¬B v ( A ^ C ) ) << I'm actually bit stuck here and i'm no where near to proofing its <=>

Do you suggest using an associative rule on ¬B v (A ^ C) or anything esle?

Thanks very much!

ssharish

Re: Proof for Tautologies uisng equations

ok i got this now

$\displaystyle \\((A \land B) \Rightarrow (A \land C)) \Longleftrightarrow ((A \land B) \Rightarrow C)\\\Longleftrightarrow \neg(A \land B) \lor (A \land C)\\\Longleftrightarrow \neg A \lor \neg B \lor (A \land C)\\\Longleftrightarrow \neg A \lor (\neg B \lor A) \land (\neg B \lor C)\\\Longleftrightarrow (\neg A \lor (\neg B \lor A)) \land (\neg A \lor (\neg B \lor C))\\\Longleftrightarrow (\neg A \lor\neg B \lor A) \land (\neg A \lor\neg B \lor C)\\\Longleftrightarrow (\neg A \lor A \lor\neg B) \land (\neg A \lor\neg B \lor C)\\\Longleftrightarrow (\mbox{True} \lor\neg B) \land (\neg A \lor\neg B \lor C)\\\Longleftrightarrow \mbox{True} \land ((\neg A \lor\neg B) \lor C)\\\Longleftrightarrow ((\neg A \lor\neg B) \lor C)\\\Longleftrightarrow \neg(A \land B) \lor C\\\Longleftrightarrow (A \land B) \Rightarrow C\\ $

Do you think my approch is right?

Thanks

ssharish

Re: Proof for Tautologies uisng equations

Hello, ssharish!

Quote:

$\displaystyle [r \to (p \wedge q)]\;\Longleftrightarrow\:[(r \to p) \wedge (r \to q)]$

. . $\displaystyle \begin{array}{cccccccccc} &\text{Left side} &&& \\ \hline 1. & r \to (p \wedge q) && 1. & \text{Given} \\ 2. & \sim\!r \vee (p \wedge q) && 2. & \text{Def. impl'n} \\ \\ \end{array} \quad\begin{array}{ccccccc}&\text{Right side} & & & \\ \hline 1. & (r\to p) \wedge (r \to q) && 1. & \text{Given} \\ 2. & (\sim\!r \vee p) \wedge (\sim\!r \vee q) && 2. & \text{Def. impl'n} \\ 3. & \sim\!r \vee (p \wedge q) && 3. & \text{Distr.} \end{array}$

Re: Proof for Tautologies uisng equations

Quote:

Originally Posted by

**ssharish** Do you think my approch is right?

Yes. It would be easier to read if you omit some parentheses, in particular, those in $\displaystyle \neg(B)$ and in $\displaystyle A\lor(B\lor C)$ (since disjunction is associative).

Re: Proof for Tautologies uisng equations

Hey thanks very much for Emakarov and Soroban, I've made the changes as per lex to look better now. Whats do you think of my reasoing now?

$\displaystyle \\((A \land B) \Rightarrow (A \land C)) \Longleftrightarrow ((A \land B) \Rightarrow C)\\\Longleftrightarrow \neg(A \land B) \lor (A \land C)\\\Longleftrightarrow \neg A \lor \neg B \lor (A \land C)\\\Longleftrightarrow \neg A \lor (\neg B \lor A) \land (\neg B \lor C)\\\Longleftrightarrow (\neg A \lor (\neg B \lor A)) \land (\neg A \lor (\neg B \lor C))\\\Longleftrightarrow (\neg A \lor\neg B \lor A) \land (\neg A \lor\neg B \lor C)\\\Longleftrightarrow (\neg A \lor A \lor\neg B) \land (\neg A \lor\neg B \lor C)\\\Longleftrightarrow (\mbox{True} \lor\neg B) \land (\neg A \lor\neg B \lor C)\\\Longleftrightarrow \mbox{True} \land ((\neg A \lor\neg B) \lor C)\\\Longleftrightarrow ((\neg A \lor\neg B) \lor C)\\\Longleftrightarrow \neg(A \land B) \lor C\\\Longleftrightarrow (A \land B) \Rightarrow C\\ $

I'm more quite interested in Step 2 and 3 as i wanted to make sure if I'm using assosiative at the right place and in a right way?

Thanks a lot for all your guidence.

ssharish

Re: Proof for Tautologies uisng equations

Do you mean associativity or distributivity? If the former, then the third and fourth line should be

$\displaystyle (\neg A\lor\neg B)\lor(A\land C)$

$\displaystyle \Leftrightarrow\neg A\lor(\neg B\lor(A\land C))$

However, I think it is better to omit associativity and commutativity steps; otherwise, derivations would be too long.

I would also make clear that you are rewriting the left-hand side. Currently, the relation between the first and second line is not absolutely clear.

All this are minor quibbles. Your derivation looks pretty good.

Re: Proof for Tautologies uisng equations

Thanks emakarov, sorry i meant associativity there. Perhaps the associativity and distributivity means the same aren't they? But from your expression I see that you put few extra brackets to make things clear which kind of make sense.

Although I’m not quite sure what you mean in the second statement though. Do you mean that I got to show I'm taking the LHS expression to derive the RHS expression? How could i explicitly show that? In addition I’m also gonna show the inference rule used at the each step to make things clear :) Didn’t know how to do that using LeTex apart from using \mbox{...}

Thanks

ssharish

Re: Proof for Tautologies uisng equations

Quote:

Originally Posted by

**ssharish** Perhaps the associativity and distributivity means the same aren't they?

No, associativity is $\displaystyle (A\lor B)\lor C\Leftrightarrow A\lor(B\lor C)$, and distributivity is $\displaystyle A\lor(B\land C)\Leftrightarrow(A\lor B)\land(A\lor C)$.

Quote:

Originally Posted by

**ssharish** Although I’m not quite sure what you mean in the second statement though. Do you mean that I got to show I'm taking the LHS expression to derive the RHS expression?

Yes. Currently, the first line has two formulas connected by $\displaystyle \Leftrightarrow$. The formula on next line is claimed to be derived from one these two (left or right) by some equivalence, but it is not clear whether you rewrite the left- or right-hand side, or maybe the whole equivalence, on the first line. You could start with the left-hand side only and gradually rewrite it until you get to the right-hand side, or you could explain your intentions with words.