Конспект лекций для студентов специальностей асу, эвт, кзи пермь, 2007 г



страница1/9
Дата15.01.2013
Размер0.77 Mb.
ТипКонспект лекций
  1   2   3   4   5   6   7   8   9




Пермский Государственный Технический Университет
Кафедра Информационных технологий и автоматизированных систем


Викентьева О. Л.

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

конспект лекций
для студентов специальностей АСУ, ЭВТ, КЗИ


Пермь, 2007 г.

Введение


Математическая логика - это современный вид формальной логики. Логика – это наука правильно рассуждать, имея какие-то утверждения, истинность которых проверена, например, на опыте. С помощью утверждений можно придти к новому утверждению, которое также может оказаться истинным.

Исходное утверждение называется посылкой, результирующее утверждение – заключением.

Пример 1.

П1: Все люди смертны.

П2. Сократ – человек.

З: Сократ смертен.
Пример 2.

П1: Все граждане России имеют право на образование.

П2: Иванов – гражданин России.

З: Иванов имеет право на образование.
Оба эти вывода имеют одну и ту же форму:

Все А есть В;

С есть А;

Следовательно, С есть В.
В этих рассуждениях нам не интересна истинность или ложность отдельных посылок. Нам важно знать вытекает ли истинность заключения из истинности посылок.
Таким образом, основная задача логики – это формализация правильных способов рассуждения. Если при этом применяется математический аппарат, то такую логику можно назвать математической.

Тема 1. Логика высказываний

1.1. Понятие высказывания


Рассмотрим логику высказываний, которая лежит в основе всех других разделов математической логики (МЛ) и необходима для их понимания.

Логика высказываний строится также как и другие математические теории. В качестве основных понятий берется некоторый класс объектов, а также некоторые свойства, отношения и операции над этими объектами.

Основным объектом логики высказываний служат простые высказывания. Высказывание – это предложение, о котором можно сказать истинно оно или ложно.

Примеры.

  1. Число 100 делится на 5.

  2. Число 3 больше числа 5.

  3. Луна больше Земли.

  4. Сегодня светит солнце.

  5. Вечером мы пойдем в кино.


Из простых высказываний с помощью некоторого числа логических операций можно построить сложные высказывания.

  1. Число 100 делится на 5 и число 100 делится на 10.

  2. Неверно, что 3 больше 5.

  3. Сегодня мы пойдем в кино или мы пойдем в театр.

При изучении логики высказываний не обращают внимание на содержание простых высказываний, а интересуются только их истинностью или ложностью.

Сложные высказывания, получаемые из простых, будут также истинными или ложными.
Их истинность или ложность будет зависеть от истинности образующих их простых высказываний.

1.2. Логические операции


Для изучения логических операций введем следующую систему обозначений:

  • простые высказывания будем обозначать буквами a, b, c, …, x, y ,z;

  • значения истинности будем обозначать 1 – истинно, 0 – ложно.


Действия логических операций будем представлять в виде таблиц истинности.

1. Отрицание или инверсия ( – НЕ)

Пример.

а: 7 делится на 5 без остатка.

а: Неверно, что 7 делится на 5 без остатка.


а

а

0

1

1

0

Эта таблица и принимается в качестве определения операции отрицания.

  1. Конъюнкция ( ,, ·, логическое И )

Действие операции определяется следующим образом: сложное высказывание аb истинно только в том случае, когда оба высказывания (а и b) имеют значение истинно.

а

b

аb

0

0

0

0

1

0

1

0

0

1

1

1


Примеры.

а. 6 делится на 3 без остатка (1);

b. 10 больше 5 (1);

с. 7 делится на 3 без остатка (0);

d. 3 больше 7 (0);
a&b=1

a&c=0

c&d=0
3. Дизъюнкция (,+,логическое ИЛИ)

Действие операции определяется следующим образом: сложное высказывание ав ложно только в том случае, когда оба высказывания (а и в) ложны.


a

b

ab

0

0

0

0

1

1

1

0

1

1

1

1

Примеры.

аb=1

ac=1

cd=0
4. Импликация () “если а, то b

Действие операции определяется следующим образом: сложное высказывание аb ложно только в том случае, когда а истинно, а b – ложно.

a

b

ab

0

0

1

0

1

1

1

0

0

1

1

1


А называется антецедентом, а b – консеквентом.

5. Эквивалентность (~)

Действие операции определяется следующим образом: сложное высказывание а~b истинно, если а истинно и b истинно, или если а ложно и b ложно.

a

b

a~b

0

0

1

0

1

0

1

0

0

1

1

1


Эквивалентность примерно соответствует употреблению выражения «тогда и только тогда».

6. сумма по модулю два


a

b

ab

0

0

0

0

1

1

1

0

1

1

1

0


7. Штрих Шеффера ( , обратная конъюнкция И – НЕ)


a

b

a  b

0

0

1

0

1

1

1

0

1

1

1

0


8. Стрелка Пирса (, обратная дизъюнкция ИЛИ – НЕ )


a

b

ab

0

0

1

0

1

1

1

0

1

1

1

0


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

Приоритет выполнения операций:

⌐   ~

Пример: Сложное высказывание: «Если вы не пропускаете занятия и успешно занимаетесь, то Вы сдадите экзамен хорошо» можно записать следующим образом. Обозначим:

П – пропускаете занятия;

Y – успешно занимаетесь;

Х – сдадите экзамен хорошо,

тогда все высказывание запишется:


Значение истинности всего выражения будет зависеть от истинности переменных обозначающих простые высказывания.

Пример.



Пусть a=1, b=0, c=0, d=1.



Символы ⌐   ~ называются пропозициональными связками, a, b, c, … и т. д. - пропозициональными переменными. Выражение, построенное из пропозициональных переменных с помощью пропозициональных связок, называется пропозициональной формой или формулой.

  1   2   3   4   5   6   7   8   9

Похожие:

Конспект лекций для студентов специальностей асу, эвт, кзи пермь, 2007 г iconКонспект лекций для студентов специальности асу пермь, 2001г

Конспект лекций для студентов специальностей асу, эвт, кзи пермь, 2007 г iconКонспект лекций для студентов специальности асу пермь, 2001г
П(M) – покрытием множества м будем называть любое подмножество множества Р(М), такое, что объединение входящих в него элементов совпадает...
Конспект лекций для студентов специальностей асу, эвт, кзи пермь, 2007 г iconКонспект лекций для студентов специальности асу пермь, 2001г
П(M) – покрытием множества м будем называть любое подмножество множества Р(М), такое, что объединение входящих в него элементов совпадает...
Конспект лекций для студентов специальностей асу, эвт, кзи пермь, 2007 г iconКонспект лекций по курсу нгииг л. В. Белозерцева, А. Г. Коробова, М. Н. Потапова
Конспект лекций предназначен для студентов механических специальностей заочной формы обучения
Конспект лекций для студентов специальностей асу, эвт, кзи пермь, 2007 г icon«международные валютно-кредитные отношения» конспект лекций бурлачков в. К
Конспект лекций предназначен для студентов экономических специальностей, аспирантов, преподавателей, практических работников внешнеэкономической...
Конспект лекций для студентов специальностей асу, эвт, кзи пермь, 2007 г iconКонспект лекций Челябинск Издательский центр юургу 2010
Конспект лекций предназначен для студентов очной формы обучения специальностей «Управление и информатика в технических системах»,...
Конспект лекций для студентов специальностей асу, эвт, кзи пермь, 2007 г iconКонспект лекций по специальности 3050305 Регионоведение США и Канады ббк 63. 3 (7Сое) Конспект лекций по дисциплине «История США и Канады»
Конспект лекций по дисциплине «История США и Канады» составлен в соответствии с требованиями государственного стандарта России. Предназначен...
Конспект лекций для студентов специальностей асу, эвт, кзи пермь, 2007 г iconКонспект лекций Часть II таганрог 2001
Конспект предназначен для студентов специальностей: 072000 "Стандартизация и сертификация в промышленности", 190304 "Приборы и комплексы...
Конспект лекций для студентов специальностей асу, эвт, кзи пермь, 2007 г iconМетодические указания и варианты заданий для самостоятельной работы студентов III курса специальностей км и дпм пермь 2006
...
Конспект лекций для студентов специальностей асу, эвт, кзи пермь, 2007 г iconКурс лекций по дисциплине «химия» для студентов нехимических специальностей Под общей редакцией
Краткий курс лекций по дисциплине «химия» для студентов нехимических специальностей
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org