This problem comes from an exercise in Enderton's Intro to Mathematical logic, which I'm currently working through. This problem tripped me up yesterday. Thought it might be fun for any logic lovers. Here goes...
Consider the ternary connective #, defined by the following truth table
A B C #(A,B,C)
T T T T
T T F T
T F T T
F T T T
T F F F
F T F F
F F T F
F F F F
# is nicknamed the majority function because it always returns T if the majority of the arguments are T, and F if the majority of the arguments are F.
The task is to prove that {#} is incomplete. What this means is that there exists some well formed expression that can't be written tautologically with only #. If you've had a little logic you know that {negation, and, or} are complete. Any expression can be written tautologically with those three connectives in what is call "disjunctive normal form". Proving that a set of connectives is complete is easy. Proving that a set of connectives is incomplete is tougher. You have to be able to figure out some peculiar property of the connective and show there is some other connective that doesn't have it. The example I think Enderton gives is proving "or" is not complete. Note that if all the sentences are T in a formula built up with "or", then the entire formula has to be true. However, -A (read, not A) is an expression that when all of its sentences are T it is not itself T. Therefore there is no way for any expression built up with "or"'s to be equivalent to -A in the row of the truth table that assigns T to all the sentences.
Okay, a long setup, but a fun problem. See if you can find special property of # that distinguishes it from at least one other formula.
Subscribe to:
Post Comments (Atom)
Posts
5 comments:
I'm not sure if this is right, but how about the fact that when any expression is written using just the majority symbol it contains a power of 3 sentences, or in particular it an odd number of sentences, and so cannot represent any of the binary connectives which must be symmetric about the two inputs. How did you do it?
I'm not quite sure what you mean by a 'power of three sentences'? You don't simply mean that # is a ternary operation?
no i mean that the number of sentence symbols in the expression is a power of three
What about #(A,B,#(A,B,A))? You have 5 sentence symbols and only 2 unique symbols. Neither is a power of 3.
ps. Anon, I'm glad you're working on this problem. It has been largely ignored. I think it's a good one.
Post a Comment