Рис. 2.9

С помощью рассмотренных связок можно построить схему для функции f(x1, x2, x3, x4), истинной на наборах 1, 3, 5, 10 и 14 методом непосредственного моделирования. Построим минимальную дизъюнктивную форму и вынесем за скобки общие множители:

МДНФ = x1 x2 x4 + x1 x3 x4 +x1 x3 x4 = x1 x4 ( x2 + x3 )+x1 x3 x4 .

Схема, полученная непосредственным моделированием, полностью совпадает с предыдущей схемой и приведена на рисунке 2.8.

Контрольные вопросы и задания

2.1.Даны три высказывания: А – «Идет дождь», В – «Ветрено»,

С– «Ясно». Формализовать следующее сложное высказывание:

85

«Неверно, что ясно бывает тогда и только тогда, когда дует ветер или идет дождь».

2.2.Даны три высказывания: А – «Идет дождь», В – «Ветрено»,

С– «Ясно». Формализовать следующее сложное высказывание: «Ясная погода является необходимым условием для отсутствия дождя или отсутствия ветра».

2.3.Даны три высказывания: А – «Идет дождь», В – «Ветрено»,

С– «Ясно». Формализовать следующее сложное высказывание: «Ясная погода является необходимым и достаточным условием для отсутствия дождя или отсутствия ветра».

2.4.Даны три высказывания: А – «Идет дождь», В – «Ветрено»,

С– «Ясно». Формализовать следующее сложное высказывание: «Ясная погода является достаточным условием для отсутствия дождя или отсутствия ветра».

2.5.Определить, какие высказывания являются ложными:

•«Ромб – частный случай параллелограмма»;

•«Квадрат – частный случай ромба»;

•« 1200 < 34 »;

•« 700 < 26»;

•«Если натуральное число делится на 3 и 4, то оно делится и на

6».

2.6. Построить таблицу истинности функции:

f (a,b,c) = a b c → a .

2.7. Даны две функции, f1 и f2. Определить, являются ли они двойственными друг другу:

f1 (a,b,c) = a b c + a b + a c ,

f2 (a,b,c) = (c → (a +b)) → a (c →b) .

2.8. Даны две функции, F1 и F2. Определить, являются ли они равносильными друг другу:

F1(a, b, c) = 1{000, 001,011,101,100.111},

F2(a, b, c) = b → c.

2.9. Дана логическая функция (x1 → x2 ) → x3 → x1 . Построить

для нее:

1) таблицу истинности;

86

2) совершенную ДНФ;

3)совершенную КНФ.

2.10.Дана логическая функция x3 → ((x1 → x2 ) → x3 → x1 . По-

строить для нее:

1) таблицу истинности;

2)совершенную ДНФ;

3)совершенную КНФ.

2.11.Дана логическая функция ((x1 → x2 ) → x3 ) → x3 → x1 . По-

строить для нее:

1) таблицу истинности;

2)совершенную ДНФ;

3)совершенную КНФ;

2.12.Для функции f (x1 , x2 , x3 ) = (x1 (x2 x3 )) x1 , используя

аналитический вывод, построить совершенную дизъюнктивную нормальную форму (СДНФ).

2.13.Для функции f (x1, x2 , x3 ) = x1 → x2 → x3 → x1 , используя аналитический вывод, построить совершенную дизъюнктивную нормальную форму (СДНФ).

2.14.Для функции f (x1 , x2 , x3 ) = (x1 → x2 ) → (x2 → x3 ) , используя аналитический вывод, построить совершенную конъюнктив-

ную нормальную форму (СКНФ).

2.15.Построить минимальную ДНФ с помощью метода Квайна

–МакКласки для функции f(a, b, c)=1{000, 001, 011, 101, 100, 111},

заданной своей областью истинности.

2.16.Построить минимальную ДНФ с помощью метода Квайна

–МакКласки для функции f = 1{0000, 0001, 0010, 0011,1100, 1101}.

2.17.Построить минимальную ДНФ с помощью метода Квайна

–МакКласки для функции f = 1{0100, 0101, 0110, 0111,1000, 1001}.

2.18.Построить монотонную функцию от трех переменных, принадлежащую классу K0.

2.19.Построить линейную функцию от трех переменных, определить, принадлежит ли она классу K1.

2.20.Дана функция F1=1{001, 010, 100, 111}, заданная своей областью истинности. Определить, является ли она линейной.

87

2.21. Построить самодвойственную функцию от трех переменных, принадлежащую классу K1.

2.22. Определить, является ли монотонной функция

f(x1, x2 ,..., x127 ) = x1 x2 x3 x4 ...x126 x127 .

2.23.Доопределить функцию f(a, b, c), q1 = {100}, q0 = {010, 110},

таким образом, чтобы она стала полной.

2.24.Определить, является ли она самодвойственной функция F1=1{001, 010, 100, 111}, заданная своей областью истинности.

2.25.Дана функция f (a, b, c). Определить, к каким замкнутым классам она принадлежит.

a b c	f (a, b, c)
0 0 0	1
0 0 1	0
0 1 0	1
0 1 1	0
1 0 0	1
1 0 1	0
1 1 0	1
1 1 1	1

2.26. Дана функция f (a, b, c). Определить, каким замкнутым классам она принадлежит.

a b c	f (a, b, c)
0 0 0	1
0 0 1	0
0 1 0	1
0 1 1	0
1 0 0	1
1 0 1	0
1 1 0	1
1 1 1	0

2.27. Дана функция f (a, b, c). Определить, каким замкнутым классам она принадлежит?

88

a b c	f (a, b, c)
0 0 0	1
0 0 1	0
0 1 0	1
0 1 1	0
1 0 0	1
1 0 1	0
1 1 0	0
1 1 1	0

2.28. Дана функция f (a, b, c). Определить, каким замкнутым классам она принадлежит?

a b c	f (a, b, c)
0 0 0	0
0 0 1	0
0 1 0	1
0 1 1	0
1 0 0	1
1 0 1	0
1 1 0	1
1 1 1	1

2.29. Дана функция F1(a, b, c). Построить двойственную ей функцию F2(a, b, c).

a b c	F1(a, b, c)	F2(a, b, c)
0 0 0	1	?
0 0 1	0	?
0 1 0	1	?
0 1 1	0	?
1 0 0	1	?
1 0 1	0	?
1 1 0	1	?
1 1 1	1	?

89

2.30. Дана функция F1(a, b, c). Построить двойственную ей функцию F2(a, b, c).

a b c	F1(a, b, c)	F2(a, b, c)
0 0 0	1	?
0 0 1	0	?
0 1 0	1	?
0 1 1	0	?
1 0 0	1	?
1 0 1	0	?
1 1 0	1	?
1 1 1	0	?

2.31. Дана частично определенная функция f (a, b, c). Доопределить ее так, чтобы она сохраняла 0 и 1 и была самодвойственной.

a b c	f (a, b, c)
0 0 0	0
0 0 1	?
0 1 0	?
0 1 1	?
1 0 0	1
1 0 1	0
1 1 0	1
1 1 1	1

2.32. Дана частично определенная функция f (a, b, c). Доопределить ее так, чтобы она была монотонной.

a b c	f (a, b, c)
0 0 0	0
0 0 1	?
0 1 0	?
0 1 1	1
1 0 0	?
1 0 1	1
1 1 0	1
1 1 1	1

90

2.33. Дана частично определенная функция f (a, b, c). Доопределить ее так, чтобы она была полной.

a b c	f (a, b, c)
0 0 0	?
0 0 1	?
0 1 0	?
0 1 1	0
1 0 0	?
1 0 1	0
1 1 0	0
1 1 1	1

2.34. Дана частично определенная функция f (a, b, c). Доопределить ее так, чтобы она была полной.

a b c	f (a, b, c)
0 0 0	?
0 0 1	?
0 1 0	?
0 1 1	0
1 0 0	?
1 0 1	0
1 1 0	0
1 1 1	0

2.35. Дана частично определенная функция f (a, b, c). Доопределить ее так, чтобы она была линейной.

a b c	f (a, b, c)
0 0 0	?
0 0 1	?
0 1 0	?
0 1 1	0
1 0 0	?
1 0 1	1
1 1 0	0
1 1 1	1

91

2.36. Дана частично определенная функция f (a, b, c). Доопределить ее так, чтобы она была полной.

a b c	f (a, b, c)
0 0 0	?
0 0 1	?
0 1 0	?
0 1 1	0
1 0 0	?
1 0 1	0
1 1 0	1
1 1 1	0

2.37. Определить, является ли линейной функция

f (x1,x2,...,x127 ) x1 x2 x3 x4 ... x126 x127 .

2.38. Определить, является ли линейной функция

f (x1,x2,...,x127 ) x1 x2 x3 x4 ... x126 x127 .

2.39. Определить, является ли монотонной функция

f (x1,x2,...,x127 ) x1 x2 x3 x4...x126 x127 .

2.40.Какими свойствами обладает группоид M, ?

2.41.Какими свойствами обладает группоид M, ?

2.42.Какими свойствами обладает группоид M,& ?

2.43.Какими свойствами обладает группоид M, ?

2.44.Какими свойствами обладает алгебра M, ,0 ?

2.45.Какими свойствами обладает алгебра M, ,0 ?

2.46.Доопределить f таким образом, чтобы группоид A = < M, f> стал абелевой полугруппой.

2.47.Является ли группоид A = < M, → > полугруппой?

2.48.Является ли группоид A M, абелевым?

2.49.Является ли группоид A = < M, | > идемпотентным.

2.50.Определить, является ли алгебра A M, , кольцом?

2.51.Определить, является ли алгебра A M, ,0 телом?

2.52.Задать свойства f1 и f2 таким образом, чтобы алгебра A = =<M, f1, f2> стала кольцом.

2.53.Задать свойства f1 и f2 таким образом, чтобы алгебра A = =<M, f1, f2> стала телом.

92