Логічні перемикальні схеми

Задачі

Для заданих формул булєвих функцій і формул, отриманих із заданих у результаті перекладу в булєв базис, довільної (по властивостях 1-18) мінімізації, синтезувати логічні схеми й оцінити їх по складності:

[(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).

Перевести формулу ((x₂®x₁)~x₃)Å(x₄¯x₁) у заданий базис і синтезувати в ньому логічні схеми:

{Ú, ù};

{Ù, ù};

{®, 0};

{, ù};

{Å, 1, Ú};

{¯};

{/}.

Виконати аналіз заданих на рис. 3.1. логічних схем, визначити відповідні логічні формули:

a b

 

 

c d

Рис. 3.1. Довільні логічні схеми

Виконати мінімізацію отриманих у задачі 3 логічних формул, синтезувати для мінімізованих формул нові логічні схеми.

Виконати канонічний синтез логічних схем для формул задачі 1, оцінити їх за складністю способом, використаним раніше.

Побудувати логічні схеми і відповідні їм графи для МДНФ і МКНФ булєвих функцій (входи і виходи можна позначати як х₀₁, х₀₂, y₀₁ і т.д.):

f(x₁, x₂, x₃) = Ú(0, 2, 3, 4);

f(x₁, x₂, x₃) = Ú(0, 2, 3, 4, 5, 7);

f(x₁, x₂, x₃, x₄) = Ú(1, 4, 5, 6, 12, 13, 14).

Мінімізація булевых функцій

Задачі

Виконати графічну мінімізацію заданих на рис.3.2. булєвих функцій від трьох перемінних, вважаючи виділені вершини конситуентами одиниці.

Виконати графічну мінімізацію заданих у задачі 2 булєвих функцій, вважаючи виділені вершини конституентами нуля.

Виконати графічну мінімізацію заданих за допомогою формул:

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₄).

a b

с d

Рис. 3.2. Графічне завдання булевых функцій

Виконати мінімізацію заданих булєвих функцій від трьох перемінних для ДНФ і КНФ за допомогою карт Карно:

a

Таблиця 3.2

x1,x2 x3

b

Таблиця 3.3

x1,x2 x3

c

Таблиця 3.4

x1,x2 x3

d

Таблиця 3.5

x1,x2 x3

 

Виконати мінімізацію булєвих функцій від чотирьох перемінних, для ДНФ і КНФ за допомогою карт Карно:

a

Таблиця 3.6

x1,x2 x3x4

b

Таблиця 3.7

x1,x2 x3x4

c

Таблиця 3.8

x1,x2 x3x4

d

Таблиця 3.9

x1,x2 x3x4

 

Виконати мінімізацію заданих чисельним методом булєвих функцій для ДНФ за допомогою методів Квайна-MакКласки і Петріка, застосувавши метод Петріка до скороченої таблиці покрить:

Ú(0, 2, 3, 6, 7, 10, 11, 12, 13, 15);

Ú(0, 2, 4, 5, 6, 8, 9, 10, 12, 14, 15);

Ú(2, 3, 5, 7, 8, 10, 11, 12, 13);

Ú(0, 2, 5, 7, 8, 10, 11, 13, 14, 15);

Ú(0, 2, 4, 5, 6, 7, 8, 9, 13).

Вирішити задачу 6 для КНФ тих же булєвих функцій, заданих чисельним методом, за допомогою методів Квайна-МакКласки і Петріка, застосувати метод Петріка до скороченої таблиці покрить:

Ù(1, 4, 5, 8, 9, 14);

Ù(1, 3, 7, 11, 13);

Ù(0, 1, 4, 6, 9, 14, 15);

Ù(1, 3, 4, 6, 9, 12);

Ù(1, 3, 10, 11, 12, 14, 15).

Застосувати метод Петріка до таблиць покрить задач 6, 7, обґрунтувати доцільність його використання для скорочених таблиць покрить.

Виконати мінімізацію заданих у задачі 6 булєвих функцій методом Блейка-Порецького для ДНФ.

Виконати мінімізацію заданих у задачі 7 булєвих функцій методом Блейка-Порецького для КНФ.

Порівняти ціни по Квайну МДНФ і МКНФ, отриманих у задачах 6 і 7 (чи 9 і 10, тому що результати повинні бути тотожні). Виконати аналітичне перетворення МДНФ у МКНФ і навпаки, переконавши в тотожності формул і правильності виконання мінімізації.

Виконати графічну мінімізацію заданих на рис. 3.3. частково визначених булєвих функцій від трьох перемінних, вважаючи світлі виділені вершини відповідними конституентам одиниці, а темні виділені вершини – байдужним наборам.

a b

Рис. 3.3. Графічне завдання частково визначених булєвих функцій

Виконати графічну мінімізацію заданих на рис. 3.3. частково визначених булєвих функцій від трьох перемінних, вважаючи світлі виділені вершини відповідними конституентам нуля, а темні виділені вершини – байдужним наборам.

Виконати мінімізацію заданих часткових булєвих функцій від чотирьох перемінних за допомогою карт Карно:

a

Таблиця 3.10

x1,x2 x3x4
	х			х
		Х		Х

b

Таблиця 3.11

x1,x2 x3x4
				х
		Х		Х
				Х
	Х

 

Виконати мінімізацію заданих чисельним методом часткових булєвих функцій для ДНФ за допомогою методів Квайна-МакКласки і Петріка, застосувавши метод Петріка до скороченої таблиці покрить:

Ú(0, 2, 3, 6, 7, 10, 11, 12, 13), ´(8, 14, 15);

Ú(0, 2, 4, 5, 6, 8, 9, 10, 12, 14), ´(7, 11, 15);

Ú(2, 3, 5, 8, 10, 11, 12, 13), ´(1, 7, 9);

Ú(2, 5, 8, 10, 11, 14, 15), ´(0, 7, 13).

Вирішити задачу 15 для КНФ тих же часткових булєвих функцій, заданих чисельним методом, за допомогою методів Квайна-МакКласки і Петріка, застосувати метод Петріка до скороченої таблиці покрить:

Ù(1, 4, 5, 9), ´(8, 14, 15);

Ù(1, 3, 13), ´(7, 11, 15);

Ù(0, 4, 6, 14, 15), ´(1, 7, 9);

Ù(1, 3, 4, 6, 9, 12), ´(0, 7, 13).

Виконати мінімізацію заданих у задачі 15 часткових булєвих функцій методом Блейка-Порецького для ДНФ.

Виконати мінімізацію заданих у задачі 16 часткових булєвих функцій методом Блейка-Порецького для КНФ.

Порівняти ціни по Квайну для МДНФ і МКНФ, отриманих у задачах 15 і 16 (чи 17 і 18, тому що результати повинні бути тотожні). Виконати аналітичне перетворення МДНФ у МКНФ і навпаки, переконавши в необов'язковій тотожності формул, пояснити причину нетотожності.

Логіка предикатів

Задачі

На безлічі натуральних чисел визначені предикати P(x) = «число х поділяється на 8» і Q(x) = «х – парне число». Необхідно визначити наступні висловлення і з'ясувати які з них щирі:

"xP(x);

$xP(x);

"xQ(x);

$xù(Q(x));

"xù(Q(x));

"x(P(x)®Q(x));

"x(Q(x)®P(x));

$x(Q(x)®P(x)).

Нехай Х – безліч прямих на площині. На цій безлічі визначені предикати R(x, y) = «пряма х перетинається з прямой у», S(x, y) = «пряма х рівнобіжна прямої у», причому х,уÎХ. Необхідно визначити наступні висловлення і з'ясувати які з них щирі:

"x$yR(x, y);

$x$yù(S(x, y));

"x"y(R(x, y)®ù(S(x, y)));

"x"y(R(x, y)ÚS(x, y)).

На безлічі натуральних чисел визначені предикати P(x) = «число х - просте» і Q(x) = «х – парне число», R(x, y) = «х не дорівнює y». Необхідно перевести на розмовну мову формулу:

$x(P(x)ÙQ(x))Ù`$x(P(x)ÙQ(x)Ù$y(R(x, y)ÙP(y)ÙQ(y))).

Записати формули логіки предикатів для приведених тверджень:

«Кожен студент чи вивчає англійську мову, чи німецьку, чи французьку»;

«Деякі лабораторні стенди укомплектовані осцилографами»;

«Не всі комп'ютери працюють добре»;

«Жоден процесор не виявився забракованим»;

«Усі студенти, що виконали завдання, здали залік».

Граф G = (V, E) визначається завданням непорожньої безлічі вершин V, безлічі ребер Е і тримісного предиката P(x, e, y) = «ребро е з'єднує вершини х и у», що визначений на всіх упорядкованих трійках (x, e, y), причому х, уÎV і еÎЕ (для орграфа х вважається початкової вершиною дуги е, а y – кінцевою вершиною дуги е). Необхідно визначити предикати, що задають твердження:

«Підмножина дуг орграфа, що виходять з вершини а»;

«Підмножина дуг орграфа, що входять у вершину а»;

«Підмножина ребер графа, інцидентних вершині а»;

«Підмножина ребер графа, що з'єднує вершини а і b».

Відповідно до визначень графів із задачі 5 необхідно визначити висловлення для предикатів, показати, що для кожного е істинно одне і тільки одне з них, і назвати в термінології графів підмножини безлічі Е, що відповідають цим висловленням:

$x, y(x¹yÙP(x, e, y)Ùù(P(y, e, x)));

$x(P(x, e, x));

$x, y(x¹yÙP(x, e, y)Ù(P(y, e, x))).

ГРАФИ