Past exam of the logic and set theory course of the University of Oxford / 2011 / A / 1 / c

Table of contents
- i c
  - Solution i
- ii c
  - Solution ii
- iii c
  - Solution iii
- iv c
  - Solution iv

i

Solution

Logical equivalence means that the two propositional formulas receive the same truth value under every Boolean valuation of the propositional variables. Equivalently,

α \leftrightarrow β

is a tautology:

\forall v v (α) = v (β) .

ii

Solution

Assign to each propositional formula its finite symbol length. The set of lengths of formulas logically equivalent to

α

is a nonempty subset of the natural numbers, because it contains the length of

α

. The well-ordering principle for the natural numbers gives a least such length, and hence a shortest equivalent formula.

A shortest equivalent formula need not be unique. For example

(p_{0} \to p_{0})

and

(p_{0} \leftrightarrow p_{0})

are distinct tautologies of the same minimal length. A shorter formula would contain no binary connective and hence be a variable with some number of negations, which is not a tautology. This counts each propositional variable as one symbol, as in the stated language, and proves that a shortest equivalent formula need not be unique.

iii

Solution

A conjunctive normal form is a finite conjunction of clauses, each clause being a finite disjunction of literals. A literal is a propositional variable or the negation of one. Thus its shape is

i = 1 ⋀ m (j = 1 ⋁ n_{i} ℓ_{ij}), ℓ_{ij} \in {p_{k}, \neg p_{k} : k \in ω} .

A single clause or single literal is allowed; the necessary parentheses can be inserted according to the grammar.

iv

Solution

First eliminate implication and biconditional using the logical equivalences

A \to B \equiv \neg A \lor B, A \leftrightarrow B \equiv (\neg A \lor B) \land (\neg B \lor A) .

Push negations inwards using De Morgan's laws and eliminate double negations. Structural induction leaves only literals joined by conjunction and disjunction.

Now induct on that remaining expression. A literal is already in conjunctive normal form. A conjunction of two conjunctive normal forms is again one after associating its clauses. For a disjunction, write the two inductively obtained forms as

⋀_{i} C_{i}

and

⋀_{j} D_{j}

and use distributivity:

(i ⋀ C_{i}) \lor (j ⋀ D_{j}) \equiv i, j ⋀ (C_{i} \lor D_{j}) .

Each

C_{i} \lor D_{j}

is a clause. All operations preserve logical equivalence, proving the required form exists.

 Ancestors (12)

 View article source

 Discussion (0) New discussion

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