рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Тема 15. Элементы математической логики

Тема 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. Элементы математической логики

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Тема 6. Современная техническая база информатики
Понятие технической базы информатики. Структура комплекса технических средств (КТС) информатики. Вычислительные средства – основа КТС информатики. Средства ввода-вывода информации. Сетевое оборудов

Дополнительная
35. Агапов А.Б. Информационное законодательство России. – М.: Горизонт, 1993. 36. Анакян Т. Цели и пути компьютеризации делопроизводства //Электронный офис. 1996. Январь–март

Тема 3. Основные составляющие информационного процесса и условия его реализации
Изучив данную тему, студент должен знать: 1. Что такое процесс? 2. Что такое информационный процесс и каковы его структурные элементы? 3. Что такое технология? 4

Тема 4. Информационное моделирование и информационные модели
Изучив данную тему, студент должен знать: 1. Что такое модель и моделирование? 2. В чем состоит сущность информационного моделирования и информационной модели? 3. Какие т

Тема 5. Алгоритмизация и программирование – инструментарий информатики
Изучив данную тему, студент должен знать: 1. Что такое алгоритм и алгоритмизация? 2. Основные свойства алгоритмов. 3. Инструментарий построения алгоритмов. 4. Чт

Тема 6. Современная техническая база информатики
Изучив данную тему, студент должен знать: 1. Что такое техническое обеспечение информатики? 2. Структуру технической базы информатики. 3. Что такое компьютер? Основные ча

Тема 7. Локальные и глобальные компьютерные сети
Изучив данную тему, студент должен знать: 1. Что такое компьютерная сеть? Основные элементы компьютерной сети. 2. Что такое сетевые протоколы? Уровни сетевых протоколов.

Тема 8. Автоматизированные информационные системы в юриспруденции
Изучив данную тему, студент должен знать: 1. Что такое система, подсистема, элемент системы? 2. Что такое автоматизированная система, какие типы автоматизированных систем существу

Тема 9. Защита информации и информационных технологий от несанкционированного доступа и вредоносных воздействий
Изучив данную тему, студент должен знать: 1. Возможные нарушения санкционированного доступа к информации и информационным технологиям. 2. Возможные вредоносные воздействия, п

Тема 10. Аксиоматические начала математики
Изучив данную тему, студент должен знать: 1. Понятие множества, подмножества. Обозначения и изображения множеств. Способы задания множеств. 2. Операции над множествами и свойства

Тема 11. Элементы математического анализа
Изучив данную тему, студент должен знать: 1. Определение предела переменной величины. Определение предела функции. 2. Понятие бесконечно малой (б.м.) и бесконечно большой (б.б.) в

Тема 12. Математическая комбинаторика
Изучив данную тему, студент должен знать: 1. Правило произведения. 2. Правило суммы. 3. Факториал и его свойства. 4. Размещения. 5. Размещения с повторе

Тема 13. Элементы теории вероятности
Изучив данную тему, студент должен знать: 1. Случайные события и их классификацию 2. Классическое и статистическое определение вероятности. 3. Теоремы сложения и умножени

Тема 14. Элементы математической статистики
Изучив данную тему, студент должен знать: 1. Задачи математической статистики. 2. Понятия генеральной и выборочной совокупности. 3. Классификацию выборок. 4. Спо

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги