Solutions of Midterm 1 Problems

  1. Verify with the help of diagrams, which of the following equalities hold in general. In order to make your conclusion draw the diagrams of the left hand side and the right hand side of these expressions.

(i)

(ii)

Solution:
(i)LHS


RHS

The equality does not hold.

(ii)LHS

RHS

The equality holds.

  1. Verify with the help of diagrams, which of the following inclusions hold in general. In order to make your conclusion draw the diagrams of the left hand side and the right hand side of these expressions.

(i)

(ii)

Solution:

(i)LHS

RHS

The inclusion holds.

(ii)LHS

RHS

The inclusion does not hold.

  1. Find logical tautologies corresponding to the following identities.
    (i)

(ii)

Solution: Let .

(i)

(ii)

  1. Find logical tautologies corresponding to the following inclusions.

(i)

(ii)

Solution: Let .

(i)

(ii)

  1. Write down truth tables of the following boolean expressions and check, which ones are tautologies.

(i)
(ii)

Solution:

(i) Let be .

t tttttt

tfffftt

ftfttff

ffftttt

This is not a tautology.

(ii) Let us introduce notation:

is ,

is ,

is .

.

t ttffft

tfftfft

fttttft

fftttft

This is a tautology.

  1. Express boolean operator in terms of and , i.e. find a boolean expression involving variables and operators , which gives the same logical values as . Provide the truth table of your expression.

Solution:

Let us recall De Morgan’s law

Applying operator to both sides of the above equivalence we obtain

Let us directly check, that and have the same truth tables. Indeed

pq t t t t

tftt

fttt

ffff

  1. Is it true in general that ? Justify the answer.

Solution:

This equality does not hold in general. Elements of the set are counted once on the left hand side and twice on the right hand side.

  1. Perform the following substitutions.

(i)

(ii)

Solution:

(i)=

(ii)