Лабораторная работа №5.
Тема: «Решение задач алгебры логики».
Задание 1.
Теоретические сведения.
· условные обозначения логических операций
A, 
не A (отрицание, инверсия)
A Ù B, 
A и B (логическое умножение, конъюнкция)
A Ú B, 
A или B (логическое сложение, дизъюнкция)
A → B импликация (следование)
· таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация» (см. презентацию «Логика»)
· операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:
A → B = A Ú B или в других обозначениях A → B = 
· если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», и самая последняя – «импликация»
· иногда полезны формулы де Моргана:
(A Ù B) = A Ú B 
(A Ú B) = A Ù B 
Пример задания:
Для какого из указанных значений X истинно высказывание ((X > 2)→(X > 3))?
1) 1 2) 2 3) 3 4) 4
Решение:
1) определим порядок действий: сначала вычисляются результаты отношений в скобках, затем выполняется импликация (поскольку есть «большие» скобки), затем – отрицание (операция «НЕ») для выражения в больших скобках
2) выполняем операции для всех приведенных возможных ответов (1 обозначает истинное условие, 0 – ложное); сначала определяем результаты сравнения в двух внутренних скобках:
| X | X > 2 | X > 3 | (X > 2)→(X > 3) | ((X > 2)→(X > 3)) |
3) по таблице истинности операции «импликация» находим третий столбец (значение выражения в больших скобках), применив операцию «импликация» к значениям второго и третьего столбцов (в каждой строке):
| X | X > 2 | X > 3 | (X > 2)→(X > 3) | ((X > 2)→(X > 3)) |
4) значение выражения равно инверсии третьего столбца (меняем 1 на 0 и наоборот):
| X | X > 2 | X > 3 | (X > 2)→(X > 3) | ((X > 2)→(X > 3)) |
5) таким образом, ответ – 3.
Контрольные задания.
1) Для какого из указанных значений числа X истинно высказывание
X < 5)→(X < 3)) Ù ((X < 2)→(X < 1))?
1) 1 2) 2 3) 3 4) 4
2) Для какого числа X истинно высказывание ((X > 3)Ú(X < 3)) →(X < 1)?
1) 1 2) 2 3) 3 4) 4
3) Для какого числа X истинно высказывание X > 1 Ù ((X < 5)→(X < 3))?
1) 1 2) 2 3) 3 4) 4
4) Для какого имени истинно высказывание:
(Первая буква имени гласная → Четвертая буква имени согласная)?
1) ЕЛЕНА 2) ВАДИМ 3) АНТОН 4) ФЕДОР
5) Для какого символьного выражения неверно высказывание:
Первая буква гласная → (Третья буква согласная)?
1)abedc 2)becde 3) babas 4) abcab
6) Для какого числа X истинно высказывание (X > 2)Ú(X > 5)→(X < 3)?
1) 5 2) 2 3) 3 4) 4
7) Для какого из значений числа Z высказывание ((Z > 2)Ú(Z > 4)) →(Z > 3) будет ложным?
1) 1 2) 2 3) 3 4) 4
8) Для какого имени истинно высказывание:
(Первая буква имени согласная → Третья буква имени гласная)?
1) ЮЛИЯ 2) ПЕТР 3) АЛЕКСЕЙ 4) КСЕНИЯ
9) Для какого из значений числа Y высказывание (Y < 5) Ù ((Y > 1) → (Y > 5)) будет истинным?
1) 1 2) 2 3) 3 4) 4
10) Для какого имени истинно высказывание:
(Вторая буква гласная → Первая буква гласная) Ù Последняя буква согласная?
1) ИРИНА 2) МАКСИМ 3) МАРИЯ 4) СТЕПАН
Задание 2.
Теоретические сведения.
Таблица 1 – Законы алгебры логики.
Пример задания:
Укажите, какое логическое выражение равносильно выражению A Ù (B Ú C).
1) A Ú B Ú C 2) A Ú B Ú C 3) A Ù B Ù C 4) A Ù B Ù C
Решение (использование законов де Моргана):
6) перепишем заданное выражение и ответы в других обозначениях:
заданное выражение 
ответы: 1) 
2) 
3) 
4) 
7) посмотрев на заданное выражение, видим инверсию (операцию «НЕ») для сложного выражения в скобках, которую раскрываем по формуле де Моргана,
а затем используем закон двойного отрицания по которому 
:
8) таким образом, правильный ответ – 3.
Контрольные задания.
1) Укажите, какое логическое выражение равносильно выражению (A Ú B Ú C)?
1) A Ú B Ú C 2) A Ù B Ù C 3) A Ú B Ú C 4) A Ù B Ù C
2) Какое логическое выражение равносильно выражению (A Ù B) Ù C?
1) A Ú B Ú C 2) (A Ú B) Ù C 3) (A Ú B) Ù C 4) A Ù B Ù C
3) Укажите, какое логическое выражение равносильно выражению (А Ù B)?
1) A Ú B 2) A Ú B 3) B Ù A 4) A Ù B
4) Какое логическое выражение равносильно выражению (А Ú B)?
1) A Ú B 2) A Ù B 3) A Ú B 4) A Ù B
5) Какое логическое выражение эквивалентно выражению (A Ú B) Ù C?
1) (A Ú B) Ú C 2) A Ù B Ù C 3) (A → B)Ú C 4) (A Ú B)Ú C
6) Какое логическое выражение эквивалентно выражению A Ù (B Ù C)?
1) A Ù B Ù C 2) A Ú B Ú C 3) A Ù (B Ú C) 4) (A Ú B) Ù C
7) Какое логическое выражение эквивалентно выражению (A Ú B) Ù C?
1) (A Ú B) Ù C 2) (A Ù B) Ù C 3) (A Ù B) Ù C 4) (A Ú B) Ù C
8) Какое логическое выражение эквивалентно выражению (A Ú B) Ù C?
1) A Ú B Ù C 2) (A Ù B) Ù C 3) (A Ú C) Ú B 4) (A Ú C) Ù B
9) Какое логическое выражение эквивалентно выражению (A Ù B) Ù C?
1) (A Ù B) Ù C 2) (A Ú B) Ú C 3) (A Ù B) Ú C 4) (A Ú B) Ù C
10) Какое логическое выражение эквивалентно выражению (A Ú B) → C?
1) A Ù B Ù C 2) A Ú B Ú C 3) (A Ú B) Ú C 4) A Ú B Ú C
11) Какое логическое выражение эквивалентно выражению (A Ú B)Ù C?
1) A Ú B Ú C 2) (A Ú B)Ù C 3) (A Ú B)Ù C 4) A Ù B Ù C
Задание 3.
Теоретические сведения.
· условные обозначения логических операций
A, не A (отрицание, инверсия)
A Ù B, A и B (логическое умножение, конъюнкция)
A Ú B, A или B (логическое сложение, дизъюнкция)
A → B импликация (следование)
· операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:
A → B = A Ú B или в других обозначениях A → B =
· иногда для упрощения выражений полезны формулы де Моргана:
(A Ù B) = A Ú B
(A Ú B) = A Ù B
· если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», и самая последняя – «импликация»
· таблица истинности выражения определяет его значения при всех возможных комбинациях исходных данных
· если известна только часть таблицы истинности, соответствующее логическое выражение однозначно определить нельзя, поскольку частичной таблице могут соответствовать несколько разных логических выражений (не совпадающих для других вариантов входных данных);
· количество разных логических выражений, удовлетворяющих неполной таблице истинности, равно 
, где 
– число отсутствующих строк; например, полная таблица истинности выражения с тремя переменными содержит 23=8 строчек, если заданы только 6 из них, то можно найти 28-6=22=4 разных логических выражения, удовлетворяющие этим 6 строчкам (но отличающиеся в двух оставшихся)
· логическая сумма A + B + C + … равна 0 (выражение ложно) тогда и только тогда, когда все слагаемые одновременно равны нулю, а в остальных случаях равна 1 (выражение истинно)
· логическое произведение A · B · C · … равно 1 (выражение истинно) тогда и только тогда, когда все сомножители одновременно равны единице, а в остальных случаях равно 0 (выражение ложно)
Пример задания:
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F:
Какое выражение соответствует F?
1) X Ù Y Ù Z 2) X Ù Y Ù Z 3) X Ú Y Ú Z 4) X Ú Y Ú Z
| X | Y | Z | F |
Решение:
1) нужно для каждой строчки подставить заданные значения X, Y и Z во все функции, заданные в ответах, и сравнить результаты с соответствующими значениями F для этих данных
2) если для какой-нибудь комбинации X, Y и Z результат не совпадает с соответствующим значением F, оставшиеся строчки можно не рассматривать, поскольку для правильного ответа все три результата должны совпасть со значениями функции F
3) перепишем ответы в других обозначениях:
1) 
2) 
3) 
4) 
4) первое выражение, , равно 1 только при 
, поэтому это неверный ответ (первая строка таблицы не подходит)
5) второе выражение, , равно 1 только при 
, поэтому это неверный ответ (первая и вторая строки таблицы не подходят)
6) третье выражение, , равно нулю при , поэтому это неверный ответ (вторая строка таблицы не подходит)
7) наконец, четвертое выражение, равно нулю только тогда, когда , а в остальных случаях равно 1, что совпадает с приведенной частью таблицы истинности
8) таким образом, правильный ответ – 4; частичная таблица истинности для всех выражений имеет следующий вид:
| X | Y | Z | F |
|
|
|
|
| 0 × | 0 × | ||||||
| – | – | 0 × | |||||
| – | – | – |
(крестик показывает, что значение функции не совпадает с F, а знак «–» означает, что вычислять оставшиеся значения не обязательно).
Контрольные задания.
1) Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?
| X | Y | Z | F |
1) X Ú Y Ú Z 2) X Ù Y Ù Z
3) X Ù Y Ù Z 4) X Ú Y Ú Z
2) 
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?
1) X Ú Y Ú Z 2) X Ù Y Ù Z
3) X Ù Y Ù Z 4) X Ú Y Ú Z
3) Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?
1) X Ù Y Ù Z 2) X Ù Y Ù Z
3) X Ù Y Ù Z 4) X Ù Y Ù Z
4) Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?
| X | Y | Z | F |
1) X Ù Y Ù Z 2) X Ú Y Ú Z
3) X Ú Y Ú Z 4) X Ú Y Ú Z
5) Символом F обозначена логическая функция от двух аргументов (A и B), заданная таблицей истинности. Какое выражение соответствует F?
| A | B | F |
1) A → (A Ú B) 2) A Ù B
3) A → B 4) A Ù B
| X | Y | Z | F |
6) Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?
1) X Ù Y Ù Z 2) X Ú Y Ú Z
3) X Ù (Y Ú Z) 4) (X Ú Y) Ù Z
7) Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?
| X | Y | Z | F |
1) X Ú Y Ù Z 2) X Ú Y Ú Z
3) X Ù Y Ú Z 4) X Ú Y Ù Z
