Propositional Logic: Tautologies

  • (2 Pages)
  • +
  • 1
  • 2

15 Replies - 6354 Views - Last Post: 09 July 2012 - 05:22 PM

#1 LowWaterMark  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 119
  • Joined: 30-July 08

Propositional Logic: Tautologies

Post icon  Posted 27 August 2008 - 01:35 AM

I'm teaching myself first order logic. I'm terribly stuck on the difference between the two tautologies of implication and identity. The links above take you to the resource I'm using. If you have any better suggestions, I'm all ears.

Assume I've worked out a 2power3 (8) cell truth table for P an Q where:
P=I win the lottery
Q=I give you a million dollars

Where is the difference between:
1. P => Q
2. P <=> Q

And how do the tautological examples above differentiate from simple, non-tautological implication and identity. For identity, assuming again the above truth table, where's the difference between:
1. P<=>Q
2. P<->Q

I know this is a pain, but I have to understand it. 'appreciate the help.

This post has been edited by jayman9: 29 August 2008 - 05:05 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Propositional Logic: Tautologies

#2 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Propositional Logic: Tautologies

Posted 28 August 2008 - 06:43 PM

Case 1: If LowWaterMark wins the lottery then he will give me a million dollars.

Case2 If and only if LowWaterMark wins the lottery will he give me a million dollars.

Case 1 does not exclude the possibility that LowWaterMark may give me a million dollars for helping him understand first order logic.

Case 2 does -- in case 2 there is only one way that LowWaterMark is going to give me a million dollars.

Now a tautology is something that is ALWAYS true. It is a logical fact.

"This statement is true if and only if this statement IS true." is a tautology. Of course self referential logic statements are not the best examples and are often "barred" from formal logic (Godel showed that you actually can't eliminate them, but you can try to avoid them).

Tautologies occur within logic itself. For example "if p or not p" is always true since there really is no dependence upon p. "p => p" and "p <=> p" are also tautologies.

Diametrically opposite to a tautology is the mathematician's best friend the contradiction. For example "p and not p" is always false since p can not be both true and false at the same time (if it can, you are using the wrong logic -- which is a hint, there are logics where a bit can be true and false).


So that leaves us with "p <-> q" which is "p imples q, and q imples p" this says nothing about the truth of p or q, only that if p is true, than q is true, and if q is true then p is true...

This situation also implies that if p is false, then q is false (because if q were not false then p would be true). And if q is false then p must be false as well. Thus p and q are equivalent.

So we could say:

((p -> q) && (q -> p)) -> ((~p -> ~q) && (~q -> ~p))
&&
((~p -> ~q) && (~q -> ~p)) -> ((p -> q) && (q -> p))

SO

(p <-> q) <-> (~p <-> ~q)

SO: what is the difference between -> and =>? Semantically they are the same. The difference in use has more to do with convention or connotation than actual meaning. p -> q is a statement, p => q is a conclusion.

"let p be true, p implies q, therefore q is true."
(p and p -> q) => q

Is there a real difference between "therefore" and "implies" -- mathematically no, logically no, but to the reader of the statement the important information is the conclusion not how you got there.


So what about <=> and <->? Again the same. <=> is a strong condition, where as <-> is tool used in a proof. But in the end they both show equivalence.
Was This Post Helpful? 0
  • +
  • -

#3 LowWaterMark  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 119
  • Joined: 30-July 08

Re: Propositional Logic: Tautologies

Posted 29 August 2008 - 01:45 AM

NickDMax - thank you much for your time. Your careful explanation helped.

I have a loosely related anxiety regarding syllogistic equivalence. I worked out a problem on idiomatic syllogisms, got the answer correct but inverted the premises of one of the wffs along the way. This stuff is harder than I anticipated and makes me long for a teacher.

Shit. Oh well, enjoy your weekend. Even Aristotle could do that.
Was This Post Helpful? 0
  • +
  • -

#4 LowWaterMark  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 119
  • Joined: 30-July 08

Re: Propositional Logic: Tautologies

Posted 29 August 2008 - 04:33 AM

You know what, I can't get this thing on my own. FWIW I'm studying "Introduction to Logic" by Harry J. Gensler alongside its quiz software, LogiCola and am stuck on biconditionals (<->, if and only if) versus conditionals (->, if-then).

Let's assume:
P = I went to Lisbon
Q = I picked my nose

Now, (P -> Q) equates to "if I went to Lisbon, then I picked my nose". (P -> Q) is not equivalent to (Q -> P) as the antecedent has switched places with the consequent. Agreed?

Now, what about the biconditional, (P <-> Q), a wff which translates to "I went to Lisbon if and only if I picked my nose". Are biconditionals reversible? Is (P <-> Q) equivalent to (Q <-> P)? To quote Gensler regarding their respective truth tables, "for (P <-> Q), the claim is made that both parts have the same truth value: both are true or both are false (for the biconditional to be true). So, "<->" is much like "equals".

Building truth tables, I certainly can see this. Intuitively though, they certainly are not. "I picked my nose if and only if I went to Lisbon" is not equivalent to "I went to Lisbon if and only if I picked my nose".

To distill this down, are the following arguments equivalent:
1. (P <-> Q)
2. (Q <-> P)


Sorry but I cannot answer this simple query myself. After two hours I'm disenchanted. Thoughts?
Was This Post Helpful? 0
  • +
  • -

#5 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Propositional Logic: Tautologies

Posted 29 August 2008 - 03:31 PM

Well, if and only if is called equivalence. So if you look at the bottom half of my last post I talk about that.

Let's assume:
P = I went to Lisbon
Q = I picked my nose

P <-> Q -- "If and only if I went to Lisbon will I have picked my nose"

I picked my nose.

Therefore I MUST have went to Lisbon, because I said that I would ONLY pick my nose if I went to Lisbon.

If you can accept that from an algebraic stand point AND is commutative than you can see:

P <-> Q <==> (P -> Q) AND (Q -> P) => (Q -> P) AND (P -> Q) <==> (Q <-> P)

sometimes the language can be awkward and seem inconsistent with an equivalence.

I will go to Lisbon if and only if I pick my nose.

This seems as though I am saying,

"There is only one way I will pick my nose, and that is if I go to Lisbon"

well If i DO pick nose, then you know that the ONLY way I would do that is if I go to Lisbon. SO, I must have gone to Lisbon because I picked my nose.

So while the is may seem that the second version is not equivalence, it is.

You have to remember that while humans are not terribly literal, logic is.
Was This Post Helpful? 0
  • +
  • -

#6 Damage  Icon User is offline

  • Lord of Schwing
  • member icon

Reputation: 44
  • Posts: 1,136
  • Joined: 05-June 08

Re: Propositional Logic: Tautologies

Posted 29 August 2008 - 03:37 PM

okay just what the hell is going on? What is this and how come i've never seen it before?
Was This Post Helpful? 0
  • +
  • -

#7 Jayman  Icon User is offline

  • Student of Life
  • member icon

Reputation: 418
  • View blog
  • Posts: 9,532
  • Joined: 26-December 05

Re: Propositional Logic: Tautologies

Posted 29 August 2008 - 05:09 PM

This is an excellent topic to be Featured on the front page. So allow me to make it so. :^:
Was This Post Helpful? 0
  • +
  • -

#8 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Propositional Logic: Tautologies

Posted 30 August 2008 - 07:24 PM

View PostDamage, on 29 Aug, 2008 - 03:37 PM, said:

okay just what the hell is going on? What is this and how come i've never seen it before?


Its first order logic. You should probably have learned a little about it in discreet mathematics. A course if formal logic itself usually requires that you take a philosophy or mathematics curriculum. Though for a mathematics major we covered this over and over in many classes.
Was This Post Helpful? 0
  • +
  • -

#9 LowWaterMark  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 119
  • Joined: 30-July 08

Re: Propositional Logic: Tautologies

Posted 30 August 2008 - 11:50 PM

NickDMax,

Thanks for all your time. Being a math major you can probably see that I'm being intellectually punished for quitting after three semesters of calculus. I'm still troubled by one thing. Quoting you:

Quote

If you can accept that from an algebraic stand point AND is commutative than you can see:

P <-> Q <==> (P -> Q) AND (Q -> P) => (Q -> P) AND (P -> Q) <==> (Q <-> P)
I can see and understand the biconditional implication, but not the logical equivalence. I'm troubled by the negation proof italicized in the last sentence of the following quote from Wikipedia. Considering what follows bold typed in the same quotation below, it seems that logical equivalence cannot follow directly from biconditionalism or bidirectional implication. I can rationalize bivalence but not equality. The reason is the negation aspect of the proof in red below.

Please note that <-> is translated to "iff" in the following link. The logical phrase, "iff" is an abbreviation of the phrase, "if and only if". The abbreviation, "iff" is not a typographical error for "wff" (abbreviation for well formed formula). From Wikipedia link: "If and only if"

Quote

Advanced considerations

Philosophical interpretation

A sentence that is composed of two other sentences joined by "iff" is called a biconditional. "Iff" joins two sentences to form a new sentence. It should not be confused with logical equivalence which is a description of a relation between two sentences. The biconditional "A iff B" uses the sentences A and B, describing a relation between the states of affairs A and B describe. By contrast "A is logically equivalent to B" mentions both sentences: it describes a relation between those two sentences, and not between whatever matters they describe.

The distinction is a very confusing one, and has led many a philosopher astray. Certainly it is the case that when A is logically equivalent to B, "A iff B" is true. But the converse does not hold. Reconsidering the sentence:

Madison will eat pudding if and only if it is custard.

There is clearly no logical equivalence between the two halves of this particular biconditional.

One way of looking at A if and only if B is that it means A if B (B implies A) and A only when B (not B implies not A). Not B implies not A means A implies B, so then we get two way implication.


Let me ask about commutivity of biconditionalism in a different way. Assume: I'm in Oregon if and only if I'm in the United States. Does it necessarily follow that I'm in the United States if and only if I'm in Oregon?

I'm getting lost somewhere in the forest and cannot find my breadcrumbs to get back home. Will you please critique my argument: (<-> ~= equivalence)?

I'm not trying for an intellectual circle jerk here. This is really tripping me up and impeding me from going forward.

This post has been edited by LowWaterMark: 31 August 2008 - 03:43 AM

Was This Post Helpful? 0
  • +
  • -

#10 LowWaterMark  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 119
  • Joined: 30-July 08

Re: Propositional Logic: Tautologies

Posted 31 August 2008 - 12:33 AM

Two other things are competing to age me prematurely. As I think about it, they are intimately related to my confusion as detailed above.

In both syllogistic and basic propositional logic - I'm unreliable at accurately extracting the premises and conclusion out of idiomatic English arguments.

FWIW, I'm using CS381 Discrete Structures/Discrete Mathematics Web Course Material in addition to reading "Introduction to Logic" by Harry J. Gensler and his Logicola companion software.

This post has been edited by LowWaterMark: 31 August 2008 - 04:51 AM

Was This Post Helpful? 0
  • +
  • -

#11 AdaHacker  Icon User is offline

  • Resident Curmudgeon

Reputation: 452
  • View blog
  • Posts: 811
  • Joined: 17-June 08

Re: Propositional Logic: Tautologies

Posted 31 August 2008 - 12:23 PM

View PostLowWaterMark, on 31 Aug, 2008 - 01:50 AM, said:

Let me ask about commutivity of biconditionalism in a different way. Assume: I'm in Oregon if and only if I'm in the United States. Does it necessarily follow that I'm in the United States if and only if I'm in Oregon?

Yes, it does. Biconditionals are commutative. Formally, this is easily proven using the very argument you quoted. So yes, formally the statement "I'm in Oregon if and only if I'm in the United States" implies that "I'm in the United States if and only if I'm in Oregon". This should be obvious.

Your problem is that this is clearly a false statement. You can be in the US without being in Oregon, so mutual implication is clearly the wrong way to model this statement. Keep in mind that just because you see the see the phrase "if and only if" in an English sentence does not necessarily mean that you should model that as a biconditional in formal logic. You can usually take a direct translation approach when going from formal logic to English, but it doesn't always work in reverse - except in the examples they put in text books.

In this case, the statement "I'm in Oregon if and only if I'm in the United States" is better captured by (A -> B ) & (~ B -> ~A): fi I'm in Oregon, then I'm in the US, and if I'm not in the US, then I can't be in Oregon. In actuality, this reduces to the simple conditional A -> B:
1) (A -> B) & (~B -> ~A)
2) (A -> B) & (~~B V ~A)	(definition of implication)
3) (A -> B) & (B V ~A)	  (double negation)
4) (A -> B) & (~A V B)	  (commutivity of disjunction)
5) (A -> B) & (A -> B)	  (definition of implication)
6) (A -> B)				 (simplification) QED



Regarding "logical equivalence", it's a subtle point and it really has little to do with mathematical logic. Formally speaking, A <-> B means logical equivalence - it means both A and B have the same truth value, with the consequence that one can be substituted for the other. Since mathematical logic doesn't really care what "A" and "B" mean, that's as far as it needs to go. What the WIkipedia article is talking about is the meaning of those sentences.

Think of it this way: Do "Madison will eat this pudding" and "This pudding is custard" mean the same thing? Clearly not. In that sense, they are not logically equivalent. However, when used in the context of a formal argument, the truth of the biconditional means that the two are logically equivalent in the truth-value sense. So, really, it depends on the context - are you looking at the statement in terms of symbols in formal logic or in terms of the philosophical interpretation of its content?

To make a long story short, in formal logic, a biconditional, for all intents and purposes, is an equivalence. That's because formal logic is really just symbol manipulation. You don't have to worry about what A and B actually mean in a metaphysical sense - you just apply given rules to transform sets of symbols. The question of what equivalence really means, and the different ways in which things can be equivalent, is for the philosophers.

I hope that didn't add to the confusion.

This post has been edited by AdaHacker: 31 August 2008 - 12:25 PM

Was This Post Helpful? 1
  • +
  • -

#12 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Propositional Logic: Tautologies

Posted 31 August 2008 - 08:41 PM

Mathematicians like to talk about rigor. To mathematicians this is very important because of statements like: "I am in Oregon if and only if I am in the United States" -- which makes sense but can be confusing since, there are other states within the united states.

This statement may be akin to a mathematics statement such as: "x is rational if and only if x is real"

Is this a contradiction (a statement that MUST be false)? well it may seem so, but it is not. There are values of x, even entire sets over which this statement is true... it is not true in general since there are also values of x and entire sets in which it is not true.

So if I ASSUME that it is true. Well then it is a statement about x, that is x can not be an irrational real number, or a complex rational number, but x can be an irrational imaginary or complex number. x can only be chosen such that the statement is true. So this statement gives information about what the possible values of x may be.

So in your statement: "I am in Oregon if and only if I am in the United States" makes a statement about situation. IF it is true, then I can't visit a state other than Oregon (lest the statement be false).

So indeed the statement "I am in the United States if and only if I am in Oregon" logically follows from the first statement since they are logical implications of each other.

The reason that it *seems* odd is because we have not built up the structure to explicitly define what the statements mean. We are relying upon a number of other statements that we have chosen to accept. There is no rigor to back up the statement.

It may be better to just replace the nouns with non-sense:

P1: "X is in A if and only if X is in B"

So, here it may be easier to see that,

P2: "X is in B if and only if X is in A"

is a logical equivalence and a logical conclusion from P1.

But if we look at just P1 then we may be tempted to infer some relationship between A and B (like A is a proper subset of B, or even A == B ).

BUT if we would be mistaken since we may find out that:

P3: If Y is in C then Y is in B.

Well... now if we imagined that A was a proper subset of B or that A was equal to B then we now have to ask ourselves what this means about C and well... this gets complected. C may be a proper subset of A or it may be equal to A or it may be a proper subset of B, or equal to B...

My point is... that we can REALLY only deal with the information that is ACTUALLY GIVEN. By making assumptions and imagining relationships we are only able to guess... to discover anything we must be able to form a proof and we can not form a proof without a set of axioms (things we assume to be true) that give us relationships.


There are reasons why we study formal logic in symbols. Because it shows us truth that can be hidden by the introduction of information that we assume but is not part of the system we are discussing.

Do your thinking in the symbols and THEN translate back into your human understanding. But to do this, you have to first trust in and believe in the logic. Which basically means that for a while you have to struggle a little bit with trying to translate back and forth and "see" that it really works.

This post has been edited by NickDMax: 31 August 2008 - 08:46 PM

Was This Post Helpful? 0
  • +
  • -

#13 LowWaterMark  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 119
  • Joined: 30-July 08

Re: Propositional Logic: Tautologies

Posted 01 September 2008 - 01:10 AM

AdaHacker and NickDMax, thanks much for your well reasoned replies.

Reading both of your responses (over and over) and going back to my primary text (Gensler) I realized that I was superimposing set theory and English colloquialisms atop of first order logic. It's frustrating because when I take quizzes that accompany this material, I do pretty well. but it is a bit of a mirage as I usually succeed by algebraically dividing and conquering until I get to a simple connective ( P something Q) for which I know the truth tables. There's an intuitive facet I am missing. Implication makes sense. Biconditionalism is just math to me. Part of it is in the phrase, "if and only if". In English, this implies a direction similar to "if, then".

I need to reason this out just a bit more. I'm not sure what in my mind is fighting against the principle of bivalence or rather, biconditionalism.

This post has been edited by LowWaterMark: 01 September 2008 - 01:11 AM

Was This Post Helpful? 0
  • +
  • -

#14 LowWaterMark  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 119
  • Joined: 30-July 08

Re: Propositional Logic: Tautologies

Posted 01 September 2008 - 01:42 AM

I think I figured it out.

Let me remove implied English colloquialisms by using the same verb in both P and Q. Let me also remove any implication of set. Now, let's assume something that is basically true for me. I'm only in joy if I'm in Oregon. Unfortunately I live in upstate New York, but that's another (illogical) story.

P = I'm in joy.
Q = I'm in Oregon.
(P<->Q) = I'm in joy if and only if I'm in Oregon.

Now it works. The only place I experience joy is in Oregon and if I'm in Oregon I am joyful. Conversely if I'm not in then I can't be in Oregon and if I'm not in Oregon than I'm not in joy. The univalent conditional (if, then) points both ways, the biconditional (if and only if) works and it sort of makes sense.

Shit, finally.

This post has been edited by LowWaterMark: 01 September 2008 - 04:15 AM

Was This Post Helpful? 0
  • +
  • -

#15 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Propositional Logic: Tautologies

Posted 01 September 2008 - 04:49 PM

Well one thing that may help is to think of this as a definition:

Given statements P and Q:

P -> Q taken as true, and Q -> P taken as true means that P <-> Q.

So if I say:

P: I am sleepy
Q I am in the airport.

Then if I state:
P <-> Q: "I am sleepy if and only if I am in the airport"

If I am sleepy then I am in the airport.
AND
If I am in the airport then I am sleepy.

now you may say that this seems illogical since surely I am sleepy other places other than the airport. And right you would probably be, BUT if I say that P <-> Q is true then I am defining it as true and all that it implies.

So if I later said: "I am in the hotel" then you could say, "Well I guess you are not sleepy so lets go get something to drink".

See, if I now argue and say, "No, I am sleepy" -- then you have to ask the only logical question, "So you are in an airport hotel?"

If I say, "No, I am downtown." -- well now you have found an apparent contradiction. The options are:

P<->Q -- is is true and there is some unifying bit of information that you don't know about.

P<->Q -- is true and one of my other statements is false.

P<->Q -- is false, and I really meant something like Q -> P but misspoke.

What I am saying is that just because it does not make sense does not make it false, at the same time, just because it is a "well formed formula" or "stated logically" does not mean it is true.

I can form a totally logically valid argument that is just plain wrong! Actually in school it happened to me quite a bit. I would form a nice proof just to have the teacher come back and say: "Well here one of your assumptions is wrong" -- In mathematics we start from axioms and we may prove some very interesting results with one set of axioms, and then completely different conclusions when we make even one of those axioms false (That is the difference between euclidean geometry and elliptic or hyperbolic geometry - one the negation of 1 axiom).

Which is why it is better to say that an argument is: "consistent or not consistent" rather than just "right or wrong".

This post has been edited by NickDMax: 01 September 2008 - 04:51 PM

Was This Post Helpful? 1
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2