1. Какие из рассмотренных законов алгебры логики аналогичны законам алгебры чисел, а какие нет?
Законы алгебры логики, аналогичные законам алгебры чисел: Закон коммутативности для операций "и" и "или": A ∧ B = B ∧ A; A ∨ B = B ∨ A. Закон ассоциативности для операций "и" и "или": (A ∧ B) ∧ C = A ∧ (B ∧ C); (A ∨ B) ∨ C = A ∨ (B ∨ C). Закон дистрибутивности: A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C); A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C). Закон двойного отрицания: ¬(¬A) = A. Законы алгебры логики, не аналогичные законам алгебры чисел:
Закон исключения третьего: A ∨ ¬A = 1 (или A ∨ ¬A = Истина). Закон противоречия: A ∧ ¬A = 0 (или A ∧ ¬A = Ложь). Закон импликации: A → B не эквивалентно B → A, а также не имеет полного аналога в алгебре чисел.
2. Докажите второй закон де Моргана с помощью таблиц истинности.
Для доказательства второго закона де Моргана, необходимо построить таблицы истинности для выражения ¬(A ∧ B) и выражения ¬A ∨ ¬B, а затем убедиться, что значения в этих таблицах истинности совпадают. A B A ∧ B ¬(A ∧ B) 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 A B ¬A ¬B ¬A ∨ ¬B 0 0 1 1 1 0 1 1 0 1 1 0 0 1 1 1 1 0 0 0 Как видно из таблиц, значения в столбцах "¬(A ∧ B)" и "¬A ∨ ¬B" совпадают для всех возможных значений A и B, что доказывает второй закон де Моргана.
3. Путём преобразования докажите равносильность следующих высказываний:
4. Упростите логические формулы:
*5. Найдите X,
6. На числовой прямой даны два отрезка: Р = [10; 25] и Q = [20; 55]. Укажите наибольшую возможную длину такого отрезка А, что выражение (х ∈ А) → ((х ∈ Р) v (x ∈ Q)) истинно при любом значении переменной х.
Выражение (х ∈ А) → ((х ∈ Р) v (x ∈ Q)) является тождественно истинным тогда и только тогда, когда его отрицание является тождественно ложным. Поэтому рассмотрим отрицание этого выражения: ¬(х ∈ А) ^ ¬((х ∈ Р) v (x ∈ Q))
Раскрывая отрицание, получаем:
х ∉ А ^ (х ∉ Р) ^ (х ∉ Q)
Таким образом, наибольшая возможная длина отрезка А будет равна длине пересечения отрезков Р и Q, то есть:
max(0, min(25, 55) - max(10, 20)) = 15.
Ответ: 15.
7. Элементами множеств А, Р и Q являются натуральные числа, причём Р = {2, 4, 6, 8, 10, 12} и Q = {2, 6, 12, 18, 24}.
Известно, что выражение истинно при любом значении переменной х. Определите наименьшее возможное количество элементов множества А.
По формуле включений и исключений имеем: |A| = |(A ∩ R) ∪ (A ∩ Q)| = |A ∩ R| + |A ∩ Q| - |(A ∩ R) ∩ (A ∩ Q)|.
Так как A, R и Q являются множествами натуральных чисел, то их пересечение может быть непустым только в том случае, когда оно содержит наименьший общий кратный всех элементов Р и Q, то есть НОК(2, 4, 6, 8, 10, 12, 18, 24) = 24.
Таким образом, имеем:
|A| = |A ∩ R| + |A ∩ Q| - |A ∩ (R ∩ Q)| = 6 + 3 - |A ∩ (R ∩ Q)|.
Чтобы выражение было истинным при любом значении переменной х, каждое натуральное число, входящее в множества Р и Q, должно входить или не входить в множество А. Следовательно, элементы множества А должны быть выбраны из пересечения множеств Р и Q. Минимальное возможное количество элементов множества А равно числу элементов в этом пересечении, то есть |R ∩ Q| = 2.
Ответ: 2.
*8. На числовой прямой даны два отрезка: М = [10; 60] и N = [40; 80]. Укажите наименьшую возможную длину такого отрезка А, что выражение истинно при любом значении переменной х.
9. Для какого наименьшего неотрицательного целого десятичного числа А формула x & 25 ≠ 0 → (x & 17 = 0 → (x & А ≠ 0) тождественно истинна, т. е. принимает значение 1 при любом неотрицательном целом значении десятичной переменной х? (Здесь & — поразрядная конъюнкция двух неотрицательных целых десятичных чисел.)
*10. Определите наибольшее натуральное десятичное число А, при котором выражение ((x & 46 = 0) v (х & 18 = 0)) → ((х & 115 ≠ 0) v (х & А = 0)) тождественно истинно, т. е. принимает значение 1 при любом натуральном значении десятичной переменной х. (Здесь & — поразрядная конъюнкция двух неотрицательных целых десятичных чисел.)
11. Сколько различных решений имеет система уравнений:
12. Сколько существует различных логических функций от четырёх переменных?
13. По заданной таблице истинности составьте логические выражения для функций F1, F2.
14. По известным таблицам истинности запишите аналитическое представление импликации, эквиваленции и строгой дизъюнкции.
15. Логические функции штрих Шеффера и стрелка Пирса названы так в честь математиков, исследовавших их свойства. Подготовьте краткую биографическую справку об одном из этих учёных.
16. По заданной таблице истинности составьте логические выражения для функций F1, F2.
17. Запишите логическое выражение для логической функции F(A, В, С), равной 1 на наборах 011, 101, 110, 111. Попытайтесь упростить полученное выражение.