Дискретная математика. Булевы функции. Сборник контрольных работ

Викторова Н.Б.

Возрастное ограничение: 0+ Жанр: Наука Издательство: Проспект Дата размещения: 20.12.2017 ISBN: 9785392267453 Язык: Объем текста: 40 стр. Формат: epub

Оглавление

Введение

Теоретическая часть

Контрольная работа 1. Простейшие свойства функций алгебры логики

Контрольная работа 2. Специальные представления булевых функций

Контрольная работа 3. Полнота систем функций алгебры логики

Ответы

Заключение

Для бесплатного чтения доступна только часть главы! Для чтения полной версии необходимо приобрести книгу

Ответы

Контрольная работа 1

Вариант 1

1. Длина 4, вес 3, номер 13.

2. 4, противоположные.

3. Формулы не эквивалентны.

4. (1111).

5. x — существенная переменная, y –существенная переменная, z — фиктивная переменная, f = xy.

6. f * = x ~ y.

7. (((x3 | x1) ˅ x3) ~ (((x2 → x3) & x1) → (¬ x3))).

Вариант 2

1. Длина 4, вес 3, номер 14.

2. 4, противоположные.

3. Формулы не эквивалентны.

4. (1101).

5. x — фиктивная переменная, y — существенная переменная, z — существенная переменная, f = yz.

6. f * = x ⊕ y.

7. ((x2 → x3) ⊕ (((x2 ~ x3) & x3) ~ (x3 ˅ (x1 ˅ x3)))).

Вариант 3

1. Длина 5, вес 2, номер 17.

2. 1, соседние.

3. Формулы не эквивалентны.

4. (1101).

5. x — существенная переменная, y — фиктивная переменная, z — существенная переменная. f = z.

6. f * = x ˅ y.

7. ((x3 ˅ (¬ x3)) ~ (x3 → ((x2 | x1) → (x1 ˅ x3)))).

Вариант 4

1. Длина 5, вес 2, номер 18.

2. 4, противоположные.

3. Формулы не эквивалентны.

4. (1000).

5. x — фиктивная переменная, y — существенная переменная, z — существенная переменная, f = y.

6. f * = xy.

7. (((x2 → (¬ x1)) → (¬ x3)) ↓ (x3 → x2)).

Вариант 5

1. Длина 5, вес 3, номер 19.

2. 4, противоположные.

3. Формулы не эквивалентны.

4. (1110).

5. x — существенная переменная, y — существенная переменная, z — фиктивная переменная, f = x ˅ y.

6. f * = y.

7. ((x2 ˅ (¬ x2)) ⊕ (((x3 | x2) ↓ x2) | x2)).

Вариант 6

1. Длина 5, вес 2, номер 20.

2. 2.

3. Формулы эквивалентны.

4. (1110).

5. x — фиктивная переменная, y — существенная переменная, z — существенная переменная, f = y | z.

6. f * = x.

7. ((((¬ x1) ˅ x2) | x1) ⊕ ((x1 ⊕ x3) ↓ (¬ x1))).

Вариант 7

1. Длина 5, вес 3, номер 21.

2. 5, противоположные.

3. Формулы эквивалентны.

4. (1110).

5. x — существенная переменная, y — фиктивная переменная, z — существенная переменная, f = xz.

6. f * = x | y.

7. ((((x2 & x3) ⊕ (¬ x3)) & x2) & (x3 ⊕ (x3 ↓ x1))).

Вариант 8

1. Длина 5, вес 3, номер 22.

2. 1, соседние.

3. Формулы не эквивалентны.

4. (1101).

5. x — фиктивная переменная, y — существенная переменная, z — существенная переменная, f = y ˅ z.

6. f * = x ↓ y.

7. (((¬ x2) → (x2 ↓ (x3 & x2))) ⊕ (x3 ~ (¬ x2))).

Вариант 9

1. Длина 4, вес 3, номер 7.

2. 2.

3. Формулы эквивалентны.

4. (1111).

5. x — существенная переменная, y — существенная переменная, z — фиктивная переменная, f = x ↓ y.

6. f * = x → y.

7. ((x2 & x3) & (((x3 | x1) ⊕ (¬ x1)) ⊕ ((¬ x3) & x2))).

Вариант 10

1. Длина 5, вес 4, номер 23.

2. 7, противоположные.

3. Формулы эквивалентны.

4. (1100).

5. x — существенная переменная, y — фиктивная переменная, z — существенная переменная, f = x | z.

6. f * = x | y.

7. ((¬ (x2 ↓ (¬ x1))) ↓ (x3 | ((x1 & x3) ⊕ x1))).

Вариант 11

1. Длина 5, вес 5, номер 31.

2. 6.

3. Формулы эквивалентны.

4. (1010).

5. x — существенная переменная, y — фиктивная переменная, z — существенная переменная, f = z → x.

6. f * = x ↓ y.

7. (((x2 ~ (¬ x1)) → x3) | (x1 ~ (x2 & (¬ x1)))).

Вариант 12

1. Длина 5, вес 3, номер 25.

2. 1, соседние.

3. Формулы эквивалентны.

4. (0011).

5. x — существенная переменная, y — существенная переменная, z — фиктивная переменная, f = x ⊕ y.

6. f * = y.

7. ((x3 ↓ (x1 ⊕ x2)) → (x3 & (¬ (x2 ˅ x3)))).

Вариант 13

1. Длина 5, вес 3, номер 26.

2. 1, соседние.

3. Формулы не эквивалентны.

4. (1011).

5. x — существенная переменная, y — фиктивная переменная, z — существенная переменная, f = x ˅ z.

6. f * = x ~ y.

7. ((¬ (x3 | x2)) ⊕ (((x1 | x2) ˅ x3) ↓ x3)).

Вариант 14

1. Длина 5, вес 4, номер 27.

2. 2.

3. Формулы эквивалентны.

4. (0101).

5. x — фиктивная переменная, y — существенная переменная, z — существенная переменная, f = y ⊕ z.

6. f * = x ⊕ y.

7. (((x3 & (x3 ⊕ x1)) ⊕ (x3 → x1)) ~ ((¬ x1) ˅ x2)).

Вариант 15

1. Длина 5, вес 3, номер 28.

2. 7, противоположные.

3. Формулы не эквивалентны.

4. (0101).

5. x — существенная переменная, y — фиктивная переменная, z — существенная переменная, f = x ↓ z.

6. f * = x.

7. (((¬ (x1 ˅ x2)) ~ (¬ (x1 & x3))) & (x2 → x3)).

Вариант 16

1. Длина 6, вес 4, номер 57.

2. 1, соседние.

3. Формулы не эквивалентны.

4. (0000).

5. x — фиктивная переменная, y — существенная переменная, z — существенная переменная, f = y ~ z.

6. f * = y.

7. ((¬ ((x2 ↓ x1) → (x3 ˅ x3))) ⊕ ((x1 & x3) ⊕ x3)).

Вариант 17

1. Длина 6, вес 4, номер 58.

2. 1, соседние.

3. Формулы не эквивалентны.

4. (1111).

5. x — существенная переменная, y — существенная переменная, z — фиктивная, f = x ~ y.

6. f * = xy.

7. ((¬ (x2 ↓ (¬ x3))) & (x3 | ((x1 & x3) ⊕ x1))).

Вариант 18

1. Длина 7, вес 4, номер 90.

2. 6, противоположные.

3. Формулы не эквивалентны.

4. (0101).

5. x — существенная переменная, y — существенная переменная, z — фиктивная переменная, f = x → y.

6. f * = x ↓ y.

7. ((x2 → (x3 ˅ x1)) ⊕ ((¬ (¬ x2)) ↓ (x3 & x1))).

Вариант 19

1. Длина 7, вес 5, номер 91.

2. 8, противоположные.

3. Формулы не эквивалентны.

4. (1011).

5. x — фиктивная переменная, y — существенная переменная, z — существенная переменная, f = y → z.

6. f * = xy.

7. ((((x3 & x2) ⊕ x3) ˅ (x2 & x1)) & (x2 ~ (x3 → x2))).

Вариант 20

1. Длина 7, вес 4, номер 92.

2. 7.

3. Формулы не эквивалентны.

4. (0100).

5. x — существенная переменная, y — фиктивная переменная, z — существенная переменная, f = x ⊕ z.

6. f * = x ↓ y.

7. ((((x1 ~ x3) ˅ x2) & (¬ (x3 ˅ x2))) → ((¬ x2) ˅ (¬ x3))).

Вариант 21

1. Длина 8, вес 6, номер 219.

2. 1, соседние.

3. Формулы не эквивалентны.

4. (1000).

5. x — существенная переменная, y — существенная переменная, z — фиктивная переменная, f = .

6. f * = x ⊕ y.

7. (¬ (((¬ x1) ⊕ x1) & ((x3 → x1) ~ (x3 ˅ x1)))).

Вариант 22

1. Длина 8, вес 5, номер 218.

2. 8, противоположные.

3. Формулы не эквивалентны.

4. (0111).

5. x — существенная переменная, y — фиктивная переменная, z — существенная переменная, f = x ~ z.

6. f * = x ⊕ y.

7. ((¬ (¬(x2 & x1))) | (x2 → ((x1 | x3) ↓ x1))).

Вариант 23

1. Длина 8, вес 5, номер 211.

2. 1, соседние.

3. Формулы не эквивалентны.

4. (0100).

5. x — существенная переменная, y — фиктивная переменная, z — фиктивная переменная, f = .

6. f * = x ~ y.

7. (((x2 → x1) ~ x3) ⊕ ((x2 → (x2 ˅ x3)) & (¬ x3))).

Вариант 24

1. Длина 8, вес 5, номер 155.

2. 1, соседние.

3. Формулы эквивалентны.

4. (0001).

5. x — существенная переменная, y — фиктивная переменная, z — существенная переменная, f = x → z.

6. f * = x ~ y.

7. ((x1 | (x3 | (x1 ⊕ x3))) & ((x1 ↓ x3) → (¬ x1))).

Вариант 25

1. Длина 9, вес 6, номер 438.

2. 1, соседние.

3. Формулы эквивалентны.

4. (0000).

5. x — фиктивная переменная, y — существенная переменная, z — фиктивная переменная, f = .

6. f * = x.

7. ((((x3 & x2) ~ x3) → x1) ↓ ((x1 → (x1 & x2)) | x1)).

Вариант 26

1. Длина 9, вес 7, номер 439.

2. 6, противоположные.

3. Формулы не эквивалентны.

4. (1010).

5. x — существенная переменная, y — фиктивная переменная, z — существенная переменная, f = .

6. f * = x → y.

7. (¬ ((x3 → (x2 & x1)) → (x2 ↓ (x2 & x3)))).

Вариант 27

1. Длина 10, вес 8, номер 951.

2. 6, противоположные.

3. Формулы не эквивалентны.

4. (0111).

5. x — фиктивная переменная, y — фиктивная переменная, z — существенная переменная, f = .

6. f * = y → x.

7. (((x2 ↓ x3) ⊕ x2) ˅ ((x2 ~ x3) & (x2 & x3))).

Вариант 28

1. Длина 10, вес 8, номер 951.

2. 4, противоположные.

3. Формулы не эквивалентны.

4. (0000).

5. x — существенная переменная, y — существенная переменная, z — фиктивная переменная, f = .

6. f * = x → y.

7. (((¬ (x3 ~ x1)) ⊕ ((x1 & x2) ~ x2)) | (x1 ⊕ (x1 → x2))).

Вариант 29

1. Длина 10, вес 7, номер 695.

2. 6, противоположные.

3. Формулы не эквивалентны.

4. (1010).

5. x — существенная переменная, y — существенная переменная, z — фиктивная переменная, f = y → x.

6. f * = x → y.

7. ((((x3 → x1) & x3) → (¬ (¬ x2))) & (x1 & x2)).

Вариант 30. Решение всего варианта

1. Найти длину, вес и номер двоичного набора (1000110111).

Решение. Длина двоичного набора — 10. Вес (или норма) набора — число координат, равных единице. У нас 6. Число , где n — длина набора, αi — i-я координата набора, начиная слева, называется номером набора.

= 1 · 29 + 0 · 28 + 0 · 27 + 0 · 26 + 1 · 25 + 1 · 24 + 0 · 23 + 1 · 22 + + 1 · 21 + 1 = 567.

2. Найти расстояние Хэмминга между вершинами α = (10111) и β = (01000) куба B 5. Определить, являются ли эти наборы противоположными или соседними?

Решение. Расстоянием Хэмминга между вершинами α и β называется число ρ(α, β) = . У нас расстояние равно 5. Наборы являются противоположными.

3. Построив таблицы истинности функций, реализуемых формулами U и B, выяснить, эквивалентны ли формулы U = x ⊕ (y | z) и B = (x ⊕ y) | (x ⊕ z).

Решение. Пусть функция f реализуется формулой U, а функция g реа­лизуется формулой B. Построим их таблицы истинности.

Викторова Н.Б. Дискретная математика. Булевы функции. Сборник контрольных работ

Викторова Н.Б. Дискретная математика. Булевы функции. Сборник контрольных работ

Данное пособие представляет собой сборник однотипных контрольных работ по дискретной математике, а именно по такому разделу, как булевы функции.<br /> Эти контрольные предлагались студентам факультета информационных систем и безопасности Института информационных наук и технологий безопасности РГГУ на протяжении нескольких последних лет. Ко всем задачам имеются ответы.<br /> Последний вариант каждой контрольной полностью разобран.<br /> Пособие рассчитано на студентов первого и второго курсов. Книга также может быть полезна преподавателям, которые начинают читать курс дискретной математики.

Внимание! Авторские права на книгу "Дискретная математика. Булевы функции. Сборник контрольных работ" (Викторова Н.Б.) охраняются законодательством!