48070

Математическая логикаи теория алгоритмов. Курс лекций

Конспект

Математика и математический анализ

Формула логики высказываний: пропозициональные буквы переменные: B C простые высказывания пропозициональные связки логические связки скобки = пропозициональная формула ПФ формула proposition – заявление утверждение; от лат. Формула F называется выполнимой если F истинна в некоторой интерпретации: существует k такое что FIk = И. Формула F называется общезначимой или тавтологией если F истинна во всех возможных интерпретациях: для всех возможных k: FIk = И. Формула F называется противоречием если F ложна во всех...

Русский

2013-12-06

125.5 KB

12 чел.

Федеральное агентство железнодорожного транспорта

Московский государственный университет путей сообщения (МИИТ)

Институт управления и информационных технологий

________________________

Кафедра «Автоматизированные системы управления»

В.В. Гуренко

Математическая логика
и теория алгоритмов

Курс лекций

Направление, профиль:

1) Информатика и вычислительная техника, АСОИУ (230100.62),

2) Информационные системы и технологии, ИСТ (230400.62).

Квалификация: бакалавр.

Семестр: 3. Форма контроля: экзамен.

Объемы (ч.):

АСОИУ (УВА): всего – 72, ауд. – 36 (лк. – 18, пр. занятия – 18), СРС – 9.   ЗЕТ = 2;

ИВТ (УИС): всего – 108, ауд. – 39 (лк. – 18, пр. занятия – 18, КСР – 3), СРС – 42.   ЗЕТ = 3.

Москва   2012


Литература

Основная.

№ п/п

Наименование

Автор(ы)

Место и год издания

Исп. при изучении разделов

1.

Дискретная математика для инженера. – 5-е изд. (Серия: Учебники для вузов. Специальная литература).

Кузнецов О.П.

СПб.: Изд-во «Лань», 2009.

МЛ, ТА

2.

Математическая логика и теория алгоритмов. Учебник. (Серия «Высшее образование»).

Судоплатов С.В., Овчинникова Е.В.

М.: Инфра-М, 2008.

МЛ, ТА

3.

Дискретная математика: Учеб. пособие. – 3-е изд., испр. и доп.

Плотников А.Д.

М.: Новое знание, 2008.

МЛ, ТА

4.

Дискретная математика для программистов. Учебник для вузов. – 2-е изд.

Новиков Ф.А.

СПб.: Питер, 2007.

МЛ

5.

Математическая логика: учеб. пособие.

Ершов Ю.Л., Палюгин Е.А.

СПб.: Изд-во «Лань», 2006.

МЛ

Дополнительная.

№ п/п

Наименование

Автор(ы)

Место и год издания

Используется

при изучении разделов

  1.  

Математическая логика и теория алгоритмов для программистов.

Гринченков Д.В., Потоцкий С.И.

М.: Изд-во «КноРус», 2010.

МЛ, ТА

  1.  

Задачи и упражнения по дискретной математике: учеб. пособие. – 3-е изд.

Гаврилов Г.П., Сапоженко А.А.

М.: Физматлит, 2005.

ТА

  1.  

Задачи по теории множеств, математической логике и теории алгоритмов. – 5-е изд.

Лавров И.А., Максимова Л.Л.

М.: Физматлит, 2009.

МЛ, ТА

  1.  

Математическая логика. Пер. с англ. – 4-е изд.

Клини С.К.

М.: ЛКИ, 2008.

МЛ

  1.  

Сложностный метод теории алгоритмов.

Шурыгин В.А.

М.: Либроком, 2009.

ТА

  1.  

Рекурсивные функции.

Марченков С.С.

М.: Физматлит, 2007.

ТА

  1.  

Математическая логика и автоматическое доказательство теорем.

Чень Ч., Ли Р.

М.: Наука, 1983.

МЛ

  1.  

Введение в математическую логику. Пер. с англ.

Мендельсон Э.

М.: Наука, 1984.

МЛ

  1.  

Логика: учеб. пособие. – 2-е изд.

Фатиев Н.И.

СПб.: СПбГУП, 2002.

МЛ


Раздел 1. Математическая логика

Предмет МЛ: логические исчисления в наиболее общем виде.


Часть 1. Логика высказываний

§ 1. Основные понятия.

Высказывание – повествовательное предложение, которое либо истинно (И), либо ложно (Л), но не то и другое вместе.

Отрицание

«НЕ»

Конъюнкция

&  

«И»

Дизъюнкция

«ИЛИ»

Импликация

«Если…, то…»

Эквивалентность

«… тогда и только тогда…»

Простые высказывания. Обозначение: A, B, C,…

Примеры. A: «Идет дождь», B: «Книга раскрыта», C: «Солнце светит».

Составные высказывания.   A & C, B, C  A.


Задача логики высказываний: изучение зависимостей между истинностными значениями простых и составных высказываний.

Формула логики высказываний:

пропозициональные буквы (переменные): A, B, C,… (простые высказывания)

+

пропозициональные связки (логические связки)

+

скобки

=

пропозициональная формула (ПФ, формула)

proposition – заявление, утверждение; от лат. propositio – основное положение, предпосылка.

Каждой ПФ можно поставить в соответствие таблицу истинности.

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

Пример. F = (A & B)  B.

A

B

A & B

F

Л

Л

Л

И

Л

И

И

Л

И

Л

Л

И

И

И

Л

И


§ 2. Интерпретации.

Пусть F(x1, x2, … xn) – ПФ, где x1, x2, … xn – входящие в F пропозициональные переменные.

Интерпретация I формулы F – конкретный набор истинностных значений переменных x1, x2, … xn.

F(I) – значение формулы F в интерпретации I.

В приведенном выше примере, где  F = (A & B)  B,  можно указать:

I1: A = «Л», B = «И» либо кратко: I1 = (Л, И). F(I1) = «Л».

I2: A = «И», B = «Л», кратко: I2 = (И, Л). F(I2) = «И».

В построении для ПФ таблицы истинности, включающей все возможные интерпретации, заключается исчисление высказываний методом таблиц истинности.

§ 3. Тавтологии и противоречия.

Формула F называется выполнимой, если F истинна в некоторой интерпретации,:

существует k такое, что F(Ik) = «И».

Формула F называется общезначимой или тавтологией, если F истинна во всех возможных интерпретациях,:

для всех возможных k: F(Ik) = «И».

Формула F называется противоречием, если F ложна во всех возможных интерпретациях (т.е. формула невыполнима):

для всех возможных k: F(Ik) = «Л».

Пример. F1 = А  А – тавтология:

I1 = «И», F1(I1) = «И»;   I2 = «Л», F1(I2) = «И».   Других интерпретаций нет.

F2 = А & А – противоречие:

I1 = «И», F2(I1) = «Л»;   I2 = «Л», F2(I2) = «Л».   Других интерпретаций нет.

F3 = (A & B)  B – выполнимая формула.


Две теоремы о тавтологиях.

Th. 1.

  1.  Если F – тавтология, то F – противоречие, и наоборот.
  2.  Если F – противоречие, то F – тавтология, и наоборот.
  3.  Если F – тавтология, то неверно, что F – противоречие, и наоборот.
  4.  Если F – выполнимая формула, то неверно, что F – тавтология.
  5.  Если F – выполнимая формула, то неверно, что F – противоречие.

Доказательства 1) … 5) следуют из определений и предшествующих утверждений для последующих. ■

Th. 2. Если формулы P и P  Q – тавтологии, то формула Q – тавтология.

Доказательство. От противного. Предположим: Q(Ij) = «Л». Из условия имеем:

P(Ij) = «И». Но тогда [P  Q] (Ij) = «Л» по определению импликации. Получили противоречие с условием в том, что P  Q – тавтология.

Предположение неверно, и Q – тавтология. ■


§ 4. Логическое следование и логическая эквивалентность.

Пусть P и Q – формулы. Говорят, что:

Q логически следует из P (обозначение P  Q), если Q истинна в тех же интерпретациях, в которых истинна P;

P и Q логически эквивалентны (обозначение P Q), если они являются логическим следствием друг друга, т.е. (P  Q) & (Q  P).

Свойство 1. Истинностные значения логически эквивалентных формул одинаковы в каждой из всех возможных интерпретаций.

Пример. (A  B)  (A & B).

Теоремы о логической эквивалентности.

Th. 3. Если формулы P и Q логически эквивалентны, то формула P Q – тавтология.

Доказательство. На основании свойства 1, формулы P и Q одновременно принимают значение либо «И», либо «Л». И в том, и в другом случае значение формулы P Q равно «И» по определению эквивалентности, т.е. [P Q](Ij) = «И» для всех возможных j.    P Q – тавтология. ■

Th. 4. Формула  P  Q  логически эквивалентна формуле P  Q:   (P  Q) (P  Q).

Доказательство: методом таблиц истинности для всех возможных интерпретаций. ■

Th. 4 позволяет заменять дизъюнкцию импликацией.


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

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

то имеют место соответствующие логические эквивалентности:

Свойство операций над множествами

Логическая эквивалентность

Коммутативность

A B = B A

A B = B A

A & B B & A

A B B A

Ассоциативность

A (B  С) = (A  B) C

A (B  С) = (A  B) C

A & (B & C) (A & B) & C

A (B C)  (A B)  C

Дистрибутивность

A (B  С) = (A  B) (A  C)

A (B  С) = (A  B) (A  C)

A & (B C)  (A & B) (A & C)

A (B & C) (A B) & (A C)

и т.д.

Доказательство: методом таблиц истинности для всех возможных интерпретаций. ■


Теоремы о логическом следовании.

Th. 6*. Если P1, P2, … Pn, Q – формулы, то (P1 & P2 & … & Pn)  Q тогда и только тогда, когда (P1 & P2 & … & Pn)  Q – тавтология.

Th. 7*. Если P1, P2, … Pn, Q – формулы, то (P1 & P2 & … & Pn)  Q тогда и только тогда, когда P1 & P2 & … & Pn & Q – противоречие.

Доказательство: см. рекомендованную литературу.

Примечание.  A  B: формулировка «В логически следует из А» эквивалентна формулировке «А логически влечет В».

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

  •  является ли формула выполнимой, тавтологией или противоречием;
  •  имеет ли место логическое следование одной формулы из другой;
  •  являются ли две формулы логически эквивалентными.


§ 5. Подстановка и замена.

Пусть F – формула, в которую входит переменная х:  F(…х…)

или подформула Q: F(…Q…).

Пусть P – формула. Тогда F(…х…) {P // х}

обозначает формулу, полученную из F подстановкой P вместо всех вхождений х в F;

F(…Q…) {P / Q}

обозначает формулу, полученную из F заменой некоторых (одного или нескольких) вхождений подформулы Q на формулу P.

Пример. Дано: F = (A & B  B  A)  A & B. Пусть x = B,  P = B A,  Q = A & B.

Тогда  подстановка F(…х…) {P // х}  =  F(…B…) {(B A) // B}  =

=  (A & (B A)   (B A)  A)  A & (B A);

однократная замена F(…Q…) {P / Q}  =  F(…(A & B)…) {(B A) / (A & B )} =

=  ((B A)  B  A)  A & B.

Th. 8 (правило подстановки). Если F(…х…) – тавтология и Р – любая формула,
то F(…х…) {P // х} – тавтология.

Th. 9 (правило замены). Если F(…Q…),  Q  S  и  D = F(…Q…) {S / Q},  то  F  D.

NB: Q и S – эквивалентные, но разные формулы!

Правила Th. 8 и Th. 9 используются при построении логического вывода в формальных теориях.

Частный случай формулы.

Формула В, полученная из формулы А подстановкой подформул В1, В2, …, Вn вместо переменных х1, х2, …, хn, называется частным случаем формулы А:

Набор подстановок  называется унификатором, т.к. в указанной подстановке формулы А и В унифицируются на основании Th. 8 (правила подстановки).

При этом если А – тавтология, то и В – тавтология  (подстановка в тавтологию порождает тавтологию).


 

А также другие работы, которые могут Вас заинтересовать

7158. Отечественная история от возникновения Древнерусского государства до первой русской революции 187 KB
  Возникновение Древнерусского государства Нет точных сведений, когда было образовано Древнерусское государство. Источников информации не сохранилось. Единственный источник, который нам дает хоть какое-то представление о тех временах - Повесть...
7159. Тепловой расчёт парового котла ДЕ-25-14 ГМО 487.5 KB
  Общие сведения о котлах ДЕ 1..25. Газомазутные котлы ДЕ конструкции котельного завода г. Бийска и ЦКТИ предназначены для выработки насыщенного или слабо перегретого пара с абсолютным давлением 14 кгс/см2 или 24 кгс/см2, паропроизводительностью 1 4...
7160. Формы и виды инфляции, причины ее возникновения 172.43 KB
  Введение Деньги - один из основных феноменов экономической жизни выступают в качестве реальной связи хозяйствующих субъектов государства. Нет ничего удивительного в том, что теории денежного обращения посвящали свои труды, выдающиеся мыслители...
7161. Разработка цифровой интегральной микросхемы по заданным параметрам 476.5 KB
  Разработка цифровой интегральной микросхемы, 10-й вариант. Рисунок 1 Раздел 1. Электрический расчет цифровой схемы. При выполнении расчетов принимаем:  U0 = 0,1 B, U1 > 3 В, падение напряжения на д...
7162. Комплексная оценка состояния и уровня содержания автомобильной дороги 214.5 KB
  Комплексная оценка состояния и уровня содержания автомобильной дороги Вопросы оценки качества и уровня содержания автомобильных дорог играют решающее значение в области технической эксплуатации автомагистралей. Результаты такой оценки служа...
7163. Мехатронная система регулирования положения стрелы, которая должна обеспечить заданную точность угла регулирования 371 KB
  Введение Целью курсового проекта является расширение, углубление и закрепление знаний, полученных на лекциях и лабораторных занятиях по проектированию мехатронных систем, а результатом должна стать система регулирования положения заданного объекта....
7164. Изучение магнитного поля кругового тока 96.5 KB
  Изучение магнитного поля кругового тока 1. ЦЕЛЬ РАБОТЫ Целью данной работы является изучение магнитного поля на оси витка с током и экспериментальная проверка закона Био–Савара–Лапласа. 2. ОПИСАНИЕ УСТАНОВКИ И МЕТОДИКИ ЭКСПЕРИМЕНТА Экспери...
7165. Определение момента инерции твердых тел при поступательном и вращательном движении 260 KB
  Определение момента инерции твердых тел 1. Цель работы Целью настоящей работы является изучение основных законов динамики поступательного и вращательного движений твердых тел, экспериментальное определение момента инерции блока и сравнение его с рас...
7166. Создание графического редактора в среде Visual Basic 270.5 KB
  Введение Цель курсовой работы является создание графического редактора в среде VisualBasic. Задачами курсовой работы является изучение среды программирования VisualBasic, создание в ней работающих программных продуктов. Курсовая работа с...