ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 5049
Скачиваний: 25
91
противоречие означает некорректность выражения, а значит и нели-
нейность функции.
В качестве примера рассмотрим функции двух переменных
f
10
= х
1
∼ х
2
– эквивалентность и f
14
= х
1
→
х
2
– импликация. Таблица
истинности для этих функций имеет вид:
x
1
x
2
f
10
f
14
0 0 1 1
0 1 0 1
1 0 0 0
1 1 1 1
Представим f
10
в виде полинома по модулю два:
f
10
(x
1
, x
2
) = a
0
⊕ a
1
x
1
⊕ a
2
x
2
.
Подставляя значения функции и переменных из набора № 0, полу-
чим
1 = a
0
⊕ a
1
0
⊕ a
2
0, откуда a
0
= 1.
Используя аналогичным образом набор № 1, получим (с учетом то-
го, что a
0
= 1)
0 = 1
⊕ a
1
0
⊕ a
2
1, откуда a
2
= 1.
Из набора № 2:
0 = 1
⊕ a
1
1
⊕ a
2
0, откуда a
1
= 1.
Подставляя полученные значения коэффициентов в выражение, где
значения переменных и функции соответствуют набору № 3, полу-
чим
1 = 1
⊕ 1
⊕ 1, что является истиной. Отсюда следует, что функ-
ция х
1
∼ х
2
линейна и может быть представлена как
х
1
∼ х
2
= 1
⊕ х
1
⊕ х
2
.
Исследуя аналогичным образом функцию f
14
= х
1
→
х
2
, полу-
чим:
a
0
= 1 (из набора № 0);
a
2
= 0 (из набора № 1);
a
1
= 1 (из набора № 2).
Используя для проверки набор № 3, получим
1 = 1
⊕ 1
⊕ 0, что является ложью. Следовательно, функция
f
14
= х
1
→
х
2
нелинейна.
92
Вариант 1
1.
Докажите, что (А ٧ B) ٨ (B ٧ C) ٨ (C ٨
⎯A) = (А ٧ B) ٨
(C ٨
⎯A), где А, В, C – простые высказывания.
2.
Функция f(x
1
, x
2
, x
3
) принимает единичные значения на наборах
№№ 1, 2, 5, 6, 7.
3.
Является ли полной система булевых функций, состоящая из
дизъюнкции, константы 0 и эквивалентности?
Вариант 2
1.
Верно ли, что (А ٨ (
⎯B ٧ С) ٨ (⎯С ٧⎯D) = ⎯А ٧ B ٨⎯C ٧ С ٨ D,
где А, В, С, D – простые высказывания?
2.
Функция f(x
1
, x
2
, x
3
) принимает единичные значения на наборах
№№ 0, 1, 4, 6, 7.
3.
Является ли полной система булевых функций, состоящая из
дизъюнкции и конъюнкции?
Вариант 3
1.
Верно ли, что
А ٨ В ٧
⎯B ٨ С ٧⎯D ٨ E = (⎯А ٧⎯B) ٨ (B ٧⎯C) ٨ (D ٧ E),
где А, В, С, D, E – простые высказывания?
2.
Функция f(x
1
, x
2
, x
3
) принимает единичные значения на наборах
№№ 0, 1, 3, 6, 7.
3.
Является ли полной система булевых функций, состоящая из
импликации и отрицания?
Вариант 4
1.
Верно ли, что
А ٨ В ٧ С ٨ D ٧ E = (
⎯А ٧ B) ٨ (⎯C ٧⎯D) ٨ E,
где А, В, С, D, E – простые высказывания?
2.
Функция f(x
1
, x
2
, x
3
) принимает единичные значения на наборах
№№ 0, 2, 3, 6, 7.
3.
Является ли полной система булевых функций, состоящая из
конъюнкции, константы 1 и сложения по модулю два?
93
Вариант 5
1.
Верно ли, что
(А ٨ В ٧ С ٨
⎯D ٧ E ٧ F) = (⎯А ٧⎯B) ٨ (⎯C ٧ D) ٧⎯E ٧⎯F,
где А, В, С, D, E, F – простые высказывания?
2.
Функция f(x
1
, x
2
, x
3
) принимает единичные значения на наборах
№№ 1, 2, 3, 5, 6.
3.
Является ли полной система булевых функций, состоящая из
конъюнкции, константы 0 и эквивалентности?
Вариант 6
1.
Верно ли, что
А ٨ В ٨ С ٨ (
⎯D ٧⎯E ) = ⎯А ٧⎯B ٧⎯C ٧ D ٨ E,
где А, В, С, D, E – простые высказывания?
2.
Функция f(x
1
, x
2
, x
3
) принимает единичные значения на наборах
№№ 1, 2, 3, 5, 7.
3.
Является ли полной система булевых функций, состоящая из
импликации и эквивалентности?
Вариант 7
1.
Верно ли, что
(А ٧
⎯В ٧⎯С) ٨ ( D ٧⎯E) ٨ F =⎯А ٨ B ٨ C ٧⎯D ٨ E ٧⎯F,
где А, В, С, D, E, F – простые высказывания?
2.
Функция f(x
1
, x
2
, x
3
) принимает единичные значения на наборах
№№ 0, 2, 5, 6, 7.
3.
Является ли полной система булевых функций, состоящая из
конъюнкции и импликации?
Вариант 8
1.
Верно ли, что
А ٨ В ٨ С ٨ ( D ٧ E) ٨ F =
⎯А ٧⎯B ٧⎯C ٧ (D ٨ E ) ٧⎯F,
где А, В, С, D, E, F – простые высказывания?
2.
Функция f(x
1
, x
2
, x
3
) принимает единичные значения на наборах
№№ 2, 4, 5, 6, 7.
3.
Является ли полной система булевых функций, состоящая из
94
конъюнкции, эквивалентности и сложения по модулю два?
Вариант 9
1.
Верно ли, что
А ٨ (
⎯В ٧⎯С) ٨ ( D ٧⎯E) ٨ F = ⎯А ٧ B ٨ C ٧⎯D ٨ E ٧⎯F,
где А, В, С, D, E, F – простые высказывания?
2.
Функция f(x
1
, x
2
, x
3
) принимает единичные значения на наборах
№№ 2, 3, 5, 6, 7.
3.
Является ли полной система булевых функций, состоящая из
дизъюнкции и импликации?
Вариант 10
1.
Верно ли, что
(А ٧ В) ٨ (С ٧
⎯D) ٨ E ٨ F) = ⎯А ٨⎯B ٧⎯C ٨ D ٧⎯E ٧⎯F,
где А, В, С, D, E, F – простые высказывания?
2.
Функция f(x
1
, x
2
, x
3
) принимает единичные значения на наборах
№№ 0, 3, 4, 6, 7.
3.
Является ли полной система булевых функций, состоящая из
сложения по модулю два, константы 1 и эквивалентности?
Контрольная
работа
№
4
Эта контрольная работа включает в себя задания по теории ал-
горитмов и перечислительной комбинаторике. В работе требуется
выполнить четыре задания.
1.
Приведите три самостоятельных примера применения оператора
подстановки к простейшим числовым функциям. Например,
s(С
2
3
(I
1
3
(3, 2, 4), I
2
3
(5, 8, 1), I
3
3
( 5, 6, 7))) = 3.
2.
Приведите два самостоятельных примера применения оператора
примитивной рекурсии (аналогично примерам из конспекта
лекций).
3.
Напишите программу для машины Тьюринга в соответствии с
Вашим вариантом.
4.
Решите комбинаторную задачу в соответствии с Вашим вариантом.
95
Вариант 1
1.
Составьте программу машины Тьюринга, печатающей число 0.
В результате работы программы происходит следующее преоб-
разование машинных слов:
01
x
q
1
1
y
000 Î 0 1
x + y
0 q
0
10.
2.
В
n
-ичной системе счисления используется
n
цифр. Сколько в
ней натуральных чисел, записываемых
k
знаками?
Вариант 2.
1.
Составьте программу машины Тьюринга, стирающей данный
массив единиц. В результате работы программы происходит
следующее преобразование машинных слов:
01
x
0
y
1
z - 1
q
1
1 0 Î 0 1
x - 1
q
0
10
y + z +1
.
2.
Сколькими способами можно посадить за круглый стол
n
муж-
чин и
n
женщин так, чтобы никакие два лица одного пола не
сидели рядом?
Вариант 3
1.
Составьте программу машины Тьюринга, уменьшающей данное
число на единицу. В результате работы программы происходит
следующее преобразование машинных слов:
01
x
q
1
1
y
0 Î 0 1
x + y - 2
q
0
100.
2.
Из колоды, содержащей 52 карты, вынули 10 карт. В скольких
случаях окажется, что среди вынутых карт
а) хотя бы один туз;
б) ровно один туз.
Вариант 4
1.
Составьте программу машины Тьюринга, заполняющей едини-
цами промежуток до следующего справа массива единиц (за ис-
ключением одного нуля). В результате работы программы про-
исходит следующее преобразование машинных слов:
01
x
q
1
1 0
y + 1
1
z
Î 0 1
x + y
q
0
10 1
z
0
(x, y
≥ 0, z > 0).
2.
Из колоды, содержащей 52 карты, вынули 10 карт. В скольких
случаях окажется, что среди вынутых карт
а) не менее двух тузов;
б) ровно два туза.