Глава 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) называют разложением