How can we determine if a boolean expression is trivial or non trivial

Question

I am given two boolean expression
1) $x_1 \wedge x_2 \wedge x_3$
2) $(x_1 \wedge x_2) \vee (x_3 \wedge x_4)$

Now I need to know which expression is trivial and which is non-trivial. I wanted to know what is the procedure of doing so?

Answer 1

The first one is trivial and is equivalent to $$x_1+x_2+x_3\ge 3$$

The second one is not trivial. Its equivalent form is$$x_1+x_2\ge 2\\\text{or}\\x_3+x_4\ge 2$$

Remark

Note that $x_1+x_2+x_3+x_4\ge 4$ leads to extra cases like$$x_1+x_3\ge 2\\\text{or}\\x_2+x_4\ge 2$$

Answer 2

The link says, that a LTU can be represented when the expression is trivial and cannot be represented when it is non-trivial (page3).

That's not what it says.

First, you've mixed up what the role of LTUs is here. The titles of the second and third slides are "What can be represented by an LTU" and "Things that cannot be represented" - the LTUs are the representers, not the representees.

Moreover, the slides don't say that nontrivial expressions can't be represented by LTUs. Indeed, they don't talk about "nontrivial expressions" at all! What the slides say is that nontrivial disjunctions cannot be represented by an LTU. A trivial disjunction is a disjunction which is equivalent to an expression not involving $\vee$ - for example, $x_1\vee x_1$ is a trivial disjunction, since it's equivalent to the $\vee$-free $x_1$.

In particular, neither of the expressions you've written are trivial disjunctions: the second one is a nontrivial disjunction, and the first one isn't a disjunction at all. Of course, this does not fully answer the question of which of the two are expressible by LTUs: we know the second one can't be since it's a nontrivial disjunction, but we still have to look at the first one a bit (it's not a nontrivial disjunction, but nontrivial disjunctions aren't the only things not expressible by LTUs).