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 (правила подстановки).

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


 

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

12584. М. Вебер Холокост: нужно выслушать обе стороны 34.42 KB
  М. Вебер Холокост: нужно выслушать обе стороны Почти каждый слышал что немцы убили во время Второй мировой войны шесть миллионов европейских евреев. Американское телевидение кино газеты и журналы постоянно муссируют эту тему. В столице США Вашингтоне построен огр...
12585. Опровержение холокоста 122.5 KB
  ОПРОВЕРЖЕНИЕ ХОЛДОКОСТА Холокост от англ. holocaust из др.греч. ὁλοκαύστος всесожжение жертвоприношение у евреев при котором жертва животное полностью пожиралась огнем: дегенераты зачемто мучили бедных животных. Для того чтобы сжечь 6 шесть млн. всем имевшим...
12586. Музей Холокоста 28.5 KB
  Музей Холокоста Музей Холокоста в Вашингтоне округ Колумбия предлагает своим посетителям увидеть вспомнить и вновь пережить трагедию. Холокост это массовое убийство еврейского народа нацистами во время Второй мировой войны который жил в Германии и в других европей...
12587. Почему я не верю в холокост 1.18 MB
  Почему я не верю в холокост Я перестал верить в холокост изза того что сочинители этого мифа считают меня идиотом постоянно пытаясь выдать за правду несуществующие и невероятные факты. Давно обратил внимание что во всей теории холокоста в какую историю не ткни – в...
12588. ОТНОШЕНИЕ РУССКОЙ ПРАВОСЛАВНОЙ ЦЕРКВИ К ТЕМЕ ХОЛОКОСТА. ДИНАМИКА И ПЕРСПЕКТИВЫ ОТНОШЕНИЯ РПЦ К ТЕМЕ КАТАСТРОФЫ И ЧЕРЕЗ НЕЕ К ЕВРЕЯМ, ИЗРАИЛЬТЯНАМ И К ГОСУДАРСТВУ ИЗРАИЛЬ 288.17 KB
  ОТНОШЕНИЕ РУССКОЙ ПРАВОСЛАВНОЙ ЦЕРКВИ К ТЕМЕ ХОЛОКОСТА. ДИНАМИКА И ПЕРСПЕКТИВЫ ОТНОШЕНИЯ РПЦ К ТЕМЕ КАТАСТРОФЫ И ЧЕРЕЗ НЕЕ К ЕВРЕЯМ ИЗРАИЛЬТЯНАМ И К ГОСУДАРСТВУ ИЗРАИЛЬ Оглавление Введение2 Патриархи и богословы3 Алексий II3 Кирилл4 Кураев5 Чаплин8 Стру
12589. Жрецы и жертвы Холокоста Кровавые язвы мировой истории 1.81 MB
  Станислав Куняев Жрецы и жертвы Холокоста Кровавые язвы мировой истории К ЧИТАТЕЛЮ Увенчается ли наше стремление к новому мировому порядку успехом зависит от того выучим ли мы уроки Холокоста. Я. Дж. Кадеган Эта работа была задумана несколько лет...
12590. РЕВИЗИОНИЗМ ХОЛОКОСТА 260 KB
  Ревизионизм холокоста Юрген Граф Лекция в Институте мировых цивилизаций Москва 15 апреля 2009 г. Существует ли на Западе свобода исторического исследования Ответ: Да существует – если только историки занимаются тематикой которая не затрагивает интересы госпо...
12591. АНАЛИЗ ТОЧНОСТИ ОБРАБОТКИ ДЕТАЛЕЙ ПО КРИВЫМ РАСПРЕДЕЛЕНИЯ 293 KB
  АНАЛИЗ ТОЧНОСТИ ОБРАБОТКИ ДЕТАЛЕЙ ПО КРИВЫМ РАСПРЕДЕЛЕНИЯ Методические указания к выполнению лабораторной работы по дисциплине Основы технологии машиностроения для студентов обучающихся по направлению 552900 Технология оборудование и автоматизация машиностр
12592. ВЛИЯНИЕ РЕЖИМОВ ТОЧЕНИЯ И АЛМАЗНОГО ВЫГЛАЖИВАНИЯ НА ШЕРОХОВАТОСТЬ ПОВЕРХНОСТИ 191 KB
  ВЛИЯНИЕ РЕЖИМОВ ТОЧЕНИЯ И АЛМАЗНОГО ВЫГЛАЖИВАНИЯ НА ШЕРОХОВАТОСТЬ ПОВЕРХНОСТИ Методические указания к выполнению лабораторной работы по дисциплине Основы технологии машиностроения для студентов обучающихся по направлению 552900 Технология оборудование и автома...