Задача №15. Использование основных понятий математической логики. Логические высказывания, числовые отрезки.

Автор материалов - Лада Борисовна Есакова.

Законы алгебры логики

Поиск слова, удовлетворяющего условию логического высказывания

Пример 1.

Для какого имени истинно высказывание:

(Вторая буква гласная  → Первая буква гласная) Ù   Последняя  буква согласная?

1) ИРИНА           2) МАКСИМ             3) МАРИЯ                 4) СТЕПАН

Решение:

Высказывание является конъюнкцией двух выражений (Вторая буква гласная  → Первая буква гласная) и Последняя  буква согласная. Конъюнкция истинна тогда, когда все операнды истинны. Значит, выражение Последняя  буква согласная должно быть истинным. Этому условию удовлетворяют имена под номерами 2 и 4.

Поочередно подставим в высказывание значения выражений для имен 2 и 4:

2) МАКСИМ

Вторая буква гласная = 1

Первая буква гласная = 0

Последняя буква согласная = 1

(1      → 0) Ù 1 = 0 Ù 1 = 0              Высказывание ложно.

4)      СТЕПАН

Вторая буква гласная = 0

Первая буква гласная = 0

Последняя буква согласная = 1

(0 → 0) Ù 1 = 1 Ù 1 = 0                Высказывание истинно.

Ответ: 4

Поиск числа, удовлетворяющего условию логического высказывания

Пример 2.

Для ка­ко­го из при­ведённых чисел X ис­тин­но ло­ги­че­ское усло­вие:

¬((X крат­но 5) →  (X крат­но 25))?

1) 37

2) 59

3) 65

4) 125

Решение:

Для того, чтобы ло­ги­че­ское усло­вие ¬((X крат­но 5) →  (X крат­но 25)) было истинным, необходимо, чтобы условие (X крат­но 5) →  (X крат­но 25) было ложным.  Им­пли­ка­ция воз­вра­ща­ет ложь, толь­ко если первый операнд равен 1 (истина), а второй - 0 (ложь).

Т.е. число Х должно быть кратно 5, но не кратно 25.

Этому условию удовлетворяет только число под но­ме­ром 3 (65).

Ответ:3

Пример 3.

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 1110₂&0101₂ = 0100₂ = 4. Для какого наименьшего неотрицательного целого числа A формула x&25 ≠ 0 → (x&17 = 0 → x&А ≠ 0) тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х)?

Решение:

Для наглядности введем обозначения: A ≡ (x&A ≠ 0); B ≡ (x&25 ≠ 0); C ≡ (x&17 = 0).

Тогда формула принимает вид: B → (C → A) = 1

Заменяем первую импликацию: ¬В \/ (C → A) = 1

Заменяем импликацию в скобках: ¬В \/ (¬C \/ A) = 1

В результате имеем: ¬В \/ ¬C \/ A = 1

x&25 = 0 \/ x&17 ≠ 0 \/ x&A ≠ 0 = 1

Выражение является дизъюнкцией трех операндов. Дизъюнкция истинна, когда хотя бы один операнд принимает значение истина (1).

25₁₀ = 11001₂ , тогда x&25 = 0 истинно для всех х, имеющих нули в 0-м, 3-м и 4-м (справа) разрядах двоичной записи: х = *…*00**0                                                                         

17₁₀ = 10001₂ , тогда x&17 ≠ 0 истинно для всех х, имеющих единицы в 0-м или 4-м разряде: x = *…*1 или x = *…1****.

«незакрытыми» (не входящими ни в первое, ни во второе множество) на числовой оси остались x, имеющие нули в 0-м и 4-м разрядах и единицу в 3-м разряде: x = *…*01**0.

Значит, A должно быть таким, чтобы конъюнкция с оставшимися числами x не была равна нулю, т.е. в 3-м разряде двоичной записи числа A должна стоять единица. Наименьшим таким числом является 1000₂ = 8₁₀.

Ответ:8

Поиск числового отрезка, удовлетворяющего условию логического высказывания

Пример 4.

На чис­ло­вой пря­мой даны два от­рез­ка: P=[3, 13] и Q=[7, 17]. Вы­бе­ри­те такой от­ре­зок A, чтобы фор­му­ла

( (x ∈ A) → (x ∈ P) ) ∨ ¬ (x ∈ Q)

была тож­де­ствен­но ис­тин­на, то есть при­ни­мала зна­че­ние 1 при любом зна­че­нии пе­ре­мен­ной x.

1) [5, 20]

2) [10, 25]

3) [15, 30]

4) [20, 35]

Решение:

Вве­дем обо­зна­че­ния:

(x ∈А) ≡ A; (x ∈ P) ≡ P; (x ∈ Q) ≡ Q.

При­ме­нив пре­об­ра­зо­ва­ние им­пли­ка­ции, по­лу­ча­ем:

¬A ∨ P ∨ ¬ Q.

Изобразим множества P и ¬ Q на числовой прямой:

Вы­ра­же­ние долж­но быть ис­тин­но для лю­бо­го x, значит нужно «закрасить» всю числовую прямую. Для этого выражение ¬A долж­но «закрасить» оставшийся отрезо­к [13;17], т.е. быть истинным на этом отрезке. Тогда, вы­ра­же­ние A долж­но быть ис­тин­но внут­ри про­ме­жут­ка, ко­то­рый не имеет ни одной общей точки с отрезком [13;17].

Из всех от­рез­ков толь­ко от­ре­зок [20, 35] удо­вле­тво­ря­ет этим усло­ви­ям:

Пра­виль­ный ответ ука­зан под но­ме­ром 4.

Ответ:4

Пример 5.

На чис­ло­вой пря­мой даны два от­рез­ка: P = [25; 50] и Q = [32; 47]. Ука­жи­те наи­боль­шую воз­мож­ную длину про­ме­жут­ка A, для ко­то­ро­го фор­му­ла

(¬ (x ΠA) → (x Î P)) → ((x Î A) → (x Î Q))

тож­де­ствен­но ис­тин­на, то есть при­ни­ма­ет зна­че­ние 1 при любом зна­че­нии пе­ре­мен­ной х.

Решение:

Введем обозначения:

(x ∈А) ≡ A; (x ∈ P) ≡ P; (x ∈ Q) ≡ Q.

Тогда формула примет вид:

(¬ A → P) → (A → Q)

Пре­об­ра­зу­ем дан­ное вы­ра­же­ние (заменим импликацию):

(A ∨ ¬ P) → (¬ A ∨ Q)

¬  (A ∨ ¬ P) ∨ (¬ A ∨ Q)

(¬ A ∧ P) ∨ ¬ A ∨ Q

((¬ A ∧ P) ∨ ¬ A) ∨ Q

¬ A ∨ Q

Выражение (¬ A ∨ Q) должно быть истинным на всей числовой прямой. Множество Q – это отрезок [32, 47], значит выражение ¬A долж­но «закрасить» оставшуюся часть числовой оси, т.е. быть истинным на этом промежутке. Тогда, вы­ра­же­ние A долж­но быть ис­тин­но внут­ри про­ме­жут­ка [32;47]. Тогда максимальная длина отрезка A достигается, когда А совпадает с Q, и равна 15.

Ответ:15

Поиск множества чисел, удовлетворяющего условию логического высказывания

Пример 6.

Эле­мен­та­ми мно­жеств А, P, Q яв­ля­ют­ся на­ту­раль­ные числа, причём

P = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}, Q = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}.

Из­вест­но, что вы­ра­же­ние ((x  A) → (x  P)) ∨ (¬(x  Q) → ¬(x  A))

ис­тин­но (т. е. при­ни­ма­ет зна­че­ние 1) при любом зна­че­нии пе­ре­мен­ной х.

Опре­де­ли­те наи­боль­шее воз­мож­ное ко­ли­че­ство эле­мен­тов в мно­же­стве A.

Решение:

Введем обозначения:

(x ∈А) ≡ A; (x ∈ P) ≡ P; (x ∈ Q) ≡ Q.

Тогда выражение примет вид:

(A → P) ∨ (¬ Q → ¬ A)

Преобразуем выражение (заменим импликацию):

(¬ A ∨ P) ∨ ( Q  ∨ ¬ A)

¬ A ∨ P ∨ Q

Чтобы выражение было истинно при любом зна­че­нии пе­ре­мен­ной х, все натуральные числа должны либо входить в P, либо входить в Q, либо не входить в A. Т.е. ¬ A – это все числа, не входящие ни в P, ни в Q. Значит A – это числа, входящие в P или Q. Наи­боль­шее воз­мож­ное ко­ли­че­ство эле­мен­тов в мно­же­стве A – это количество всех различных элементов множеств P и Q. Таких элементов 17.

Ответ:17

Пример 7.

Эле­мен­та­ми мно­же­ства А яв­ля­ют­ся на­ту­раль­ные числа. Из­вест­но, что вы­ра­же­ние

(x ∈ {2, 4, 6, 8, 10, 12}) → (((x ∈ {3, 6, 9, 12, 15}) ∧ ¬(x ∈ A)) → ¬(x ∈ {2, 4, 6, 8, 10, 12}))

ис­тин­но (т. е. при­ни­ма­ет зна­че­ние 1) при любом зна­че­нии пе­ре­мен­ной х. Опре­де­ли­те наи­мень­шее воз­мож­ное зна­че­ние суммы эле­мен­тов мно­же­ства A.

Решение:

Вве­дем обо­зна­че­ния:

(x ∈ {2, 4, 6, 8, 10, 12}) ≡ P; (x ∈ {3, 6, 9, 12, 15}) ≡ Q; (x ∈ A) ≡ A.

Тогда выражение примет вид:

P → ((Q ∧ ¬A) → ¬P)

Преобразуем выражение (заменим импликацию):

P → (¬(Q ∧ ¬А) ∨ ¬P)

¬P ∨ (¬(Q ∧ ¬А) ∨ ¬P)

¬P ∨ ¬Q ∨ А.

Вы­ра­же­ние ¬P ∨ ¬Q ис­тин­но при всех зна­че­ни­ях x, кроме зна­че­ний 6 и 12. Сле­до­ва­тель­но, про­ме­жу­ток А долж­ны со­дер­жать точки 6 и 12. То есть ми­ни­маль­ный набор точек в про­ме­жут­ке А ≡ {6, 12}. Сумма эле­мен­тов мно­же­ства А равна 18.

Ответ:18