Church Booleans

Haskell, 50 - 6 = 44 bytes

-1 byte thanks to Khuldraeseth na'Barya, and -1 byte thanks to Christian Sievers.

t=const
f=n t
n=flip
a=n n f
o=($t)
x=(n>>=)
i=o.n

Try it online!

Binary Lambda Calculus, 13.875 12.875 bytes (103 bits)

Binary Lambda Calculus Language (BLC) by John Tromp is basically an efficient serialization format for lambda calculus. It is a great fit for this task, as Church notation is even the "idiomatic" way to work with booleans in BLC.

I used the following lambda functions for the combinators, some of which I copied and golfed from the Haskell answer:, which were found by an exhaustive search with a proof limit of 20 β-reductions for each case. There is a good chance these are shortest possible.

True:  (\a \b a)
False: (\a \b b)
Not:   (\a \b \c a c b)
And:   (\a \b b a b)
Or:    (\a a a)
Xor:   (\a \b b (a (\c \d d) b) a)
Impl:  (\a \b a b (\c \d c))

These translate to the following (binary) BLC code sequences:

 bits |  name | BLC
------+-------+---------
    7 | True  | 0000 110
    6 | False | 0000 10
   19 | Not   | 0000 0001 0111 1010 110
   15 | And   | 0000 0101 1011 010
    8 | Or    | 0001 1010
   28 | Xor   | 0000 0101 1001 0111 0000 0101 0110
   20 | Impl  | 0000 0101 1101 0000 0110

Functions above are in total 111 bits long (13.875 bytes) 103 bits long (12.875 bytes). They don't need to be aligned to byte boundaries to be used inside a program, so it makes sense to count fractional bytes.

There is no code re-use between the combinators, because there are no variables/references/names in BLC - everything had to be copied over. Still, the efficiency of the encoding makes for quite a terse representation.

Python 2, (-3?)  101  95 bytes

David Beazley eat your heart out!

-6 thanks to Chas Brown (moved the repeated : into the join text >.<)

exec'=lambda x,y=0:'.join('F y;T x;N x(F,T);A x(y,F);O x(T,y);X x(N(y),y);I O(y,N(x))'.split())

Try it online!

I think it might be 95 - 3 because I don't reuse the functions A, X, or I, but I use a single = for assignment (in front of lambda). Maybe I cant remove any; maybe I even get to remove 3.5?