РІВЕНЬ B. 102. Перемикальна функція – це

ТЕМА

102. Перемикальна функція – це

в) булева функція;

103. Якими методами задається булева функція?

б) подати набір всіх кортежів та відповідні їм значення функції;

104. Областю визначення булевої (перемикальної) функції n аргументів є

а) сукупність 2ⁿ булевих кортежів;

105. Число всіх функцій, що залежать від n змінних дорівнює

а) ;

106. Принцип суперпозиції формулюється…

в) Якщо задана булева функція, то замість будь-якої змінної можна використовувати власну змінну, так і змінну, що є функцією інших змінних.

107. Формули F ₁ і F ₂ називають рівносильними, якщо

б) при будь-яких значеннях змінних , що входять в ці формули, вони набувають одинакових значень;

108. Формули й називаються тотожними (еквівалентними), якщо

а) відповідні функції і рівні;

109. Чому дорівнюють дані вирази

1. подвійне заперечення змінної х

2 );

3. );

4. x + 0

5. ?

б) х;

110. Чому дорівнює вираз ?

а) ;

111. Чому дорівнює вираз ?

а) ;

112. Чому дорівнює вираз x ?

г) 0.

113. Чому дорівнює вираз x ?

а) ;

114. Функція додавання за модулем 2 володіє властивостями

г) комутативності, асоціативності та дистрибутивності;

115. Чому дорівнює вираз ?

в) ;

116. Чому дорівнюють дані вирази

1.

2.

3.

в) 1;

117. Чому дорівнюють дані вирази

1.

2.

а) ;

118. Функція імплікації володіє наступними властивостями

г) інша відповідь.

119. Чому дорівнює вираз

в) ;

120. Чому дорівнює вираз

г) .

121. Функція Шеффера володіє наступними властивостями

а) комутативності;

122. Чому дорівнюють вирази , ?

а) ;

123. Чому дорівнюють вирази

; ; ?

в) 1;

124. Функція Пірса-Вебба володіє наступними властивостями

а) комутативності;

125. Чому дорівнює вираз

в) ;

126. Чому дорівнює вираз ?

г) .

127. Функція називається двоїстою до функції якщо

б) = .

128. Формула або функція називається самодвоїстою, якщо

б) = .

129. Система функцій називається функціонально повною, якщо

в) якщо будь-яка булева функція може бути записана у вигляді формули через функції цієї системи.

130. Повну систему називають ослабленою повною системою, якщо

в) в системі присутні функції константи 0 або 1;

131. Система функцій називається мінімально повним базисом, якщо

а) в системі не більше 3 функцій;

б) всі функції системи є нелінійними;

в) в системі присутні функції константи 0 або 1;

г) вилучення з неї будь-якої функції перетворює цю систему на неповну.

132. Який поліном називається поліномом Жегалкіна?

а)

б)

в)

г) інша відповідь.

133. Чи будь-яку функцію алгебри логіки можна представити у вигляді полінома Жегалкіна?

а) тільки якщо функція не має властивості лінійності;

б) тільки якщо функція не є самодвоїстою;

в) тільки якщо функція не є монотонною;

г). будь-яку.

134. Функція називається монотонною, якщо

а) для двох наборів і виконується відношення передування;

б) функція не є самодвоїстою і не зберігає константу нуль або 1;

в) вона може бути подана у вигляді полінома:

г) для двох будь-яких наборів, що знаходяться у відношенні передування, справджується нерівність .

135. Перемикальна функція називається лінійною, якщо

а) для двох наборів і виконується відношення передування;

б) функція не є самодвоїстою і не зберігає константу нуль або 1;

в) вона може бути подана у вигляді полінома:

г) для двох будь-яких наборів, що знаходяться у відношенні передування, справджується нерівність .

136. Теорема Поста формулюється..

а) Щоб система перемикальних функцій була повною, необхідно і достатньо, щоб вона містила хоча б одну функцію яка не зберігає нуль, одиницю, не була б лінійною, монотонною та самодвоїстою.

б) Щоб система перемикальних функцій була повною, необхідно і достатньо, щоб вона містила хоча б одну функцію яка не зберігає нуль, одиницю, була б лінійною, монотонною та самодвоїстою.

в) Щоб система перемикальних функцій була повною, необхідно і достатньо, щоб вона містила хоча б одну функцію яка зберігає нуль, одиницю, не була б лінійною, монотонною та двоїстою.

г) Щоб система перемикальних функцій була повною, необхідно і достатньо, щоб вона містила хоча б одну функцію яка не зберігає нуль, одиницю, не була б лінійною, монотонною та двоїстою.

137. Формула називається тотожно істиною, якщо

а) вона при всіх можливих значеннях змінних, які входять у неї, набуває значення одиниці;

б) вона набуває значення одиниці при деяких значеннях змінних і нуля при інших значеннях цих же змінних;

в) змінні можуть набувати значення із множини ;

г) інша відповідь.

.

138. Формула називається тотожно хибною, якщо

а) вона при всіх можливих значеннях змінних, які входять у неї, набуває значення нуля;

б) вона набуває значення одиниці при деяких значеннях змінних і нуля при інших значеннях цих же змінних;

в) змінні можуть набувати значення із множини ;

г) інша відповідь.

139. Формула називається здійсненою, якщо

а) вона при всіх можливих значеннях змінних, які входять у неї, набуває значення нуля;

б) вона набуває значення одиниці при деяких значеннях змінних і нуля при інших значеннях цих же змінних;

в) змінні можуть набувати значення із множини ;

г) інша відповідь.

140. Якщо функцію задано у вигляді диз'юнкції елементарних кон'юнкцій, то її задано

а) ДДНФ;

б)ДНФ;

в) КНФ;

г) ДКНФ.

141. Конституентою одиниці (мінтермом) називають

а) логічний добуток будь-якої кількості незалежних змінних, що входять із запереченням або без нього;

б) перемикальну функцію n аргументів, яка набуває значення одиниці на одному із її кортежів;

в) логічна сума будь-якої кількості різих незалежних змінних, що входять із запереченням, або без нього;

г) абсолютну істинну функцію.

142. Максимальна кількість конституент одиниці дорівнює

а) кількості змінних n;

б) ;

в) кількості конституент нуля;

г) кількості кортежів;

143. Максимальна кількість макстермів дорівнює

а) кількості змінних n;

б) ;

в) кількості конституент нуля;

г) кількості кортежів;

144. У якій з наведених форм може бути подана будь-яка задана таблично функція алгебри логіки n аргументів?

а) , де - елементарна кон'юнкція рангу ; - номера кортежів, на яких функція дорівнює одиниці, , де - елементарна диз'юнкція рангу ; - номера кортежів, на яких функція дорівнює нулю;

б) , де - елементарна кон'юнкція рангу ; - номера кортежів, на яких функція дорівнює одиниці, , де - елементарна диз'юнкція рангу ; - номера кортежів, на яких функція дорівнює нулю;

в) , де - елементарна кон'юнкція рангу ; - номера кортежів, на яких функція дорівнює одиниці, , де - елементарна диз'юнкція рангу ; - номера кортежів, на яких функція дорівнює нулю;

г)

145. Диз'юнкція тих конституент (мінтермів) одиниці, які перетворюються в одиницю на тих самих наборах, що і сама функція називається

а) ДДНФ;

б) ДНФ;

в) КНФ;

г) ДКНФ.

146. Будь-яка перемикальна функція має…

а) одну ДДНФ і одну ДНФ;

б) одну ДДНФ і декілька ДНФ;

в) декілька ДДНФ і декілька ДНФ;

г) кількість ДНФ визначається кількістю доданків у ДДНФ.

147. Будь-яка перемикальна функція має…

а) одну ДКНФ і одну КНФ;

б)одну ДКНФ і декілька КНФ;

в) декілька ДКНФ і декілька КНФ;

г) кількість КНФ визначається кількістю доданків у ДКНФ.

148. ДНФ можна утворити …

а) розгортанням ДДНФ;

б) із таблично заданої функції;

в) з мінтермів функції:

г) ДНФ є первинною функцією і тільки з неї утворюється ДДНФ.

149. Ранг елементарної диз’юнкції або кон’юнкції визначається

а) кількістю операцій логічного додавання або множення;

б) кількістю інверсій над змінними, що входять у елементарну диз’юнкцію або кон’юнкцію;

в) кількістю змінних, що входять у елементарну диз’юнкцію або кон’юнкцію;

г) інша відповідь.

150.

Якщо будь-яку функцію задано формулою у вигляді кон`юнкції елементарних диз`юнкцій, то функцію задано

а) ДДНФ;

б) ДНФ;

в) КНФ;

г) ДКНФ.

151. Конституентою нуля називають

а) логічний добуток будь-якої кількості незалежних змінних, що входять із запереченням або без нього;

б) перемикальну функцію n аргументів, яка набуває значення нуля на одному із її кортежів;

в) логічна сума будь-якої кількості різих незалежних змінних, що входять із запереченням, або без нього;

г) тотожно хибну функцію.

152. Яка функція алгебри логіки може бути подана і в ДДНФ і в ДКНФ?

а) будь-яка;

б) будь-яка, крім одиничної і нульової функції;

в) у ДДНФ така, що не містить одиниць на жодному з кортежів;

г) у ДКНФ така, що не містить нулів на жодному з кортежів.

153. Якщо функція подана у вигляді F= f_im_i, (де f_i значення перемекальної функції, що відповідає i -тому кортежу, m_i – відповідний мінтерм), то функція подана у

а) ДДНФ;

б) ДНФ;

в) КНФ;

г) ДКНФ.

154. Якщо функція подана у вигляді (f_i + M_i) (де f_i значення перемекальної функції, що відповідає i -тому кортежу, M_i – відповідний макстерм), то функція подана у

а) ДДНФ;

б) ДНФ;

в) КНФ;

г) ДКНФ.

155. ДНФ (КНФ), що реалізує функцію f(x₁, x₂,..., x_n) і має мінімальний індекс L, називається

а) скороченою до заданого коефіцієнта простоти;

б) мінімальною відносно коефіцієнта L;

в) спрощеною до заданого коефіцієнта простоти;

г) імплікатою.

156. Мінімальні ДНФ (КНФ) аналітично отримують шляхом вибору з

а) тупикових форм мінімальної;

б) скорочених форм мінімальної;

в) шляхом додавання простих імпікат;

г) інший спосіб.

157. Функція Y входить в функцію f, якщо

а) функція Y має не менше нулів ніж функція f;

б) функція Y має менше нулів ніж функція f;

в) функція Y має не більше нулів ніж функція f;

г) функція Y має більше нулів ніж функція f.

158. Якщо функція Y входить в f, то імплікатою називають

а) функцію Y;

б) функцію f;

в) умова входження не є означенням імплікати;

г) Y називається власною частиною імплікати.

159. Терм –добуток – це

а) елементарний добуток, що входить у задану перемекальну функцію;

б) власна частина імплікати;

в) елементарні добутки, що самі входять у задану функцію, але ніяка власна частина їх у функцію f не входить;

г) інша відповідь.

160. Простими імплікатами перемекальної функції називають

а) елементарний добуток, що входить у задану перемекальну функцію;

б) власна частина імплікати;

в) терм-елементарні добутки, що самі входять у задану функцію, але ніяка власна частина їх у функцію f не входить;

г) інша відповідь.

161. Скороченою ДНФ називається

а) Диз`юнкція всіх простих імплікат;

б) Диз`юнкція терм-добутків;

в) Диз`юнкція стермдобутків;

г) інша відповідь.

162. Дана операція xy+x =x(y+ )=x є операцією

а) повного склеювання;

б) неповного склеювання;

в) поглинання;

г) самопоглинання.

163. Дана операція x+xy+x =x+x(y+ )=x+x=x є операцією

а) повного склеювання;

б) неповного склеювання;

в) поглинання;

г) самопоглинання.

164. Дана операція x+xy=x(1+y)=x є операцією

а) повного склеювання;

б) неповного склеювання;

в) поглинання;

г) самопоглинання.

165. Якщо в ДДНФ виконати всі операції неповного склеювання, а потім усі операції поглинання, то отримаємо

а) мінімальну ДНФ;

б) скорочену ДНФ;

в) тупикову ДНФ;

г) необхідно ще виконати операцію повного склеювання для отримання мінімальної ДНФ.

166. Диз`юнкція простих імплікат, жодну із яких не можна виключити називається

а) мінімальною ДНФ;

б) скороченою ДНФ;

в) тупиковою ДНФ;

г) ДНФ.

РІВЕНЬ B

167. Застосувавши рівносильні перетворення привести булеву до мінімальної ДНФ.

а) ;

б) ;

в) ;

г) інша відповідь.

168. Чи буде функціонально повною система булевих функцій, яка складається з диз’юнкціі та імплікаціі?

а) так;

б) ні;

в) дана система є ослабленою повною системою;

г) система буде повною, якщо додати функцію інверсії.

169. Довести повноту (або неповноту) приведеної системи булевих функцій , , .

а) система неповна;

б) система повна;

в) система буде повною, якщо додати функцію константа 1;

г) система буде повною, якщо додати функцію інверсії.

170. До якого класу належить функція ?

а) константа 1;

б) константа 0;

в) лінійна;

г) монотонна.

171. До якого класу належить функція ?

а) константа 1;

б) константа 0;

в) лінійна;

г) монотонна.

172. Чи буде система функцій повною?

а) так;

б) ні;

в) дана система є ослабленою повною системою;

г) система буде повною, якщо додати функцію інверсії.

173. Чи є функція f є двоїстою до функції g (f=xÅ y, g=x~y). Встановити чи якась з даних функцій є самодвоїстою?

а) f є двоїстою до функції g;

б) f не двоїста до функції g;

в) g є самодвоїстою;

г) f є самодвоїстою.

174. Чи є функція f є двоїстою до функції g (f=(x× y)Ú (x× z)Ú (y× z), g=x× yÅ x× zÅ y× z). Встановити чи якась з даних функцій є самодвоїстою?

а) f є двоїстою до функції g і обидві функції самодвоїсті;

б) f не двоїста до функції g;

в) g є самодвоїстою;

г) f є двоїстою до функції g.

175. Чи є функція f є двоїстою до функції g (f=x~y, g= ). Встановити чи якась з даних функцій є самодвоїстою?

а) f є двоїстою до функції g і обидві функції самодвоїсті;

б) f не двоїста до функції g;

в) g є самодвоїстою;

г) f є двоїстою до функції g.

176. Чи є функція f є двоїстою до функції g (f=(xÅ y)× z, g=(x+y)× (zÅ 1)). Встановити чи якась з даних функцій є самодвоїстою?

а) f є двоїстою до функції g;

б) f не двоїста до функції g;

в) g є самодвоїстою;

г) f є самодвоїстою.

177. Визначити, чи є функція xyÅ yÅ x монотонною?

а) так;

б) ні;

в) тільки для певних кортежів;

г) тільки на певному інтервалі.

178. Визначити, чи є функція x®(x®y) монотонною?

а) так;

б) ні;

в) тільки для певних кортежів;

г) тільки на певному інтервалі.

179. Визначити, чи є функція (x× y)Ú (x× z)Ú (y× z) монотонною?

а) так;

б) ні;

в) тільки для певних кортежів;

г) тільки на певному інтервалі.

180. Визначити, чи є функція x®(y®x) монотонною?

а) так;

б) ні;

в) тільки для певних кортежів;

г) тільки на певному інтервалі.

181. Визначити, чи є функція yxÅ y монотонною?

а) так;

б) ні;

в) тільки для певних кортежів;

г) тільки на певному інтервалі.

182. Встановити, чи буде функція лінійною?

а) так;

б) ні;

в) функція, що містить інверсію ніколи не буде лінійною;

г) неможливо встановити через протиріччя у таблицях істинності.

183. Встановити, чи буде функція лінійною?

а) так;

б) ні;

в) функція, що містить інверсію ніколи не буде лінійною;

г) неможливо встановити через протиріччя у таблицях істинності.

184. Встановити, чи буде функція лінійною?

а) так;

б) ні;

в) функція, що містить інверсію ніколи не буде лінійною;

г) неможливо встановити через протиріччя у таблицях істинності.

185. Встановити, чи буде функція лінійною?

а) так;

б) ні;

в) функція, що містить інверсію ніколи не буде лінійною;

г) неможливо встановити через протиріччя у таблицях істинності.