43

Цикл задач по теме «Элементы математической логики»

Образец решения.

1. Составьте таблицу истинности для высказывания : ( );

Решение.

Таблица истинности имеет вид :

				( )
и	и	л	л	и
и	л	л	и	и
л	и	и	и	и
л	л	и	л	л

2. Докажите закон ассоциативности дизъюнкции;

Решение.

Ассоциативность дизъюнкции можно доказать составлением таблицы истинности :

				( )		( )
и	и	и	и	и	и	и
и	и	л	и	и	и	и
и	л	и	и	и	и	и
и	л	л	и	и	л	и
л	и	и	и	и	и	и
л	и	л	и	и	и	и
л	л	и	л	и	и	и
л	л	л	л	л	л	л
				--------		--------

Замечаем, что при любом наборе значений истинности высказываний , , значения истинности формул в подчеркнутых столбцах совпадают, тем самым убеждаемся в справедливости закона ассоциативности дизъюнкции.

3. Докажите равносильность формул двумя способами:

= ;

Решение.

Равносильность формул логики можно доказать составлением таблицы истинности :

и	и	и	л	л	л	л	и	и	и
и	и	л	л	л	и	и	и	л	и
и	л	и	л	и	л	и	и	л	и
и	л	л	л	и	и	и	и	л	и
л	и	и	и	л	л	л	л	и	л
л	и	л	и	л	и	и	и	л	и
л	л	и	и	и	л	и	и	л	и
л	л	л	и	и	и	и	и	л	и
							-------		------

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

Можно равносильность формул доказать, используя известные законы логики :

= ( )=	использовали замену импликации дизъюнкцией отрицания первого компонента и второго : q = q; и закон двойного отрицания
= =	использовали коммутативность и ассоциативность дизъюнкции
= =	использовали закон де Моргана и формулу : q = q

4. Докажите эквивалентность двух высказываний : и ;

Решение.

Эквивалентность формул логики то же самое, что их равносильность и обосновывается теми же двумя способами.

Таблицей истинности :

A	B	C
и	и	и	л	л	л	и	л	л	и
и	и	л	л	л	и	и	л	и	и
и	л	и	и	и	л	л	л	л	л
и	л	л	и	и	и	и	л	и	и
л	и	и	л	л	л	и	и	и	и
л	и	л	л	л	и	и	и	и	и
л	л	и	и	л	л	и	и	и	и
л	л	л	и	л	и	и	и	и	и
						------			-----

С помощью законов :

= =	использовали закон: q = q;
= =	использовали закон де Моргана и закон двойного отрицания;
=	использовали закон коммутативности и ассоциативности дизъюнкции

5. Упростите :( ) ( )=;

Решение.

Упрощаем формулу на основании использования известных законов:

( ) ( ) = ( )= л =

-использовали дистрибутивность дизъюнкции относительно конъюнкции и закон : =л, а также закон: л = .

6. Образуйте отрицание высказывания двумя способами и определите, что истинно -само высказывание или его отрицание :"Всякие два угла не являются равными";

Решение.

Отрицание высказывания можно построить, используя универсальный способ : "Неверно, что всякие два угла не являются равными" или на основании правила построения отрицания высказывания с квантором : "Найдутся два угла, являющиеся равными" - при этом квантор всеобщности "всякие" меняется на квантор существования "найдутся", а отрицание переносится на предикат: = .

7. Укажите, какой предикат следует из какого: "Запись числа п оканчивается цифрой 5" и " Число п кратно 5";

Решение.

Обозначим предикат "Запись числа п оканчивается цифрой 5" как , а предикат "Число п делится на 5 " . Множество истинности предиката является подмножеством множества истинности предиката . Действительно, любое число, оканчивающееся цифрой 5 делится на 5, а число , которое делится на 5 не обязательно оканчивается цифрой 5. Следовательно, предикат логически следует из предиката , т.е. .

8. Имеется 6 красных, 2 синих и 3 белых капюшона. Все остальные спрятаны. В темноте на 5 гномов надели 1 белый,1 синий и 3 красных капюшона. Может ли кто-нибудь из гномов сказать, какого цвета капюшон на его голове , если знает, что надеты капюшоны всех трех цветов ?

Решение.

к к к

к

с б

5 гномов сидят в трех красных, одном белом и одном синем капюшонах. Они знают, что на них капюшоны трех цветов.

Проследим за рассуждениями того гнома, что в белом капюшоне. "Должны быть использованы все три цвета. А я вижу перед собой гномов только в синем и красном. Значит, я в белом."

Таким же образом, тот, что в синем догадывается о цвете своего капюшона, ибо видит только белый и красные капюшоны.

А может ли любой из тех, что в краном сказать о цвете своего капюшона ? Поразмыслим вместе с любым из них. "Если я в белом, то тот, что в белом не мог бы узнать свой цвет. А если я в синем, то "синий" не узнал бы о цвете своего капюшона. Т.к. они бы видели перед собой гномов , одетых в капюшоны всех трех цветов. Значит, мой цвет - красный."

Итак, все гномы могут определить цвет своего капюшона.

9. Три ученика различных школ приехали в один летний лагерь. На вопрос вожатого, в каких школах города они учатся, каждый дал ответ : Петя : "Я учусь в школе №24, а Леня - в школе № 8", Леня :"Я учусь в школе № 24,а Петя - в школе № 30", Коля : "Я учусь в школе № 24, а Петя - в школе № 8". Вожатый попросил объяснить, где правда, а где ложь. Тогда ребята признались, что в ответах каждого из них одно утверждение верно, а другое - ложно. В какой школе учится каждый из мальчиков ?

Решение.

Расположим высказывания мальчиков в виде таблицы:

Петя	школа №24	и	л
Леня	школа №8	л	и
Леня	школа №24	л	л
Петя	школа №30	и	и
Коля	школа №24	л	и
Петя	школа №8	и	л

Одно из высказываний Пети истинно, другое - ложно. Допустим, что истинно первое - он учится в школе №24.

Отметим это в третьем столбце, тогда ложны первое утверждение Лени, и первое утверждение Коли, а вторые их утверждения истинны. Но! Петя не может учиться одновременно в школе № 30 и школе №8. Значит, первое утверждение Пети истиной не является.

Если его второе утверждение истинно, то (заносим в таблицу значения истинности )- ложно второе утверждение Коли, Петя учится в школе №30. Значит, первое утверждение Лени ложно, получаем, что Коля учится в школе №24. В итоге по последнему столбцу таблицы определяем, что Леня учится в школе №8, Петя - №30, а Коля - №24.

Вариант 1.