Функції

Задачі

Побудувати таблиці істинності для формул:

(P®Q)Ú(P®(QÙP));

ù(P®ù(QÙP))®(PÚR);

(P®Q~R))®((P®Q)~(P®R));

(PÙ(QÚùP))Ù((Q®P)ÚQ)).

Довести виконуємость формул:

ù(P®ùP);

(P®Q)®(Q®P);

(Q®(PÙR))Ù((PÚR)®Q).

Довести тотожну істинність формул:

(P®Q)Ú(Q®P);

P®(Q®(PÙQ));

(Q®R)®((PÚQ)®(PÚR));

(P®R)®((Q®R)®((P(Q)®R))).

Довести еквівалентність:

(AÚ(BÚC))~((AÙB)Ú(AÙC));

(AÚ(BÙC))~((AÚB)Ù(AÚC));

(AÚ(BÙA))~A;

(AÙ(AÚC)Ù(BÚC))~((AÙB)Ú(AÙC));

((AÚB)Ù(AÚB))~A.

Способи завдання булєвих функцій

Задачі

Представити функції алгебри логіки (ФАЛ), що рівні 1 на наступних наборах аргументів х₁х₂х₃ і х₁х₂х₃х₄, у табличному, графічному і чисельному виді:

001, 010, 110, 011;

100, 010, 000;

0001, 0100, 0110, 1011, 1101;

0010, 0101, 1000, 1001, 1100, 1111.

Представити задані ФАЛ у табличному, графічному і чисельному виді:

ù(x₁+ù(x₁x₂x₃+ùx₃));

x₁x₂+ù(x₂x₃+x₁+ùx₂ùx₃);

(x₁Åx₂)x₃+(x₁Åx₃)x₂;

(x₁+x₂)(x₁x₂+ùx₂x₃);

x₁+ùx₂+x₃;

(ùx₁+x₂)(ùx₂+x₃);

ù(ùx₁ùx₂ùx₁)+(ùx₁+ùx₂+ùx₃).

Записати СДНФ і СКНФ ФАЛ, що рівні 1 на наступних наборах аргументів х₁х₂х₃ і х₁х₂х₃х₄:

1. 001, 010, 110, 011;

1. 100, 010, 000;

2. 0001, 0100, 0110, 1011, 1101;

3. 0010, 0101, 1000, 1001, 1100, 1111.

Записати в ДНФ наступні ФАЛ:

[(x₂®x₁)~x₃]+(x₄ /x₁);

ù(ùx₁~(ùx₂+x₃))(x₁®x₄);

(x₁+ùx₂)x₃+(ùx₃+ùx₄)(ùx₁+x₃ùx₄);

ù(x₁+ù(x₁x₂x₃+ùx₃));

x₁x₂+ù(x₂x₃+x₁+ùx₂ùx₃);

ù(x₁ùx₂)ù(x₁ùx₃+(x₃x₄));

x₁ùx₃+ù(x₁ùx₂+ùx₁x₃)+x₂x₃x₄(x₁+ùx₁x₂x₃);

(x₁Åx₂)x₃+(x₁Åx₃)x₂;

(x₁¯x₂)/x₃+(ùx₂®x₃)¯x₄;

ù((x₁+ùx₂+x₃+x₄)(x₁+x₂+x₃+ùx₄))+(x₁x₃x₄®0).

Записати в КНФ ФАЛ з попередньої задачі.

Для ФАЛ f(x₁, x₂, x₃), заданих у табл. 3.1. (таблиці істинності), записати СДНФ і СКНФ.

Таблиця 3.1

X1
X2
X3
F1
F2
F3
F4

Записати в СДНФ наступні ФАЛ:

x₁x₂+ùx₁ùx₃+x₂x₃+ùx₂ùx₃;

(x₁+x₂)(x₁x₂+ùx₂x₃);

(x₁ùx₂+x₃x₄)(x₂+x₄)(x₁+ùx₃+ùx₄);

x₁+ùx₂+x₃;

(ùx₁+x₂)(ùx₂+x₃);

ù(ùx₁ùx₂ùx₁)+(ùx₁+ùx₂+ùx₃);

x₁(x₂+ùx₄)+x₁(x₁+x₃);

ùx₂(x₁ùx₄+x₃x₄)+ùx₁[ùx₃(ùx₂+x₄)+x₂x₃x₄]+x₁x₂(ùx₃+x₄).

Записати в СКНФ ФАЛ із задачі 6.

Записати СДНФ і СКНФ ФАЛ задачі 3.

Записати в СДНФ і СКНФ ФАЛ, задані в цифровій формі:

1. f(x₁,..., x₄) = Ú(0, 1, 3, 5, 9, 12, 14);

2. f(x₁,..., x₄) = Ú(1, 4, 6, 8, 10, 13, 15);

3. f(x₁,..., x₄) = Ú(0, 2, 5, 7, 8, 10, 11, 14);

4. f(x₁,..., x₄) = Ú(1, 3, 4, 7, 9, 12, 13, 15);

5. f(x₁,..., x₄) = Ù(2, 5, 7, 9, 12, 14, 15);

6. f(x₁,..., x₄) = Ù(1, 2, 4, 5, 7, 8, 9, 12, 14);

7. f(x₁,..., x₄) = Ù(3, 4, 6, 9, 11, 13, 14, 15);

8. f(x₁,..., x₄) = Ù(2, 5, 8, 10, 12, 13, 14).

По заданих СДНФ знайти СКНФ наступних ФАЛ:

a) f(x₁, x₂, x₃) = ùx₁ùx₂ùx₃+ x₁x₂ùx₃+x₁ùx₂x₃+ùx₁x₂x₃;

a) f(x₁, x₂, x₃) = ùx₁ùx₂x₃+x₁ùx₂x₃+x1x₂ùx₃;

b) f(x₁, x₂, x₃) = x₁x₂ùx₃+ùx₁ùx₂x₃;

c) f(x₁, x₂, x₃) = ùx₁ùx₂x₃+ùx₁x₂ùx₃+ùx₁x₂x₃+x₁x₂x₃.

Показати, що якщо в СДНФ знак Ú скрізь замінити на знак Å, то вийде формула, еквівалентна вихідної. Чи справедливо аналогічне твердження для довільної ДНФ?