Информатика / METOD

6.В пустыне есть растения,

7.В пустыне много песка,

8.В пустыне очень жарко.

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

А – В пустыне есть вода, В – В пустыне есть растения, С – В пустыне много песка, D – В пустыне очень жарко.

б) Логических связок в данном высказывании пять: первая – нет, вторая – и,

третья – нет, четвертая – тогда и только тогда, когда, пятая – или.

Первая и третья соответствуют операции отрицания ( ), вторая – операции конъюнкции (/\), четвертая – операции эквиваленции (Ù), пятая – операции дизъюнкции (\/).

в) На основе пунктов а) и б) делаем вывод, что формула имеет следующий вид: (А В) (С D).

г) Делаем проверку: А – В пустыне есть вода, В – В пустыне есть растения, С –

В пустыне много песка, D – В пустыне очень жарко, х – операция отрицания

(нет), /\ – операция конъюнкции (и), \/ – операции дизъюнкции (или), Ù –

операции эквиваленции (тогда и только тогда, когда).

Следовательно, формулу (А В) (С D) можно прочитать следующим образом: В пустыне нет воды и нет растений тогда и только тогда, когда много песка или очень жарко.

Ответ: высказывание соответствует формуле (А В) (С D).

III тип. Перевод с формального языка на естественный

Повторите алгоритм перевода с формального языка на естественный из теоретической части занятия.

Задание. Представить логическую формулу в виде высказывания на русском языке: (А В) С.

Решение.

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

С – Пушкин А. С. доживет до 70 лет.

Логические операции заменим соответствующими логическими

связками:

А– Пушкин А. С. – не поэт;

В– Пушкин А. С. – не дуэлянт;

– и;

– Если …, то …

Составим предложение по формуле, заменяя логические переменные заданными высказываниями, а операции – логическими связками:

«Если Пушкин А. С. – не поэт и Пушкин А. С. – не дуэлянт, то Пушкин А. С. доживет до 70 лет».

В соответствии с правилами русского языка, избавимся от повторяющихся слов: «Если Пушкин А. С. – не поэт и не дуэлянт, то он доживет до 70 лет».

Ответ: «Если Пушкин А. С. – не поэт и не дуэлянт, то он доживет до 70 лет». IV тип. Нахождение значение истинности формулы, доказательство логических законов, доказательство тождественной истинности или ложности формул

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

Задание: вычислить значение логической формулы, предварительно указав

порядок действий X X Y ; Решение.

X X Y

X - первое действие;

X Y - второе действие;

X X Y - третье действие.

	X	Y		X		X Y			X Y
								X
1.	T	T	F			T			F
2.	T	F	F			T			F
3.	F	T	T			T			T
4.	F	F	T			F			F

Ответ: формула принимает истинное значение, когда Х – истина,Y – ложь. Во всех остальных случаях формула принимает значение ложь.

Задание: доказать логический закон исключенного третьего X X . Решение.

X X

X - первое действие;

X X - второе действие.

	X		X		X
						X
1.	T		F		T
2.	F		T		T

Ответ: формула является законом логики.

V тип. Решение задач с применением логических формул и таблиц истинности

Задача. Три студента: Андрей, Владимир и Сергей собирались в кинотеатр. Известно, Андрей пойдет тогда и только тогда, когда не пойдут одновременно Владимир и Сергей. Если пойдет Владимир, то пойдет Сергей. В итоге выяснилось, что Сергей пошел в кинотеатр. Выяснить кто пошел с Сергеем?

Решение.

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

Представим известные факты в виде логических формул:

Андрей пойдет тогда и только тогда, когда не пойдут одновременно Владимир и Сергей – А В С.

Если пойдет Владимир, то пойдет Сергей – В С. Сергей пошел в кинотеатр – С.

Из условия следует что формулы А В С = Т и В С = Т и С = Т (истинны). Составим таблицу истинности для данных высказываний и найдем значения переменных А и В в тех строках, где данные формулы принимают истинное значение (они выделены темным цветом):

А В С В С В С А В С В С
T	T	T	T	F	F	T
T	T	F	F	T	T	F
T	F	T	F	T	T	T
T	F	F	F	T	T	T
F	T	T	T	F	T	T
F	T	F	F	T	F	F
F	F	T	F	T	F	T
F	F	F	F	T	F	T

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

Ответ: Сергей пошел с Андреем или с Сергеем. VI тип. Задачи на применение законов формальной логики

Задача. У каждой из трех одноклассниц Синельниковой, Красновой и Зелениной есть по одной ручке: у кого-то с зеленым стержнем, у другой с красным, у третьей

– с синим. Известно, что у каждой подружки ручка цветом не соответствующим фамилии. Когда одноклассник попытался выяснить у какой подружки, какая ручка, Синельникова сказала, что у нее однозначно нет зеленой ручки. Какого цвета ручка у каждой из подружек?

Решение.

а) Решим задачу используя двухмерную таблицу, в столбцах перечислим цвета стержней: с – синий, з – зеленый, к – красный; в строках – фамилии: С –

Синельникова, К – Краснова, З – Зеленина. На пересечении строк и столбцов будем ставить знак «+», если у школьницы есть стержень соответствующего цвета, знак «–»

– если стержня нет (см. табл. 7.1.).

Таблица 7.1.

Решение задачи с помощью двухмерной таблицы

с к з

С

К

З

б) Из условия следует, что у Синельниковой нет синей и зеленой ручки, у Красновой нет красной, у Зелениной отсутствует зеленая ручка. Поставим в соответствующих ячейках таблицы знаки «–» (табл. 7.2.):

Таблица 7.2.

Решение задачи с помощью двухмерной таблицы (продолжение)

	с	к	з
С	–		–
К		–
З			–

в) У Синельниковой нет ни зеленой, ни синей ручки, следовательно у нее может быть только красная ручка. Поэтому у других подружек уже не может быть красной ручки. Отобразим это в таблице 7.3.:

Таблица 7.3.

Решение задачи с помощью двухмерной таблицы (продолжение)

	с	к	з
С	–	+	–
К		–
З		–	–

г) Из таблицы 7. 3. очевидно, что синяя ручка может быть только у Зелениной, а зеленая ручка может быть только у Красновой. Получим итоговую таблицу (табл. 7.4.):

Таблица 7.4.

Решение задачи с помощью двухмерной таблицы (итог)

	с	к	з
С	–	+	–
К	–	–	+
З	+	–	–

Ответ: у Синельниковой красная ручка, у Красновой – зеленая, у Зелениной – синяя.

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

Примечание 2. Задача решается и с помощью графов. Рассмотрим подобное решение при тех же условиях задачи.

Графом на плоскости называется конечное множество точек плоскости, где некоторые из них соединены линиями. Точки – вершины графа; соединяющие их линии – ребра. Степень вершины графа – количество ребер, исходящих из этой вершины.

Решение.

			Таблица 8.
	Решение задачи с помощью графа
	Граф		Пояснение
а)		а) В	задаче идет речь о двух
		множествах: множество фамилий (С –
		Синельникова, К – Краснова, З –
		Зеленина) и множество цветов (с –
		синий,	з – зеленый, к – красный).

	С	с	Построим граф с соответствующими
			вершинами.
	К	к
	З	з

б) Соответствующие элементы двух множеств будем соединять сплошным ребром (линией), а несоответствующие пунктирной.

в)

С

К

З

г)

С

К

З

д)

С

К

З

е)

С

К

З

		в) Прочитаем условие.
	с	Так	как	у	каждой		подружки		ручка
		цветом не соответствующим фамилии,
	к	то	соединим		С	и с,	К и	к,	З и з
		пунктирной				линией,		как	не
	з	соответствующие элементы.
		г) Так как у Синельниковой нет зеленой
	с	ручки, то соединим С и з пунктирной
		линией,		как		не	соответствующие

кэлементы. Единственным вариантом остается, что у Синельниковой ручка

з	красного цвета. Соединим С и к
	сплошной линией как соответствующие
	элементы.
	д) З и к соединим пунктирной линией,
с	как не соответствующие элементы. Так
	как у Зелениной нет ни красной, ни
к	зеленой ручки, то у нее синяя ручка.
з	Соединим З и с сплошной линией как
	соответствующие элементы, и К и с –
	пунктирной, как не соответствующие
	элементы.
	е) По графу видно, что у Красновой нет
с	ни	синей,	ни	красной	ручки,
к	следовательно у нее может быть лишь
	зеленая ручка. Соединим К и з
з	сплошной линией как соответствующие
	элементы.

Ответ: у Синельниковой красная ручка, у Красновой – зеленая, у Зелениной – синяя.

Примечание 3. Подобные задачи логического характера рационально решать с помощью таблиц, когда в условии фигурируют два множества с числом элементов

более 2. Если в задаче участвуют три и более множества с несколькими элементами, то она решается с помощью графов.

Задачи для самостоятельного решения

I тип

Задача 1*. Определить является ли предложение высказыванием. Высказывания обозначить и определить их истинность:

а) Сегодня воскресенье.

б) Дисплей – это устройство ввода информации. в) Проверь домашнее задание.

г) Математика – это наука о количественных отношениях и пространственных формах действительного мира.

д) День был дождливым?

е) 19 делится на 5 без остатка. ж) Какой красивый дом!

з) Александр Сергеевич Пушкин – великий поэт серебряного века.

Задача 2*. Определить из скольких высказываний состоит предложение. Сформулировать предложение, используя наиболее подходящую логическую связку:

а) Купаясь в неположенном месте, человек может утонуть.

б) В повествовательном предложении ставится точка, а может быть многоточие.

в) Ленивому студенту трудно учиться.

г) Студента переводят на следующий курс, когда он не имеет задолженностей. д) Чапаев – герой гражданской войны, а также современных анекдотов.

е) Вода при температуре менее 0 градусов – лед.

ж) Проигравший теннисист выходит из соревнований.

Задача 3*. Для высказываний, сформулированных в задании 2, подчеркнуть простые высказывания, обвести кружком логическую связку.

Задача 4**. Определить из скольких высказываний состоит предложение. Сформулировать предложение, используя наиболее подходящую логическую связку:

а) Лампочка горит когда есть электричество. б) На яблоне растут яблоки.

в) У блондина белый цвет волос.

г) Спортсмен – олимпийский чемпион, следовательно он победитель Олимпийских игр.

д) Студент, не сдавший всех зачетов, не допускается до экзаменов. е) Зимой на улице холодно.

ж) Спортсмен вышел в полуфинал вследствие того, что выиграл четверть финала.

з) Встречаясь, люди приветствуют друг друга.

Задача 5**. Для высказываний, сформулированных в задании 4, подчеркнуть простые высказывания и обвести кружком логическую связку.

Задача 6***. Определить из скольких высказываний состоит предложение. Сформулировать предложение, используя наиболее подходящую логическую связку:

а) Чтобы сдать зачет студенту необходимо: решить все домашние задания, написать контрольную работу на положительную оценку, посещать все лекции. б) Порядочный человек извинится, а также постарается загладить вину, в случае, когда он кого-то сильно обидел.

в) Спортсмен будет дисквалифицирован в случае, когда он нарушает правила либо некорректно ведет себя по отношению к сопернику.

Задача 7**. Для высказываний, сформулированных в задании 6, подчеркнуть простые высказывания и обвести кружком логическую связку.

II тип

Задача 8*. Представить высказывания в виде логических формул:

а) Если пойдешь гулять, то возьмешь с собой зонт или наденешь плащ. б) Человек голоден тогда и только тогда, когда он не умеет готовить.

Задача 9**. Представить высказывания в виде логических формул: а) Студент не сдал сессию, следовательно, он будет отчислен. б) Я буду отдыхать, если начнутся каникулы.

в) Неверно, что Земля плоская и вращается вокруг Солнца.

ж) Можно будет кататься на роликах или велосипедах, когда наступит лето. Задача 10***. Представить предложения в виде логических формул, если это возможно:

а) Прочитай книгу и сходи в кино. б) Выучил уроки, если помыл посуду.

в) Если сдал экзамен или зачет, можешь отдохнуть с друзьями.

III тип.