Основы логики

3.1.1.  Основы логики

Для выполнения заданий № 4 и № 5 необходимы знания основ логики, являющейся одним из разделов дисциплины «Информатика».

Простое логическое высказывание — это некоторое выражение, которое может быть истинно (верно) или ложно. Это фразы типа «два больше одного», «5,8 является целым числом». В первом случае мы имеем истину, а во втором — ложь.

Сложное логическое высказывание — логическое выражение, составленное из одного или нескольких простых (или сложных) высказываний, связанных с помощью логических операций. В естественном языке мы используем различные союзы и другие части речи. Например, «и», «или», «либо», «не», «если», «то», «тогда». Пример сложных высказываний: «у него есть знания и навыки», «она приедет во вторник либо в среду», «я буду играть тогда, когда сделаю уроки», «5 не равно 6». Формализованная запись этих высказываний с помощью логических операций.

Название операции	Альтернативные названия	Знаки	Примеры
Конъюнкция	Логическое умножение, Логическое И	Λ & and	A Λ B A & B A and B
Дизъюнкция	Логическое сложение, Логическое ИЛИ	V | or	A V B A | B A or B
Отрицание	Инверсия	not	A not A
Следование	Импликация	→	A →B
Эквивалентность		=	A = B

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

A	B	A Λ B	A V B	A	A →B	A = B
0	0	0	0	1	1	1
0	1	0	1	1	1	0
1	0	0	1	0	0	0
1	1	1	1	0	1	1

При преобразовании логических выражений используют следующие свойства логических операций:

1.  Свойства констант

2.  Рефлексивность

3.  Коммутативность

4.  Ассоциативность

5.  Дистрибутивность

6.  Закон отрицания (двойного отрицания)

7.  Законы де Моргана

8.  Законы поглощения

Также вводятся дополнительные операции:

·  импликация: A → B  = (A V B);

·  эквивалентность: (A = B) = (A Λ B) V (A Λ B).

3.1.2.  Примеры решения логических задач

1)  Запишите интервал значений X, для которых истинно высказывание:

РЕШЕНИЕ

Введем обозначения: A = X > 5; B = X > 6. Тогда высказывание примет вид

(A → B).

Составим для этого высказывания таблицу истинности:

A	B	A → B	(A → B)
0	0	1	0
0	1	1	0
1	0	0	1
1	1	1	0

Высказывание истинно, если A истинно, а B ложно.

Следовательно, если рассматривать действительные числа, то интервал значений Х равен: . Для целых чисел: Х=6.

2)  Укажите, какое логическое выражение равносильно выражению

.

1)

2)

3)

4)

РЕШЕНИЕ

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

а) применив закон де Моргана к выражению в скобках, получаем:

б) используя закон двойного отрицания, получаем:

Следовательно, ответ: 3.

3)  На числовой прямой даны два отрезка: P = [2, 10] и Q = [6, 14]. Выберите такой отрезок A, что формула

( (x Î А) → (x Î P) ) \/ (x Î Q)

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

1) [0, 3] 2) [3, 11] 3) [11, 15] 4) [15, 17]

Решение

1)  Введем обозначение: A: x Î А, P: x Î P, Q: x Î Q. Тогда высказывание примет вид:

Z = (A→P) \/ Q

2)  Представим импликацию A → P через операции «\/» и «Ø»: (A→P) =ØA \/ P. В результате получаем Z = ØA \/ P \/ Q.

Выражение Z истинно во всех случаях, кроме одного, когда все аргументы ложны. Следовательно, выражение Z = ØA \/ P \/ Q ложно при A = 1, P = 0, Q = 0. Поэтому если область истинности A выйдет за пределы отрезка [2,14], где одновременно ложны P и Q, то Z = (A→P) \/ Q будет ложно. Это значит, что A может быть истинно только внутри отрезка [2,14]. Из всех отрезков, приведенных в условии, только отрезок [3,11] (вариант 2) находится целиком внутри отрезка [2,14], это и есть правильный ответ.

3)  Ответ: 2.

3.1.3.  Задания

1.  Каково наибольшее целое число X, при котором истинно высказывание

(50 < X·X) → (50 > (X+1) ∙ (X+1))?

2.  Для какого из указанных значений числа X истинно высказывание

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

1 4

3.  Для какого числа X истинно высказывание

((X > 3)Ú(X < 3)) →(X < 1)

1 4

4.  Для какого числа X истинно высказывание

X > 1 Ù ((X < 5)→(X < 3))

1 4

5.  Для какого имени истинно высказывание

(Первая буква имени гласная → Четвертая буква имени согласная)?

1) ЕЛЕНА 2) ВАДИМ 3) АНТОН 4) ФЕДОР

6.  Для какого символьного выражения неверно высказывание:

Первая буква гласная → (Третья буква согласная)?

1) abedc 2) becde 3) babas 4) abcab

7.  Для какого числа X истинно высказывание

(X > 2)Ú(X > 5)→(X < 3)

1 4

8.  Для какого из значений числа Z высказывание

((Z > 2)Ú(Z > 4)) →(Z > 3) будет ложным?

1 4

9.  Для какого имени истинно высказывание:

(Первая буква имени согласная → Третья буква имени гласная)?

1) ЮЛИЯ 2) ПЕТР 3) АЛЕКСЕЙ 4) КСЕНИЯ

10.  На числовой прямой даны два отрезка:

P = [2, 20] и Q = [15, 25]. Выберите такой отрезок A, что формула

( (x Ï А) → (x Ï P) ) \/ (x Î Q)

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

1) [0, 15] 2) [10, 25] 3) [2, 10] 4) [15, 20]

11.  На числовой прямой даны три отрезка:

P = [10, 25], Q = [15, 30] и R=[25,40]. Выберите такой отрезок A, что формула

( (x Î Q) → (x Ï R) ) /\ (x Î A) /\ (x Ï P)

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

1) [0, 15] 2) [10, 40] 3) [25, 35] 4) [15, 25]

12.  На числовой прямой даны два отрезка:

P = [5, 15] и Q = [12, 18]. Выберите такой отрезок A, что формула

( (x Î А) → (x Î P) ) \/ (x Î Q)

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

1) [3, 11] 2) [2, 21] 3) [10, 17] 4) [15, 20]

13.  На числовой прямой даны два отрезка:

P = [5, 10] и Q = [15, 18]. Выберите такой отрезок A, что формула

( (x Î А) → (x Î P) ) \/ (x Î Q)

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

1) [3, 11] 2) [6, 10] 3) [8, 16] 4) [17, 23]

14.  На числовой прямой даны два отрезка:

P = [25, 30] и Q = [15, 20]. Выберите такой отрезок A, что формула

( (x Î А) → (x Î P) ) \/ (x Î Q)

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

1) [10, 15] 2) [12, 30] 3) [20, 25] 4) [26, 28]

15.  На числовой прямой даны два отрезка:

P = [2, 20] и Q = [15, 30]. Выберите такой отрезок A, что формула

( (x Ï А) → (x Ï P) ) \/ (x Î Q)

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

1) [0, 15] 2) [3, 20] 3) [10, 25] 4) [25, 40]