ТЕМА 18

"Основные понятия и законы математической логики"

Пример 1

На числовой прямой заданы два отрезка: M[21, 28] и N[23, 33]. Определить наибольшую возможную длину отрезка А, для которого формула (xϵN) ⋁ ((xϵA) → (xϵM)) тождественно истинна, то есть принимает значение 1 при любом значении переменной x.

Решение

Сначала необходимо преобразовать исходное выражение в более простую форму записи:

N ⋁ (A → M), где N = (xϵN) ; M = (xϵM) ; A= (xϵA).

Изобразим числовую ось, обозначив на ней исходные отрезки:

В данном случае на числовой оси можно выделить пять интервалов:

Далее перейдем от импликации к дизъюнкции, используя правило: А →В = ¬А⋁В,

получим N ⋁¬A ⋁ M.

По условию задачи выражение: N ⋁ ¬A ⋁ M равно 1 при любом значении переменной x. Перепишем равенство в виде: (N ⋁ M) ⋁ ¬A = 1

Это выражение будет истинно в трех случаях (дизъюнкция двух переменных):

1) (N ⋁ M) =0; ¬A = 1

2) (N ⋁ M) =1; ¬A = 0

3) (N ⋁ M) =1; ¬A = 1

Только из первого случая можно однозначно сделать вывод, так как во втором и третьем случаях при (N ⋁ M) =1 отрицание А может принимать значение либо 0 либо 1.

Значит из первого условия, при (N ⋁ M) = 0, когда N = 0 и M = 0 (интервалы 1 и 5 над числовой осью) однозначно ¬A = 1. Это означает A = 0 (отсутствие отрезка А).

Следовательно, где N = 0 и M = 0 (отсутствие отрезков M и N) отрезка А не должно быть. Получили, что отрезок А должен перекрывать 2, 3 и 4 интервалы на числовой оси.

Находим длину этого отрезка: 33 – 21 = 12

Ответ: 12

Пример 2

Укажите наименьшее значение А, при котором выражение:

(x > 10) ∨ (2·x + y < A) ∨ (y > 20)

тождественно истинно (то есть принимает значение 1 для любых целых положительных значений x и y.).

Решение

Сначала перепишем исходное выражение в виде:

((x > 10) ∨ (y > 20)) ∨ (2·x + y < A) = 1, выделив слева известную часть, а справа с параметром А.

В таком случае выражение может быть равно 1 в трех ситуациях:

1) ((x > 10) ∨ (y > 20)) = 0; (2·x + y < A) = 1

2) ((x > 10) ∨ (y > 20)) = 1; (2·x + y < A) = 0

3) ((x > 10) ∨ (y > 20)) = 1; (2·x + y < A) = 1

Только из первого случая можно однозначно сделать вывод, так как во втором и третьем случаях при ((x > 10) ∨ (y > 20)) = 1 выражение (2·x + y < A) может принимать значение либо 0, либо 1.

Значит, из первого условия получаем, что (x > 10) = 0 и (y > 20) = 0, следовательно, x≤10, y≤20.

Подставим эти значения в неравенство (2·x + y < A), получим:

2·10 + 20 < A, значит A > 40.

По условию задачи необходимо определить наименьшее значение А, при условии A > 40.

Такое число 41.

Пример 3

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Например, 29&6 = 11101₂&00110₂ = 00100₂ = 4.

Для какого наименьшего неотрицательного целого числа А формула

x&20 ≠ 0 → (x&18 = 0 → x&А ≠ 0)

тождественно истинна (то есть принимает значение 1 при любом неотрицательном целом значении переменной х)?

Решение

Преобразуем исходное выражение, используя правило: А →В = ¬А∨В

¬(x&20 ≠ 0) ∨ (x&18 = 0 → x&А ≠ 0) = 1

(x&20 = 0) ∨ (¬(x&18 = 0)∨( x&А ≠ 0)) = 1

(x&20 = 0) ∨ (x&18 ≠ 0)∨( x&А ≠ 0) = 1

((x&20 = 0) ∨ (x&18 ≠ 0)) ∨ ( x&А ≠ 0) = 1

Это выражение будет истинно в трех случаях (дизъюнкция двух переменных):

1) ((x&20 = 0) ∨ (x&18 ≠ 0)) = 0 - ЛОЖЬ; ( x&А ≠ 0) = 1 - ИСТИНА

2) ((x&20 = 0) ∨ (x&18 ≠ 0)) = 1 - ИСТИНА; ( x&А ≠ 0) = 0 - ЛОЖЬ

3) ((x&20 = 0) ∨ (x&18 ≠ 0)) = 1 - ИСТИНА; ( x&А ≠ 0) = 1 - ИСТИНА

Однозначное решение можно получить лишь из первого случая, так как для

((x&20 = 0) ∨ (x&18 ≠ 0)) = 1 выражение ( x&А ≠ 0) может быть как истинным так и лживым.

Из первого случая получаем, так как ((x&20 = 0) ∨ (x&18 ≠ 0)) = 0 – ЛОЖЬ, то

(x&20 = 0) – ЛОЖЬ и (x&18 ≠ 0) – ЛОЖЬ.

Значит (x&20 ≠ 0) – ИСТИНА, (x&18 = 0) – ИСТИНА и ( x&А ≠ 0)- ИСТИНА

Запишем двоичное представление чисел и проанализируем поразрядную конъюнкцию:

Число А будет наименьшим, если 4, 3 и 0 –й биты будут равны нулю.

Значит А = 100₂ = 4₁₀.

Ответ: 4

Пример 4

Элементами множеств А, M, N являются натуральные числа, причём M = {3, 5, 7, 9, 11, 13, 15, 17, 19, 21}, N = {2, 5, 8, 11, 14, 17, 20, 23, 26, 29}.

Известно, что выражение (¬(x ∈ A) → ¬(x ∈ N)) ∨ ((x ∈ M) → (x ∈ A)) истинно (то есть принимает значение 1) при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A.

Решение

Преобразуем исходное выражение, используя правило: А →В = ¬А∨В.

((x ∈ A) ∨ ¬(x ∈ N)) ∨ (¬(x ∈ M) ∨ (x ∈ A)) = 1

(x ∈ A) ∨ ¬(x ∈ N) ∨ ¬(x ∈ M) = 1

(x ∈ A) ∨ ( ¬(x ∈ N) ∨ ¬(x ∈ M)) = 1

Это выражение будет истинно в трех случаях (дизъюнкция двух переменных):

1) ( ¬(x ∈ N) ∨ ¬(x ∈ M)) = 0 - ЛОЖЬ; (x ∈ A) = 1 - ИСТИНА

2) ( ¬(x ∈ N) ∨ ¬(x ∈ M)) = 1 - ИСТИНА; (x ∈ A) = 0 - ЛОЖЬ

3) ( ¬(x ∈ N) ∨ ¬(x ∈ M)) = 1 - ИСТИНА; (x ∈ A) = 1 - ИСТИНА

Однозначное решение можно получить лишь из первого случая, по той же причине, что и в предыдущих задачах.

Значит, при ( ¬(x ∈ N) ∨ ¬(x ∈ M)) = 0 получаем:

¬(x ∈ N) = 0 – ЛОЖЬ и ¬(x ∈ M)) = 0 – ЛОЖЬ, следовательно

(x ∈ N) = 1 - ИСТИНА

(x ∈ M)) = 1 - ИСТИНА

Учитываем, что (x ∈ A) = 1 – ИСТИНА, получаем, что все элементы множества А должны лежать в множествах M и N (общие элементы множеств M и N).

Таких элементов три: 5, 11, 17. Их сумма равна: 5 + 11 + 17 = 33

Ответ: 33

• Примеры, рассмотренные на этой странице в формате pdf: скачать
• Решенные задачи по теме других авторов: скачать
• Смотреть видеоуроки по теме: видео 1, видео 2, видео 3

Комментарии, отзывы и предложения Вы можете направить на e-mail, указанный в контактах или оставить в гостевой книге, указав тему вопроса: перейти в гостевую книгу