When is a template more specialized than the other? 'And'/'Or' confusion with logics.

Question 1

Update: This has now been added as an official C++ Issue

I have finally figured out how to read the paragraph in question. Below I have bulleted it

If for each type being considered a given template is at least as specialized for all types, and

more specialized for some set of types and the other template is not more specialized for any types, or

{the other template} is not at least as specialized for any types,

then the given template is more specialized than the other template.

This way the following first template is also more specialized than the second template

template<typename T> void f(T*);
template<typename T> void f(T);

Note that the first template's parameter is at least as specialized as the second template, but is not defined to be "more specialized" - that term only applies for the case where both parameters were references and certain conditions apply (see paragraph 9 of 14.8.2.4) . The rules are apparently not meant to follow any formal ordering laws. The second template is not at least as specialized as the first template. This means that the second bullet applies, and not the first.

Question 2

This answer is based on an incorrect parsing of the Standard paragraph's abstract syntax tree. The grouping of conditions assumed in the "Back to the Standard" section turned out not to be the intended one. The intended grouping is the one Johannes Schaub has shown in his answer.

Why is there then that mentioned fallback for when none of the Us are at least as specialized than the corresponding Ts?

I agree with you that the second part (actually, the whole second condition) is redundant.

Some vocabulary of reference:

Let's have some fun with logics and introduce 3 fundamental relations between two templates for a pair of corresponding parameters:

More specialized than: for parameters Ti and Ui respectively, one template matches the other but not vice versa. I will indicate this as Ti < Ui;
Equally specialized: for parameters Ti and Ui respectively, one template matches the other and vice versa. I will indicate this as Ti == Ui;
Specialization-incomparable: for parameters Ti and Ui respectively, none of the templates matches the other for the particular parameter. I will indicate this as T1 ~ U1.

For instance, in the code snippet below:

template<typename X> struct A { };
template<typename X> struct B { };

template<typename X> void foo(A<X>, X, A<X>) { } // 1
template<typename X> void foo(X,    X, B<X>) { } // 2

For the first parameter, (1) is more specialized than (<) (2); for the second parameter, (1) is equally specialized as (or "as specialized as", ==) (2); for the third parameter, (1) is specialization-incomparable to (~) (2).

And let' now define a derived relation:

A template (1) is at least as specialized as another template (2) for respective parameters Ti and Ui when (Ti < Ui) or (Ti == Ui), i.e. when either (1) is more specialized than (2) or (1) is as specialized as (2). In the above example, therefore, T1 <= U1, T2 <= U2, and U2 <= T2.

Back to the Standard:

With the help of a couple of parentheses, the quote above becomes (A && (B1 || B2)):

[...] for each type being considered:

( a given template is at least as specialized for all types and more specialized for some set of types )
                                 AND 
( the other template is not more specialized for any types
                                 OR
is not at least as specialized for any types )

Given two templates to be ordered with respect to the corresponding sequences of parameter types T1, ..., Tn and U1, ..., Un, the condition (A):

[...] a given template is at least as specialized for all types and more specialized for some set of types [...]

Means that for each i = 1..n, Ti <= Ui, and for some js in 1..n, it applies the stricter condition that Tj < Uj. Dropping the index i, this means that for each parameter:

(T < U) || (T == U) // (A)

This condition is put in logical conjunction ("and") with another condition (B), which is in turn the logical disjunction ("or") of two sub-conditions, (B1) and (B2). Let's start examining sub-condition (B1):

[...] the other template is not more specialized for any types [...]

This means that for any i, it is never the case that Ui < Ti, which means that either:

Ti is more specialized than Ui (Ti < Ui); or
Ti and Ui are equally specialized (Ui == Ti); or
Ti and Ui are specialization-incomparable (Ui ~ Ti):

More formally:

!(U < T) <==> (T < U) || (T == U) || (T ~ U) // (B1)

Now let's see the second sub-condition (B2), which is put in logical disjunction with (B1):

[...] is not at least as specialized for any types [...]

This is the negation of U <= T, which means:

!(U <= T) <==> !((U == T) || (U < T)) ==> !(U == T) && !(U < T)

So in other words, T and U are not equally-specialized, nor U is more specialized than T. Therefore, the only possibilities left are that:

(T < U) || (T ~ U) // (B2)

Now it is evident that (B2) implies (B1), because (B2) is more restrictive. Therefore, their disjunct (B) will be coincident with (B1), and (B2) is redundant:

(T < U) || (T ~ U) || (T == U) // (B)

But what is also evident here is that (A) is stricter than (B), so the conjunction of (A) and (B) is equivalent to (A).

Conclusion:

The whole condition (B) is redundant.