Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Digital systems, linear algebra and introduction to formal proof / 7 / c

Table of contents
- Solution c

Solution

Apply the propositional substitution simultaneously to the atomic variables:

φS = ((X \lor Y) \land (X \lor \neg Y)) \lor ((Y \to X) \to \neg X) .

By distributivity and the complementary literals

Y, \neg Y

,

(X \lor Y) \land (X \lor \neg Y) \equiv X .

The other disjunct simplifies using logical implication and absorption:

(Y \to X) \to \neg X \equiv \neg (\neg Y \lor X) \lor \neg X \equiv (Y \land \neg X) \lor \neg X \equiv \neg X .

Thus $φS \equiv X \lor \neg X \equiv ⊤$ , a tautology.

 Ancestors (12)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version