Реферат Курсовая Конспект
Тема 15. Элементы математической логики - раздел Информатика, Информатика и математика Изучив Данную Тему, Студент Должен Знать: 1. Что Такое Высказывание?...
|
Изучив данную тему, студент должен знать:
1. Что такое высказывание? Логические значения высказывания.
2. Основные операции с высказываниями: конъюнкция, дизъюнкция,
отрицание и импликация. Их свойства.
3. Что такое формула алгебры логики высказываний Равносильность формул и свойства равносильности.
4. Понятие предиката и операции над ними.
5. Кванторы всеобщности и существования.
6. Что такое формула логики предикатов. Равносильность формул логики предикатов.
Уметь:
7. Выполнять основные операции с высказываниями и предикатами.
Средства и методы доказательств значительно облегчаются введением символических обозначений и математических операций над высказываниями и комбинациями высказываний. Рассмотрим некоторые задачи
математической логики.
1. Составить таблицу истинности для формулы .
Для решения таких задач надо прежде всего определить число вариантов по формуле m = 2n, где n – число независимых высказываний. В данном случае для двух высказываний x и y m = 22 = 4, т.е. таблица истинности будет содержать четыре строки. Следующим шагом является перебор всех значений 1 и 0 для x и y и использование известных свойств дизъюнкции.
В результате имеем таблицу:
x | y | ||
2. Составить таблицу истинности для формулы .
В отличие от примера 1 здесь n =3, т.е. x, y и z. Поэтому m = 23 = 8
и таблица содержит восемь строк. Остальное – аналогично примеру 1:
x | y | z | |||
3. Доказать равносильность .
Для решения таких задач необходимо использовать важнейшие равносильности алгебры логики, приведенные в плане-конспекте. Преобразуем левую часть:
(формула второй группы).
А теперь переведем импликацию в дизъюнкцию (по формуле ):
.
Используем дистрибутивный закон (третья группа):
.
Но по основным равносильностям (первая группа):
, т.е.
.
Используя теперь и , имеем (для ясности поставим скобки):
.
Полученное выражение полностью совпало с правой частью исходной формулы (ясно, что ), поэтому равносильность доказана.
Обычно такие доказательства и преобразования записываются короче в виде цепочки:
4. Упростить формулу .
Рассуждая аналогично предыдущему примеру и, используя основные равносильности, получим цепочку:
5. За отсутствие документов наряд милиции задержал трех студентов разных вузов: Романа, Сергея и Павла. На допросе каждый из них показал следующее:
‑ Роман: Я учусь в ИМПЭ, а Сергей – в СГУ;
‑ Сергей: Я учусь в ИМПЭ, а Роман – в МИЭП;
‑ Павел: Я учусь в ИМПЭ, а Роман – в СГУ.
В ответах каждого из них одно утверждение истинно, а другое – нет. Поэтому в милиции легко определили, кто где учится. Как это было установлено?
При решении таких логических задач, постоянно возникающих в деятельности юриста, необходимо формализовать имеющиеся утверждения,
определить базовую связь между ними и упростить полученное выражение путем равносильных преобразований.
Обозначим через Xy студента, имя которого начинается с буквы X,
а y – первая буква названия института, в котором он учится. К примеру, утверждение «Роман учится в ИМПЭ» запишется Ри.
Так как в показаниях студентов одно утверждение верно, а другое – нет, то по условию задачи можно составить следующие истинные дизъюнкции:
РиСс = 1,
СиРм =1,
ПиРс =1.
Но тогда будет истинной и конъюнкция этих дизъюнкций:
(РиСс) (СиРм) (ПиРс) =1.
Используем свойства равносильностей. Для первых двух скобок:
(РиСс)(СиРм)=(РиСи)(РиРм)(СсСи)(СсРм)=
=000(СсРм) = СсРм.
Так как все студенты из разных вузов, то XyXz = 0 и, кроме того, один студент не может учиться в двух вузах, поэтому XyZy = 0, что
и приводит к такой формуле.
А теперь полученный результат используем с третьей скобкой конъюнкции:
(СсРм) (ПиРс)=
=(СсПи)(СсРс)(РмПи)(РмРс)=
=(СсПи)0(РмПи)0=(СсПи)(РмПи)=
=(СсРм) Пи=СсРмПи.
Так как по конъюнкции СсРмПи = 1, то Сергей учится в СГУ,
Роман – в МИЭП, а Павел – в ИМПЭ.
Решение полученной задачи есть логическое рассуждение.
6. По подозрению в совершенном преступлении задержали Брауна, Джона и Смита. Один из них был уважаемым в городе стариком, другой был малоизвестным чиновником, третий – известным мошенником. В процессе следствия старик говорил правду, мошенник лгал, а третий задержанный в одном случае говорил правду, а в другом – ложь. Вот что они утверждали:
Браун: «Я совершил это, Джон не виноват».
Джон: «Браун не виноват. Преступление совершил Смит».
Смит: «Я не виноват, виноват Браун».
Требуется определить имена старика, мошенника и чиновника, и кто из них виноват, если известно, что преступник один.
В этой задаче условие может быть записано в виде формулы, истинность которой не очевидна. Следует провести анализ.
Обозначим буквами B, D и S высказывания: «виноват Браун», «виноват Джон» и «виноват Смит» соответственно. Тогда утверждения, высказанные задержанными, можно записать в виде конъюнкций:
,
из которых по условию задачи две ложны, а одна истинна и поэтому будет истинна формула:
.
Эта формула не тождественно истинна. Действительно, если истинно высказывание D и ложны высказывания B и S, то L = 0. Но эта формула
и не тождественно ложна. Например, при истинном высказывании B
и ложных высказываниях D и S имеем L = 1. В связи с этим имеет смысл рассмотреть таблицу истинности формулы L и проанализировать все случаи, при которых формула L истинна.
Таблица истинности этой формулы имеет вид:
B | D | S | L | ||||
Отсюда видно, что формула L истинна в пяти из восьми нумерованных случаев. Случай 4 следует исключить из рассмотрения, так как здесь оказываются истинными две конъюнкции, а это противоречит условию
задачи.
В случаях 2, 3 и 5 оказываются истинными по два высказывания B и D, B и S, D и S соответственно, что также противоречит условию задачи. Следовательно, справедлив случай 7, т.е. преступник – Смит. Он известный мошенник, и оба его высказывания ложны . При этом B = 0 и D = 0, т.е. высказывания B и D ложны. Значит, истинна пара высказываний Джона, а у Брауна первое высказывание ложное, а второе – истинное. Отсюда ясно, что Джон – уважаемый в городе старик, а Браун – малоизвестный чиновник.
7. Пусть заданы предикаты : «x – четное число» и : «x – дели-тся на 3», определенные на множестве N. Найти область истинности предиката .
Сначала определим области истинности исходных предикатов.
На множестве N четные числа имеют вид:
,
а числа, кратные 3:
.
Пересечение этих областей и явится решением задачи:
.
8. Пользуясь равносильностями, найти отрицание формулы
.
Возьмем отрицание всей формулы и используем замену кванторов
по первой основной равносильности предикатов :
.
А теперь используем равносильность (вторая группа равносильных формул алгебры логики):
.
Следовательно:
.
9. Пусть функция f(x) определена на множестве R. На языке логики предикатов записать определение: функция f(x) называется четной, если область ее определения симметрична относительно начала координат и для каждого x из этой области справедливо равенство .
Здесь задача заключается в переводе текстовой формулировки на язык предикатов. С помощью квантора:
Функция f(x) называется четной, если
.
– Конец работы –
Эта тема принадлежит разделу:
На сайте allrefs.net читайте: "Информатика и математика"
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Тема 15. Элементы математической логики
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов