Погода
Календарь
Май 2019
Пн Вт Ср Чт Пт Сб Вс
« Сен    
 12345
6789101112
13141516171819
20212223242526
2728293031  
Страницы сайта

Преобразование логических выражений.

Что нужно знать:

  • условные обозначения логических операций

¬ A, не A (отрицание, инверсия)
A * B, A и B (логическое умножение, конъюнкция)
A + B, A или B (логическое сложение, дизъюнкция)
A B  импликация (следование)

  • таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация»
  • операцию «импликация» можно выразить  через «ИЛИ» и «НЕ»:
    A B = ¬ A+ B 
  • если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем  – «ИЛИ», и самая последняя – «импликация»
  • иногда полезны формулы де Моргана[1]:

¬ (A * B) = ¬ A + ¬ B          

¬ (A + B) = ¬ A * ¬ B          

  • для упрощения выражений можно использовать формулы
  • некоторые свойства импликации

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ МНОЖЕСТВ

  • пересечение множеств соответствует логическому умножению, а объединение – логическому сложению;
  • пересечением двух множеств называется новое множество, состоящее из элементов, принадлежащих одновременно обеим множествам:

Пример:

объединением двух множеств называется новое множество, состоящее из элементов, принадлежащих отдельно каждому из множеств (без повторений);

Пример

  • пустое множество  – это множество, в котором не содержится ни одного элемента; пустому множеству в теории множеств соответствует 0;
  • универсальное множество U (на кругах Эйлера обозначается в виде прямоугольника) – это множество, содержащее все возможные элементы определенного типа (например, все вещественные числа):


универсальное множество
  • универсальное множество соответствует логической единице: для любого множества целых чисел Xсправедливы равенства:
    X ∨ U = U и X ∧ U = X
    разностью двух множеств A и B называется новое множество, элементы которого принадлежат A, но не принадлежат B:
разность двух множеств

Пример разности множеств:

пример разности множеств
  • дополнение множества X – это разность между универсальным множеством U и множеством X(например, для целых чисел ¬ X – все целые числа, не входящие в X)
  • пусть требуется выбрать множество A так, чтобы выполнялось равенство A ∨ X = I; в этом случае множество A должно включать дополнение ¬ X, то есть A ≥¬ X (или A ⊇¬ X), то есть Amin = ¬ X
  • пусть требуется выбрать множество A так, чтобы выполнялось равенство ¬ A ∨ X = I, в этом случае множество ¬ A должно включать дополнение ¬ X, то есть ¬ A ⊇ ¬ X; отсюда A ⊆ X, то есть Amax = X

ЗАДАНИЯ С ОТРЕЗКАМИ И ДЕЛ

Для решения заданий необходимо знать рассмотренную тему о множествах.

Для упрощения решений можно пользоваться следующими законами.

1. Если в задании формула тождественно истинна (равна 1), и
2. после упрощения A  без отрицания
то используется закон:
Amin = ¬B
где B — известная часть выражения.

1. Если в задании формула тождественно истинна (равна 1), и
2. после упрощения A с отрицанием
то используется закон:
Amax = B
где B — известная часть выражения.

1. Если в задании формула тождественно ложна (равна 0), и
2. после упрощения A без отрицания
то используется закон:
Amin = B
где B — известная часть выражения.

Решение заданий

Задание 1. Для какого наибольшего целого числа А формула
((x ≤ 9) →(xx A)) ⋀ ((yy A) → (y ≤ 9))
тождественно истинна, то есть принимает значение 1 при любых
целых неотрицательных x и y?

Решение:
Раскрываем импликацию по правилу А → B = ¬ A + B, заменяя логическую сумму совокупностью, а логическое произведение системой соотношений, определим значение параметров А, при котором система совокупностей x > 9, х2 ≤ А, у2 > A, у ≤ 9 будет иметь решениями для любых целых неотрицательных чисел.
Решениями первой совокупности были все неотрицательные х, а решениями второй совокупности будет все неотрицательные у.
Решениями неравенства x > 9 являются числа 10,11,12…. Чтобы совокупность выполнялось число должно быть решением неравенства х2 ≤ А значит А ≥ 81.
Аналогично решаем неравенство у ≤ 9 решением являются числа 0,1,2,3…9.Следовательно числа 10,11,12…. Должны быть решениями неравенства  у2 > A. Поэтому А < 100.
 Тем самым 81 ≤ А < 100. Искомое наибольшее целое значение параметра равно 99.
Ответ: 99.

Задание 2. На чис­ло­вой пря­мой даны два от­рез­ка: P = [3, 33] и Q = [22, 44]. Вы­бе­ри­те такой от­ре­зок A, что фор­му­ла (x ∈ Q) → ((x ∈ P) → (x ∈ A)) тож­де­ствен­но ис­тин­на, то есть при­ни­ма­ет зна­че­ние 1 при любом зна­че­нии пе­ре­мен­ной х.

1) [2, 20]

2) [10, 25]

3) [20, 40]

4) [25, 30]

Реше­ние.

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

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

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

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

Ло­ги­че­ское ИЛИ ис­тин­но, если ис­тин­но хотя бы одно утвер­жде­ние. Усло­вие¬Q ∨ ¬P = 1 ис­тин­но на мно­же­стве (−∞, 22)  ∨  (33, ∞). По­сколь­ку вы­ра­же­ние ¬Q ∨ ¬P ∨ A долж­но быть тож­де­ствен­но ис­тин­ным, вы­ра­же­ние A долж­но быть ис­тин­ным на от­рез­ке [22, 33]. Из пе­ре­чис­лен­ных от­рез­ков толь­ко от­ре­зок [20, 40] удо­вле­тво­ря­ет этому усло­вию.
Пра­виль­ный ответ ука­зан под но­ме­ром 3.
Ответ: 3

Задание 3. На чис­ло­вой пря­мой даны два от­рез­ка: Р = [12, 62] и Q = [52, 92]. Вы­бе­ри­те из пред­ло­жен­ных от­рез­ков такой от­ре­зок А, что ло­ги­че­ское вы­ра­же­ние ¬((х ∈ А) ∧ (х ∈ Q)) ∨ (х ∈ P) тож­де­ствен­но ис­тин­но, то есть при­ни­ма­ет зна­че­ние 1 при любом зна­че­нии пе­ре­мен­ной х.

1) [7,60]

2) [40,95]

3) [45,65]

4) [55,100]

Решение.
Вве­дем обо­зна­че­ния: (x ∈А) ≡ A; (x ∈ P) ≡ P; (x ∈ Q) ≡ Q.
Пре­об­ра­зо­вав, по­лу­ча­ем: ¬(A ∧ Q) ∨ P = ¬A ∨ ¬ Q ∨ P.
Ло­ги­че­ское ИЛИ ис­тин­но, если ис­тин­но хотя бы одно утвер­жде­ние. Усло­вию ¬ Q ∨ P = 1 удо­вле­тво­ря­ют лучи (−∞;62) и (92; +∞). По­сколь­ку вы­ра­же­ние ¬A ∨ ¬ Q ∨ P долж­но быть тож­де­ствен­но ис­тин­ным, вы­ра­же­ние ¬A долж­но быть ис­тин­но на от­рез­ке [62, 92].
Из всех за­дан­ных от­рез­ков толь­ко от­ре­зок [7, 60] удо­вле­тво­ря­ет этим усло­ви­ям.
Ответ: 1

Задание 4. Обо­зна­чим через ДЕЛ(n, m) утвер­жде­ние «на­ту­раль­ное число n де­лит­ся без остат­ка на на­ту­раль­ное число m». Для ка­ко­го наи­боль­ше­го на­ту­раль­но­го числа А фор­му­ла
¬ДЕЛ(x, А) → (¬ДЕЛ(x, 21) ∧¬ ДЕЛ(x, 35)) тож­де­ствен­но ис­тин­на (то есть при­ни­ма­ет зна­че­ние 1 при любом на­ту­раль­ном зна­че­нии пе­ре­мен­ной x)?
(За­да­ние М. В. Куз­не­цо­вой) 

Решение.
Введём обо­зна­че­ния: A = ДЕЛ(x, А), D21 = ДЕЛ(x, 21), D35 = ДЕЛ(x, 35) и DN = ДЕЛ(x, N).
Введём мно­же­ства:
A — мно­же­ство на­ту­раль­ных чисел, для ко­то­рых вы­пол­ня­ет­ся усло­вие A,
D21 — мно­же­ство на­ту­раль­ных чисел, для ко­то­рых вы­пол­ня­ет­ся усло­вие D21,
D35 — мно­же­ство на­ту­раль­ных чисел, для ко­то­рых вы­пол­ня­ет­ся усло­вие D35,

Тогда ис­ход­ное вы­ра­же­ние ¬ДЕЛ(x, А) → (¬ДЕЛ(x, 21) ∧¬ ДЕЛ(x, 35))
при­ни­ма­ет вид

от­ку­да в силу пра­ви­ла

по­лу­ча­ем:

За­ме­тим, что вто­рое сла­га­е­мое при­ни­ма­ет зна­че­ние 0 для чисел крат­ных 21 или 35, то есть для чисел вида 21k и 35n, где k и n на­ту­раль­ные. Чтобы ло­ги­че­ская сумма была тож­де­ствен­но ис­тин­ной, для чисел ука­зан­но­го вида пер­вое сла­га­е­мое долж­но об­ра­щать­ся в 1. Сле­до­ва­тель­но, число А долж­но быть таким, чтобы любое из чисел 21k и 35n де­ли­лось на него на­це­ло. Общие де­ли­те­ли чисел 21k и 35n, не за­ви­ся­щие от k и n, — суть числа 1 и 7. Наи­боль­шее из них равно 7.
Ответ: 7.

При­ме­ча­ние.
Если бы тре­бо­ва­лось опре­де­лить наи­мень­шее на­ту­раль­ное А, обес­пе­чи­ва­ю­щее ис­тин­ность ис­ход­но­го вы­ра­же­ния для всех чисел Х, можно было бы на­чать ана­лиз с наи­мень­ше­го на­ту­раль­но­го числа — с числа 1, и убе­дить­ся, что оно и яв­ля­ет­ся ис­ко­мым: по­сыл­ка им­пли­ка­ции для числа 1 ложна, а зна­чит, сама им­пли­ка­ция ис­тин­на.

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

Решение: Преобразуем исходное выражение

x&25 ≠ 0 → (x&17 = 0 → x&А ≠ 0)
¬(x&25 ≠ 0) ∨ (¬(x&17 = 0) ∨ x&А ≠ 0)
x&25 = 0 ∨ x&17 ≠ 0 ∨ x&А ≠ 0

Переведем числа из выражения в двоичную систему счисления
2510 = 110012
1710 = 100012
Определяем те значения Х, при которых истинно выражение x&25 = 0
2510 11001
  Х    00??0
  0    00000
Х – 00??0
Определяем те значения Х, при которых истинно выражение x&17 ≠ 0
1710 10001
  Х    ?????
  0    ?000?
Х – 1????, ????1, 1???1
Следовательно Х – 01??0
Определим наименьшее А, при котором истинно выражение x&А ≠ 0
Х – 01??0
А10 ?????
 Х   01??0
≠ 0  0???0
Очевидно, что А ≠ 0
Пусть А = 12
А10 ????1
 Х   01??0
≠ 0  00000
не подходит, так как не выполняется условие А ≠ 0
Пусть А = 10002
А10 01000
 Х   01??0
≠ 0  01000
подходит, 10002 = 810
Ответ: 8

Задание 6. На числовой прямой даны два отрезка: P = [37; 60] и Q = [40; 77]. Укажите наименьшую возможную длину такого отрезка A, что формула

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

  • для того, чтобы упростить понимание выражения, обозначим отдельные высказывания буквами
  • перейдем к более простым обозначениям
  • раскрываем обе импликации по формуле :
  • теперь используем закон де Моргана :
  • в таком виде выражение уже смотрится совсем не страшно; Сразу видно, что отрезок  должен перекрыть область на числовой оси, которая не входит в область :
  • по рисунку видно, что не перекрыт только отрезок [40;60] (он выделен жёлтым цветом), его длина – 20, это и есть правильный ответ.
  • Ответ: 20.   


Top