Примение логических операций и законов на практике

2. Примение логических операций и законов на практике.

Пример 1. (Задание А11 демоверсии)
Для какого имени истинно высказывание:
¬ (Первая буква имени гласная -> Четвертая буква имени согласная)?
1) ЕЛЕНА
2) ВАДИМ
3) АНТОН
4) ФЕДОР




Решение. Сложное высказывание состоит из двух простых высказываний:
А – первая буква имени гласная,
В – четвертая буква имени согласная.

Применяемые формулы:
1. Импликация через дизъюнкцию А ? В = ¬A V В
2. Закон де Моргана ¬(A V B) = ¬A /\ ¬B
3. Закон двойного отрицания.
(Первая буква имени гласная /\ Четвертая буква имени гласная)

Ответ: 3

Пример 2. (Задание А12 демоверсии 2004 г.)
Какое логическое выражение равносильно выражению ¬ (А \/ ¬B)?
1) A \/ B
2) A /\ B
3) ¬A \/ ¬B
4) ¬A /\ B

Решение. ¬ (А \/ ¬B)= ¬ А \/ ¬ (¬B)= ¬ А \/ B

Ответ: 4

Пример 3.
Составить таблицу истинности для формулы

Порядок выполнения логических операций:

2   1   5   3   4
Составить таблицу истинности.
Сколько строк будет в вашей таблице? 3 переменных: А, В, С; 2³=8
Сколько столбцов? 5 операций + 3 переменных = 8

Решение:

A	B	C	(B /\ C)	¬ (B /\ C)	A/\C	(A/\C ? B)
0	0	0	0	1	0	1	1
0	0	1	0	1	0	1	1
0	1	0	0	1	0	1	1
0	1	1	1	0	0	1	1
1	0	0	0	1	0	0	1
1	0	1	0	1	1	1	1
1	1	0	0	1	0	0	1
1	1	1	1	0	1	1	1

Какие ответы получились в последнем столбце?

Ответ: 1
Логическое выражение называется тождественно-истинным, если оно принимает значения 1 на всех наборах входящих в него простых высказываний. Тождественно-истинные формулы называют тавтологиями.

Решим этот пример аналитическим методом:
упрощаем выражение
= (применим формулу для импликации)
¬ (B /\ C) V ¬ (A /\ C) V B = (применим 1 и 2 законы де Моргана)
(¬B V ¬C) V (¬A V ¬C) V B = (уберём скобки)
¬B V ¬C V ¬A V ¬C V B= (применим переместительный закон)
¬B V B V ¬C V ¬C V ¬A = (закон исключения третьего, закон идемпотентности)
1 V ¬С V ¬A = 1 V ¬A = 1 (закон исключения констант)

Ответ: 1, означает, что формула является тождественно-истинной или тавтологией.
Логическое выражение называется тождественно-ложным, если оно принимает значения 0 на всех наборах входящих в него простых высказываний.

Пример 4.

В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдёт поисковый сервер по каждому запросу.

Для обозначения логической операции “ИЛИ” в запросе используется символ I, а для логической операции “И” – символ &.

А	Законы & Физика
Б	Законы I (Физика & Биология)
В	Законы & Физика & Биология & Химия
Г	Законы I Физика I Биология

Решение:

Первый способ основан на рассуждении. Рассуждая логически, мы видим, что больше всего будет найдено страниц по запросу Г, так как при его исполнении будут найдены и страницы со словом “законы”, и страницы, со словом “физика”, и страницы со словом “биология”. Меньше всего будет найдено страниц по запросу В, так как в нем присутствие всех четырех слов на искомой странице. Осталось сравнить запросы А и Б. По запросу Б будут найдены все страницы, соответствующие запросу А, (так как в последних обязательно присутствует слово “законы”), а также страницы, содержащие одновременно слова “физика” и “биология”. Следовательно по запросу Б будет найдено больше страниц, чем по запросу А. Итак, упорядочив запросы по возрастанию страниц, получаем ВАБГ.

Ответ: ВАБГ.

Второй способ предполагает использование графического представления операций над множествами. (Смотри презентацию)

Пример 5. (Задание А16 демоверсии 2006 г.)

Ниже в табличной форме представлен фрагмент базы данных о результатах тестирования учащихся (используется стобалльная шкала)

Фамилия	Пол	Математика	Русский язык	Химия	Информатика	Биология
Аганян	ж	82	56	46	32	70
Воронин	м	43	62	45	74	23
Григорчук	м	54	74	68	75	83
Роднина	ж	71	63	56	82	79
Сергеенко	ж	33	25	74	38	46
Черепанова	ж	18	92	83	28	61

Сколько записей в данном фрагменте удовлетворяют условию

“Пол=’м’ ИЛИ Химия>Биология”?

1) 5

2) 2

3) 3

4) 4

Решение:

Выбираем записи: Мальчики (двое) и Химия>Биология (трое, но один мальчик, уже взялся 1 раз). В итоге 4 записи удовлетворяют условию.

Ответ: 4

Задание 6. (Задание В4 демоверсии 2007 г)

В школьном первенстве по настольному теннису в четверку лучших вошли девушки: Наташа, Маша, Люда и Рита. Самые горячие болельщики высказали свои предположения о распределении мест в дальнейших состязаниях.

Один считает, что первой будет Наташа, а Маша будет второй.

Другой болельщик на второе место прочит Люду, а Рита, по его мнению, займет четвертое место.

Третий любитель тенниса с ними не согласился. Он считает, что Рита займет третье место, а Наташа будет второй.

Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов.

Какое место на чемпионате заняли Наташа, Маша, Люда, Рита?

(В ответе перечислите подряд без пробелов числа, соответствующие местам девочек в указанном порядке имен.)

Решение:

Обозначим высказывания:

Н1 = “первой будет Наташа”;

М2 = “второй будет Маша”;

Л2 = “второй будет Люда”;

Р4 = “четвертой будет Рита”;

Р3 = “третьей будет Рита”;

Н2 = “второй будет Наташа”.

Согласно условию:

из высказываний 1 болельщика следует, что Н1VМ2 истинно;

из высказываний2 болельщика следует, что Л2VР4 истинно;

из высказываний 3 болельщика следует, что Р3VН2 истинно.

Следовательно, истинна и конъюнкция

(Н1VМ2) /\ (Л2VР4) /\ (Р3VН2) = 1.

Раскрыв скобки получим:

(Н1VМ2) /\ (Л2VР4) /\ (Р3VН2) = (Н1/\Л2V Н1/\Р4 V М2/\Л2 V М2/\Р4) /\ (Р3VН2)=

Н1/\ Л2/\Р3 V Н1/\Р4/\Р3 V М2/\Л2/\Р3 V М2/\Р4/\Р3 V Н1/\Л2/\Н2 V Н1/\Р4/\Н2 V М2/\Л2/\Н2 V М2/\Р4/\Н2 = Н1/\ Л2/\Р3 V 0 V 0 V 0 V 0 V 0 V 0 V= Н1/\ Л2/\Р3

Наташа-1, Люда-2, Рита-3, а Маша-4.

Ответ: 1423