Примерные варианты контрольных работ.

Приведем пять вариантов контрольных работ. Задания соответствующих задач всех пяти вариантов имеют единую формулировку. Поэтому для каждой задачи сначала дается формулировка задания, а затем под цифрами I, II, III, IV, V приводятся варианты.

№1. Составив таблицы истинности, определить вид формулы (тождественно истинная, тождественно ложная, выполнимая или опровержимая):

1. F(X,Y,Z)=((XY)Z)((XY)Z);

2. F(X,Y,Z)=(XYZ)X(XY)(XYZ);

3. F(X,Y,Z)=(((YZ)X)(X(YZ)));

4. F(X,Y,Z)=X(YZ)(XY);

5. F(X,Y,Z)=X(YZ)(XZ)(YZ).

№2. Доказать тождественную истинность формулы (без использования таблицы истинности):

1. (PQ)(PQ);

2. (PQ)(QP);

3. ((PQ)P)P;

4. P(PQ);

5. (PQ)P.

№3. Используя равносильные преобразования, привести формулы к более простой форме:

1. ((XY)Z)(ZY);

2. ((X(YZ))(YX))Y;

3. ((XY)(YZ))(XZ);

4. ((XY)(XY))((XY)(XY));

5. ((XY)Z)(XZ).

№4. Формулу F(X,Y,Z) привести сначала к СДНФ, а затем к СКНФ:

1. F(X,Y,Z)=((XY)Z)((XY)Z);

2. F(X,Y,Z)=((X(YZ))X)((XY)Z);

3. F(X,Y,Z)=(((YZ)X)(X(YZ)));

4. F(X,Y,Z)=(X((YZ)(XY)));

5. F(X,Y,Z)=((X(YZ))(XZ))(YZ).

№5. Используя совершенную дизъюнктивную нормальную форму, найти наиболее простую формулу алгебры высказываний от четырех переменных, принимающую значение 1 на следующих наборах значений переменных и только на них:

1. F(0,0,0,0)=F(1,0,0,1)=F(1,1,0,0)=F(1,1,1,1)=1;

2. F(0,0,0,1)=F(0,0,1,0)=F(0,1,0,0)=F(1,0,0,0)=F(1,1,0,0)=1;

3. F(0,0,1,1)=F(1,1,0,0)=F(1,1,1,0)=F(0,1,1,1)=1;

4. F(0,0,0,0)=F(1,0,1,1)=F(0,0,0,1)=F(1,1,1,0)=F(1,1,1,1)=1;

5. F(1,1,1,0)=F(0,1,1,1)=F(0,1,1,0)=F(1,1,1,1)=1.

№6. Выяснить, верны ли следующие выводимости:

1. AC; (AB)M; (AN)K; (AB)N |= AM;

2. KN; FG; SH; FK; HN |= SG;

3. (FG)H; HN; M(KN) |= (FG)M;

4. (NK)R; F(GN); M(KR) |= F(GM);

5. (NM)K; G(FN); GK; F(GH) |= GN.

№7. Доказать полноту систем булевых функций:

1. {,,},{,};

2. {,,},{,};

3. {,,},{,};

4. {,,},{/};

5. {,,},{}.

№8. Записать формулу алгебры высказываний в виде полинома Жегалкина:

1. (XY)(XY)X;

2. ((XY)(XY))X;

3. ((XY)Y)(XY);

4. ((XY)Y)(XY);

5. (XY)(XY)Y.

№9. Составить релейно-контактную схему по заданной функции проводимости:

1. ((XY)(YZ))Z;

2. ((XY)(YZ))(XZ);

3. (XY)(X(YZ));

4. ((X(YZ))(YX);

5. ((XY)(YZ))Z.

№10. Минимизировать СДНФ, используя метод матрицы Карно:

1. XYZTXYZTXYZTXYZTXYZTXYZT XYZTXYZT;

2. XYZUXYZUXYZUXYZUXYZUXYZU;

3. XYZTXYZTXYZTXYZTXYZTXYZT;

4. XYZTXYZTXYZTXYZTXYZTXYZT;

5. XYZTXYZTXYZTXYZTXYZTXYZT XYZT.

№11. Минимизировать СДНФ одним из методов: графическим, методом Квайна, методом неопределенных коэффициентов или методом минимизирующих карт:

1. XYZXYZXYZXYZXYZ;

2. XYZXYZXYZXYZXYZXYZ;

3. XYZXYZXYZXYZXYZ;

4. XYZXYZXYZXYZXYZ;

5. XYZXYZXYZXYZXYZ.

ОТВЕТЫ

§1.

§2.

§3.

§4.

4.4. а) 1; б) PQ; в) PQ; г) PR; д) P(QR); е) QP;

ж) P(RS)(SR)Q.

4.5. а) XY; б) XZ; в) (XY)(XY);

г) (XYZ)(XZ); д) (XY)(XZ).

4.6. а) (XYZ); б) (XY); в) (XYZ);

г) (XY)(XZ); д) (XY)(XZ).

4.7. а) (XY)(YZ); б) XY(XY);

в) ((XY)Z)(YZ);

г) ((X(YZ))(XY)Y;

д) ((XY)(YYZ))(XZ).

4.8. а) (X(YZ))Z; б) XYZ; в) UZ(XY);

г) Y(XZ); д) (X(YZ)Z)(YZ).

4.9. а) (X(YZ))(XY);

б) ((XYZ)R)UVW;

в) (((X(YZ))P)Q)(R(ST)).

§5.

5.1. б) (XYZT)(XYZT);

в) XYZ;

г) (XYZ)YZ;

д) (XYZ)(XZ)XY.

5.2. б) (XY)(XY)ZT;

в) (XY)XZ;

г) (XYZ)(XYZ);

д) XX.

5.3. б) (XYZ)(XYZ)(XYZ);

в) (XYZ)(XYZ)(XYZ)(XYZ);

г) (XYZT)(XYZT)(XYZT)(XYZT)

(XYZT)(XYZT);

д) (XYZ)(XYZ)(XYZ)(XYZ);

е) (XYZ)(XYZ)(XYZ)(XYZ)

(XYZ)(XYZ)(XYZ);

ж) (XYZ)(XYZ)(XYZ)(XYZ)

(XYZ)(XYZ);

з) XYZT)(XYZT)(XYZT)(XYZT)

(XYZT)(XYZT)(XYZT)(XYZT)

(XYZT)(XYZT);

и) (XYZ)(XYZ)(XYZ)(XYZ)

(XYZ)(XYZ).

5.4. б) (XYZ)(XYZ)(XYZ)(XYZ)(XYZ);

в) (XYZ)(XYZ)(XYZ)(XYZ);

г) (XYZT)(XYZT)(XYZT)(XYZT)

(XYZT)(XYZT)(XYZT)(XYZT) (XYZT);

е) (XYZ)(XYZ)(XYZ)(XYZ)

(XYZ)(XYZ)(XYZ);

и) (XYZ)(XYZ)(XYZ);

л) (XYZ)(XYZ)(XYZ)(XYZ)

(XYZ)(XYZ).

5.5. б) (XYZT)(XYZT);

в) XYZ;

г) (XYZ)(XYZ)(XYZ)(XYZ)

(XYZ)(XYZ);

д) (XYZ)(XYZ)(XYZ)(XYZ)

(XYZ)(XYZ)(XYZ)(XYZ);

е) (XYZT)(XYZT)(XYZT)

(XYZT)(XYZT);

ж) (XY)(XY)(XY);

з) XY.

5.6. в) (XYZ)(XYZ)(XYZ)(XYZ)

(XYZ)(XYZ)(XYZ);

г) (XYZ)(XYZ);

д) не имеет СКНФ, так как является тавтологией;

ж) (XYZ)(XYZ)(XYZ)(XYZ)

(XYZ);

з) (XYZ)(XYZ)(XYZ).

5.7. а) XY; б) XY; в) XY; д)XYZ;

е) XYZT.

5.10. а) XY; б) XY; в) XY г) XYZ;

д) XYZ; е) XYZT.

5.16. б) (XY)(XY);

в) (XY)(XY);

г) (XYZ)(XYZ)(XYZ);

д) (XYZ)(XYZ)(XYZ)(XYZ)

(XYZ).

5.18. б) F(X,Y,Z)=Z;

в) F(X,Y,Z)=(XYZ)(XYZ);

д) F(X,Y,Z)=(XY)(XYZ).

5.19. F(X,Y,Z)=X((YZ)(YZ))(XYZ).

5.21. (XYZ)(XYZ)(XYZ)(XYZ).

22. (XYZ)(XYZ)(XYZ).

5.24. б) XY, XY, YX, X, Y, XY, X(XY);

в) XY, YX, XY, XY, X, Y, XY;

г) XY, YX, XY, XY, X, Y, XY;

д) XY, YX, XY, X, Y, (XY)(XY), XY,

е) XYZ, XYZ, XYZ, XYZ, XY, (XY)Z, XZ, (XYZ)(XYZ), X(YZ), YZ, (XYZ)(YZ), (XZ)(XYZ), (XY)(XYZ), (XY)(XYZ), (XY)(YZ).

ж) СКНФ конъюнкции посылок: (XYZ)(XYZ) (XYZ)(XYZ)(XYZ)(XYZ);

з) (XY)Z, XYZ, XYZ, (XYZ)(XYZ), (XYZ)(XYZ), XY, ((XY)Z)(XY);

и) (XY)Z, XYZ, XYZ, YZ, (XZ)Y, YX, ((XY)Z)(YX);

к) СКНФ конъюнкции посылок: (XYZ)(XYZ) (XYZ)(XYZ)(XYZ)(XYZ);

л) СКНФ конъюнкции посылок: (XYZ)(XYZ) (XYZ)(XYZ)(XYZ)(XYZ)(XYZ).

5.25. б) XY;

в) XY;

г)XY;

д) такой формулы нет;

е) XY.

5.26. а) XZ;

б) YZ.

5.27. а) V(XV);

б) Z(YV).

5.28. XV.

29. (VW)Z.

5.30. а) X;

б) XV.

5.37. б) Y, XY, X, XY, XY, XY;

в) X, XY, Y, XY, XY, XY;

г) только тождественно ложная формула;

д) XY, XY.

5.38. б) ZV;

в) XY;

г) XY;

д) XY;

е) Y(XZ).

§6.

6.1. Четыре функции.

6.2. Шестнадцать функций.

6.4. а) не равны;

б) равны;

в) не равны;

г) равны.

6.7. XY=(XY);

XY=(XY);

XY=(XY)(XY);

X+Y=((XY)(XY));

X|Y=(XY);

XY=XY.

6.8. XY=(XY);

XY=XY;

XY=((XY)(YX));

X+Y=(XY)(YX);

X|Y=XY;

XY=(XY).

6.9. X=X|X;

XY=(X|Y)|(X|Y);

XY=(X|X)|(Y|Y);

XY=X|(Y|Y);

XY=((X|(Y|Y))|(Y|(X|X)))|((X|(Y|Y))|(Y|(X|X)));

XY=((X|X)|(Y|Y))|((X|X)|(Y|Y)).

6.10. X=XX;

XY=(XX)(YY);

XY=(XY)(XY);

XY=((XX)Y)((XX)Y);

XY=((XX)Y)(X(YY));

X|X=((XX)(YY))((XX)(YY));

X+X=(XY)((XX)(YY)).

6.16. а) XY=XY+X+1;

б) (XY)(YZ)=XYZ+XZ+XY+YZ+X+Y+Z+1;

в) (X|Y)Z=XYZ+XY;

г) ((XY)Z)|X=XYZ+XY+XZ+1;

д) (XY)Z=XZ+YZ+Z.

6.18. а) является;

б) не является;

в) не является;

г) является;

д) не является.

6.19. а) линейная;

б) не является линейной;

в) линейная;

г) не является линейной.

6.21. а) не является монотонной;

б) монотонная;

в) монотонная;

г) не является монотонной;

д) монотонная;

е) не является монотонной.

6.22. б) система полная;

в) система не является полной;

г) система полная.

§7.

7.1. а) (X,Y,Z) = XYZX;

б) (X,Y,Z) = (XY)ZZY;

в) (X,Y,Z) = (XYZ)U(XY);

г) (X,Y,Z) = XZYXYXYZ.

7.4. Приводим функции проводимости упрощенных схем:

а) YZ;

б) 0;

в) XY;

г) YZXYZ;

д) X₂(X₂X₄)

7.5. а) (X,Y,Z) = Y(XZXZ);

б) (X,Y,Z) = (XY)Z;

в) (X,Y,Z) = XYYZ;

г) (X,Y,Z,T) = (XZTZT)Y;

д) (X,Y,Z,T) = XY(ZTZT)XYZTXY ZT;

е) (X,Y,Z,T)=(XZXZ)YT.

6. (X,Y,Z)=XYYZXZ.

6. (X,Y)=XYXY;

7.9. (X,Y,Z)=(XYZ)(XYZ);

10. (X,Y,Z,T)=X((YZ)(YT));

7.11. (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₅.

67