Connectives Homework: Incomplete Set, Propositions P & Contradictions

[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?

 

[Owen Holden]

{<->, ~} 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]

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]

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]

Thanks!

Anyway, thanks a lot to all guys!

 

[honestrosewater]

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]

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]

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]

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]

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]

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]

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]

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]

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 referring 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]

But to what set of connectives was the second "formula" referring? If it was referring 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]

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]

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]

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.

 

[honestrosewater]

Honestrosewater, "formula" is defined in an absolute sense.

No, "formula" can be, and usually is, defined relative to some language containing some set of connectives.

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.

But your definition contains two occurences of "formula" each with a different referent. Otherwise, it states that there is only one complete set of connectives. BTW, that is another problem with the definition.

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.

"A 'complete' set of connectives is one which can be used to build a formula equivalent to any given formula." There is no formula that is equivalent to any given formula. The definition is indefensible if taken at face-value. Even after you fix it, it is still not a connotative definition, and I've already said that is my main complaint. I also already said the definition would work after it was fixed.
I gather the definition I am looking for will be stated in terms of truth-functions. I didn't know it would be such a big deal, so nevermind; I will try to find it myself.

 

[Bartholomew]

I guess you're right, the word "formula" is used in two different senses. The second sense is according to the original formal definition of "formula," and the first sense is according to an analogous idea of formula for the set of connectives in question.

I looked on mathworld.wolfram.com for "formula" and (going to the "sentential formula" link) there is a more general definition of "formula." That may be what he is using.

There is no formula that is equivalent to any given formula.

"A 'complete' set of connectives is one which can be used to build a formula equivalent to any given formula"

To use more precise language, it obviously means, "A 'complete' set of connectives is one where, for any given formula, the set of connectives can be used to build a formula equivalent to it." The definition is unflawed and does not need to be fixed.

Represent your statement, "there is no formula that is equivalent to any given formula," using logic, with Fx means x is a formula. ~Ex(Ey(Fx & Fy & x = y))

This is obviously false. What you had meant to say was, "there is no formula that is equivalent to _every_ given formula." But "any" does not mean "every." If it did, then the statement "I don't have any apples" with Px meaning x is an apple and Hx = I have x, would be represented as ~(Ax(Px --> Hx)), which does not conflict with the statement "I have three apples."

 

[BicycleTree]

You could prove that when all atomic statements of a formula of {AND, OR} are false, the formula is false.

 

[nounou]

Still I cannot find a formal way to prove that {AND, OR} is not a complete set of connectives. Any help? I'm really lost.

 

[davidseed]

quoted from www.ida.liu.se/~TDDB08/2005/slides/l5-6.pdf[/URL]
but this is not a very good reference for it.
<<<
Sheffer in 1913 provided a connective, called the Sheffer
stroke and denoded by |, which is suffcient to express any
other connective in the case the of two-valued propositional
logic. >>

e.g.
a |a == not a
(not a) | (not b) == a and b
(a | b) | (a and b) == a or b

-> or <- seems essential as a logical connective without something like this
you have no way to make a logical statement rather than just a logical contidition from nor, and, etc.

from -> you can generate <-> and <-

e.g. a->b == b <-a

and

(a->b) and (b<-a ) == a<->b but
<-> cannot generate -> or <-

The problem with not (~) as the basis for other logical operators is that it is monadic and so no diadic operator (such as nor and etc ) can be generated.

 

[nounou]

Thank you davidseed for your help.
But I need a formal proof to state that the set {AND,OR} is not complete. I understand the concept u r saying but saying that using this set, we cannot represent the connective ~ is just not good enough an answer. I want to find a way to logically prove why they are not complete.
Thanx.

 

[BicycleTree]

How formal do you need it to be? One semi-formal way is to say, where P is any formula of {AND, OR} and Q is any atomic statement,

P
Q
:.P AND Q

P
Q
:.P OR Q

So by induction, given any set of atomic statements, every formula of those statements with {OR, AND} can be proved. Whereas with the set of operators {AND, OR, NOT}, where R is a formula of {AND, OR, NOT} and Q is any atomic statement,
R
Q
:.R AND Q
is valid so
NOT (R AND Q)
is invalid and can't be proved, so no equivalent formula can be constructed with {OR, AND}.

 

[nounou]

Thank you . Maybe an induction proof that is more formal. I mean with a more convincing base case, and induction steps.

 

[BicycleTree]

Well, you would make the induction proof yourself. I didn't provide any base case at all or even any ordering on the formulas. I just meant, it could be done.

 

[nounou]

Yeah I know, I get the idea, but I just can't seem to write it down formally enough. Thanx anyway. If anyone can help, please let me know.