Author |
Topic: logic (Read 3452 times) |
|
hparty
Newbie
Gender: 
Posts: 15
|
it is known that the connective "or : v" can be defined using => (implies) only as followes
(P v Q )<=> ((P => Q )=> Q )
how we can show that we cannot express all the truth functions using only the set {=>, v} or { ~, <=>}.
/where ~ :not , <=> :equivalence/
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
 |
Re: logic
« Reply #1 on: Sep 13th, 2010, 3:15pm » |
 Quote  Modify
|
You could probably use exhaustion of the possible sets of truth values.
So to start,
P Q A:PvQ B:P=>Q
1 1 1 1
1 0 1 0
0 1 1 1
0 0 0 1
Then try to get a new set of truth values with combinations of P,Q,A,B, etc
And at some point you've either covered all 24=16 possible sets, or it's impossible.
Or you could note that at least in the case of => (and the redundant addition of v) you can't get negation, because if P=Q=1, no application of =>'s will ever get you 0.
|
| « Last Edit: Sep 13th, 2010, 3:15pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print