Who's who
Three men A, B and C are grandfather, father and son:
If C is the grandfather then B is the father.
If C is the father then B is the son.
If B is not the grandfather then A is the father.
If A is the son then C is the father.
Who's who?
If C is the grandfather then B is the father.
If C is the father then B is the son.
If B is not the grandfather then A is the father.
If A is the son then C is the father.
Who's who?
Labels: logic
posted by Chris at
8:32 PM
16 Comments:
Hi Cam. What a surprise, you got it.
The formal method takes up a lot more space. But I realised, after posting, that there were so few possibilities, that it'd be cracked quite quickly. And I was right :)
5 am, so I'm orft for a kip.
Chris...your post said 5 am
but the blog said 9 pm.
i was just wondering where in the world u are?
when the blog says 1 am, my time is 3 am.
maybe u can make a riddle out of that?
btw...has anyone seen my pants?
I'm in England. It's now 12:43 pm
Strangely enough, Ragknot had thought of doing a problem based on that very idea.
Although it's overkill, here's the formal solution.
I'll use the notation Ag for A is the grandfather etc. So we have
AgAf = 0 as A cannot be both the father and grandfather and
AdBd = 0 as And B cannot both be the father. I know, in converting
the original problem that g is the father of f, but ignore that.
The technique is to convert the original statements into true
logcal statements, AND them together, and solve for Af etc.
As a reminder, if X then Y is true => X -> Y => !X + Y = 1
In the order given, we get, !Cg + Bf = 1, !Cf + Bs = 1,
!!Bg + Af = 1 => Bg + Af = 1, !As + Cf = 1
ANDing and expanding gives (without simplifying) =>
!Cg!CfBg!As + !Cg!CfBgCf + !Cg!CfAf!As + !Cg!CfAfCf
+ !CgBsBg!As +!CgBsBgCf + !CgBsAf!As + !CgBsAfCf + Bf!CfBg!As
+ Bf!CfBgCf + Bf!CfAf!As + Bf!CfAfCf + BfBsBg!As + BfBsBgCf
+ BfBsAf!As + BfBsAfCf = 1
Now simplify using the obvious contradictions =>
!Cg!CfBg!As + !Cg!CfAf!As + !CgBsAf!As = 1
Factorising => !Cg!As(!CfBg + !CfAf + BsAf) = 1
So !Cg = 1 and !As = 1 or Cg =1, As = 0.
and (!CfBg + !CfAf + BsAf) = 1
But Cf + !Cf = 1 (obviously)
so (Cf + !Cf)(!CfBg + !CfAf + BsAf) = 1
partial expansion =>
Cf(!CfBg + !CfAf + BsAf) + !Cf(!CfBg + !CfAf + BsAf) = 1
The first term = 0, therefore the second term = 1
so !Cf = 1 => Cf = 0
It is clear that Xg + Xf + Xs = 1 and Ax + Bx + Cx = 1
But we have Cg = Cf = 0 so Cs = 1 and so Bs = As = 0
But Ag + Af + As = 1 => Ag + Af = 1 and Bg + Af = 1 (a given)
So (Ag + Af)(Bg + Af) = 1 = AgBg + AgAf + AfBg + AfAf
= AfBg + Af =Af(1 + Bg) = Af = 1 and so Ag = As = 0
So far we have C is the son, A is the father
so that leaves B is the grandfather.
Having done all that (which was a sort of fun). I fancy that for
simpler problems, this is an unecessarily painful process and
still requires quite a lot of heuristic reasoning. I also find
it quite hard to read.
I'm sorry that I call that a formal solution. I'm trying to suggest that that it was somehow a more mathematical way of doing it. The real point being that, with experience, much harder problems could be solved than by using a trial and error approach.
I expect that the process could be turned into a general computer program that could solve any (soluble) logic problem.
Hmm! methinks that a computer could also provide a good brute force approach.
Made a typo about half-way through:
"So !Cg = 1 and !As = 1 or Cg =1, As = 0."
should hae read:
"So !Cg = 1 and !As = 1 so Cg = 0, As = 0."
Also, I'm sorry about the notation, but if I put in an explicit AND operator (&, *, .) then the lines would become too long. Just in case, AfBg = 1 means A is the father AND B is the grandfather. Also, I hadn't stated that "+" is the logical OR operator (some authors, including myself also use "¦"). "^" is often used for the logical exclusive OR operator.
Hi Cam. Ooops, I wrote that in an ambiguous way (it was very late). What I meant was, "if the statement 'if X is true then Y is true' is true", then this may be written !X + Y = 1. i.e. I'm asserting that because the statement 'if X is true then Y is true' is a true statement, then !X + Y = true. This gives a means of assigning a truth value to the given statement. Let your head spin on that for a while, and I hope that you see that's really quite sweet.
Although I'm sure you'll get it yourself, just for completeness:
X Y X->Y
0 0 1
0 1 1
1 0 0
1 1 1
In the context that I've used it, note that only the first, second and fourth lines satisfy /X + Y = 1. Note the third line; because X is 1 and Y is 0 (so X hasn't implied Y) the statement 'if X then Y' is false. Or in other words, X didn't imply Y. But in the context of the problem, that cannot be, as it is clear that the statements were meant to be true statements. Just tell me that you love it.
I see that I have been sloppy though; I should have said "If 'if X then Y' is true" that can be written "X->Y = 1" which then may be written "!X + Y = 1", which in turn means we can't be on the third line of the truth table above.
Thanks for questioning that, it's actually helped me to understand it better (I think).
PS This stuff is called the algebra of statements. I don't recall having come across it before. It certainly bent my brain the first time round (i.e. yesterday).
I'll give a couple of examples.
"2 is an even integer" = 1
"π (pi) is rational" = 0.
So we're dealing with the truth of a statement. So now try: "If C is the father then B is the son" = 1.
I think it is "self-evident" that "if X then Y" is equivalent to X->Y. So now consider "X->Y" to be a statement. If it is a true statement, then X->Y = 1. But X->Y is equivalent to !X+Y. So altogether, get !X+Y = 1.
Just in case, X->Y more fully means if X is true then Y is true. It doesn't imply that if X is false that Y is false. Rotten example: Given that only dogs can be hairy (just bear wih me), then "if it's hairy then it's a dog", doesn't mean that "if it's not hairy then it isn't a dog", because some dogs might not be hairy.
Again thanks for questioning, it's nice to know that my efforts aren't all being ignored.
Hi again Cam. Just playing now.
I thought I'd analyse your example in the context of the algebra of statements:
(if X is TRUE then Y is TRUE)
AND
(if X is FALSE then Y is FALSE)
If we were to say that the above is a true statement, then I'd translate it to:
((X->Y)=1)&((!X->!Y)=1) = 1
[The =1s on the LHS are redundant.
If you were programming you wouldn't write If (5 = 5) = TRUE]
(X->Y)&(!X->!Y) = 1
(!X+Y)&(X+!Y) = 1
(!X&X+!X&!Y+Y&X+Y&!Y) = 1
(!X&!Y + X&Y) = 1
=> (X=0 & Y=0) + (X=1 & Y=1) = 1
=> X = Y
A lot of steps, but I'm new at this.
I expect that you'll recognise the signature of the exclusive nor operator (aka the equivalence operator). The previous could have been written !(X^Y) = 1, where ^ is the exclusive or operator.
X Y !(X^Y)
0 0 1
0 1 0
1 0 0
1 1 1
Note that !(X^Y) is only true if X = Y, otherwise it is false. But by asserting that the statement is true, we conclude that X = Y. OTOH if we had asserted that the statement was false, then we'd conclude that X = !Y.
I find this new way of looking at logic statements quite fascinating and very disorienting. I only previously knew about Boolean logic (where the truth of statements was never mentioned) in the context of logic based control systems.
I'm going to post one more logic problem before moving on.
Now I cme to think of it, I have seen this stuff being used before, but didn't know what was going on. I think that when you see things like e.g. !X+Y it is assumed that they are statements that are true (or are assertions). I think I have seen this idiom being used for defining axiomatic algebras.
If you are interested in this logic, I've just done an update on the 'More guilt' problem.
Hi Cam. I felt like I was speaking Egyptian.
i'll be BAC
B=Grandfather
A=Father
C=Son
Much later... I think that I was so wrapped up in the logic of
statements, that I completely missed Cam's meaning when he
challenged the equivalence and interpretation of
"if a then b" is equivalent to "!a + b = 1"
NB "!a + b = 1" can be said as "if !b then !a"
If a = 1 then !a + b = !1 + b = 0 + b = b =1, i.e. if a = 1 then b = 1
If a = 0 then !a + b = !0 + b = 1 + b = 1 and does not imply that b = 1
i.e. if a = 0 then b = 0 or 1
Note that this is entirely consistent with the usual meaning of
"if a then b". In programming for instance, if the part being tested
by the "if" is false, we skip the "then" part of the statement.
"=>": "implies (but isn't necessarily implied by)", "is sufficent
(but may not be necessary)".
"<=": "is implied by (but doesn't necessarily imply)" or even
"is necessary (but may not be sufficient)"
"<=>": "implies and is implied by", "is necessary and sufficient",
"if and only if", "iff", "is equivalent to" or "≡".
a|b means "a divides b" or "b is exactly divisible by a". Then
4|a => 2|a and 2|a <= 4|a - now try with all the interpretations.
Post a Comment
Links to this post:
Create a Link
<< Home