Упражнения.

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

а) XYZXYZXYZXYZXYZ;

б) XYZXYZXYZXYZXYZXYZ;

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

а) XYZTXYZTXYZTXYZTXYZTXYZTXYZT XYZT;

б)XYZTXYZTXYZTXYZTXYZTXYZTXYZT XYZT;

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

Приведем пять вариантов контрольных работ. Задания соответствующих задач всех пяти вариантов имеют единую формулировку. Поэтому для каждой задачи сначала дается формулировка задания, а затем под цифрами 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.

1.7.	а) A=1 б) С=1 в) A=1 г) B=0	д) B=0 e) D=0 ж) E=0 или E=1 з) C=0 и) D=1
1.8.	а) (a0)(b0) б) (a=0)(b=0) в) (a=0)(b=0) г) (a=0)(b0) д) (a=3)(a=-3) е) (a>-3)(a<3)	ж) (a<-3)(a>3) з) (a0)(b0) и) (a0)(b0)
1.9.	а) 0 б) 1 в) 1	г) 1 д) 1 е) 0	ж) 1 з) 0 и) 1
1.10.	а) A=1 б) B=0	в) C=0 г) D=1
1.11.	а) достаточно, 1. б) достаточно, 0. в) достаточно, 1. г) достаточно, 1.	д) достаточно, 1. е) достаточно, 1. ж) достаточно, 1.
1.12.	а) AB б) AB
1.13.	(ABC)(ABC)(ABC)
1.14.	Высказывание истинно.
1.15.	а) ложно б) ложно в) может быть как истинно, так и ложно г) истинно
1.16.	Не существуют.

§2.

2.4.	а) при наборе (0,1,1) значение формулы равно 0. при наборе (0,0,0) значение формулы равно 1. б) при наборе (1,0,0,1) значение формулы равно 1. при наборе (1,1,0,0) значение формулы равно 0.
2.5.	а) тавтология б) выполнимая и опровержимая в) выполнимая и опровержимая г) выполнимая и опровержимая д) тавтология е) тавтология ж) выполнимая и опровержимая з) выполнимая и опровержимая
2.8.	б) (P,Q,R)=(1,0,0) в) решений нет г) (P,Q)=(0,0); (P,Q)=(1,1) д) (P,Q)=(0,0); (P,Q)=(1,1); (P,Q)=(1,0). е) решений нет ж) (P,Q,R,S)=(1,1,1,1); (P,Q,R,S)=(1,0,1,1). з) (P,Q,R)=(0,1,1)

§3.

3.1.	а) не верна в) верна г) не верна д) не верна е) не верна	ж) верна з) верна и) верна к) верна л) верна м) верна
3.4.	а) верна б) не верна в) верна г) верна д) не верна	е) не верна ж) верна з) верна и) не верна
3.5.	а) логично б) нелогично в) логично г) нелогично д) нелогично	е) логично з) нелогично и) нелогично к) логично

§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