Основы дискретной математики

Упражнение 1:

Номер 1

Построить таблицу для функции, заданной формулой

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

Ответ:

(1) 2

(2) 3

(3) 4

(4) 5

(5) 6

(6) 7

Номер 2

Построить таблицу для функции, заданной формулой

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

Ответ:

(1) 2

(2) 3

(3) 4

(4) 5

(5) 6

(6) 7

Номер 3

Построить таблицу для функции, заданной формулой

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

Ответ:

(1) 2

(2) 3

(3) 4

(4) 5

(5) 6

(6) 7

Упражнение 2:

Номер 1



Представленная выше таблица показывает бинарное кодирование десятичных цифр от 0 до 9. Какие из булевых формул задают множество всех ошибочных кодов?

Ответ:

(1) (A ∨ (B ∧ C))

(2) ((A ∧ B) ∧ (C ∧ D))

(3) ((A ∧ B) ∨ (A ∧ D))

(4) ((A ∧ B) ∨ (C ∧ D))

(5) ((A ∧ B) ∨ (A ∧ C))

Номер 3


Представленная выше таблица показывает бинарное кодирование десятичных цифр от 0 до 9 (коды начинаются с 4-ой строки). Какие из булевых формул задают множество всех ошибочных кодов?

Ответ:

(1) (¬A ∨ ¬B) ∧(¬C ∨ ¬D))

(2) (((A ~ B) ∧ ¬(C~D)) ∨ ((A ∧ B) ∧ (C ∧ D)))

(3) (((¬A ∧ ¬B) ∧(¬C ∨ ¬D)) ∨ ((A ∧ B) ∧(C ∨ D)))

(4) (((A ↓ B) ∧(¬C ∨ ¬D)) ∨ ( (A ∧ C) ∧ D))

(5) ((¬A ∧ ¬B) ∨ (C → ¬D))

Упражнение 3:

Номер 1

Булева функция f(X₀, X₁, X₂)равна 1, если число, двоичная запись которого имеет вид X₂X₁X₀, равно 1, 4, 5или 6. Какая из следующих формул задает эту функцию?

Ответ:

(1) ((¬X₀ ∨ ¬X₁ ) ∨ ¬X₂)

(2) ((¬X₂ ∧ X₀) ∨ (X₂ ∧ X₁))

(3) ((¬X₁∧ X₀) ∨ (X₂ ∧ ¬X₀))

(4) ((¬X₂ ∧ (X₁ ∧ X₀)) ∨ (X₂ ∧ ¬X₁))

(5) (X₂ ∨ (¬X₁ ∧ X₀))

Номер 2

Булева функция f(X₀, X₁, X₂)равна 1, если число, двоичная запись которого имеет вид X₂X₁X₀, равно 3, 4, 5или 7. Какая из следующих формул задает эту функцию?

Ответ:

(1) ((X₀ ∨ ¬X₁) ∨ ¬X₂)

(2) ((X₀ ∧ X₁) ∨ (X₂ ∧ ¬X₁))

(3) ((¬X₁ ∧ X₀) ∨ (X₂ ∧ ¬X₀))

(4) ((X₂ ∧ X₁) ∧ X₀) ∨ (X₂ ∧ ¬X₁))

(5) (X₂ ∨ (¬X₁ ∧ X₀))

Номер 3

Булева функция f(X₀, X₁, X₂)равна 1, если число, двоичная запись которого имеет вид X₂X₁X₀, равно 1, 2, 3или 5. Какая из следующих формул задает эту функцию?

Ответ:

(1) ((X₀∨ ¬X₁ ) ∨ ¬X₂)

(2) ( (X₀ ∧ X₁ ) ∨ (X₂ ∧ ¬X₁))

(3) ((¬X₁ ∧ X₀) ∨ (X₂ ∧ ¬X₀))

(4) ((X₁ ∧ ¬X₂) ∨ (X₀ ∧ ¬X₁))

(5) (X₂ ∨ (¬X₁ ∧ X₀))

Упражнение 4:

Номер 1

Какие из следующих формул являются тождественно истинными?
,
,
,

Ответ:

(1) ни одна

(2) только A

(3) только B

(4) A и B

(5) A и C

(6) A, B и C

(7) A, C и D

(8) все

Номер 2

Какие из следующих формул являются тождественно истинными?
,
,
,

Ответ:

(1) ни одна

(2) только A

(3) только B

(4) A и B

(5) A и C

(6) B и C

(7) A, Cи D

(8) все

Номер 3

Какие из следующих формул являются тождественно истинными?

,
,
,

Ответ:

(1) ни одна

(2) только A

(3) только B

(4) A и B

(5) A и C

(6) A, C и D

(7) A, B и C

(8) B, C и D

Упражнение 5:

Номер 1

Какие из следующих условий можно выразить булевскими формулами от переменных p₁, p₂, p₃, p₄, использующими лишь логические связки ∨и ∧(без отрицания ¬)?
По крайней мере три переменных из p₁, p₂, p₃, p₄истинны (равны 1).
В точности три переменных из p₁, p₂, p₃, p₄истинны (равны 1).
Четное число переменных из p₁, p₂, p₃, p₄истинны (равны 1).

Ответ:

(1) только 1

(2) только 2

(3) только 3

(4) 1 и 2

(5) 1 и 3

(6) 2 и 3

Номер 2

Какие из следующих условий можно выразить булевскими формулами от переменных p₁, p₂, p₃, p₄, использующими лишь логические связки ∧и ∨(без отрицания ¬)?
По крайней мере две переменные из p₁, p₂, p₃, p₄истинны (равны 1).
В точности две переменных из p₁, p₂, p₃, p₄истинны (равны 1).
Хотя бы одна переменная из p₁, p₂, p₃, p₄истинна (равна 1).

Ответ:

(1) только 1

(2) только 2

(3) только 3

(4) 1 и 2

(5) 1 и 3

(6) 2 и 3

Номер 3

Какие из следующих условий можно выразить булевскими формулами от переменных p₁, p₂, p₃, p₄, использующими лишь логические связки ∧и ∨(без отрицания ¬)?
По крайней мере две переменные из p₁, p₂, p₃, p₄истинны (равны 1).
Не все из переменных из p₁, p₂, p₃, p₄ложны (равны 0).
Нечетное число переменных из p₁, p₂, p₃, p₄истинны (равны 1).

Ответ:

(1) только 1

(2) только 2

(3) только 3

(4) 1 и 2

(5) 1 и 3

(6) 2 и 3

Упражнение 6:

Номер 1

Детектив Ш. Холмс подозревает в совершении преступления
трех лиц: Джонса, Брауна и Карта. Он установил, что
если Браун преступник, то и Карт является преступником ;
кто-то один из пары Джонс, Карт является преступником, но не оба вместе;
если Карт не преступник, то и Джонс не преступник.
Какие из следующих выводов он может сделать из установленных фактов:
Джонс является преступником.
Браун является преступником.
Карт является преступником.
Преступник действовал в одиночку.

Ответ:

(1) только 1

(2) только 2

(3) только 3

(4) 1 и 4

(5) 2 и 3

(6) 3 и 4

(7) 1 и 3

Номер 2

Детектив Ш. Холмс подозревает в совершении преступления
трех лиц: Джонса, Брауна и Карта. Они дали следующие показания:
Джонс: если Браун преступник, то Карт не виновен.
Браун: если Джонс виновен, то и Карт является преступником.
Карт: Джонс преступник.

Ш. Холмс установил, что если Джонс сказал правду, то Браун соврал, и что показаниям Карта нельзя доверять.

Какие из следующих выводов он может сделать из установленных фактов:

Джонс является преступником.
Браун является преступником.
Карт является преступником.
Преступников могло быть двое.

Ответ:

(1) только 1

(2) только 2

(3) только 3

(4) 1 и 4

(5) 2 и 3

(6) 2 и 4

(7) 1 и 3

Номер 3

Детектив Ш. Холмс подозревает в совершении преступления
трех лиц: Джонса, Брауна и Карта. Он установил, что
если Джонс не преступник, то Браун является преступником ;
кто-то один из пары Джонс, Карт является преступником, но не оба вместе;
Браун и Карт вместе не совершали преступление.
Какие из следующих выводов он может сделать из установленных фактов:
Джонс является преступником.
Браун является преступником.
Карт является преступником.
Преступник действовал в одиночку.

Ответ:

(1) только 1

(2) только 2

(3) только 3

(4) 1 и 4

(5) 2 и 3

(6) 3 и 4

(7) 1 и 3

Основы дискретной математики - тест 3