X < 5)→(X < 3)) Ù ((X < 2)→(X < 1))?

Лабораторная работа №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

· если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», и самая последняя – «импликация»

· таблица истинности выражения определяет его значения при всех возможных комбинациях исходных данных

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

· количество разных логических выражений, удовлетворяющих неполной таблице истинности, равно , где – число отсутствующих строк; например, полная таблица истинности выражения с тремя переменными содержит 2³=8 строчек, если заданы только 6 из них, то можно найти 2^8-6=2²=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