Tree #1:
or(x, and(or(y,x),and(y,y)), or(not(x)))
Tree #2:
xor(x,and(or(not(x),and(y,y)),implies(x,y)),nand(and(nand(x,x),y),y))
Tree #3:
implies(xor(implies(x,y),y),and(nor(and(x,x),nand(y,y)),y),nor(nor(nor(nor(x,x),y),y),implies(x,y)), nand(x,x,x,x))
Tree #4:
nand(nand(nand(nand(x,x),y),x),xor(xor(xor(x,y),y), x),and(and(and(y,x),x),y),or(or(or(or(y,y),x),y),x))



