ГЛАВА 3 Булевы функции.

Глава 2.

41.Если множество А является декартовым произведением n множеств, то аргументом функции f: A®B является

1) упорядоченная n-ка.+

2) строго упорядоченная n-ка.

3) линейно упорядоченная n-ка.

4) частично упорядоченная n-ка.

42.Функцию j: Сⁿ®С называют

1) n-показательной.

2) n-степенной.

3) n-арной.+

4) n-аргументной.

43.Предикатом от n аргументов называется функция

1) с областью определения С´С´…´С, n³3, и областью значений, равной множеству {И,Л}.

2) с областью определения С´С´…´С, n³1, и областью значений, равной множеству {И,Л}.+

3) с областью определения С´С´…´С, n³1, и областью значений, равной множеству {М,Л}.

4) с областью определения С´С´…´С, n³1, и областью значений, равной множеству {Л,М}.

44.n-местный предикат Р отображает Сⁿ в (на) множество

1){И,Л}.+

2) {Л,И}.

3) {М,Л}.

4) {Л,М}.

45.Пусть С=(-¥,¥), А=С´С и Р(х,у) обозначает х>у. Тогда

1) Р(3,1)=И, Р=(3,5)=Л.+

2) Р(3,1)=Л, Р=(3,5)=И.

3) Р(3,1)=И, Р=(3,5)=И.

4) Р(3,1)=Л, Р=(3,5)=Л.

46.Алгебраической системой называют

1) непустое множество А с введенными на этом множестве предикатами.

2) непустое множество А с введенными на этом множестве операциями.

3) пустое множество А с введенными на этом множестве операциями и предикатами.

4) непустое множество А с введенными на этом множестве операциями и предикатами.+

47.Алгебраическая система áА;W_F,W_Pñ называется алгеброй, если

1) W_Р¹Æ и W_F=Æ.

2) W_Р=Æ и W_F=Æ.

3) W_Р¹Æ и W_F¹Æ.

4) W_Р=Æ и W_F¹Æ.+

48. Алгебраическая система áА;W_F,W_Pñ называется моделью, если

1) W_Р¹Æ и W_F=Æ.+

2) W_Р=Æ и W_F=Æ.

3) W_Р¹Æ и W_F¹Æ.

4) W_Р=Æ и W_F¹Æ.

49.Алгебра-непустое множество А, на котором задана совокупность операций, переводящих элементы

1) из А в А.+

2) из А в В.

3) из В в А.

4) из В в В.

50.Пусть имеем алгебру с n операциями F₁,F₂,…,F_n и пусть m_i число аргументов операции F_i(1£i£n).Тогда вектор t=(m₁,m₂,…,m_n) называют

1) типом алгебры.+

2) элементом алгебры.

3) носителем алгебры.

4) множество алгебры.

51.Подмножество В множества А называется замкнутым относительно операции F_i переводит элементы

1) из В в А.

2) из В в В.+

3) из А в А.

4) из А в В.

52.Пусть имеем алгебру áА;W_Fñ, здесь

1) W_F-множество n операции на непустом множестве А.+

2) W_F-подмножество n операции на непустом множестве А.

3) W_F- множество n операции на пустом множестве А.

4) W_F- подмножество n операции на пустом множестве А.

53.Если подмножество В (ВÍА) замкнуто относительно всех операций алгебры, то В=áВ;W_Fñ называют

1) подалгеброй алгебры áВ, W_Fñ.

2) подмножество алгебры áВ, W_Fñ.

3) подмножество алгебры áА, W_Fñ.

4) подалгеброй алгебры áА, W_Fñ.+

54.Пусть А=[0,¥) и введем операции сложения (+) и умножения (´). Множество натуральных чисел N содержится в А замкнуто относительно операций + и ´. Поэтому

1) N порождает подмножество в алгебре á[0,¥);+,´ñ.

2) N порождает подалгебру в алгебре á[0,¥);+,´ñ.+

3) N порождает подалгебру в алгебре á[0,¥);+ñ.

4) N порождает подмножество в алгебре á[0,¥);+ñ.

55.Пересечение любой совокупности подалгебр данной алгебры

1) либо непусто, либо является подалгеброй данной алгебры.

2) либо пусто, либо является подалгеброй данной алгебры.+

3) либо непусто, либо является подмножеством данной алгебры.

4) либо пусто, либо является подмножество данной алгебры.

56.Всякое отображение j основного множества А в(на) основное множество В называем

1) отображением алгебры А в(на) алебру В.+

2) изоморфизмом алгебры А в(на) алебру В.

3) гоморфизмом алгебры А в(на) алебру В.

4) отображением алгебры А в(на) алебру А.

57.Изоморфизмом алгебры А=áА; F₁, F₂,…, F_nñ в(на) однотипную алгебру В=áВ; G₁,G₂,…,G_nñ называется взаимно однозначное (биективное) отображение j

1) множество А в(на) В, сохраняющее главные операции алгебры.+

2) множество А в(на) А, сохраняющее главные операции алгебры.

3) множество В в(на) В, сохраняющее главные операции алгебры.

4) множество А, сохраняющее главные операции алгебры.

58.Гоморфизмом алгебры А=áА; F₁, F₂,…, F_nñ в(на) однотипную алгебру В=áВ; G₁,G₂,…,G_nñ называется отображенеие j

1) множества В в(на) множество В, сохраняющее главные операции алгебры.

2) множества А в(на) множество А, сохраняющее главные операции алгебры.

3) множества А в(на) множество В, несохраняющее главные операции алгебры.

4) множества А в(на) множество В, сохраняющее главные операции алгебры.+

59.Изоморфизм алгебры на себя называется

1) автоизоморфизм.

2) автоморфизм.+

3) автогоморфизм.

4) морфизм.

60.Отображение j: А®В сохраняет операцию, но это отображение не является изоморфным, так как различные матрицы могут иметь

1) одинаковый определитель.+

2) различный определитель.

3) одинаковый и различный определитель.

4) пустой определитель.

61.Самой простой алгеброй является

1) пустое множество G с двумя двуместной (бинарной) операцией.

2) непустое множество G с двумя двуместной (бинарной) операцией.

3) пустое множество G с одной двуместной (бинарной) операцией.

4) непустое множество G с одной двуместной (бинарной) операцией.+

62.Множество с одной двуместной операцией называют

1) пустая группа.

2) полугруппа.

3) группа.

4) группоид.+

63.Множество G, на котором введена одна ассоциативная двуместная (бинарная) операция

1) пустая группа.

2) полугруппа.+

3) группа.

4) группоид.

64.Моноид-это

1) пустая группа.

2) полугруппа с единицей.+

3) группа с единицей.

4) группоид.

65.Всякий моноид над множеством М изоморфен некоторому моноиду преобразований над

1) М.+

2) А

3) В

4) G

66.Группа-это моноид, в котором для любого элемента существует

1) группа элементов.

2) прямой элемент.

3) обратный элемент.+

4) полугруппа элементов.

67.Множество G с одной бинарной операций “°” называем группой, если:

1) существует единица в G,для любого элемента аÎG существует обратный элемент.

2) операция ассоциативна, для любого элемента аÎG существует обратный элемент.

3) операция ассоциативна, существует единица в G,для любого элемента аÎG существует обратный элемент.+

4) операция ассоциативна, существует единица в G.

68.Если операция в группе называется умножением, то группа называется

1) мультипликативной.+

2) аддитивной.

3) пликативной.

4) дитивной.

69.Если групповая операция называется сложением, то группа называется

1) мультипликативной.

2) аддитивной.+

3) пликативной.

4) дитивной.

70.Группа с одной образующей называется

1) коммутативной.

2) образующей.

3) циклической.+

4) абелевой.

71.Кольцом называется непустое множество R, на котором введены

1) одна бинарная операции °.

2) одна бинарная операции +.

3) две бинарные операции + и °.+

4) две бинарные операции + и -.

72.Кольцо называется коммутативным, если для

1) "a,bÎR:a°b=b°a.+

2) $a,bÎR:a°b=b°a.

3) "a,bÏR:a°b=b°a.

4) $a,bÏR:a°b=b°.

73.Коммутативное кольцо без делителей нуля, отличных от тривиального делителя нуля, называют

1) множественным кольцом.

2) элементным кольцом.

3) образующим кольцом.

4) целостным кольцом.+

74.Если в кольце R имеем, что a°b=0, то элемент 0 считаем

1) тривиальным делителем.+

2) левым делителем.

3) правым делителем.

4) бинарным делителем.

75. Если в кольце R имеем, что a°b=0, то a называется

1) тривиальным.

2) левым.+

3) правым.

4) бинарным.

76. Если в кольце R существует единица относительно умножения, то эту мультипликативную единицу обозначают через

1) 1 и 0.

2) 0.

3) 1.+

4) °.

77.Элементы 0 и 1 являются

1) различными элементами нулевого кольца R.

2) одинаковыми элементами нулевого кольца R.

3) одинаковыми элементами ненулевого кольца R.

4) различными элементами ненулевого кольца R.+

78.Аддитивная единица, то есть

1) 1, не имеет аддитивного обратного.

2) 0, не имеет аддитивного обратного.

3) 1, не имеет мультипликативного обратного.

4) 0, не имеет мультипликативного обратного.+

79.Характеристикой кольца R называют наименьшее натуральное число k такое, что

1) a+a+…+a=0 для всех aÎR.+

2) a+a+…+a=0 для всех aÏR.

3) a-a-…-a=0 для всех aÎR.

4) a-a-…-a=0 для всех aÏR.

80.Характеристика кольца записывается

1) k=charR.+

2) k=setR.

3) k=resetR.

4) k=gradR.

81.Полем называется коммутативное кольцо

1) у которого нулевые элементы образуют коммутативную группу относительно сложения.

2) у которого ненулевые элементы образуют коммутативную группу относительно сложения.

3) у которого нулевые элементы образуют коммутативную группу относительно умножения.

4) у которого ненулевые элементы образуют коммутативную группу относительно умножения.+

82.Поле-это множество P с двумя бинарными операциями

1) + и °.+

2) + и -.

3) ° и /.

4) / и -.

83.Если a¹0, то в поле единственным образом разрешимо уравнение

1) a+x=b.

2) a-x=b.

3) a°x=b.+

4) a/x=b.

84.Для любого ненулевого элемента (а¹0) существует

1) обратный элемент по умножению.+

2) прямой элемент по умножению.

3) обратный элемент по сложению.

4) прямой элемент по сложению.

85.áR;+,xñ-это

1) поле рациональных чисел.

2) поле вещественных чисел.+

3) поле комплексных чисел.

4) поле иррациональных чисел.

86.Решетки иногда называют

1) списками.

2) графами.

3) структурами.+

4) таблицами.

87.Решетка-это множество М с двумя бинарными операциями

1) + и Ç.

2) Ç и È.+

3) È и °.

4) + и °.

88.Если в решетке $ 0ÎМ, что для "а: 0Çа=0, то 0 называется

1) нижней гранью.+

2) средней гранью.

3) верхней гранью.

4) гранью.

89.В ограниченной решетке элемент а’ называется дополнением элемента а,если

1) aÇa’=1 и aÈa’=1.

2) aÇa’=0 и aÈa’=1.+

3) aÇa’=0 и aÈa’=0.

4) aÇa’=1и aÈa’=0.

90.Пусть a£b Û aÇb=a.Тогда отношение £ является отношением

1) частичного порядка.+

2) полного порядка.

3) выборочного порядка.

4) нулевого порядка.

91.Дистрибутивная ограниченная решетка, в которой для каждого элемента существует дополнение, называется

1) алгеброй.

2) булевой.

3) булевой алгеброй.+

4) дистрибутивной алгеброй.

92.М¹Æ, á2^м,È,Ç,-ñ, здесь

1) 1¹2^м,0¹Æ, А£В Û АÍВ.

2) 1¹2^м,0=Æ, А£В Û АÍВ.

3) 1=2^м,0¹Æ, А£В Û АÍВ.

4) 1=2^м,0=Æ, А£В Û АÍВ.+

93.Так как дополнение существует, то

1) аÈa’=0, aÇa’=0.

2) аÈa’=1, aÇa’=1.

3) аÈa’=0, aÇa’=1.

4) аÈa’=1, aÇa’=0.+

94.По теореме о свойствах дополнения

1) а”=a.+

2) а”¹a.

3) а’=a.

4) а’¹a.

95.По следствию из теоремы ограниченности, следует что

1) аÈ1=а, аÇ0=а.

2) аÈ0=а, аÇ0=а.

3) аÈ0=а, аÇ1=а.+

4) аÈ1=а, аÇ1=а.

96.Матроидом М=áЕ;Хñ называется конечное множество Е, |Е|=n, и семейство его подмножеств Х, для

1) ХÍ2^Е.+

2) ЕÍ2^Х.

3) ХÊ2^Е.

4) ЕÊ2^Х.

97. Матроидом М=áЕ;Хñ называется конечное множество Е, что выполняется следующие аксиомы

1) ÆÎХ; АÎХ и ВÍА, то ВÎХ.

2) ÆÎХ; если А,ВÎХ и |В|=|А|+1,то $е, еÎВ\А, такой, что АÈ{e}ÎХ.

3) АÎХ и ВÍА, то ВÎХ; А,ВÎХ; если А,ВÎХ и |В|=|А|+1,то $е, еÎВ\А, такой, что АÈ{e}ÎХ.

4) ÆÎХ; АÎХ и ВÍА, то ВÎХ; А,ВÎХ; если А,ВÎХ и |В|=|А|+1,то $е, еÎВ\А, такой, что АÈ{e}ÎХ.+

98.График одноаргументной функции у=f(x) (хÎА, уÎА) является

1) объектом декартового произведения А´А..

2) элементом декартового произведения А´А..

3) множеством декартового произведения А´А..

4) подмножеством декартового произведения А´А,+

99.Матроидом называется конечное множество Е и семейство С={С₁,С₂,С₃,…,С_m}

1) непустых множеств множества Е, называемых циклами.

2) пустых подмножеств множества Е, называемых циклами.

3) непустых подмножеств множества Е, называемых циклами,+

4) пустых подмножеств множества Е, называемых циклами.

100.Какие аксиомы справедливы для цикла

1) ни одно собственное подмножество цикла есть цикл; если хÎ(С₁ÇС₂), то (С₁ÈС₂)\{х} содержит цикл.

2) ни одно собственное подмножество цикла не есть цикл; если хÎ(С₁ÇС₂), то (С₁ÈС₂)\{х} содержит цикл,+

3) одно собственное подмножество цикла не есть цикл; если хÎ(С₁ÇС₂), то (С₁ÈС₂)\{х} содержит цикл.

4) если хÎ(С₁ÇС₂), то (С₁ÈС₂)\{х} содержит цикл.

ГЛАВА 3 Булевы функции.

101.Булевой переменной называется переменная, имеющая только

1) Одно возможное значение.

2)Два возможных значения.+

3) Три возможных значения.

4) Четыре возможных значения.

102.Функция f(x₁,x₂,…,x_n) называется булевой (преключительной) функцией, если она может принимать

1) только одно из двух.+

2) два из двух.

3)ни одно из двух.

4) из двух.

103.Булеву функцию можно задать таблицей ее значений, которая и называется

1) таблицей истинности.+

2) таблицей ложности.

3) таблицей отрицания.

4) таблицей значения.

104.Функция (хÞу) называется

1) эквивалентности.

2) сложением по модулю два.

3) импликацией.+

4) конъюнкцией.

105.Функция (хºу) называется

1) эквивалентности.+

2) сложением по модулю два.

3) импликацией.

4) конъюнкцией.

106.С помощью чего можно задавать булевы функции

1) теорем.

2) аксиом.

3) формул.+

4) понятий.

107.Каждая булева переменная (х,y,z,…,x₁,x₂,…) является

1) формулой.+

2) функцией.

3) множеством.

4) элементом.

108.Если А и В формулы, то

1) (ØА), (А&В), (АÚВ), (АÞВ), (АºВ), (А|В) и (А¯В) тоже формулы.+

2) (ØА), (А&В), (АÚВ), (А|В) и (А¯В) тоже формулы.

3) (ØА), (А&В), (АÚВ), (АÞВ), (АºВ), (А|В) тоже формулы.

4) (ØА), (АÚВ), (АÞВ), (АºВ), (А|В) и (А¯В) тоже формулы.

109.Заглавные буквы латинского алфавита (А,В,С,…) или те же буквы с числовыми индексами (А₁,А₂,…,В₁,В₂,…,С₁,С₂,…) употребляются для обозначения

1) произвольных множеств.

2) произвольных функций.

3) произвольных элементов.

4)произвольных формул.+

110.Метод построения таблиц истинности называют алгоритмом

1)Кельвина.

2)Квайна.+

3)Эйвера.

4)Кулона.

111.Сколько всего соглашений о более экономном употреблении скобок в записях формул

1)1.

2)2.

3)3.+

4)4.

112.Если формула содержит вхождения только одной бинарной связки &,Ú,Þ или º, то для каждого вхождения этой связки опускаются внешние скобки у той

1) из одной формулы (соединяемых этим вхождением) которая стоит слева.

2)из двух формул(соединяемых этим вхождением) которая стоит слева.+

3) из трех формул(соединяемых этим вхождением) которая стоит слева.

4) из четырех формул(соединяемых этим вхождением) которая стоит слева.

113.Все ли формулы могут быть записаны без скобок

1) нет

2) да, при данном в задаче условии.

3)да.+

4) нет, при данном в задаче условии.

114.Какое вхождение знака относится к наименьшей формуле

1)Ø.+

2) |.

3) &.

4) ¯.

115.Для каких операций не указаны порядки их выполнения, поэтому последовательность их выполнения устанавливается с помощью скобок

1) |,&,Ú.

2) +,Ú,¯

3) &,¯,Ø.

4)+,|,¯.+

116.Формулы А и В называются равносильными, если при каждой совокупности значений всех переменных, входящих в А и В, эти формулы принимают

1) единичное значение.

2) нулевое значение.

3) различные значения.

4)одинаковые значения.+

117.Отношение равносильности формул, обладает следующими свойствами

1)рефлексивностью, симметричностью, транзитивностью.+

2) рефлексивностью, транзитивностью.

3) симметричностью, транзитивностью.

4) рефлексивностью, симметричностью.

118.Отношение равносильности является отношением

1) частичного порядка.

2) порядка.

3)эквивалентности.+

4) строгого порядка.

119.Формула называется тавтологией, если она

1)тождественно равна единице.+

2) тождественно не равна единице.

3) тождественно равна нулю.

4) тождественно не равна нулю.

120. Формула называется противоречивой, если она

1)тождественно равна единице.

2) тождественно не равна единице.

3) тождественно равна нулю.+

4) тождественно не равна нулю.

121.Сколько соотношении в свойствах(законах) булевых переменных

1) 5.

2) 10.

3) 15.

4) 20.+

122.С помощью чего доказываются булевы соотношения

1) таблицей истинности.+

2) таблицей ложности.

3) таблицей отрицания.

4) таблицей значения.

123.Булевы соотношения будут иметь место и тогда, когда вместо переменных x,y и z будут подставлены

1) произвольные множества.

2) произвольные функции.

3) произвольные элементы.

4)произвольные формулы.+

124.Какой из данных свойств(законов) является коммутативным

1) х&у~у&х, хÚу~уÚх.+

2) (х&у)&z~x&(у&z), (хÚу)Úz~xÚ(уÚz).

3) Ø(х&у)~ØхÚØу, Ø(хÚу)~Øх&Øу.

4) х&х~х, хÚх~х.

125.Какой из данных свойств(законов) является де Моргана

1) х&у~у&х, хÚу~уÚх.

2) (х&у)&z~x&(у&z), (хÚу)Úz~xÚ(уÚz).

3) Ø(х&у)~ØхÚØу, Ø(хÚу)~Øх&Øу.+

4) х&х~х, хÚх~х.

126.Операции (связки) Ø,&,Ú,Þ,º,+,| и ¯ не являются независимыми друг от друга в том смысле, что одни из них можно выражать через другие так, что при этом получаются

1) произвольные формулы.

2) равносильные формулы.

3) порядковые формулы.

4) частичные формулы.

127.Для каждой формулы А существует равносильная ей формула, содержащая только связки

1) +,&,|.

2) &,Ø,¯.

3) Ú,+,¯.

4)Ø,&,Ú.+

128. Для каждой формулы А существует равносильная ей формула, содержащая

1) либо только связки Ø,&, либо только Ø,Ú, либо только Ø,Þ.+

2) либо только связки Ø,&, либо только Ø,Ú.

3) либо только связки Ø,&, либо только Ø,Þ.

4) либо только связки Ø,Ú, либо только Ø,Þ.

129.Если формулы А и В равносильны, то и двойственные им формулы равносильны при

1) А и В.

2) А* и В*.+

3) А* и В.

4) А и В*.

130.Формулы А и А* называются двойственными, если одна получается из другой заменой каждой связки

1) Ú и Ú на двойственную.

2) & и + на двойственную.

3) & и Ú на двойственную.+

4) ¯ и Ú на двойственную.

131.Какой из данных свойств(законов) является штрих Шеффера

1) х¯у=Ø(хÚу).

2) (х&у)&z~x&(у&z), (хÚу)Úz~xÚ(уÚz).

3) Ø(х|у)~ØхÚØу, Ø(хÚу)~Øх&Øу.

4) х|у=Ø(х&у).+

132.Какой из данных свойств(законов) является стрелка Пирса

1) х¯у=Ø(хÚу).+

2) (х&у)&z~x&(у&z), (хÚу)Úz~xÚ(уÚz).

3) Ø(х|у)~ØхÚØу, Ø(хÚу)~Øх&Øу.

4) х|у=Ø(х&у).

133.Для каждой формулы существует равносильная ей формула, содержащая

1) только связку |, либо только связку ¯.+

2) только связку |.

3) только связку ¯.

4) связку | и связку ¯.

134.Единственными бинарными связками, каждой из которых достаточно для выражения всех формул, являются связки

1) ¯ и &.

2) & и Ú.

3) ¯ и |.+

4) Ú и |.

135.Каким знаком определяется штрих Шеффера

1) |.+

2) &.

3) ¯.

4) Ú.

136.Элементарной суммой называют дизъюнкцию

1) булевых переменных.

2) булевых переменных либо их произведение.

3) булевых переменных либо их сумму.

4)булевых переменных либо их отрицаний.+

137.Слагаемые элементарной суммы называются

1) литералами.+

2) дизъюнкцией.

3) конъюкцией.

4) конституентами.

138.Среди элементарных сумм, которые можно составить из данных переменных х₁,х₂,…,х_n входит один и только один раз либо без знака отрицания, либо со знаком отрицания, такие элементарные суммы называют

1) литералами.+

2) дизъюнкцией.

3) конъюкцией.

4) конституентами нуля.

139.Какая из этих формул вида является конституентой нуля

1) х^|₁&х^|₂&…&х^|_n.

2) х^|₁Úх^|₂&…&х^|_n.

3)х^|₁Úх^|₂Ú…Úх^|_n.+

4) х^|₁&х^|₂Ú…Úх^|_n.

140. Какая из этих формул вида является конституентой единицы

1) х^|₁&х^|₂&…&х^|_n.+

2) х^|₁Úх^|₂&…&х^|_n.

3)х^|₁Úх^|₂Ú…Úх^|_n.

4) х^|₁&х^|₂Ú…Úх^|_n.

141.Дизъюнкцией нормальной формой (д.н.ф.) называется дизъюнкция

1) элементарных произведений.+

2) элементарных разниц

3) элементарных сумм.

4) элементарных отрицаний.

142.Конъюктивной нормальной формой (к.н.ф.) называется конъюкция

1) элементарных произведений.

2) элементарных разниц

3) элементарных сумм.+

4) элементарных отрицаний.

143.Для того, чтобы формула А была противоречивым, необходимо и достаточно, чтобы равносильная ей д.н.ф. содержала в каждом слагаемом хотя бы одну пару множителей, из которых

1) один некоторая произвольная, а второй суммирование этой произвольной.

2) один некоторая переменная, а второй отрицание этой переменной.+

3) один некоторая произвольная, а второй отрицание этой произвольной.

4) один некоторая переменная, а второй суммирование этой переменной.

144.Формула А будет выполнимой, если равносильная ей д.н.ф. содержит хотя бы одно слагаемое, в котором нет таких множителей, что

1) один некоторая произвольная, а второй суммирование этой произвольной.

2)один некоторая переменная, а второй отрицание этой переменной.+

3) один некоторая произвольная, а второй отрицание этой произвольной.

4) один некоторая переменная, а второй суммирование этой переменной.

145.Для того, чтобы формула А была тавтологией, необходимо и достаточно, чтобы равносильная ей к.н.ф. содержала в каждом множителе

1) хотя бы одну переменную вместе с отрицанием этой переменнной.+

2) хотя бы две переменные вместе с отрицанием этих переменнных.

3) хотя бы три переменные вместе с отрицанием этих переменнных.

4) хотя бы четыре переменные вместе с отрицанием этих переменнных.

146.С помощью чего можно задавать булеву функцию

1) табличным и графическим способом, порождающей процедурой.

2) табличным и графическим способом, словесным описанием, порождающей процедурой или в аналитическом виде.+

3) графическим способом, словесным описанием, порождающей процедурой или в аналитическом виде.

4) табличным и словесным описанием, порождающей процедурой или в аналитическом виде.

147.Для любой булевой функции f(x₁,x₂,…,x_n) и любого m, 1£ m£n, имеет место следующее равенство, где дизъюнкция берется по всем возможным наборам (а₁,а₂,…,а_m):

1) f(x₁,x₂,…,x_m,x_m+1,…,x_n)= V_{(a1,a2,…,am)} x₁^a1Úx₂^a2Ú…Úx_m^amÚf(a₁,a₂,…,a_m,x_m+1,…,x_n).

2) f(x₁,x₂,…,x_m,x_m+1,…,x_n)= V_{(a1,a2,…,am)} x₁^a1&x₂^a2Ú…Úx_m^am&f(a₁,a₂,…,a_m,x_m+1,…,x_n).

3) f(x₁,x₂,…,x_m,x_m+1,…,x_n)= V_{(a1,a2,…,am)} x₁^a1Úx₂^a2&…&x_m^am&f(a₁,a₂,…,a_m,x_m+1,…,x_n).

4) f(x₁,x₂,…,x_m,x_m+1,…,x_n)= V_{(a1,a2,…,am)} x₁^a1&x₂^a2&…&x_m^am&f(a₁,a₂,…,a_m,x_m+1,…,x_n).+

148. Для любой булевой функции f(x₁,x₂,…,x_n) и любого m, 1£ m£n, имеет место следующее равенство, где конъюнкция берется по всем возможным наборам (а₁,а₂,…,а_m):

1) f(x₁,x₂,…,x_m,x_m+1,…,x_n)= &_{(a1,a2,…,am)} x₁^a1Úx₂^a2Ú…Úx_m^amÚf(a₁,a₂,…,a_m,x_m+1,…,x_n).+

2) f(x₁,x₂,…,x_m,x_m+1,…,x_n)= V_{(a1,a2,…,am)} x₁^a1&x₂^a2Ú…Úx_m^am&f(a₁,a₂,…,a_m,x_m+1,…,x_n).

3) f(x₁,x₂,…,x_m,x_m+1,…,x_n)= &_{(a1,a2,…,am)} x₁^a1Úx₂^a2&…&x_m^am&f(a₁,a₂,…,a_m,x_m+1,…,x_n).

4) f(x₁,x₂,…,x_m,x_m+1,…,x_n)= V_{(a1,a2,…,am)} x₁^a1&x₂^a2&…&x_m^am&f(a₁,a₂,…,a_m,x_m+1,…,x_n).

149.Представление функции f в виде (смотри вопрос 147) называют разложением

1) Квайна.

2)Шеннона.+

3) Пирса.

4) де Моргана.

150.Если f(х₁,х₂,…,х_n) не тождественно равна 0, где дизъюнкция берется только по тем наборам (a₁,a₂,…,a_n), для которых f(а₁,а₂,…,а_n)=1, то:

1) f(x₁,x₂,…,x_n)=Ú_{(a1,a2,…,an)}x₁^a1&x₂^a2&…&x_n^an.+

2) f(x₁,x₂,…,x_n)=&_{(a1,a2,…,an)}x₁^a1Úx₂^a2Ú…Úx_n^an.

3) f(x₁,x₂,…,x_n)=&_{(a1,a2,…,an)}x₁^a1&x₂^a2&…&x_n^an.

4) f(x₁,x₂,…,x_n)=Ú_{(a1,a2,…,an)}x₁^a1Úx₂^a2Ú…Úx_n^an.

151. Если f(х₁,х₂,…,х_n) не тождественно равна 1, где конъюнкция берется только по тем наборам (a₁,a₂,…,a_n), для которых f(а₁,а₂,…,а_n)=0, то:

1) f(x₁,x₂,…,x_n)=Ú_{(a1,a2,…,an)} (x₁^1-а1&x₂^1-а2&…&x_n^1-аn)

2) f(x₁,x₂,…,x_n)=&_{(a1,a2,…,an)} (x₁^1-а1Úx₂^1-а2Ú…Úx_n^1-аn).+

3) f(x₁,x₂,…,x_n)=&_{(a1,a2,…,an)} (x₁^1-а1&x₂^1-а2&…&x_n^1-аn)

4) f(x₁,x₂,…,x_n)=Ú_{(a1,a2,…,an)} (x₁^1-а1Úx₂^1-а2Ú…Úx_n^1-аn)

152.Правая часть разложения f(x₁,x₂,…,x_n)=Ú_{(a1,a2,…,an)}x₁^a1&x₂^a2&…&x_n^an называется

1) совершенной конъюнкцией нормальной формой.

2) элементарной конъюнктивной нормальной формой.

3)совершенной дизъюнктивной нормальной формой.+

4) элементарной дизъюнктивной нормальной формой.

153.Совершенной дизъюнктивной нормальной формой функции f(x₁,x₂,…,x_n) это д.н.ф. этой функции, удовлетворяющая следующим условиям:

1) в каждое слагаемое входят все переменные х₁,х₂,…,x_n один и только один раз (и только они) с отрицанием либо без отрицания.

2) нет одинаковых слагаемых.

3) есть одинаковое слагаемое; в каждое слагаемое входят все переменные х₁,х₂,…,x_n один и только один раз (и только они) с отрицанием либо без отрицания.

4) нет одинаковых слагаемых; в каждое слагаемое входят все переменные х₁,х₂,…,x_n один и только один раз (и только они) с отрицанием либо без отрицания.+

154.Конституенты единицы, построенные для строк, где функция f равна 1, называются

1) несобственными конституентами единицы функции f.

2)собственными конституентами единицы функции f.+

3) собственными конституентами истинности функции f.

4) несобственными конституентами истинности функции f.

155.Правая часть разложения f(x₁,x₂,…,x_n)=&_{(a1,a2,…,an)} (x₁^1-а1Úx₂^1-а2Ú…Úx_n^1-аn) называется

1) совершенной конъюнкцией нормальной формой.+

2) элементарной конъюнктивной нормальной формой.

3)совершенной дизъюнктивной нормальной формой.

4) элементарной дизъюнктивной нормальной формой.

156.Совершенной конъюнкцией нормальной формой функции f(х₁,х₂,…х_n), является к.н.ф. этой функции, удовлетворяющая следующим условиям:

1) в каждый множитель входят все переменные х₁,х₂,…,x_n один и только один раз (и только они) с отрицанием либо без отрицания.

2) нет одинаковых множителей.

3) есть одинаковые множителя; в каждый множитель входят все переменные х₁,х₂,…,x_n один и только один раз (и только они) с отрицанием либо без отрицания.

4) нет одинаковых множителей; в каждый множитель входят все переменные х₁,х₂,…,x_n один и только один раз (и только они) с отрицанием, либо без отрицания.+

157.Метод равносильных преобразований, который применяется, когда

1) булева функция задана в виде формулы.+

2) булева формула задана в виде функции.

3) булева функция не задана в виде формулы.

4) булева формула не задана в виде функции.

158.Если в выбранной строке, где f=0, переменная х_j

1) принимает значение 1, то в К⁰ она входит с отрицанием, если х_j=0, то х_j входит в К⁰ без отрицания.+

2) принимает значение 1, то в К⁰ она входит без отрицания, если х_j=0, то х_j входит в К⁰ без отрицания.

3) принимает значение 1, то в К⁰ она входит с отрицанием, если х_j=0, то х_j входит в К⁰ с отрицанием.

4) принимает значение 1, то в К⁰ она входит без отрицания, если х_j=0, то х_j входит в К⁰ с отрицанием.

159.Любую булеву функцию f(x₁,x₂,…,x_n) можно единственным образом представить в виде (где а_i(0£i£к) являются постоянными, равными нулю и единице):

1) f(x₁,x₂,…,x_n)=a₀-a₁Úx₁-a₂Úx₂-…-a_nÚx_n-a_n+1Úx₁Úx₂-a_n-2Úx₁Úx₃-…-a_mÚx₁Úx_n-a_m+1Úx₁Úx₂Úx₃-…-a_rÚx_n-2Úx_n-1Úx_n-…-a_kÚx₁Úx₂Ú…Úx_n.

2) f(x₁,x₂,…,x_n)=a₀+a₁Úx₁+a₂Úx₂+…+a_nÚx_n+a_n+1Úx₁Úx₂+a_n-2Úx₁Úx₃+…+a_mÚx₁Úx_n+a_m+1Úx₁Úx₂Úx₃+…+a_rÚx_n-2Úx_n-1Úx_n+…+a_kÚx₁Úx₂Ú…Úx_n.

3)f(x₁,x₂,…,x_n)=a₀+a₁&x₁+a₂&x₂+…+a_n&x_n+a_n+1&x₁&x₂+a_n-2&x₁&x₃+…+a_m&x₁&x_n+a_m+1&x₁&x₂&x₃+…+a_r&x_n-2&x_n-1&x_n+…+a_k&x₁&x₂&…&x_n.+

4) f(x₁,x₂,…,x_n)=a₀-a₁&x₁-a₂&x₂-…-a_n&x_n-a_n+1&x₁&x₂-a_n-2&x₁&x₃-…-a_m&x₁&x_n-a_m+1&x₁&x₂&x₃-…-a_r&x_n-2&x_n-1&x_n-…-a_k&x₁&x₂&…&x_n.

160.Правая часть равенства f(x₁,x₂,…,x_n)=a₀+a₁&x₁+a₂&x₂+…+a_n&x_n+a_n+1&x₁&x₂+a_n-2&x₁&x₃+…+a_m&x₁&x_n+a_m+1&x₁&x₂&x₃+…+a_r&x_n-2&x_n-1&x_n+…+a_k&x₁&x₂&…&x_n называется

1) де Морганом.

2)полиномом Жегалкина.+

3) Пирсом.

4) Квайном.

161.Импликативной булевой функции f называется булева функция j, которая

1)обращается в 0 на всех тех наборах значений аргументов, на которых равна 1 функция f.

2) обращается в 1 на всех тех наборах значений аргументов, на которых равна 0 функция f.

3) обращается в 0 на всех тех наборах значений аргументов, на которых равна 0 функция f. +

4) обращается в 1 на всех тех наборах значений аргументов, на которых равна 1 функция f.

162.Собственной частью произведения называют произведение, полученное исключением из данного произведения

1) одного или нескольких сомножителей.+

2) двух или нескольких сомножителей.

3) трех или нескольких сомножителей.

4) четырех или нескольких сомножителей.

163.Элементарные произведения, которые сами являются импликантами функции f, но никакая собственная часть этих произведений не является импликантой этой функции называется

1) элементарными импликантами булевой функции f.

2) простыми импликантами булевой функции f.+

3) собственными импликантами булевой функции f.

4) импликантами булевой функции f.

164.сокращенной д.н.ф. для булевой функции f(x₁,x₂,…,x_n) называется

+1) дизъюнкция всех простых импликант этой функции.

2) конъюнкция всех простых импликант этой функции.

3) дизъюнкция всех импликант этой функции.

4) конъюнкция всех импликант этой функции.

165.Каждая булева функция f(x₁,x₂,…,x_n)

1) равносильна своей сокращенной д.н.ф.+

2) не равносильна своей сокращенной д.н.ф.

3) равносильна своей сокращенной к.н.ф.

4) не равносильна своей сокращенной к.н.ф.

166.Метод Квайна основан на преобразовании совершенной д.н.ф. с помощью операций

1) неполного склеивания.

2) полного склеивания и поглощения.

3) неполного склеивания и поглощения.+

4) поглощения.

167.Операция склеивания (полного) определяется соотношением

1) х&уÚх&Øу~х.+

2) хÚх&у~х.

3) х&уÚх&Øу~хÚх&уÚх&Øу.

4) х~хÚх.

168.Операция поглощения определяется соотношением

1) х&уÚх&Øу~х.

2) хÚх&у~х.+

3) х&уÚх&Øу~хÚх&уÚх&Øу.

4) х~хÚх.

169.Операция неполного склеивания определяется соотношением

1) х&уÚх&Øу~х.

2) хÚх&у~х.

3) х&уÚх&Øу~хÚх&уÚх&Øу. +

4) х~хÚх.

170.Если в совершенной д.н.ф. булевой функции провести все операции неполного склеивания и затем все операции поглощения, то в результате получится

1) полная к.н.ф. этой функциии.

2) сокращенная к.н.ф. этой функциии.

3) полная д.н.ф. этой функциии.

4) сокращенная д.н.ф. этой функциии.+

171.Дизъюнкция простых импликант функции f, ни одну из которых исключить нельзя, и указанная дизъюнкция равносильна функции f называется

1) тупиковой д.н.ф. булевой функции f. +

2) минимальной д.н.ф.булевой функции f.

3) тупиковой к.н.ф. булевой функции f.

4) минимальной к.н.ф. булевой функции f.

172.Минимальной д.н.ф. булевой функции называется д.н.ф., равносильная этой функции и содержащая наименьшее возможное число вхождений переменных

1) с отрицанием.

2) без отрицания.

3) с отрицанием или без отрицания.+

4) с отрицанием и без отрицания.

173.Некоторые булевые функции имеют

1) равных тупиковых форм.

2) ни одну тупиковую форму.

3) одну тупиковую форму.

4) несколько тупиковых форм.+

174.Всякая минимальная д.н.ф. булевой функции f является её

1) минимальной д.н.ф.

2) тупиковой д.н.ф.+

3) минимальной к.н.ф.

4) тупиковой к.н.ф.

175.Для отыскания тупиковых, следовательно, и минимальных д.н.ф. существует

1) бесконечное число методов.

2) ни один метод.

3) один метод.

4) несколько методов.+

176.Метод импликантных матриц применяется для нахождения

1) тупиковых или минимальных д.н.ф.

2) минимальных д.н.ф.

3) тупиковых д.н.ф.

4) тупиковых и минимальных д.н.ф.+

177.Слагаемые сокращенной д.н.ф. являются

1) равными импликантами.

2) сложными импликантами.

3) простыми импликантами.+

4) эквивалентными импликантами.

178.Для уменьшения выкладок на этапе получения сокращенной д.н.ф. можно применить метод

1) Мак-Класки.+

2) Пирса.

3) Квайна.

4) де Моргана.

179.В каком методе необходимо проводить попарное сравнение всех слагаемых с.д.н.ф.

1) Мак-Класки.

2) Пирса.

3) Квайна.+

4) де Моргана.

180.При склеивании слагаемых в разряды (метод Мак-Класки), соответсвующие исключенным переменным, пишется знак

1) тире.+

2) отрицания.

3) присваивания.

4) эвиваленттнсти.

181.Равносильная f, которая содержит наименьшее число вхождений переменнных называется к.н.ф.

1) минимальной к.н.ф.+

2) максимальная к.н.ф.

3) минимальной д.н.ф.

4) максимальная д.н.ф.

182.Нахождение сокращенной к.н.ф.Считаем, что для заданной функции уже найдена совершенная к.н.ф.В этой с.к.н.ф. выполняют всевозможные операции

1) неполного склеивания.

2) полного склеивания и поглощения.

3) неполного склеивания и затем операция поглощения.+

4) поглощения.

183.Операция неполного склеивания в к.н.ф. определяется следующим образом:

1) х&уÚх&Øу~х.

2) хÚх&у~х.

3) (хÚу)&(хÚØу)~х&(хÚу)&(хÚØу). +

4) х~хÚх.

184.Операция поглощения в к.н.ф. определяется следующим образом:

1) х&уÚх&Øу~х.

2) х&(хÚу)~х.+

3) (хÚу)&(хÚØу)~х&(хÚу)&(хÚØу).

4) х~хÚх.

185.Клетки имплицентной матрицы, находящиеся на пересечении столбца с конституентой нуля, и строки с членом, который ее поглощает, отмечаются

1) тире.

2) отрицания.

3) присваивания.

4) звездочки.+

186.Система функций Ф={j₁,j₂,…,j_k} называется функционально полной, если всякая булева функция представима посредством

1) суперпозиции функций из системы Ф.+

2) сверхпозиции функций из системы Ф.

3) позиции функций из системы Ф.

4) макспозиции функций из системы Ф.

187.Если система булевых функций {j₁,j₂,…,j_n} является полной системой функций, но никакая ее собственная часть не образует полную систему функций называется

1) множеством.

2) базисом.+

3) элементом.

4) объектом.

188.Какая из этих систем будет базисным

1) {Ø,&},{|}.+

2){Ø,&,|}.

3) {Ø,&,¯}.

4) {Ø,&,Ú}.

189.Булева функция f(x₁,x₂,…,x_n) называется сохраняющей нуль (единицу), если

1) f(0,0,…,0)=0 (f(1,1,…,1)=1).+

2) f(0,0,…,0)=1 (f(1,1,…,1)=0).

3) f(0,1,…,0)=0 (f(1,0,…,1)=1).

4) f(0,0,…,1)=1 (f(1,1,…,0)=0).

190. Булева функция f(x₁,x₂,…,x_n) называется самодвойственной, если

1) Øf(x₁,x₂,…,x_n)=f(x₁,Øx₂,…,x_n).

2) Øf(x₁,x₂,…,x_n)=f(Øx₁,Øx₂,…,Øx_n).+

3) Øf(x₁,x₂,…,x_n)=f(x₁,x₂,…,x_n).

4) f(x₁,x₂,…,x_n)=f(Øx₁,Øx₂,…,Øx_n).

191.Если некоторые из значений аргументов первого набора больше или равны, а другие меньше значений второго набора, то такие наборы называются

1) равными.

2) сравнимыми.

3) несравнимыми.+

4) неравными.

192.Функция f(x₁,x₂,…,x_n) называется линейной (где с_i –константы (единица или нуль), 0£i£n.), если

1) f(x₁,x₂,…,x_n)=с₀-с₁Úх₁-с₂Úх₂-…-с_nÚx_n.

2) f(x₁,x₂,…,x_n)= с₀-с₁&х₁-с₂&х₂-…-с_n&x_n.
3) f(x₁,x₂,…,x_n)= с₀+с₁Úх₁+с₂Úх₂+…+с_nÚx_n.

4) f(x₁,x₂,…,x_n)= с₀+с₁&х₁+с₂&х₂+…+с_n&x_n.+

193.Для полноты системы функций Ф={j₁,j₂,…,j_n} необходимо и достаточно, чтобы для каждого из классов Р₀,Р₁,S, M, L в Ф нашлась функция j_i, ему (классу)

1) принадлежащая.

2) не принадлежащая.+

3) включающая.

4) не включающая.

194.Контанты (переключатели) можно рассматривать как

1) булевы объекты.

2) булевы множества.

3) булевы элементы.

4) булевы переменные.

195.Каждая из булевых переменных может принимать

1) одно значение.+

2) два значения

3) три значения.

4) четыре значения.

196.Последовательное соединение двух контактов х и у моделируется

1) конъюнкцией.+

2) дизъюнкцией.

3) отрицанием.

4) вычитанием.

197. Параллельное соединение двух контактов х и у моделируется

1) конъюнкцией.

2) дизъюнкцией.+

3) отрицанием.

4) вычитанием.

198.Под контактной (переключательной) схемой понимается схема, состоящая

1) из замкнутых и разомкнутых контактов, соединенных параллельно или последовательно.

2) из соединенных параллельно или последовательно, или смешанным образом.

3) из замкнутых и разомкнутых контактов, соединенных параллельно или последовательно, или смешанным образом.+

4) из замкнутых и разомкнутых контактов, смешанным образом.

199.Отрицанием контакта х называется контакт (правильных два ответа)

1) равный 1, если х=0.+

2) равный 1, если х=1.

3) равный 0, если х=1.+

4) равный 0, если х=0.

200.Любую булеву функцию можно представить в виде контактной схемы, в которой ток будет тогда и только тогда, когда функция принимает значение

1) 1.+

2) 2.

3) 3.

4) 4.

201.Огромные скорости работы современных ЭВМ достигнуты из-за применения

1) контактных схем.

2) бесконтактных схем.+

3) последовательных соединений.

4) параллельных соединений.

202.Как по другому называются устройства

1) формульными множествами.

2) функциональными множествами.

3) формульными элементами.

4) функциональными элементами.+

203.Устройство, реализующее отрицание, имеет один вход и

1) один выход.+

2) два выхода.

3) три выхода.

4) четыре выхода.

204.Устройство, реализующее конъюнкцию, имеет два и более входов и

1) один выход.+

2) два выхода.

3) три выхода.

4) четыре выхода.

205.Устройство, реализующее дизъюнкцию, имеет два и более входов и

1) один выход.+

2) два выхода.

3) три выхода.

4) четыре выхода.

206.Декомпозицией булевой функции f(X) называется представление ее в виде

1) f(X)=g₀(x⁰,g₁(x¹),…,g_k(x^m)).

2) f(X)=g₀(g₁(X¹),…,g_k(X^m)).

3) f(X)=g₀(X⁰,g₁(X¹),…,g_k(X^m)).+

4) f(X)=g₀(g₁(x¹),…,g_k(x^m)).

207.Если булева функция f(X) допускает декомпозицию при k=1и m=1, т.е. f(X)=g₀(X⁰,g₁(X¹)), то такая декомпозиция называется

1) неполной.

2) полной.

3) простой.+

4) сложной.

208.Число множеств Хⁱ называется

1) кратностью.

2) размерностью.+

3) декомпозицией.

4) раздельностью.

209.Если декомпозиция выполняется при условий, что ХⁱÇX^j=Æ для любых i, j, i¹j, то декомпозиция называется

1) кратностью.

2) размерностью.

3) декомпозицией.

4) разделительной.+

210.Булева функция f(X), зависящая от n переменных, допускает двумерную разделительную декомпозицию кратности один тогда и только тогда, когда декомпозиционная матрица, соответствующая заданному разбиению множества Х на непересекающиеся подмножества Х⁰ и Х¹, содержит не более

1) одного столбца значений функций.

2) двух различных столбцов значений функций.+

3) трех различных столбцов значений функций.

4) четырех различных столбцов значений функций.

Дата добавления: 2015-11-14