Math Logic Proving Proofs

**Bungkai** · April 4th 2010, 11:42 AM

Give a proof of

A ^ (A V B)

A.

I have an additional question. I do not really understand what

means, as sometimes I have seen it placed in the middle of proofs and sometimes I see it has no influence to the answer to the question at all.

A ^ (AVB)
By Golden Rule
=> A

A V B

A V A V B
By Idempotency of V
=> A

A V B

A V B
By symmetry of

=> A

I need a lot of clarification for these steps as they do not make sense to me. I understand the last part of every step, but do not understand the rest of it.

**emakarov** · April 4th 2010, 02:30 PM

The symbol $\vdash$ (called "turnstile", maybe because it looks like a turnstile in the subway) separates assumptions from conclusions. For example, $A,A\to B\vdash B$ is a correct statement. In your example, there are no assumptions.

A ^ (AVB)
By Golden Rule
=> A

A V B

A V A V B

Judging by Axioms for propositional logic E, The Golden Rule is "p /\ q == p == q == p \/ q". We instantiate p = A and q = A V B to get

$(A\land (A\lor B)\equiv A)\equiv ((A\lor B)\equiv (A\lor A\lor B))$

Now, $A\land (A\lor B)\equiv A$ is what we need to show. So, the right-hand side $A\lor A$ is rewritten as $A$ by the idempotency of disjunction. So we get $A\lor B\equiv A\lor B$ , which can be rewritten to $\mathsf{true}$ .

With all due respect to D. Gries, this formulation of propositional logic seems curious but eccentric; I have not seen any serious logician using it these years.

**Bungkai** · April 4th 2010, 04:45 PM

Ok, I understand most of what you are saying. Regarding the steps I showed though, you mentioned the right hand side.

A

A V B

A V A V B

The middle and left side I do not know where they came from. Only the right side makes sense to me.

I would also like to throw another question at you since we're on the topic if you don't mind.

The weakening rule states A $\vdash$ A V B

How would a hypothesis B become notA v B

(Sorry I do not know how to use the mathematical symbols on forums.

**emakarov** · April 5th 2010, 04:04 AM

A

A V B

A V A V B

The middle and left side I do not know where they came from.

Take the Golden Rule $p\land q\equiv p\equiv q \equiv p\lor q$ . This is an axiom schema, which means that $p$ and $q$ may be replaced by arbitrary formulas. Also, due to associativity of $\equiv$ , parentheses can be distributed in an arbitrary way.

So, replace $p$ with $A$ and $q$ with $A\lor B$ . We'll get $A\land(A\lor B)\equiv A\equiv A\lor B\equiv A\lor(A\lor B)$ . Also, let's surround with parentheses the first \equiv and the rest of the formula: $\Big(A\land(A\lor B)\equiv A\Big)\equiv \Big(A\lor B\equiv A\lor(A\lor B)\Big)$ . The left-hand side is what needs to be proved. The right-hand side can be rewritten to "true" after $A\lor(A\lor B)$ is replaced by $(A\lor A)\lor B$ by associativity of $\lor$ and $A\lor A$ is replaced by $A$ due to idempotency of $\lor$ .

The weakening rule states A

A V B

How would a hypothesis B become notA v B

Why do you call B a "hypothesis" when it occurs only to the right of the turnstile and not even by itself? Hypotheses are placed to the left of

. Second, is this a question about the same problem or not? In the original problem there was no negation (is notA the negation of A?). I am not sure what the question is asking.

Sorry I do not know how to use the mathematical symbols on forums.

Not a problem. You can write \/ for $\lor$ , /\ for $\land$ , -> for $\to$ , and (not A) for $\neg A$ (in parentheses). I prefer leaving a space on each side of a binary connective, like this: A /\ B, rather than A/\B. It is only important to parenthesize formulas correctly.

**Bungkai** · April 5th 2010, 06:33 PM

I am stating B as a situational hypothesis.

**emakarov** · April 6th 2010, 12:45 AM

I am stating B as a situational hypothesis.

Sorry, I am not sure what "situational" means.

The weakening rule states A

A V B

How would a hypothesis B become notA v B

If you want to clarify the question, could you say if it is related to the original problem "A ^ (A V B)

A"? Also, I am not sure what "become" here means. I can write anything on paper; the question is whether this would make sense according to the rules of inference, etc. Could you re-state your question, e.g., "How to derive this from this?" or "Is this a legal formula"?

**Bungkai** · April 6th 2010, 06:38 AM

From the weakening rule, is it possible to derive $\neg A$ $\lor B$ using B instead of A as the hypothesis?

**MoeBlee** · April 6th 2010, 07:54 AM

Originally Posted by Bungkai

From the weakening rule, is it possible to derive $\neg A$ $\lor B$ using B instead of A as the hypothesis?

You stated the weakening rule as:

A |- A v B

whre 'A', and 'B' are variables ranging over formulas, right?

So here are instances of the rule:

~A |- ~A v B

B |- B v A

B |- B v ~A

Etc.

That is, the rule is: Given a formula A (of any complexity at all) you can infer the formula A v B (where B is any formula of any complextity at all).

Now, you asked, "How would a hypothesis B become ~A v B ?"

In the manner you stated the rule, that wouldn't work, since the hypothesis must be the FIRST conjunct (as you've stated the rule). But, of course, we ordinarily also have commutativity of disjunction so:

B |- B v ~A (by weakening)
B v ~A |- ~A v B (by commutativity of disjunction)
So B |- ~A v B.

**emakarov** · April 6th 2010, 10:47 AM

In the manner you stated the rule, that wouldn't work, since the hypothesis must be the FIRST disjunct

I usually work with system with two disjunction introduction rules: left and right.

How would a hypothesis B become ~A v B ?

This is the wording that confused me. If one derives $A\vdash B$ , one may think that $A$ becomes $B$ . However, this is not only extremely personal and informal interpretation, but not even a very accurate one. After all, the hypothesis $A$ did not disappear after $B$ was derived from it; one can still use it to derive further consequences of $B$ .

**MoeBlee** · April 6th 2010, 12:05 PM

Originally Posted by emakarov

I usually work with system with two disjunction introduction rules: left and right.

Indeed, but I was only responding to the rule as he literally gave it. And then I mentioned that commutativity would do the rest of the job (as would, as you mentioned, the disjunction introduction rule being both left and right).

Originally Posted by emakarov

If one derives $A\vdash B$ , one may think that $A$ becomes $B$ . However, this is not only extremely personal and informal interpretation

Yes, I was not dissuaded by his rather informal descriptions. I took it for granted that it is understand that one thing doesn't "become" another, but rather that one formula allows the derivation of another, etc.

Thread: Math Logic Proving Proofs

LinkBack

Thread Tools

Display

Math Logic Proving Proofs

Similar Math Help Forum Discussions

[SOLVED] Logic proofs

Logic Proofs

Logic Proofs

predicate logic proofs

Logic & Propositions & Proofs

Search Tags