how to prove this?


by flying2000
Tags: prove
flying2000
flying2000 is offline
#1
Mar20-05, 07:02 PM
P: 40
{<->, ~} is not a complete set of connectives..
It seems that we can't use Propostions P is all true and thus lead to contradition since ~ can make it false.

Any suggestion?
Phys.Org News Partner Science news on Phys.org
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language
Owen Holden
Owen Holden is offline
#2
Mar21-05, 02:35 AM
P: 89
Quote Quote by flying2000
{<->, ~} is not a complete set of connectives..
It seems that we can't use Propostions P is all true and thus lead to contradition since ~ can make it false.

Any suggestion?
1. {nor}
2. {nand}
3. {<-, True}
4. {->, False}
5. {~, v}
6. {~, &}
7. {~, ->}
8. {~, <-}

These sets of connectives are complete in the sense that all of the other propositional connectives can be defined by them.

{~, <->} and {~, xor} are not complete.
honestrosewater
honestrosewater is offline
#3
Mar21-05, 11:58 AM
PF Gold
honestrosewater's Avatar
P: 2,330
This is very sad because- if I have a specialty- it's finding things, and I can't find a decent definition of what it means for a set of connectives to be functionally complete. Does "functionally" refer to truth-functions? Does anyone have a definition to begin the proof with?

BicycleTree
BicycleTree is offline
#4
Mar21-05, 02:28 PM
P: 552

how to prove this?


I did a Google search: http://www.cs.toronto.edu/~yilan/TA/236/note
"A 'complete' set of connectives is one which
can be used to build a formula equivalent to any given formula."

I looked some more on Google for ways to prove this type of thing, and although I have no experience, here is a way I think you could approach it: in some multivariate logical formulas, you can reverse the truth value of all variables and that will reverse the truth value of the formula. But with only ~ and <->, reversing the truth value of all variables must leave the truth value of the formula unchanged if the formula is multivariate.
flying2000
flying2000 is offline
#5
Mar21-05, 07:07 PM
P: 40
Anyway, thanks a lot to all guys!
honestrosewater
honestrosewater is offline
#6
Mar22-05, 10:17 AM
PF Gold
honestrosewater's Avatar
P: 2,330
Quote Quote by BicycleTree
I did a Google search: http://www.cs.toronto.edu/~yilan/TA/236/note
"A 'complete' set of connectives is one which
can be used to build a formula equivalent to any given formula."
Well, every formula is equivalent to itself and there isn't any formula that is equivalent to every other formula. I think the author meant that, for each formula that can be written using connectives from a complete set of connectives, like {~, &, v, ->, <->}, you can write an equivalent formula using only connectives from a different set of connectives (the set you're trying to prove is complete). This isn't a good definition because it contains the term it's trying to define; How do you know the original set of connectives is complete? It only tells you something about relationships between complete sets of connectives.
BicycleTree
BicycleTree is offline
#7
Mar22-05, 01:18 PM
P: 552
Yes, that's what the author's sentence means (I don't think anyone was confused over that). It is not circular because it doesn't say "a formula equivalent to any given formula that can be written using a complete set of connectives." It says "equivalent to any given formula." The term "formula" has a clear definition, generally in terms of {~, &, v, ->, <->}, and without reference to completeness.

Your argument--as I interpret it--about whether formulas can represent all possible situations (i.e. whether they are intuitively "complete") just isn't relevant because the technical definition of a complete set of connectives doesn't have to comply with the intuitive idea of it.
honestrosewater
honestrosewater is offline
#8
Mar22-05, 04:09 PM
PF Gold
honestrosewater's Avatar
P: 2,330
Quote Quote by BicycleTree
Yes, that's what the author's sentence means (I don't think anyone was confused over that). It is not circular because it doesn't say "a formula equivalent to any given formula that can be written using a complete set of connectives." It says "equivalent to any given formula." The term "formula" has a clear definition, generally in terms of {~, &, v, ->, <->}, and without reference to completeness.
But "formula" occurs twice in the definition. Do both occurences have the same referent? You've just agreed that they don't. The first occurence refers to formulas of the set whose completeness is in question; The second occurence must refer to formulas of a set already known to be complete. If the second occurence doesn't refer to formulas of a set already known to be complete, the definition is wrong, since the second occurence could refer to formulas of an incomplete set of connectives.
I didn't mean the definition was circular. I suppose you could call the definition inductive; It says x is complete, and all sets bearing such and such relation to x are also complete. In that way, I guess it is close to a denotative definition. The problem I have with the definition is that it doesn't tell us what properties of x make x complete. I have seen a few connotative definitions of completeness, but they included terms I didn't know. Anyway, there is a connotative definition of completeness, and such a definition is preferable to a denotative one.
Your argument--as I interpret it--about whether formulas can represent all possible situations (i.e. whether they are intuitively "complete") just isn't relevant because the technical definition of a complete set of connectives doesn't have to comply with the intuitive idea of it.
I didn't mean to make any such argument.
BicycleTree
BicycleTree is offline
#9
Mar22-05, 06:30 PM
P: 552
The definition does not state that the second use of the word "formula" must refer only to formulas in a complete set. (Also, completeness here is defined with respect to sets of connectives, not sets of formulas)

A stipulative definition can't be wrong unless it's paradoxical, and there isn't any immediately apparent paradox.
honestrosewater
honestrosewater is offline
#10
Mar22-05, 07:39 PM
PF Gold
honestrosewater's Avatar
P: 2,330
Quote Quote by BicycleTree
The definition does not state that the second use of the word "formula" must refer only to formulas in a complete set.
Then "formula" can refer to formulas of an incomplete set of connectives, making the definition wrong.
(Also, completeness here is defined with respect to sets of connectives, not sets of formulas)
Where did I say otherwise?
A stipulative definition can't be wrong unless it's paradoxical, and there isn't any immediately apparent paradox.
This is clearly not a stipulative definition but a lexical one. If the context doesn't make it clear enough, the author says:
I've mentioned the idea of a "functionally complete set of propositional
calculus connectives", also known as a "basis for propositional calculus" (or
a "basis for boolean algebra").
How could a stipulative definition already be known by other names?
BicycleTree
BicycleTree is offline
#11
Mar22-05, 08:08 PM
P: 552
All mathematical definitions are stipulative. A mathematical definition is not intended to explain common usage, but to precisely define the term as it will be used. The other names are simply where he refers to a stipulative term which he had not yet defined for his students. It doesn't mean that the forthcoming definition was based on common usage.

Yes, the word "formula" could indeed refer to formulas of an incomplete set of connectives. And this would be fine for the definition and not make it wrong.

However, it's easy to prove that {v, &, ~, -->, <-->} is a complete set of connectives. You start with the definition of a formula. I'll state it here, as best I remember it: if P is an atomic statement, then P is a formula. If R is a formula, then ~R is a formula. If R and S are formulas, then (R v S) is a formula, (R & S) is a formula, (R --> S) is a formula, and (R <--> S) is a formula, and anything that cannot be said to be a formula by these implications is not a formula. Call the set of all formulas F.

Now, given the set of connectives {v, &, ~, -->, <-->}, any atomic statement P can be built. If R can be built, then ~R can be built. If R and S can be built, then (R v S) can be built, (R & S) can be built, (R --> S) can be built, and (R <--> S) can be built, and anything that cannot be built by these implications cannot be built. Call the set of all formulas that can be built with {v, &, ~, -->, <-->} B. So B = F, so F is a subset of B, so any formula can be built with {v, &, ~, -->, <-->}, so {v, &, ~, -->, <-->} is a complete set of connectives.
honestrosewater
honestrosewater is offline
#12
Mar22-05, 08:47 PM
PF Gold
honestrosewater's Avatar
P: 2,330
Quote Quote by BicycleTree
All mathematical definitions are stipulative. A mathematical definition is not intended to explain common usage, but to precisely define the term as it will be used. The other names are simply where he refers to a stipulative term which he had not yet defined for his students. It doesn't mean that the forthcoming definition was based on common usage.
I've mentioned the idea of a "functionally complete set of propositional
calculus connectives", also known as a "basis for propositional calculus" (or
a "basis for boolean algebra"). A "complete" set of connectives is one which
can be used to build a formula equivalent to any given formula.
What about this makes you think it was not intended to agree with the way the term is commonly used in logic? If you thought the definition wasn't meant to agree with common usage, then why did you post it without saying so?
Yes, the word "formula" could indeed refer to formulas of an incomplete set of connectives. And this would be fine for the definition and not make it wrong.
It could also refer to formulas of all sets of connectives, both complete and incomplete.
However, it's easy to prove that {v, &, ~, -->, <-->} is a complete set of connectives. You start with the definition of a formula. I'll state it here, as best I remember it: if P is an atomic statement, then P is a formula. If R is a formula, then ~R is a formula. If R and S are formulas, then (R v S) is a formula, (R & S) is a formula, (R --> S) is a formula, and (R <--> S) is a formula, and anything that cannot be said to be a formula by these implications is not a formula. Call the set of all formulas F.

Now, given the set of connectives {v, &, ~, -->, <-->}, any atomic statement P can be built. If R can be built, then ~R can be built. If R and S can be built, then (R v S) can be built, (R & S) can be built, (R --> S) can be built, and (R <--> S) can be built, and anything that cannot be built by these implications cannot be built. Call the set of all formulas that can be built with {v, &, ~, -->, <-->} B. So B = F, so F is a subset of B, so any formula can be built with {v, &, ~, -->, <-->}, so {v, &, ~, -->, <-->} is a complete set of connectives.
You haven't defined what it means for a set of connectives to be complete so you haven't proven any set of connectives is complete.
BicycleTree
BicycleTree is offline
#13
Mar22-05, 09:33 PM
P: 552
I was going solely by the definition from the site: "A "complete" set of connectives is one which can be used to build a formula equivalent to any given formula." No further definition was needed for the proof.

If you believe there is a "common usage" of the word "complete" as it applies to a set of connectives which differs from that given definition, then what is it? (though I don't think it could properly be referred to as common usage, but rather as something like "common stipulation," since the meaning of mathematical terms is not defined by the way they are used)
honestrosewater
honestrosewater is offline
#14
Mar22-05, 11:18 PM
PF Gold
honestrosewater's Avatar
P: 2,330
Quote Quote by BicycleTree
I was going solely by the definition from the site: "A "complete" set of connectives is one which can be used to build a formula equivalent to any given formula." No further definition was needed for the proof.
But to what set of connectives was the second "formula" referring? If it was refering to {v, &, ~, -->, <-->}, what have you proved? Your definition?
If you believe there is a "common usage" of the word "complete" as it applies to a set of connectives which differs from that given definition, then what is it?
I don't think it differs from the common definition- that's what I've been saying; It was meant to agree with common usage. The definition given, if you fill in the gaps and don't take it at face value, amounts to the same thing as other definitions. The definition given is still bad because you can't take it at face value, there are gaps to fill in, and it doesn't tell you what properties make a set of connectives complete.
(though I don't think it could properly be referred to as common usage, but rather as something like "common stipulation," since the meaning of mathematical terms is not defined by the way they are used)
Logic and math aren't exempt from lexical definitions. I doubt they could manage without them.
Can you answer my other questions?
BicycleTree
BicycleTree is offline
#15
Mar23-05, 12:48 AM
P: 552
Quote Quote by honestrosewater
But to what set of connectives was the second "formula" referring? If it was refering to {v, &, ~, -->, <-->}, what have you proved? Your definition?
The second use of the word "formula" was not referring to any set of connectives. It was referring to the already clearly (and arbitrarily) defined term "formula."


Logic and math depend entirely on stipulative definitions. There is no definition in math that is not stipulative.

I think I've indirectly answered all of your previous questions. If you think I haven't then please restate the question.
honestrosewater
honestrosewater is offline
#16
Mar23-05, 01:26 AM
PF Gold
honestrosewater's Avatar
P: 2,330
Quote Quote by BicycleTree
The second use of the word "formula" was not referring to any set of connectives. It was referring to the already clearly (and arbitrarily) defined term "formula."
A set of formulas is defined using a set of connectives. If it refers to a set of formulas, it refers to the set of connectives used to define them. In fact, this is why the two occurences of "formula" can have different referents.
Logic and math depend entirely on stipulative definitions. There is no definition in math that is not stipulative.
Mathematicians use terms, and I can give lexical definitions of the terms mathematicians use.
I think I've indirectly answered all of your previous questions. If you think I haven't then please restate the question.
Nevermind, I think I'm about done arguing over this.
Owen Holden
Owen Holden is offline
#17
Mar23-05, 04:22 AM
P: 89
Quote Quote by honestrosewater
You haven't defined what it means for a set of connectives to be complete so you haven't proven any set of connectives is complete.
A set of connectives is truth functionally complete if any formula can be expressed using only the set of connectives. (given p, q, r, etc.)

For example:

{nor} is complete.

~p =df (p nor p)
p v q =df ~(p nor q)
p -> q =df ~p v q
p & q =df ~(~p v ~q)
(p nand q) =df ~(p & q)
p <-> q =df (p -> q) & (q -> p)
(p xor q) =df ~(p <-> q)

Any formula of propositional logic, can be expressed by using 'nor' alone.

..and so on.
BicycleTree
BicycleTree is offline
#18
Mar23-05, 11:02 AM
P: 552
Owen, that's the definition honestrosewater won't accept.

Honestrosewater, "formula" is defined in an absolute sense. Once you define a formula with {&, v, -->, ~, <-->}, then that set of connectives is not "just one way of looking at it." Once you've so defined it, that is the definition of a formula, and all further usage of the term "formula" refers back to that.

From a logical standpoint there is no reason why this definition--now from two sources, wherever Owen Holden got his--doesn't work. It does.


Register to reply

Related Discussions
Please prove this Differential Geometry 6
Need help proving an expression of roots of sums including roots General Math 16
To Prove Calculus 3
Prove the following: Introductory Physics Homework 3
is this ok to prove? Introductory Physics Homework 6