Search code examples
logical-operatorsor-operatorand-operator

Given A∧B what is the equivalent using just → and ⊕(Xor)


Consider the set of connectives consisting of just → and ⊕, where ⊕ is an exclusive OR connective: A⊕B is true if and only if A and B have the opposite truth values (one is true and the other one false).

Given A∧B what is the equivalent formula using only → and ⊕(Xor).


Solution

  • Assumming that -> is the material conditional.

    A and B is equivalent to not(A implies not B)
    
    not C is equivalent to (C implies C) xor C
    

    so

    not B is equivalent to (B implies B) xor B)
    

    and

    A implies not B  equivalent to A implies ((B implies B) xor B))
    

    finally the equivalent expression is

    ((A implies ((B implies B) xor B)) implies (A implies ((B implies B) xor B)))xor (A implies ((B implies B) xor B)) 
    

    in your notation:

    ((A → ((B → B) ⊕ B)) → (A → ((B → B) ⊕ B)))⊕ (A → ((B → B) ⊕ B)) 
    

    with some care you can surely minimize these formulas

    Checking the final formula on wolfram alpha

    A general framework to answer such questions is functional completness. The people at mathoverflow might be helpful.

    EDIT

    i've made a mess of copying the long formulas, corrected now