5_Основы АЛ (Повторение). Лицей игу, liguirk ru Тема 5. Основы алгебры логики (Повторение) 11. 10. 22
Скачать 3.09 Mb.
|
Лицей ИГУ, liguirk.ru Тема №5. Основы алгебры логики (Повторение) 11.10.22 Лавлинский М.В., LavlinskiMV@mail.ru Логика - наука, изучающая законы и формы мышления Аристотель (384-322 гг. до н. э.) Джордж Буль (1815-1864) Основоположник логики как науки Основоположник математической логики
0 1 0 1 0 0 1 1 1 1 0 0 0 0 0 1 0 1 1 1 1 1 0 1 1 0 0 1 Порядок вычислений: (), , , , , Представление через базовые операции (“”, “”, “”): I. Логические операции 0 1 1 0 Инверсия Конъюнкция & Дизъюнкция + Импликация Эквиваленция Исключающее «ИЛИ» II. Законы алгебры логики
Показывают, чему равно значение ЛВ при возможных комбинациях значений исходных переменных. Кол-во строк: 2n n – кол-во логических переменных III. Таблицы истинности
Решение: 1) ложно для набора в третьей строке, где F(…) = 1 и x1 = 0 2) ложно для набора в третьей строке, где F(…) = 1 и x2 = 0 3) истинно для всех наборов переменных 4) ложно для набора в первой строке, где F(…) = 1 и x4 = 0 Ответ: 3 Задача 2. Дано логическое выражение, зависящее от 5 логических переменных: z1 ¬z2 ¬z3 ¬z4 z5 Сколько существует различных наборов значений переменных, при которых выражение ложно? 1) 1 2) 2 3) 31 4) 32 Решение: 1) Выражение с 5-ю переменными 25 = 32 различных комбинации значений 2) Операция – это логическое умножение выражение истинно одном случае (10001) 3) 32 – 1 = 31 – вариант когда выражение ложно Ответ: 3 Задача 3. Дан фрагмент таблицы истинности выражения F. Какое выражение соответствует F? 1) (x1 x2) ¬x3 x4 ¬x5 x6 ¬x7 2) (x1 x2) ¬x3 x4 ¬x5 x6 x7 3) (x1 ¬x2) x3 ¬x4 ¬x5 x6 ¬x7 4) (¬x1 ¬x2) x3 ¬x4 x5 ¬x6 x7
Решение: В столбце F одна единица Рассмотрим функции, состоящие из цепочки «И» (1, 3 или 4 в-ты) Должна быть инверсия для x3, x5 и x7 (т.к. они равны нулю) Остается вариант ответа 1 Проверяем скобку (x1 x2) Ответ: 1
Решение: Ответ: 3 Задача 5. На числовой прямой даны два отрезка: P = [14, 34] и Q = [24, 44]. Выберите такой отрезок A, что формула ( x A) → ((x P) (x Q) ) тождественно истинна, то есть принимает значение 1 при любом значении переменной х. Если таких отрезков несколько, укажите тот, который имеет большую длину. 1) [15, 29] 2) [25, 29] 3) [35,39] 4) [49,55] Решение: 1) A: x А, P: x P, Q: x Q Перейдем к более простым обозначениям A → (P Q) 14 24 x 44 34 (P Q) = 1 1) [15, 29] 2) [25, 29] 3) [35,39] 4) [49,55] A → (P Q) = 0 если А=1, (P Q) = 0 = 4 = 6 Ответ: 4 Задача 6. На числовой прямой даны два отрезка: P = [20, 50] и Q = [10, 60]. Выберите такой отрезок A, что формула ( (x P) → (x А) ) /\ ( (x A) → (x Q) ) тождественно истинна, то есть принимает значение 1 при любом значении переменной х. Если таких отрезков несколько, укажите тот, который имеет большую длину. 1) [5, 40] 2) [15, 54] 3) [30,58] 4) [5, 70] Решение: 1) A: x А, P: x P, Q: x Q Перейдем к более простым обозначениям: (P → A) /\ (A → Q) 2) = 1 = 1 20 50 x 2) и 4) 10 60 x 2) и 3) Ответ: 2 Задача 7. На числовой прямой даны два отрезка: Р = [35, 55] и Q = [45, 65]. Выберите такой отрезок А, что обе приведённые ниже формулы истинны при любом значении переменной х: (x P) → (x A) ( (x А)) → ((x Q)) Если таких отрезков несколько, укажите тот, который имеет большую длину. 1) [40,50] 2) [30,60] 3) [30,70] 4) [40, 100] Решение: 1) A: x А, P: x P, Q: x Q 2) 35 55 x 2) и 3) 45 65 x 3) и 4) Ответ: 3 Задача 8. Какое из приведённых имен удовлетворяет логическому условию: (первая буква согласная → вторая буква согласная) /\ (предпоследняя буква гласная → последняя буква гласная)? 1) КРИСТИНА 2) МАКСИМ 3) СТЕПАН 4) МАРИЯ Решение: 1) Конъюнкция (/\) истинна (первая буква согласная → вторая буква согласная) 1 (предпоследняя буква гласная → последняя буква гласная) 1 2) Импликация () ложна, если первая часть «1», а вторая «0» 3) (первая буква согласная → вторая буква согласная) 0 1-ая буква согласная, а 2-ая – гласная, т.е. для 2) и 4) 4) (предпоследняя буква гласная → последняя буква гласная) 0 предпоследняя буква гласная, последняя – согласная, т.е. для 3) 5) Т.о., для 1) КРИСТИНА оба промежуточных условия истинны Ответ: 1 Задача 9. Для какого из указанных значений X истинно высказывание ¬((X > 2)→(X > 3))? 1) 1 2) 2 3) 3 4) 4
Решение: Ответ: 3 Задача 10. Составьте таблицу истинности для логической функции X = (А ↔ B) ¬(A → (B C)) в которой столбец значений аргумента А представляет собой двоичную запись числа 27, столбец значений аргумента В – числа 77, столбец значений аргумента С – числа 120. Число в столбце записывается сверху вниз от старшего разряда к младшему. Переведите полученную двоичную запись значений функции X в десятичную систему счисления. Решение: 1) Перепишем уравнение, используя простые обозначения: 2) Переведем числа 27, 77 и 120 в 2-ую СС, дополняя запись до 8 знаков нулями 27 = 000110112 77 = 010011012 120 = 011110002 3) Заполняем таблицу истинности
4) 101010112 = = 27 + 25 + 23 + 21 + 20 = = 171 Ответ: 171 Домашнее заданиеЛицей ИГУ, liguirk.ru 11.10.22 «5_Основы АЛ (Повторение) [ДЗ].doc» Подготовиться к СР |