48070
Математическая логикаи теория алгоритмов. Курс лекций
Конспект
Математика и математический анализ
Формула логики высказываний: пропозициональные буквы переменные: B C простые высказывания пропозициональные связки логические связки скобки = пропозициональная формула ПФ формула proposition заявление утверждение; от лат. Формула F называется выполнимой если F истинна в некоторой интерпретации: существует k такое что FIk = И. Формула F называется общезначимой или тавтологией если F истинна во всех возможных интерпретациях: для всех возможных k: FIk = И. Формула F называется противоречием если F ложна во всех...
Русский
2013-12-06
125.5 KB
14 чел.
Федеральное агентство железнодорожного транспорта
Московский государственный университет путей сообщения (МИИТ)
Институт управления и информационных технологий
________________________
Кафедра «Автоматизированные системы управления»
В.В. Гуренко
Математическая логика
и теория алгоритмов
Курс лекций
Направление, профиль:
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. |
МЛ |
Дополнительная.
№ п/п |
Наименование |
Автор(ы) |
Место и год издания |
Используется при изучении разделов |
|
Математическая логика и теория алгоритмов для программистов. |
Гринченков Д.В., Потоцкий С.И. |
М.: Изд-во «КноРус», 2010. |
МЛ, ТА |
|
Задачи и упражнения по дискретной математике: учеб. пособие. 3-е изд. |
Гаврилов Г.П., Сапоженко А.А. |
М.: Физматлит, 2005. |
ТА |
|
Задачи по теории множеств, математической логике и теории алгоритмов. 5-е изд. |
Лавров И.А., Максимова Л.Л. |
М.: Физматлит, 2009. |
МЛ, ТА |
|
Математическая логика. Пер. с англ. 4-е изд. |
Клини С.К. |
М.: ЛКИ, 2008. |
МЛ |
|
Сложностный метод теории алгоритмов. |
Шурыгин В.А. |
М.: Либроком, 2009. |
ТА |
|
Рекурсивные функции. |
Марченков С.С. |
М.: Физматлит, 2007. |
ТА |
|
Математическая логика и автоматическое доказательство теорем. |
Чень Ч., Ли Р. |
М.: Наука, 1983. |
МЛ |
|
Введение в математическую логику. Пер. с англ. |
Мендельсон Э. |
М.: Наука, 1984. |
МЛ |
|
Логика: учеб. пособие. 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) … 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 (правила подстановки).
При этом если А тавтология, то и В тавтология (подстановка в тавтологию порождает тавтологию).
А также другие работы, которые могут Вас заинтересовать | |||
363. | Модель промислового верстата з ЧПУ | 1.84 MB | |
Промисловий верстат з ЧПУ використовується для обробки різного роду матеріалів, нанесення зображень на різні види поверхонь, отримання різного роду фігурних елементів, фрезерних робіт. | |||
364. | Экономический расчет работы предприятия | 473.5 KB | |
Расчет численности младшего обслуживающего персонала. Определение средней тарифной ставки по видам воздействий. Расчет сдельного расценка за 1 автомобиле-день работы автомобиля. Затраты на расходные материалы и запасные части для ремонтной. | |||
365. | Основы программирования | 110 KB | |
Описание процесса компиляции и запуска программы. Программа для вычислений над матрицами. Microsoft Visual Studio Express. Стандартная библиотека шаблонов (STL). Создание динамического класса для работы с матрицами. | |||
366. | Создание транспортной сети SDH в городе Темиртау. | 517.5 KB | |
Разработка схемы включения станций в проектируемую сеть SDH города Темиртау. Выбор топологии включения станций проектируемой сети. Возможность интеграции с каналами PDH. Развитие магистральных телекоммуникаций казахстанских операторов связи. | |||
367. | Трансформация образа трикстера в современной культуре | 843 KB | |
Основные характеристики трикстера как мифологического персонажа в архаической традиции. Исходная парадигма образа героя-трикстера: этиологические мифы. Трикстериада и ее взаимоотношения с институтом шаманизма и волшебной сказкой. | |||
368. | Смарт-карты известных мировых производителей | 139.5 KB | |
Основные сведения о смарт-картах. Чтение/запись смарт-карты через параллельный порт. Основные управляющие команды карты. Назначение областей данных. Принципиальная схема источника питания. | |||
369. | Решение вопросов теории вероятности на уроках математики | 583 KB | |
Выделить основные цели и задачи изучения теории вероятностей в курсе школьной математики. Изучение и анализ научной учебно-методической литературы, программ по математике для общеобразовательных учреждений. Наблюдение за деятельностью учащихся, ее анализ. | |||
370. | Проектирование усилителя низкой частоты | 354.5 KB | |
Расчет режима работы транзистора по постоянному и переменному току. Расчет КПД каскада для максимального входного сигнала. Расчет коэффициента гармонических искажений. Расчет элементов цепи смещения. | |||
371. | Управление производственной деятельностью станций технического обслуживания | 380.5 KB | |
Расчет производственной программы по количеству ТО и ТР автомобилей. Выбор метода технологического процесса на объекте проецирования. Выбор режима работы объекта и график работы автомобиля на линии. Выбор метода организации производства ТО и ТР на предприятии. | |||