wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        general >> wanted >> logic
        
(Message started by: hparty on Sep 13^th, 2010, 11:24am)

Title: logic
Post by hparty on Sep 13^th, 2010, 11:24am

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/

Title: Re: logic
Post by towr on Sep 13^th, 2010, 3:15pm

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⁴=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.