Author 
Topic: logic (Read 3451 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 13^{th}, 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 2^{4}=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 13^{th}, 2010, 3:15pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



