Совершенные нормальные формы

Практические задания

Задание 1

С помощью равносильных преобразований построить ДНФ и проверить критерий ложности.

  1. x→ (y→z x) (x ↔ (y→x))
  2. (x y z) → (x ┐z)
  3. (x↔y z)→┐x

Задание 2

Построить СДНФ и СКНФ двумя способами, по таблице истинности и с помощью равносильных преобразований.

(x↔y) →┐x

Задание 3

Доказать, что

┐((AC)(BC))=(┐A┐BC)┐C

Задание 4

Доказать:

  1. ┐(X ┐Y)=XY;
  2. (X Y)(Z V) = XZ YZ XV YV;
  3. XY ZV = (X Z)(Y Z)(X Z)(Y V);
  4. X XY = X;
  5. X(X Y) = X;
  6. X(┐X Y) = XY;
  7. ┐(X → (Y→Z)) = X ┐Z.

Задание 5

Упростить формулы:

  1. X XY YZ ┐XZ;
  2. (X↔Y)( ┐X→Y);
  3. X(X→Y) →Y;
  4. (X→Y)(Y→Z) → (X→Z);