Register to reply 
How to prove this?by flying2000
Tags: prove 
Share this thread: 
#1
Mar2005, 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? 


#2
Mar2105, 02:35 AM

P: 89

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. 


#3
Mar2105, 11:58 AM

PF Gold
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 truthfunctions? Does anyone have a definition to begin the proof with?



#4
Mar2105, 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. 


#5
Mar2105, 07:07 PM

P: 40

Anyway, thanks a lot to all guys!



#6
Mar2205, 10:17 AM

PF Gold
P: 2,330




#7
Mar2205, 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 argumentas I interpret itabout 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. 


#8
Mar2205, 04:09 PM

PF Gold
P: 2,330

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. 


#9
Mar2205, 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. 


#10
Mar2205, 07:39 PM

PF Gold
P: 2,330




#11
Mar2205, 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. 


#12
Mar2205, 08:47 PM

PF Gold
P: 2,330




#13
Mar2205, 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) 


#14
Mar2205, 11:18 PM

PF Gold
P: 2,330

Can you answer my other questions? 


#15
Mar2305, 12:48 AM

P: 552

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. 


#16
Mar2305, 01:26 AM

PF Gold
P: 2,330




#17
Mar2305, 04:22 AM

P: 89

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. 


#18
Mar2305, 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 definitionnow from two sources, wherever Owen Holden got hisdoesn'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 