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

Таблица 6

Таблица истинности для эквиваленции

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

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

Логические законы доказываются с помощью таблиц истинности.

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

1.Выделить и обозначить простые высказывания.

2.Найти логические связки и заменить их на соответствующие логические операции.

3.Записать логическую формулу сложного высказывания.

4.Сделать проверку на соответствие полученной формулы исходному высказыванию.

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

1.Заменить логическую переменную простым высказыванием.

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

3.Составить предложение.

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

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

Практические задания

Примеры решений

I тип. Определение высказываний, выявление логических связок

Задание. Определить, является ли предложение высказыванием: «С утра идет дождь».

Решение

а) Предложение является повествовательным. б) Мысль выражена утвердительно.

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

Ответ: Да, предложение является высказыванием.

Задание. Определить, является ли предложение высказыванием: «Реши эту задачу».

Решение

а) Предложение не является повествовательным (оно побудительное). Ответ: Нет, предложение не является высказыванием.

Задание. Определить, является ли предложение высказыванием: «Пробежал дистанцию».

Решение

а) Предложение является повествовательным.

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

Ответ: Нет, предложение не является высказыванием.

Задание. Определить, является ли предложение высказыванием. Если является, то обозначить его и определить истинность: «В море соленая вода».

Решение

а) Предложение повествовательное.

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

в) Обозначим высказывание латинской буквой: А – В море соленая вода. г) Высказывание истинное, т. е. А = T.

Ответ: да, предложениеявляетсявысказыванием. А– Вморесоленаявода, А= T.

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

Решение

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

б) Наиболее подходящая логическая связка «Если …, то…», так в предложении неявно выражена условная форма.

в) Получим предложение: «Если студент добросовестный, то он учится хорошо».

Ответ: предложение состоит из двух простых высказываний. «Если студент добросовестный, то он учится хорошо».

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

Решение

а) Предложение состоит из четырех простых высказываний:

Вконце предложения надо обязательно поставить точку.

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

Вконце предложения надо обязательно поставить восклицательный знак.

Вконце предложения надо обязательно поставить вопросительный знак. б) Так как по смыслу исходного предложения возможен лишь один из

вариантов знака препинания, то единственно подходящая логическая связка

«или».

в) Получим предложение: «В конце предложения надо обязательно поставить точку или многоточие или восклицательный знак или вопросительный знак».

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

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

Если с утра пасмурно, то я беру зонтик.

За экзамен я получу «отлично» или за экзамен я получу «хорошо».

У зверя нет иголок тогда и только тогда, когда зверь не ежик или зверь не дикообраз.

Неверно следующее высказывание: небо пасмурное тогда и только тогда, когда идет дождь.

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

Задание. Представить высказывание в виде логической формулы: «Солнце светит тогда и только тогда, когда на небе нет туч».

Решение

а) Простых высказываний в данном предложении два:

1.Солнце светит,

2.На небе есть тучи.

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

А – Солнце светит, В – На небе есть тучи.

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

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

г) Делаем проверку: А – Солнце светит, В – На небе есть тучи, Ù -

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

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

Солнце светит тогда и только тогда, когда на небе нет туч.

Ответ: высказывание соответствует формуле A В.

Задание. Представить высказывание в виде логической формулы: «Неверно высказывание: книга интересная, если она дорогая, и ее скучно читать».

Решение

а) Простых высказываний в данном предложении три:

1.Книга интересная,

2.Книга дорогая,

3.Книгу скучно читать.

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

А – Книга интересная, В – Книга дорогая, С – Книгу скучно читать.

б) В данном высказывании можно заметить две особенности: 1) посылка и заключение «поменялись местами» друг с другом, 2) частица то в данном предложении пропущена, но можно легко определить ее местоположение – после слова что.

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

Поскольку отрицание стоит в начале предложения, данная операция относится ко всей формуле.

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

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

г) Делаем проверку: А – Книга интересная, В – Книга дорогая, С – Книгу скучно читать, => - операция импликации (если, …то), х- операция отрицания

(неверно высказывание), /\. - операция конъюнкции (и).

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

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

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

Решение

а) Простых высказываний в данном предложении четыре:

1.	В пустыне есть вода,
2.	В пустыне есть растения,
3.	В пустыне много песка,
4.	В пустыне очень жарко.
Обозначим высказывания латинскими буквами:
А – В пустыне есть вода,
В – В пустыне есть растения,
С – В пустыне много песка,
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 Y		X	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.).