Лабораторная работа 1. Логика и исчисление высказываний
Лабораторная работа 1. Логика и исчисление высказываний
Цель: получить представление о методах и средствах формальной логики для решения практических задач.
определять простые и сложные высказывания, выявлять в сложных высказываниях логические связки; осуществлять перевод с естественного языка на формальный и с формального на естественный язык; определять значение истинности логической формулы, доказывать тождественную истинность или ложность формул, доказывать логические законы; решать практические задачи с применением логических формул и таблиц истинности; строить цепочки умозаключений с применением законов формальной логики.
Общие теоретические сведения
Условные обозначения логических связок
…, тогда и только тогда, когда…
А тогда и только тогда, когда В
Истинное высказывание условимся обозначать латинской буквой T (true),
ложное высказывание F (false).
Чтобы определить значение истинности для сложной формулы, необходимо знать значения истинности для операций отрицания, конъюнкции, дизъюнкции, импликации, эквиваленции (см. табл. 2 — 6).
Таблица истинности для отрицания
Таблица истинности для конъюнкции
Таблица истинности для дизъюнкции
Таблица истинности для импликации
Таблица истинности для эквиваленции
Формулы, имеющие все значения истинности при любых значениях переменных, называются тождественно-истинными. Тождественно-истинные формулы являются законами логики.
Логические законы доказываются с помощью таблиц истинности.
Практические задания
тип. Определение высказываний, выявление логических связок
Задание. Определить, является ли предложение высказыванием:
«С утра идет дождь».
а) Предложение является повествовательным. б) Мысль выражена утвердительно.
в) Относительно данного предложения можно однозначно сказать, является оно ложным или истинным.
Ответ: Да, предложение является высказыванием.
Задание. Определить, является ли предложение высказыванием:
«Реши эту задачу».
а) Предложение не является повествовательным (оно побудительное).
Ответ: Нет, предложение не является высказыванием.
тип. Перевод с естественного языка на формальный
Задание. Представить высказывание в виде логической формулы: «Солнце светит тогда и только тогда, когда на небе нет туч».
а) Простых высказываний в данном предложении два:
Солнце светит, На небе есть тучи.
Обозначим их латинскими буквами:
А – Солнце светит,
В – На небе есть тучи.
б) Логических связок в данном высказывании две: первая – тогда и только тогда, когда, вторая – нет. Первая соответствует операции эквиваленции ( ⇔ ), вторая – операции отрицания ( ).
в) На основе пунктов а) и б) делаем вывод о том, что формула имеет следующий вид: A ⇔ В.
Задание. Представить высказывание в виде логической формулы:
«Неверно высказывание: книга интересная, если она дорогая, и ее скучно читать».
а) Простых высказываний в данном предложении три:
Книга интересная, Книга дорогая, Книгу скучно читать.
Обозначим высказывания латинскими буквами:
А – Книга интересная, В – Книга дорогая,
С – Книгу скучно читать.
б) В данном высказывании можно заметить две особенности: 1) посылка и заключение «поменялись местами» друг с другом, 2) частица то в данном предложении пропущена, но можно легко определить ее местоположение – после слова что.
Логических связок в данном высказывании три: первая – неверно высказывание, вторая – если, …то, третья – и.
Поскольку отрицание стоит в начале предложения, данная операция относится ко всей формуле.
Первая логическая связка соответствует операции отрицания ( ), вторая операции импликации (=>), третья – операции конъюнкции (/\).
в) На основе пунктов а) и б) делаем вывод, что формула имеет следующий
тип. Нахождение значения истинности формулы, доказательство логических законов, доказательство тождественной истинности или ложности формул
Последовательность выполнения операций в логических формулах определяется старшинством операций. В порядке убывания старшинства логические операции расположены так: х, ∧ , ∨ , ⇒ , ⇔ . Кроме того, на порядок операций влияют скобки, которые можно использовать в логических формулах.
Задание: вычислить значение логической формулы, предварительно
указав порядок действий X ⇔ X ∨ Y ;
X — первое действие;
X ∨ Y — второе действие;
X ⇔ X ∨ Y третье действие.
Ответ: формула принимает истинное значение, когда Х – истина, Y –
ложь. Во всех остальных случаях формула принимает значение ложь.
тип. Решение задач с применением логических формул и таблиц истинности
Задача. Три студента: Андрей, Владимир и Сергей собирались в кинотеатр. Известно, Андрей пойдет тогда и только тогда, когда не пойдут одновременно Владимир и Сергей. Если пойдет Владимир, то пойдет Сергей. В итоге выяснилось, что Сергей пошел в кинотеатр. Выяснить, кто пошел с Сергеем.
а) Обозначим простые высказывания:
А – Андрей ходил в кинотеатр,
В – Владимир ходил в кинотеатр,
С – Сергей ходил в кинотеатр.
б) Представим известные факты в виде логических формул:
Андрей пойдет тогда и только тогда, когда не пойдут одновременно Владимир и Сергей – А ⇔ (В ∧ С) .
Если пойдет Владимир, то пойдет Сергей – В ⇒ С
Сергей пошел в кинотеатр – С.
в) Из условия следует, что формулы А ⇔( В ∧ С) = Т и В ⇒ С = Т и С = Т
(истинны). Составим таблицу истинности для данных высказываний и найдем значения переменных А и В в тех строках, где данные формулы принимают истинное значение (они выделены темным цветом):
г) Так высказывания истинны в двух случаях: когда А – истинно или когда В – истинно, то в кинотеатр Сергей пошел либо с Андреем, либо с Владимиром (варианты, что пошли все трое или Сергей один – отклоняются).
Ответ: Сергей пошел с Андреем или с Владимиром.
тип. Задачи на применение законов формальной логики
Задача. У каждой из трех одноклассниц Синельниковой, Красновой и Зелениной есть по одной ручке: у кого-то с зеленым стержнем, у другой с красным, у третьей – с синим. Известно, что у каждой подружки ручка цветом, не соответствующим фамилии. Когда одноклассник попытался выяснить, у какой подружки какая ручка, Синельникова сказала, что у нее однозначно нет зеленой ручки. Какого цвета ручка у каждой из подружек?
а) Решим задачу, используя двухмерную таблицу, в столбцах перечислим цвета стержней: с – синий, з – зеленый, к – красный; в строках – фамилии: С – Синельникова, К – Краснова, З – Зеленина. На пересечении строк и столбцов будем ставить знак «+», если у школьницы есть стержень соответствующего цвета, знак «–» – если стержня нет.
Решение задачи с помощью двухмерной таблицы
б) Из условия следует, что у Синельниковой нет синей и зеленой ручки, у Красновой нет красной, у Зелениной отсутствует зеленая ручка. Поставим в соответствующих ячейках таблицы знаки «–» (табл. 7.2.).
Решение задачи с помощью двухмерной таблицы (продолжение)
в) У Синельниковой нет ни зеленой, ни синей ручки, следовательно, у нее может быть только красная ручка. Поэтому у других подружек уже не может быть красной ручки. Отобразим это в таблице 7.3.
Решение задачи с помощью двухмерной таблицы (продолжение)
г) Из таблицы 7.3 очевидно, что синяя ручка может быть только у Зелениной, а зеленая ручка может быть только у Красновой. Получим итоговую таблицу (табл. 7.4.).
Решение задачи с помощью двухмерной таблицы (итог)
Ответ: у Синельниковой красная ручка, у Красновой – зеленая, у Зелениной – синяя.
Примечание 1. Задачу можно решить и простым перебором вариантов, но фиксирование результатов рассуждений в таблице делает решение более наглядным и позволяет не упустить ни одну версию.
Задачи для самостоятельного решения
Задача 1. Определить, является ли предложение высказыванием. Высказывания обозначить и определить их истинность:
а) Сегодня воскресенье.
б) Дисплей – это устройство ввода информации. а) Проверь домашнее задание.
в) Математика – это наука о количественных отношениях и пространственных формах действительного мира.
г) День был дождливым?
д) 19 делится на 5 без остатка. е) Какой красивый дом!
ж) Александр Сергеевич Пушкин – великий поэт серебряного века.
Задача 2. Представить высказывания в виде логических формул:
а) Если пойдешь гулять, то возьмешь с собой зонт или наденешь плащ. б) Человек голоден тогда и только тогда, когда он не умеет готовить.
Задача 3. Построить таблицы истинности для формул:
Задача 4. Определить, являются ли формулы тождественно истинными:
а) ( A ∨ B) ∧ C ⇔ A ∧ C ∨ B ∧ C
Задача 5. У сороки было трое птенцов: А, В, С. Кого сорока угостила кашей, если известно, что если она угостит А и С, то и В получит свою порцию. Также известно, что А не угостит тогда и только тогда, когда не угостит С.
Задача 6. В картинной галерее украдено полотно. В момент кражи в галерее могли находиться три человека: охранник, смотритель и уборщица. В ходе допроса смотритель сказал: «Если в момент кражи в помещении был я, то не было уборщицы или был охранник». Затем следствие выяснило, что смотритель солгал. Кто украл полотно?
Задача 7. После угона четыре машины: «Жигули», «Волга», «Запорожец» и «Москвич» были перекрашены в один цвет. Известно, что до угона машины были разных цветов: желтого, зеленого, синего, красного. Показания свидетелей позволили выявить следующее. Во-первых, водитель «Жигулей» возил владельца машины желтого цвета, и это был не водитель «Волги». Во-вторых, пассажирами на синей машине видели водителей «Волги» и «Запорожца». В-третьих, водитель «Жигулей» не любит синий цвет, так же сильно, как водитель «Волги» не любит красный цвет. Какой цвет соответствовал каждой марке машины до угона?
Источник