Proving equivalences

Question

Here I have a proposition:

((¬p ∨ x) ∧ (p ∨ y)) → (x ∨ y)

I am proving that it's a tautology but I wanted to know if what I am doing is correct. I'm just learning equivalences, I have tried to type it out as neatly as possible. Please give feedback toward what step are wrong or if there are simpler ways to prove this eq. Yes it took about two hours for me to get this posted.

≡ ¬[((¬p ∨ x) ∧ (p ∨ y))] ∨ (x ∨ y) implication equivalence

≡ (¬(¬p ∨ x) ∨ ¬(p ∨ y)) ∨ (x ∨ y) DeMorgans

≡ (p ∧ ¬x) ∨ (¬p ∧ ¬y) ∨ (x ∨ y) DeMorgans

≡ [(p ∨ (¬p ∧ ¬y)) ∧ (¬x ∨ (¬p ∧ ¬y))] ∨ (x ∨ y) Distributivity

≡ [(p ∨ ¬p) ∧ (p ∨ ¬y) ∧ (¬x ∨ ¬p) ∧ (¬x ∨ ¬y)] ∨ (x ∨ y) Distributivity

≡ [ T ∧ (p ∨ ¬y) ∧ (¬x ∨ ¬p) ∧ (¬x ∨ ¬y)] ∨ (x ∨ y) Distributivity

≡ [ T ∧ (p ∨ ¬y) ∧ (¬x ∨ ¬p) ∧ (¬x ∨ x)] ∨ (¬y ∨ y) Associativity

≡ [ T ∧ (p ∧ (¬x ∨ ¬p)) ∨ (¬y ∧ (¬x ∨ ¬p))] ∧ T ∨ T Distributivity

≡ [ T ∧ (p ∧ ¬x) ∨ T ∨ (¬y ∧ x) ∨ (¬y ∨ ¬p)] ∧ T Distributivity and Negation law and Idempotent

What do can I do with all these "T"'s in my equation? I'm just going to try to eliminate them.

≡ [(T ∧ T) ∨ (p ∧ ¬x) ∨ (¬y ∧ x) ∨ (¬y ∨ ¬p)] ∧ T Commutative

≡ [T ∨ (p ∧ ¬x) ∨ (¬y ∧ x) ∨ (¬y ∨ ¬p)] ∧ T Idempotent

≡ [T ∨ (p ∨ (¬y ∧ ¬x)) ∧ (¬x ∨ (¬y ∧ ¬x)) ∨ (¬y ∨ ¬p)] ∧ T Distributivity

≡ [T ∨ [(p ∨ ¬y) ∧ (p ∨ ¬x)] ∧ [(¬x ∨ ¬x) ∧ (¬x ∨ ¬y)] ∨ (¬y ∨ ¬p)] ∧ T Distributivity and Commutative

≡ [T ∨ (p ∨ ¬y) ∧ (p ∨ ¬x) ∧ T ∧ (¬x ∨ ¬y) ∧ (¬y ∨ ¬p)] ∧ T Associativity and negation law

≡ [T ∨ (p ∨ ¬y) ∧ (p ∨ ¬x) ∧ T ∧ (¬x ∨ ¬p) ∧ (¬y ∨ ¬y)] ∧ T Associativity

≡ [T ∨ (p ∨ ¬y) ∧ (p ∨ ¬x) ∧ T ∧ (¬x ∨ ¬p)] ∧ T Negation and Idempotent

≡ T ∨ (p ∨ ¬y) ∧ (p ∨ ¬x) ∧ (¬x ∨ ¬p) ∧ T ∧ T Associativity (for the T value)

≡ T ∨ (p ∨ ¬y) ∧ (p ∨ ¬x) ∧ (¬x ∨ ¬p) ∧ T Idempotent

≡ [T ∨ (p ∨ ¬y)] ∧ (¬x ∨ ¬p) ∧ (¬x ∨ p) ∧ T Associativity

≡ [T ∨ p ∨ ¬y] ∧ (¬x ∨ ¬p) ∧ (¬x ∨ p) ∧ T Associativity

≡ [(T ∨ ¬y) ∨ p] ∧ (¬x ∨ ¬p) ∧ (¬x ∨ p) ∧ T Associativity

≡ [T ∨ p] ∧ (¬x ∨ ¬p) ∧ (¬x ∨ p) ∧ T Domination

≡ T ∧ (¬x ∨ ¬p) ∧ (¬x ∨ p) ∧ T Domination

≡ T ∧ T ∧ (¬x ∨ ¬p) ∧ (¬x ∨ p) Associativity

≡ T ∧ (¬x ∨ ¬p) ∧ (¬x ∨ p) Idempotent

≡ T ∧ (¬x ∨ (¬p ∧ p)) Distributivity

≡ T ∧ (¬x ∨ F) Negation

≡ T ∧ ¬x Identity

≡ ¬x Identity

Great. The wrong answer.

I didn't read it, but at some point you wrote something like $P\lor Q \land R$ and this is senseless due to lack of parentheses. Needs fixing. — Git Gud, Sep 18 '13 at 18:25
Ok, so it was near the end, where I tried to switch somethings around, but did not work. — GivenPie, Sep 18 '13 at 18:52
Still not good, your last few lines look like this: $$T\color{red}\lor \text{ something } \land \text{ something } \land \text{ something }\land T $$ — Git Gud, Sep 18 '13 at 18:57
That would be way easier, if substitute \begin{align} T &\to 1 \ F &\to 0 \ \wedge &\to ,\cdot \ \vee &\to + \ \neg &\to \ ^\overline{} \end{align} — Kaster, Sep 18 '13 at 19:05
I've made some changes, hopefully correct. Does (¬x ∨ F) = false? If it does, I've definably done this whole problem incorrectly. @Kaster, I will know for next time to use those simple notations. — GivenPie, Sep 18 '13 at 19:11
Same as comments above, around your first "Associativity", you miss brackets — peterwhy, Sep 18 '13 at 19:17
@peterwhy Right, so the Identity rule. My error should have come from that missing brackets, you think? — GivenPie, Sep 18 '13 at 19:18
Now, you have added brackets there. Can you see you have applied associativity wrongly now? — peterwhy, Sep 18 '13 at 19:23
@peterwhy Let me confirm with you that it's this line ≡ [ T ∧ (p ∨ ¬y) ∧ (¬x ∨ ¬p) ∧ (¬x ∨ x)] ∨ (¬y ∨ y) Associativity that is the place I used associativity incorrectly. — GivenPie, Sep 18 '13 at 19:25
the last line is $F$ is you substitute $T$ for the vatriable $x$ (and for arbitrary values of $p$ and $y$). The term you are starting with is $T$ for if you substitute $x$ by $T$ ((and for arbitrary values of $p$ and $y$). So set $x=T$ and $y=F$ and $p=F$ ($y$ and $p$ can be seleceted arbitrary) and substitute them in the lines of your proof. You will find one that evaluates to $T$ and its successor evaluates to $F$. Then you know there must be an error in transforming the $T$-line to the successing $F$-line and you can search for the error. — miracle173, Sep 18 '13 at 19:40
I prefer parantheses to brackets. If you have a constatnt $T$ or $F$ you can immediately get rid of it. Example:
$( T ∧ (p ∨ ¬y) ∧ \ldots) $ you can use associativity to get $( (T ∧ (p ∨ ¬y) )∧ \ldots)$ but now $T ∧ (p ∨ ¬y)$ is $(p ∨ ¬y)$ by the law of idendity and your expression is simplified to $((p ∨ ¬y) ∧ \ldots$). In a similiar way the $( (T ∨ (p ∧ ¬y) )∨ \ldots)$ can be simplified to $ T ∨ \ldots)$ which can simplifid further until the constant has vanished. Analogous laws alre valid for $F$. — miracle173, Sep 18 '13 at 19:57

miracle173 · Accepted Answer · 2013-09-18T21:45:16.340

There are different methods to solve this problem from propositional logic. One should use always use paranthese to avoid expressions like

$$a \lor b \land c$$

Does this mean

$$(a \lor b) \land c$$ because $\lor$ has higher precedence than $\land$ or because they have euqal precedence and the expressions is evaluated from left to right? Or is it $$ a \lor (b \land c)$$ because $\land$ has higher precedence than $\lor$ or because they have equal precedence and the expressions is evaluated from right to left?

The latter is the case because $\land$ has a higher precedence than $\lor$.

Using this precedence rules the following lines of your proof are wrong

  T ∨ (p ∨ ¬y) ∧ (p ∨ ¬x) ∧ (¬x ∨ ¬p) ∧ T Idempotent

≡ [T ∨ (p ∨ ¬y)] ∧ (¬x ∨ ¬p) ∧ (¬x ∨ p) ∧ T Associativity

Deduction

I use the laws of Boolean algebra

$$\begin{eqnarray} && ((\lnot p \lor x) \land (p \lor y)) \to (x \lor y) \\ &\equiv & \lnot ((\lnot p \lor x) \land (p \lor y)) \lor (x \lor y) & \text{implication equivalence}\\ &\equiv & (\lnot(\lnot p \lor x) \lor \lnot (p \lor y)) \lor (x \lor y) & \text{DeMorgan}\\ &\equiv & ((\lnot(\lnot p) \land \lnot x) \lor (\lnot p \land \lnot y)) \lor (x \lor y) & \text{DeMorgan}\\ &\equiv & ((p \land \lnot x) \lor (\lnot p \land \lnot y)) \lor (x \lor y) & \text{Double negation}\\ &\equiv & (p \land \lnot x) \lor (\lnot p \land \lnot y) \lor x \lor y & \text{Associativity}\\ &\equiv & ((p \land \lnot x) \lor x) \lor ((\lnot p \land \lnot y) \lor y )& \text{Commutativity and Associatvity}\\ &\equiv & ((p \lor x) \land (\lnot x \lor x) ) \lor ((\lnot p \lor y) \land (\lnot y \lor y) )& \text{Distributivity}\\ &\equiv & ((p \lor x) \land T ) \lor ((\lnot p \lor y) \land T ) & \text{Complementation}\\ &\equiv & (p \lor x) \lor (\lnot p \lor y ) & \text{Identity}\\ &\equiv & (p \lor x \lor \lnot p \lor y ) & \text{Associativity}\\ &\equiv & ((p \lor \lnot p) \lor x \lor y ) &\text{Commutativity and Associativity}\\ &\equiv & (T \lor x \lor y ) & \text{Complementation}\\ &\equiv & ((T \lor x ) \lor y ) & \text{Associativity}\\ &\equiv & (T\lor y ) & \text{Annihilator}\\ &\equiv & T\ & \text{Annihilator}\\ \end{eqnarray} $$

Using a truth table

I use $0$ and $1$ instead of $F$ and $T$. This is easier to read in the following truth table $$ \begin{array}{c} p&x&y&\lnot p&\lnot p \lor x&p \lor y&(\lnot p \lor x) \land (p \lor y)&x \lor y&((\lnot p \lor x) \land (p \lor y)) \to (x \lor y)\\ \hline\\ 0&0&0&1&1&0&0&0&1\\ 0&0&1&1&1&1&1&1&1\\ 0&1&0&1&1&0&0&1&1\\ 0&1&1&1&1&1&1&1&1\\ 1&0&0&0&0&1&0&0&1\\ 1&0&1&0&0&1&0&1&1\\ 1&1&0&0&1&1&1&1&1\\ 1&1&1&0&1&1&1&1&1\\ \end{array} $$

Admirably detailed, but perhaps too detailed! For it is worth pointing out that 3/4 of the entries in columns 4, 5, 6, and 7 are entirely redundant, as the entries in 3/4 of the lines in column 8 fix the value in column 9 .... This kind of labour-saving should be second nature. — Peter Smith, Sep 18 '13 at 22:10
@Peter Smith No, I think it is not too detailed. It was my intention to show a full truth table. On the one hand it shows how to evaluate Boolean expression. This technic can be useful when finding errors in derivations as I mentioned in one of my comments. On the otherhand it shows a mechanical prove method that does not need any creativity in contrast do the method the OP used. Reducing the truth table by 3/4 would run contrary to both targets. — miracle173, Sep 18 '13 at 23:40
it is a minor point indeed. But applying standard heuristics like "if working our the value of $A * B$ for a dyadic connective, look at the simpler of $A, B$ first" require no creativity ... — Peter Smith, Sep 19 '13 at 06:49

score 1 · Answer 2 · answered Sep 18 '13 at 19:31

It has to be said, this is a crazy way to go about establishing the given wff is a tautology. A brute force truth-table would be very much quicker and (evidently!) more fool-proof.

For note that the conditional ((¬p ∨ x) ∧ (p ∨ y)) → (x ∨ y) is true whenever the consequent (x ∨ y) is true, which is on six of the eight lines of the truth-table. So you only have to do any more working on two lines, and job done!

A tautology is, by definition, a formula which is true on all valuations of its atoms -- so a brute force truth-table (looking at every valuation and seeing if the formula is true) has to be the most direct method of checking. Not always the quickest, to be sure. By all means, then, use short-cuts (e.g. use known equivalences), or "work backwards" (using tableaux) if that cuts down the necessary working. But it isn't very smart to use those other methods if they make more work than a direct assault!!

He didn't say the logical system only had two values. He could want to prove it for an infinite (or very large) valued Boolean algebra, and might not know he can solve such problems using the two-valued Boolean algebra or he might think that no one has proved that you can use the two-valued Boolean algebra to evaluate identities for greater valued Boolean algebras. So, the truth table method might not work. — Doug Spoonwood, Sep 19 '13 at 01:31

score 1 · Answer 3 · answered Sep 18 '13 at 20:11

$$\begin{align} ((\neg p \vee x)\wedge(p\vee y))\rightarrow(x\vee y) \equiv& \neg((\neg p \vee x)\wedge(p\vee y))\vee(x\vee y)\\ \equiv& (\neg(\neg p\vee x)\vee\neg(p\vee y)) \vee (x\vee y)\\ \equiv& ((p\wedge\neg x)\vee(\neg p\wedge \neg y)) \vee (x\vee y)\\ \equiv& (p\wedge\neg x)\vee(\neg p\wedge \neg y) \vee x\vee y\\ \equiv& (p\wedge\neg x)\vee(\neg p\wedge \neg y) \vee (T\wedge x)\vee (T\wedge y)\\ \equiv& (p\wedge\neg x)\vee(\neg p\wedge \neg y) \vee ((p\vee T)\wedge x)\vee ((\neg p\vee T)\wedge y)\\ \equiv& (p\wedge\neg x)\vee(\neg p\wedge \neg y) \vee (p\wedge x)\vee(T\wedge x)\vee (\neg p\wedge y) \vee(T\wedge y)\\ \equiv& (p\wedge\neg x) \vee (p\wedge x)\vee(\neg p\wedge \neg y)\vee (\neg p\wedge y)\vee(T\wedge x) \vee(T\wedge y)\\ \equiv& (p\wedge(\neg x\vee x))\vee(\neg p\wedge(\neg y\vee y))\vee(T\wedge x) \vee(T\wedge y)\\ \equiv& (p\wedge T)\vee(\neg p\wedge T)\vee(T\wedge x) \vee(T\wedge y)\\ \equiv& p\vee\neg p\vee x\vee y\\ \equiv& T\vee x \vee y\\ \equiv& T \end{align}$$

I tried another way to do my implication equivalence last, It seems like it working out atm. Is there a specific order of presence, for what to convert first and what to convert after? Negations are usually always first, but after must I do disjunction or conjunctions before implication? — GivenPie, Sep 18 '13 at 20:14

Doug Spoonwood · Answer 4 · 2013-09-19T01:33:48.273

Suppose p=0. Then we have:

[((¬0 ∨ x) ∧ (0 ∨ y)) → (x ∨ y)]=[(1 ∨ x)∧ (0 ∨ y)) → (x ∨ y)].

=[(1 ∨ x)∧ (0 ∨ y)) → (x ∨ y)]=[(1∧y)→ (x ∨ y)] since (1 $\lor$ x)=1, and (0∨y)=y.

[(1∧y)→ (x ∨ y)]=[y→(x ∨ y)], which can get read "if y, then x or y". So, this case holds.

Suppose p=1. Then we have:

[[((¬1 ∨ x) ∧ (1 ∨ y)) → (x ∨ y)]=[[((0 ∨ x) ∧ (1 ∨ y)) → (x ∨ y)].

[[((0 ∨ x) ∧ (1 ∨ y)) → (x ∨ y)]=[(x$\land$1)→ (x ∨ y)]. (see the above).

[(x$\land$1)→ (x ∨ y)]=[x→ (x ∨ y)], which can get read "if x, then x or y". So, this case holds.

Since the above two cases covers all cases, it holds in all cases.

If you have more than two truth values you only need to change 0 to "falsum" here and "1" to "verum", the identities used still work. The "if x, then x or y" and "if y, then x or y" statements would need checked more thoroughly in such a case, but that won't end up posing a problem.

Proving equivalences

4 Answers4