авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

КУРГАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Кафедра алгебры, геометрии и методики преподавания математики

МАТЕМАТИЧЕСКАЯ ЛОГИКА

Методические указания для практических занятий для студентов первого и

второго курсов специальностей «Математика» и «Информатика с

дополнительной специальностью Математика» (010101, 050202) Курган 2009 Кафедра алгебры, геометрии и методики преподавания математики Дисциплина: «Математическая логика»

Составитель: доцент А.В. Чернышова Утверждены на заседании кафедры «19» ноября 2009 г.

Рекомендованы методическим советом университета «24» ноября 2009 г.

2 СОДЕРЖАНИЕ Введение………………………………………………………………… Тема 1. Высказывания и операции над ними. Формулы алгебры высказываний. Классификация формул……………………………… Тема 2. Логическая равносильность формул…………………………. Тема 3. Нормальные формы для формул алгебры высказываний....... Тема 4. Понятие логического следствия. Виды теорем……………… Тема 5. Применение алгебры высказываний…………………………. Тема 6. Исчисление высказываний……………………………………. Тема 7. Логика предикатов…………………………………………….. Тема 8. Применение логики предикатов. Исчисление предикатов… Темы рефератов, курсовых…………………………………………….. Список литературы……………….......................................................... Вопросы к зачету (экзамену) …………………………………………. Справочные материалы………….…………………………………….. ВВЕДЕНИЕ Настоящие методические указания включают в себя темы практических занятий по основным разделам курса математической логики: алгебра высказываний и ее приложение к логико-математической практике, логика предикатов, математическая логика и информатика. Материал разбит на соответствующие темы и содержит:

1) цели изучения темы, которые определяют требования к знаниям, умениям и навыкам студентов;

2) задачи для аудиторного и самостоятельного решения (двух уровней сложности);

3) темы для рефератов и курсовых работ;

4) справочные материалы.

Практические занятия – наиболее активный вид учебных занятий в вузе.

Они предполагают самостоятельную работу над лекциями и учебными пособиями. При подготовке к практическим занятиям необходимо повторить теорию (по лекциям или учебным пособиям) и решить задачи, предложенные преподавателем. Основной набор задач приведен в пособии. Дополнительный рекомендуется брать в сборнике задач [4] из списка рекомендованной литературы. Каждая задача оценена от 1 до 10 баллов в зависимости от уровня сложности (для применения рейтинговой системы контроля знаний).

В течение всего курса студент должен подготовить 1 – 2 сообщения для выступления на практическом занятии из списка тем рефератов. На каждом занятии преподаватель осуществляет контроль знаний студентов устным опросом или с помощью небольших проверочных работ, позволяющих оценить степень усвоения материала. При подготовке к занятиям студент может ознакомиться со справочным материалом, который имеется в пособии.

Тема 1. Высказывания и операции над ними. Формулы алгебры высказываний. Классификация формул Цели занятия После изучения темы студент должен:

Знать: определение высказывания, высказывательной формы, логической операции, пропозициональной (высказывательной) переменной;

какие союзы считаются логическими связками;

определения и обозначения логических операций: негации (отрицания), конъюнкции, дизъюнкции, импликации, эквиваленции;

порядок выполнения операций;

процедуру формализации высказываний;

алгоритм определения истинности формулы в зависимости от наборов значений составляющих переменных;

классификацию формул алгебры высказываний;

правила получения тавтологий.

Иметь представление: о том, какие предложения считаются простыми и составными с точки зрения математической логики;

как переформулировать предложение, чтобы выявить логические связки;

о значении тавтологий для логико-математической и научной практики.

Уметь: по виду и смыслу предложения определять, является оно высказыванием, высказывательной формой;

выделять логические связки;

определять истинность составного высказывания;

формализовывать составное высказывание;

строить таблицу истинности для формулы;

с помощью таблицы истинности определять вид высказывания.

Задачи Базовый уровень 1. Следующие предложения разделите на группы: высказывания, высказывательные формы, не являются высказываниями: 1) Москва – столица России;

2) Студент университета;

3) Треугольник АВС подобен треугольнику А1В1С1;

4) Луна – спутник Марса;

5) Кислород – газ;

6) Каша – вкусное блюдо;

7) Математика – интересный предмет;

8) Картины Пикассо слишком абстрактны;

9) Железо тяжелее свинца;

10) Да здравствуют музы!

11) Треугольник называется равносторонним, если все его стороны равны;

12) Если в треугольнике все углы равны, то он равносторонний;

13) Сегодня плохая погода;

14) В романе А.С. Пушкина «Евгений Онегин» 136 245 букв;

15) Река Ангара впадает в озеро Байкал;

16) Число 12345 кратно 3 ;

17) Чтобы подключиться к Интернету с домашнего компьютера, необходим модем и соответствующее программное обеспечение;

18) Солнце светит для всех;

19) Все ученики любят информатику;

20) Некоторые из учеников любят информатику;



21) А ты любишь информатику? 22) Посмотри в окно;

23) Крокодилы летают очень низко;

24) Число 8456 является совершенным;

25) Без труда не выловишь и рыбку из пруда;

26) Как хорошо быть генералом! 27) Революция может быть мирной и немирной;

28) Зрение бывает нормальное, или у человека имеется дальнозоркость или близорукость;

29) Познай самого себя;

30) Не может быть, что ни один человек не дышит жабрами. (3 балла) 2. Для каждого высказывания из упражнения 1 определите значение истинности. (1 балл) 3. В каждую высказывательную форму из упражнения 1 подставьте значение переменной так, чтобы получилось: а) истинное высказывание;

б) ложное высказывание. (2 балла) 4. Каждую высказывательную форму из упражнения 1 превратите в истинное высказывание с помощью слова «всякий» или «существует». (2 балла) 5. Во всех составных высказываниях упражнения 1 выделите составляющие их элементарные предложения и логические связки. (1 балл) 6. Из элементарных высказываний упражнения 1 выберите любые два и составьте из них новые предложения с помощью всех логических связок. ( балла) 7. Установите, какие из высказываний в следующих парах являются отрицаниями друг друга, и какие – нет (объясните, почему): 1) 2 0, 2 0;

2) 6 9, 6 9;

3) «Треугольник АВС прямоугольный», «Треугольник АВС тупоугольный»;

4) «Натуральное число п четно», «Натуральное число п нечетно»;

5) «Функция f нечетна», «Функция f четна»;

6) «Все простые числа четны», «Все простые числа нечетны»;

7) «Все простые числа нечетны», «Существует простое четное число»;

8) «Человеку известны все виды животных, обитающих на земле», «На земле существует вид животных, не известный человеку»;

9) «Существуют иррациональные числа», «Все числа рациональные»;

10) «Каждый кашалот является водоплавающим», «Ни один кашалот не является водоплавающим». (3 балла) 8. Укажите, какие из следующих высказываний являются общеутвердительными, общеотрицательными, частноутвердительными, частноотрицательными: 1) Всякий моряк умеет плавать;

2) У каждой лошади есть хвост;

3) Ни одна кошка не дружит с мышами;

4) Есть кошки, которые дружат с собаками;

5) Не все книги содержат полезную информацию;

6) Привидений не существует;

7) Некоторые люди не умеют писать;

8) На всякого мудреца довольно простоты;

9) Не все то золото, что блестит;

10) Ряд водоплавающих не дышит жабрами;

11) Несколько человек не пошли в музей;

12) Многие люди все еще верят в злых духов;

13) Люди в подавляющем своем большинстве хотят добра;

14) Некоторые учебные предметы трудны;

15) Всякая истина является конкретной. (2 балла) 9. Какие из приведенных высказываний не могут быть вместе истинными, но могут быть вместе ложными: 1) Все лыжники – мастера спорта;

2) Некоторые лыжники не являются мастерами спорта;

3) Ни один лыжник не является мастером спорта;

4) Отдельные лыжники – мастера спорта;

(1 балл) 10. Какие из приведенных высказываний могут быть одновременно истинными, но не могут быть одновременно ложными: 1) Все врачи – окулисты;

2) Некоторые из врачей окулисты;

3) Некоторые врачи не окулисты;

4) Среди врачей нет окулистов;

(1 балл) 11. Пользуясь определениями логических операций, определите значения истинности следующих высказываний: 1) Луна – планета и 2 + 3 = 5. 2) 1 – простое число или 2 – простое число. 3) Цинк – металл и цезий – металл. 4) Каждое число делится на 2 или делится на 3. 5) Эйфелева башня находится в Париже или она находится в Нью-Йорке. 6) Лев Толстой написал роман «Воскресение» или он написал роман «Анна Каренина». 7) Если 17 делится на 4, оно делится на 2. 8) Если 20 делится на 4, оно делится на 2. 9) Если Солнце всходит на юге, то оно заходит на западе. 10) Если Солнце всходит на севере, то оно заходит на западе. 11) Если Москва – большой город, то Солнце заходит на юге. 12) Если 2 2 = 5, то Нью-Йорк – большой город.

13) Число 2 четное или оно простое. 14) 2 2 = 4 или белые медведи живут в Африке. 15) Если 12 делится на 6, то оно делится на 3. 16) Если 15 делится на 6, то оно делится на 3. 17) Если 15 делится на 3, то оно делится на 6. 18) Если Париж расположен на Темзе, то белые медведи обитают в Африке. 19) Солнце восходит на востоке тогда и только тогда, когда оно заходит на западе. 20) Если я – Наполеон, то у кошки четыре ноги. (1 балл) 12. Определите значения истинности высказываний А, В, С, и D в следующих предложениях, если известны их значения истинности: 1) «А и 2 2 = 4» = И. 2) «В и 2 2 = 4» = Л. 3) «С или 2 2 = 5 » = И. 4) «D или 2 2 = 5» = Л.

5) «Если 4 – четное число, то А» = И. 6) «Если В, то 4 – нечетное число» = И.

7) «Если 4 – четное число, то С» = Л. 8) «Если D, то 4 – нечетное число» = Л.

9) «А и Марс – планета» = И. 10) «В и Марс – планета» = Л. 11) «С или Солнце – спутник Земли» = И. 12) «D или Солнце – спутник Земли» = Л. 13) «А тогда и только тогда, когда 2 3» = И. 14) «В тогда и только тогда, когда 2 3» = И. 16) «С тогда и только тогда, когда 2 3» = Л. (2 балла) 13. Пусть а = «9 – четное число» и b = «9 – нечетное число». Определите значения истинности следующих высказываний: 1) a b ;

2) b a ;

3) a b ;

4) a b ;

5) b ;

6) b a ;

7) b a ;

8) a b ;

9) a b ;

10) a b ;

11) a b ;

12) a b ;

13) a b ;

14) a b ;

15) a b ;

16) a b. (1 балл) 14. Определите значение истинности приведенных высказываний, предполагая, что а = И (а = Л): 1) a a ;

2) a a ;

3) a a ;

4) a a ;

5) a a ;

6) a a ;

7) a a ;

8) a a ;

9) a a ;

10) a a. (2 балла) 15. Пусть а = И и b = Л. Определите истинностное значение следующих сложных высказываний: 1) a b a ;

2) a b a ;

3) a a b ;

4) a a b ;

5) a b a ;

6) a (b a ) ;

7) a a b ;

8) a a b ;

9) a a b ;

10) a b b a. (2 балла) 16. Формализуйте следующие сложные высказывания: 1) Если число делится на 2 и не делится на 3, то оно не делится на 6. 2) Если производная функции в точке равна нулю и вторая производная этой функции в этой же точке отрицательна, то данная точка есть точка локального максимума функции. 3) Лошадь погибает от одного грамма никотина, но я не лошадь, следовательно, курить вредно. 4) Если у меня будет свободное время и не будет дождя, то я не буду писать сочинение, а пойду на дискотеку. 5) Если в треугольнике медиана не является высотой и биссектрисой, то этот треугольник не равнобедренный и не равносторонний. (3 балла) 17. По форме высказываний и выраженным на естественном языке составляющим его простым высказываниям получите фразу на естественном языке. а = «8 – четное число»;

b = «8 делится на 4»: 1) a b ;

2) b a ;

3) a b ;

4) a b ;

5) а b ;

6) b a ;

7) b a ;

8) a b ;

9) a b ;

10) a b ;

11) a b ;

12) a b ;

13) a b ;

14) a b ;

15) a b ;

16) a b. (3 балла) 18. В следующих формулах расставьте порядок выполнения операций и выпишите соответствующие подформулы: 1) ( p q r ) ( p q r ) ;

2) p q ( p q p q) ;

3) p (q p ) ((q p) q) ;

4) p r ( p q) ;

5) ( p q) r s ;

6) ( p q r ) ( p r ) ;

7) p (q (r p q )) ;

8) p (q r s ) s.

(3 балла) 19. Для следующих формул постройте таблицы истинности и определите вид каждой формулы (выполнима, опровержима, тавтология, противоречие): 1) p q ( p q p) ;

2) p q p q ;

3) p (q p ) ((q p) q) ;

4) p q q ( p q) ;

5) p q ( p q) ;

6) pqqqq;

7) ( p q q ) ( p q) ;

8) ( p p q) (q p p ). (3 балла) Повышенный уровень 20. Формализуйте следующие сложные высказывания: 1) Если прямая параллельна каждой из двух пересекающихся плоскостей, то она параллельна и линии их пересечения. 2) Без Вас хочу сказать Вам много,/ При Вас я слушать Вас хочу. 3) Люди получают высшее образование тогда, когда они заканчивают институт, университет или академию. 4) Произведение трех чисел равно нулю тогда и только тогда, когда одно из них равно нулю. 5)Чтобы погода была солнечной, достаточно, чтобы не было ни ветра, ни дождя. (5 баллов) 21. По форме высказываний и выраженным на естественном языке составляющим его простым высказываниям получите фразу на естественном языке. а = «Теория Дарвина является научной»;

b = «Теория Дарвина может быть подтверждена опытными данными»;

с = «Теория Дарвина может быть опровергнута опытными данными»: 1) a (b c) ;

2) a (b c) ;

3) (b c) a ;

4) (b c) a ;

5) (b c) a ;

6) a (b c) ;

7) (b c) a ;

8) b (c a). (5 баллов) 22. Для следующих формул постройте таблицы истинности и определите вид каждой формулы (выполнима, опровержима, тавтология, противоречие): 1) ((( p q) ( p r )) (q r )) p ;

2) p (q r ) (r p q q r p) ;

3) r p q r p q ;

4). ( p q) (q r ) r q. (4 балла) Дополнительно: [4] Базовый уровень: № 1.8, 1.13, 1.23, 1.24 (а, в), 1.29 (д, е, ж, и, т).

Повышенный уровень: 1.15, 1.16, 1.17, 1.18, 1.19, 1.20, 1.21, 1.22, 1.24 (б), 1. а, б, в, г), 1.28 (а, б, в, г), 1.30 (б, е, ж, з, п, р).

Тема 2. Логическая равносильность формул Цели занятия После изучения темы студент должен:

Знать: определение равносильных формул, свойства отношения равносильности;

основные равносильности (законы логики);

понятия равносильных преобразований и упрощения формул;

определение двойственных формул;

принцип двойственности.

Иметь представление: о различных способах доказательства равносильности формул;

о способах выражения одних логических операций через другие;

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

Уметь: доказывать свойства отношения равносильности формул;

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

Задачи Базовый уровень 1. С помощью таблиц истинности выясните, какие из данных формул равносильны: 1) F = X Y ;

G = X Y ;

H = Y X. 2) F = Y X ;

G = X Y ;

H = Y X. 3) F = X Y ;

G = X Y ;

H = X Y. 4) F = X Y ;

G = ( X Y ) (Y X ) ;

H = Y X. 5) F = X Y ;

G = X Y ;

H = X Y. 6) F = X Y ;

G = ( X Y ) (Y X ) ;

H = X Y. (3 балла) 2. Установите, какие из следующих предложений равносильны в логике высказываний: «Я читал эту книгу» (Р1);

«Я не видел этого фильма» (Р2);

«Я читал эту книгу, но не видел этого фильма» (Р3);

«Неверно, что эту книгу я не читал» (Р4);

«Неверно, что я видел этот фильм» (Р5);

«Неверно, что я не читал эту книгу или видел этот фильм» (Р6). «Если отрезки равны, то их длины равны» (Q1);

«Если длины отрезков равны, то они равны» (Q2);

«Если отрезки не равны, то их длины не равны» (Q3);

«Если длины отрезков не равны, то они не равны» (Q4). (1 балл) x 2, 3. Имеет ли решение система неравенств ? На каком законе логики x основан ваш ответ? (1 балл) 4. Как объяснить, что загадка «Хожу на голове, хотя и на ногах, хожу я без сапог, хотя и в сапогах» имеет отгадку (гвоздь в подошве сапога)? Не нарушен ли здесь закон противоречия? (1 балл) 5. Что можно сказать об истинности предложения «Прямые а и b на плоскости параллельны или пересекаются»? Зависит ли его значение от взаимного расположения прямых а и b? На каком законе логики основан ваш ответ? ( балл) 6. С помощью равносильных преобразований докажите, что данные формулы являются тавтологиями: 1) p (q p) ;

2) p p q ;

3) ( p q) (q p) ;

4) ( p q) (q p) p q p q. (4 балла) 7. С помощью равносильных преобразований докажите, что данные формулы являются противоречиями: 1) ( p q p) p ;

2) q p ( p q) ;

3) ( p q) p (q q) ;

4) ( p q) ( p q ) p. (4 балла) Повышенный уровень 8. С помощью таблиц истинности выясните, какие из данных формул равносильны: 1) F = X (Y Z ) ;

G = ( X Y ) ( X Z ) ;

H = X Y Y Z. 2) F= X (Y Z ) ;

G = ( X Y ) ( X Z ) ;

H = (Y X ) ( Z X ). 3) F = X (Y Z ) ;

G = X Y Z ;

H = X Y Z. 4) F = X (Y Z ) ;

G = X (Y Z ) ;

H = X Y Z. 5) F = ( X Y ) Z ;

G = ( X Y ) ( X Y ) Z ;

H = Z ( X Y ) (Y X ). (5 баллов) 9. С помощью равносильных преобразований упростите следующие формулы:

1) x y ( x z ) ;

2) ( x y ) ( y x) x y ;





3) ( x y ) ( y x) ( z x) ;

4) ( x y ) z ( x z ) ;

5) x ( y z ) z ;

6) x y x y. (10 баллов) 10. Упростите следующую инструкцию: «Подчеркивайте числа, которые одновременно кратны трем, оканчиваются нулем и имеют сумму цифр, большую 37. Подчеркивайте также те числа, которые не делятся на 3, оканчиваются нулем и имеют сумму цифр, не превосходящую 37. Кроме того, подчеркивайте числа, которые оканчиваются нулем, делятся на 3 и сумма цифр которых не более 37, а также числа, оканчивающиеся нулем, с суммой цифр, большей 37, и не кратные трем. И, наконец, подчеркивайте числа, кратные трем, не оканчивающиеся нулем и имеющие сумму цифр, превосходящую 37». (Указание: Формализуйте инструкцию.

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

Сформулируйте полученную инструкцию.) (6 баллов) 11. При составлении расписания на понедельник были высказаны пожелания, чтобы математика была первым или вторым уроком, физика – первым или третьим, литература – вторым или третьим. Можно ли удовлетворить все высказанные пожелания? (5 баллов) 12. Обвиняемые А, В и С дали следующие показания. А: «В виновен, а С невиновен»;

В: «А невиновен или С виновен»;

С: «Я невиновен, но хотя бы один из А и В виновен». Совместимы ли эти показания, то есть могут ли они быть верны одновременно? Предполагая, что все показания правдивы, определите, кто виновен. (5 баллов) Дополнительно: [4] Базовый уровень: № 1.42 (ж, и, н, п), 1.43 (г, д, ж, л), 1.44 (а, б, в), 1.45 (а, б), 1.50 (а).

Повышенный уровень: № 1.44 (г. д), 1.45 (в, г, д), 1.46 (а, в, г), 1.47, 1.51 (б, в, д), 1.53, 1.54, 1.60.

Тема 3. Нормальные формы для формул алгебры высказываний Цели занятия После изучения темы студент должен:

Знать: понятие конъюнктивной и дизъюнктивной нормальной формы для формул алгебры высказываний;

понятие совершенной конъюнктивной и дизъюнктивной нормальной формы для формул алгебры высказываний;

характерные особенности совершенных нормальных форм;

алгоритм приведения формулы алгебры высказываний к совершенной нормальной форме.

Иметь представление: о том, для чего применяются совершенные нормальные формы в логико-математической практике.

Уметь: для любой формулы алгебры высказываний находить совершенную нормальную форму с помощью таблицы истинности и с помощью равносильных преобразований;

получать из одной совершенной нормальной формы другую.

Задачи Базовый уровень 1. Составьте формулы, соответствующие данным таблицам истинности (выберите рациональный способ). Упростите полученные формулы (1 балл):

x y F1 F2 F3 F4 F5 F 1 1 1 0 1 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 1 0 2. Для каждой из данных формул найдите ее СДНФ и СКНФ с помощью таблицы истинности: 1) x y ;

2) x y ;

3) x y z ;

4) ( x y ) z. (2 балла) 3. Установите, какие из данных формул являются ДНФ;

СДНФ;

КНФ;

СКНФ формул с переменными x, y и z: 1) x y x z ;

2) ( x y z ) ( x y z ) ;

3) ( x y ) ( x z ) ;

4) x y z ;

5) ( x y ) ( x y ) ( x y ) ;

6) x y z ( x y z ) ;

7) x y z. (1 балл) 4. Равносильными преобразованиями приведите каждую из формул к КНФ: 1) z ( x y ) ;

2) x y z ;

3) ( x y ) x z ;

4) x z ( x y ). (3 балла) 5. Равносильными преобразованиями приведите каждую из формул предыдущей задачи к ДНФ. (3 балла) 6. Равносильными преобразованиями приведите каждую формулу задачи 4 к СКНФ, начав с найденной КНФ. (1 балл) 7. Равносильными преобразованиями приведите каждую формулу задачи 4 к СДНФ, начав с найденной в задаче 5 ДНФ. (1 балл) 8. По данному набору значений переменных постройте конъюнктивный одночлен, принимающий значение 1 только на этом наборе значений переменных: 1) (0, 0);

2) (0, 1);

3) (1, 1);

4) (1, 0, 0);

5) (1, 1, 0);

6) (0, 1, 0).

(1 балл) 9. По данному набору значений переменных постройте дизъюнктивный одночлен, принимающий значение 0 только на этом наборе значений переменных: 1) (0, 0);

2) (0, 1);

3) (1, 1);

4) (1, 0, 0);

5) (1, 1, 0);

6) (0, 1, 0).

(1 балл) Повышенный уровень 10. Составьте формулы, соответствующие данным таблицам истинности (выберите рациональный способ). Упростите полученные формулы ( балла):

x y z F1 F2 F3 F4 F5 F 1 1 1 1 1 0 1 0 1 1 0 0 0 0 1 0 1 0 1 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 1 1 0 1 0 11. Приведите следующие формулы к СДНФ с помощью равносильных преобразований: 1) ( x y z ) ( x y ) ;

2) x ( y z ) ;

3) ( x y z ) ( x y z ) ;

4) ( x z ) x y. (4 балла) 12. Приведите следующие формулы к СКНФ с помощью равносильных преобразований: 1) ( x y z) ( x y z) ;

2) ( x y z) ( x y) ;

3) ( x y ) x z. (4 балла) 13. Установите, какие из формул в задачах 11 и 12 равносильны, сравнив их совершенные нормальные формы. (5 баллов) 14. Установите, какие из данных формул являются тавтологиями, приведя их к КНФ: 1) ( x y) ( x z y) ;

2) ( x y) ( y z) ( x y) z ;

3) x y ( x z y ). (7 баллов) Дополнительно: [4] Базовый уровень:, № 2.3 (б, в), 2.4 (б, в), 2.5 (б, в), 2.6 (б, в), 2.8 (а, б, г), 2.11 (а, б, в).

Повышенный уровень: № 2.3 (г, д), 2.4 (г, д), 2.5 (г, д), 2.6 (г, д), 2.15, 2.18 (б, в, г), 2.19 (б, в, г).

Тема 4. Понятие логического следствия. Виды теорем Цели занятия После изучения темы студент должен:

Знать: понятие и свойства отношения логического следования формул алгебры высказываний;

виды теорем;

понятия аргумента, посылки, следствия, правильного и неправильного рассуждения и правила определения правильности рассуждения.

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

Уметь: определять, следует ли одна формула алгебры высказываний из другой;

выполняется ли логическое следование формулы из указанных посылок;

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

Задачи Базовый уровень 1. Приведите по два примера известных вам теорем, для которых обратные предложения верны;

не верны. (1 балл) 2. Сформулируйте предложения: а) обратные данным, б) противоположные данным: 1) «Если в четырехугольнике две противоположные стороны равны и параллельны, то этот четырехугольник – параллелограмм»;

2) «Если последовательность монотонна и ограниченна, то она имеет предел»;

3) «Если треугольник равнобедренный, то два его угла равны»;

4) «Если каждое слагаемое суммы четно, то сумма четна»;

5) «Если четырехугольник – ромб, то его диагонали взаимно перпендикулярны»;

6) «Если параллелограмм – ромб, то его диагонали взаимно перпендикулярны»;

7) «Точка пересечения диагоналей параллелограмма является его центром симметрии»;

8) «В прямоугольном треугольнике квадрат гипотенузы равен сумме квадратов длин катетов». (4 балла) 3. Какие из предложений, сформулированных в упражнении 2, являются теоремами? (1 балл) 4. Для каждой теоремы из упражнения 2 сформулируйте теорему, равносильную ей согласно закону контрапозиции. (2 балла) 5. Какие из следующих предложений равносильны: Р1 «Если х – сепулька, то х – обитатель Интеропии»;

Р2 «Если х – не сепулька, то х не обитает в Интеропии»;

Р3 «Если х – житель Интеропии, то х - сепулька»;

Р4 «Если х – сепулька, то х не обитает в Интеропии». Ответ обоснуйте. (1 балл) 6. Сформулируйте теорему «Если два треугольника равны, то площади их равны» в виде: а) необходимого условия;

б) достаточного условия. (1 балл) 7. Утверждения «Равенство геометрических фигур есть достаточное условие их равновеликости» и «Четность суммы есть необходимое условие четности каждого слагаемого» сформулируйте в виде условного предложения (в форме импликации). (1 балл) 8. 1) Утверждение «Для того, чтобы диагонали четырехугольника были перпендикулярны, достаточно, чтобы этот четырехугольник был ромбом»

сформулируйте в виде: а) условного предложения;

б) необходимого условия.

2) Утверждение «Для того, чтобы функция была дифференцируемой в точке, необходимо, чтобы она была непрерывной в этой точке» сформулируйте в виде: а) условного предложения;

б) достаточного условия. (2 балла) 9. Установите, в каких случаях из первой формулы следует вторая: 1) x y;

x ;

2) x;

x y ;

3) y;

x y ;

4) x y;

x y ;

5) x y;

x y ;

6) x y;

y x ;

7) х у;

у х ;

8) ( х у ) х;

у ;

9) ( х у ) у;

х. (2 балла) 10. Докажите, что справедливы следующие логические следования, пользуясь определением этого понятия;

выясните, будут ли верны обратные следования, т.е. будет ли формула, стоящая слева, логическим следствием формулы, стоящей справа: 1) x y x y ;

2) x y x y ;

3) x y x y ;

4) у х х у х ( х у ) ;

5) х у х у ;

6) х у х у. (3 балла) 11. Выясните, справедливы ли следующие логические следования (правильны ли соответствующие аргументы): 1) P Q, P Q P ;

2) P Q, Q P P ;

3) P Q, P Q Q ;

4) P Q Q, P, Q P ;

5) P Q, P R P R P Q 6) P R, R Q P Q. (4 балла) Повышенный уровень 12. Докажите, пользуясь законом контрапозиции, следующие теоремы: а) «Если тп – нечетное число, то т и п нечетны»;

б) «Если a 2 + b 2 0, то a 0 или b 0 ». (3 балла) 13. Родители сказали детям: «Если мы поедем в дом отдыха, то вы поедете в лагерь». В школе детей спросили, куда они поедут летом. «Если мы поедем в лагерь, то родители поедут в дом отдыха», – ответил Петя. Галя сказала:

«Если папа с мамой не поедут в дом отдыха, то мы не поедем в лагерь».

«Нет, не так, – вмешался Коля. – Если мы не поедем в лагерь, то родители не поедут в дом отдыха». Чей ответ равносилен тому, что сказали родители?

Кто из детей сказал своими словами одно и то же? (3 балла) 14. Расположите следующие формулы в таком порядке, чтобы из каждой формулы следовали все, стоящие после нее: а) х х, х у, х х, х у, х у ;

б) х у, х ( х у ), х ( у х), х у, х у. (4 балла) 15. Сокращенным способом выясните, выполняются ли следующие логические следования: 1) P Q, R S, P R Q S ;

2) P Q ( R S ), P Q R S ;

3) F G, K L, S H, F K, H L S G. (10 баллов) Дополнительно: [4] Базовый уровень: 1.40 (а, ж), 3.1 (а, б), 3.2 (а, б), 3.5 (б, в), 3.17 (б, в, г, д), 3.20.

Повышенный уровень:3.5 (б, в), 3.19, 3.33, 3.34, 3.37, 3.38, 3.39, 3.40, 3.41, 3.42, 3.43.

Тема 5. Применение алгебры высказываний Цели занятия После изучения темы студент должен:

Знать: способы нахождения следствий из данных посылок;

методы решения текстовых логических задач.

Иметь представление: о том, как находить посылки для данных следствий;

как классифицируются текстовые логические задачи.

Уметь: находить все следствия из данных посылок;

следствия, содержащие только некоторые переменные из числа входящих в посылки;

Задачи Базовый уровень 1. Найдите все следствия из посылок: 1) х у и у ;

2) х у и x y z ;

3) х у и y z ;

4) x y z и z. (5 баллов) 2. Найдите все следствия из посылок: «Если данное число делится на 2 и на 5, то оно делится на 10»;

«Данное число делится на 2 и не делится на 5».

Выразите полученные следствия в содержательной форме. (3 балла) 3. Найдите следствие из посылок x y z, x y и y x z, содержащее только переменные: 1) х и z, 2) y и z. (1 балл) 4. Найдите все следствия из посылок 1) «Если последняя цифра целого числа п обозначает четное число, то это целое число делится на 2 или на 4»;

2) «Если целое число п делится на 4, то оно делится на 2». Выразите полученные следствия в содержательной форме. (3 балла) 5. Проехав половину всего пути, пассажир заснул. Когда он проснулся, то оказалось, что ему осталось ехать половину того пути, который он проехал спящим. Какую часть пути он проехал спящим? (1 балл) 6. Три друга – Иван, Дмитрий и Степан – преподают различные предметы (химию, физику, и биологию) в школах Москвы, Львова и Киева. Известно, что: 1) Иван работает не в Москве, а Дмитрий не в Львове;

2) москвич преподает не физику;

3) тот, кто работает в Львове, преподает химию;

4) Дмитрий преподает не биологию. Какой предмет и в каком городе преподает каждый из товарищей? (2 балла) 7. Написав контрольную работу, сестры сообщили родителям: Света: на этот раз я написала на 5;

Люда: я написала не на 3;

Ира: я написала не на 5.

Сестры получили разные положительные оценки, причем из трех высказываний одно верное, два ошибочных. Какие оценки получили девочки? (2 балла) 8. Кто-то принес в класс цветы. Были высказаны следующие предположения:

это Андрей и Борис, Андрей и Даша, Андрей и Сергей, Борис и Даша, Борис и Володя, Володя и Галя, Галя и Даша. Учитель сказал, что в одном из этих предположений одно имя названо правильно, а второе неправильно, во всех же остальных предположениях оба имени названы неверно. Кто принес цветы? (1 балл) 9. Имеются кубики из картона и из дерева, большие и маленькие, зеленые и красные. Известно, что: зеленых кубиков 16;

зеленых больших 6;

больших зеленых из картона 4;

красных из картона 8;

красных из дерева 9;

больших деревянных 7;

маленьких деревянных 11. Сколько всего кубиков? (2 балла) 10. В семье четверо детей. Им 5, 8, 13 и 15 лет. Детей зовут Аня, Боря, Вера и Галя. Сколько лет каждому ребенку, если одна девочка ходит в детский сад, Аня старше Бори и сумма лет Ани и Веры делится на три? (2 балла) 11. Боги Правды, Лжи и Дипломатии (старинная индийская задача) (1 балл):

В старинном храме, говорят, Но всякий раз «ей-ей».

Стоят на чердаке Пришел в тот храм мудрец Рашид Бог Правды, Лжец и Дипломат, И к первому:

- Привет!

Все – с лотосом в руке. С тобою рядом кто стоит?

Бог Правды, лотосом клянясь, – Бог Правды! – был ответ.

Лишь истину твердит. Теперь скажи мне о себе, – Бог Лжи, нимало не смутясь, Второго он спросил Неправду говорит. Я – Дипломат, служу судьбе, А Дипломат дает ответ Второй проговорил.

По прихоти своей – Шагает к третьему Рашид То правду говорит, то – нет, (Рашид был стар и сед).

Мой бог, сомненья разреши, Ответил третий бог.

Скажи, кто твой сосед? Теперь, читатель, разбери – О, досточтимейший мудрец, Узнать я был бы рад:

Не бей напрасно ног. Кто Лжец, кто правду говорит Могу сказать: он страшный И кто же Дипломат?

лжец, – 12. Решите задачу (2 балла):

В универмаге встретил я Они купили в этот раз Осла, козу и кошку, Лишь желтую матрешку.

Они купили красный мяч Мне срочно нужен твой совет, И желтую гармошку. Задумайся немножко.

Зайдя потом, увидел я Скажи: какой любимый цвет Осла, козу и белку, У белки и у кошки.

Они купили красный плащ И кто не сделал ни одной И белую тарелку. Покупки в магазинах, Зашел я в третий, встретил там Поскольку не было, увы, Опять осла и кошку. Товаров ярко-синих?

Повышенный уровень 13. Найдите все следствия из посылок: 1) х у z, z и у ;

2) х у, y z и x y z ;

3) х у z, x z и y z ;

4) x y z, y x и z y x. (6 баллов) 14. Даны посылки: «Если данный четырехугольник – ромб, то его диагонали перпендикулярны»;

«Если данный четырехугольник – квадрат, то его диагонали равны»;

«Если диагонали данного четырехугольника не равны, то он не квадрат»;

«Диагонали данного четырехугольника не перпендикулярны и равны». Найдите следствие, состоящее из высказываний: а) «Данный четырехугольник – ромб» и «Данный четырехугольник – квадрат»;

б) «Данный четырехугольник - ромб» и «Диагонали данного четырехугольника равны». (5 баллов) 15. Найдите следствие из посылок x y, x z и y t, содержащее только переменные: 1) х и t, 2) y, z и t. (5 баллов) 16. В купе одного из вагонов поезда ехали москвич, ленинградец, туляк, киевлянин, харьковчанин и одессит. Их фамилии начинались буквами А, Б, В, Г, Д, Е. В дороге выяснилось, что: 1) А и москвич – врачи, Д и ленинградец – учителя, В и туляк – инженеры;

2) киевлянин, Б и Е – участники войны, туляк в армии не служил;

3) харьковчанин старше А, одессит старше В, а Е – самый молодой;

4) Б и москвич вышли в Киеве, а В и харьковчанин – в Виннице. (5 баллов) 17. На общей кухне. Жилица Тройкина положила в общую плиту 3 полена своих дров, Пятеркина 5 полен, жилец Бестопливный, у которого не было своих дров, получил от обеих соседок разрешение сварить обед на общем огне. В возмещение расходов он уплатил соседкам 8 рублей. Как должны они поделить эту плату? «Пополам, - поспешит заявить кто-то. – Бестопливный пользовался их огнем поровну». «Ну, нет, - возразит другой. – Надо принять во внимание, что «дровяные вложения» были различными.

Кто дал три полена, должен получить 3 рубля, кто дал 5 полен – получает рублей. Вот это будет справедливый дележ». Окончательное решение головоломки, друзья, за вами. (6 баллов) 18. Кто муж? Кто жена? Однажды на семейном празднике собрались семь супружеских пар. Фамилии мужчин: Владимиров, Федоров, Назаров, Викторов, Степанов, Матвеев и Тарасов. Женщин зовут: Тоня, Люся, Лена, Света, Маша, Оля и Галя. На вечере Владимиров танцевал с Леной и Светой, Назаров – с Машей и Светой, Тарасов – с Леной и Олей, Викторов – с Леной, Степанов – со Светой, Матвеев – с Олей. Затем стали играть в карты. Сперва Викторов и Владимиров играли с Олей и Галей, потом мужчин сменили Степанов и Назаров, а женщины продолжали игру. И, наконец, Степанов и Назаров сыграли одну партию с Тоней и Леной. Попробуйте определить, кто на ком женат, если известно, что на вечере ни один мужчина не танцевал со своей женой и ни одна супружеская пара не садилась одновременно за стол при игре. (4 балла) Дополнительно: [4] Базовый уровень: № 2.28 (д, ж, з), 2.29 (б, в), 2.30, 3.45, 3.47, 3.60.

Повышенный уровень: № 2.29 (г, д, е), 2.31, 2.32 (г, д, е), 2.33, 2.36 (б, в), 2. (б, в), 3.49, 3.50, 3.53, 3.55, 3.56, 3.58, 3.59, 3.61.

Тема 6. Исчисление высказываний Цели занятия После изучения темы студент должен:

Знать: определение переключательной схемы, понятие контакта, виды контактов (однотипные, инверсные), соответствие видов соединения контактов логическим операциям.

Иметь представление: о том, как проанализировать работу переключательной схемы средствами логики высказываний;

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

Уметь: составить формулу алгебры высказываний по заданной переключательной схеме;

анализировать работу переключательной схемы;

упрощать переключательные схемы;

составлять переключательные схемы с заданными свойствами.

Задачи Базовый уровень 1. Проанализируйте работу следующих переключательных схем (3 балла):

1) 2) 3) 4) 2. Упростите схемы из упражнения 1. (3 балла) 3. Постройте переключательные схемы, соответствующие данным формулам, предварительно упростив их: 1) ( x y z x) ( x y ) ;

2) x ( y z x y ).

(3 балла) 4. Проверьте равносильность следующих переключательных схем (3 балла):

1) 2) 5. Составьте схему с тремя независимыми контактами, которая замкнута тогда и только тогда, когда: 1) замкнуты по меньшей мере два контакта;

2) замкнуты не более чем два контакта;

3) разомкнут только один контакт.

(3 балла) 6. Постройте простейшую схему, условия работы которой заданы следующей таблицей (3 балла):

xyzF Повышенный уровень 7. Проанализируйте работу следующих переключательных схем и возможность их упрощения (5 баллов):

1) 2) 8. Постройте наиболее простые переключательные схемы, соответствующие формулам: 1) ( x y ) ( y z x) u z ;

2) ( x y ) t y x ( y z ). (5 баллов) 9. Проверьте равносильность следующих переключательных схем (5 баллов):

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

а) контакт х замкнут и только один из контактов у или z замкнут;

б) контакт t разомкнут и только два из остальных контактов разомкнуты;

в) только два контакта, но не контакты у и t, замкнуты. (5 баллов) Дополнительно: [4] Базовый уровень: № 5.2 (а, б, в), 5.3 (а, г), 5.4 (б, в), 5.5 (а), 5.6 (а, б), 5.7.

Повышенный уровень: № 5.2 (г), 5.3 (в, д), 5.4 (г, е), 5.5 (г), 5.8, 5.10.

Тема 7. Логика предикатов Цели занятия После изучения темы студент должен:

Знать: понятие предиката;

способы задания предикатов;

понятие множества истинности предиката;

понятия логических операций над высказывательными формами и их связь с теорией множеств;

отношения логического следования и логической истинности высказывательных форм;

понятие отношений;

свойства отношений;

классификации элементов множества по данному основанию.

Иметь представление: о том, как задать предикат для данной высказывательной формы;

как с помощью теории множеств описать взаимосвязь между множествами истинности предикатов;

какая классификация называется правильной.

Уметь: находить множество истинности данного предиката;

выяснять равносильность высказывательных форм, образованных с помощью логических операций;

выяснять, следует ли одна высказывательная форма из другой;

определять свойства заданных отношений;

классифицировать множества по 1, 2 и 3 основаниям;

определять, какие отношения являются отношениями эквивалентности и отношениями порядка.

Задачи Базовый уровень 1. Предикаты Р1, Р2 и Р3 заданы высказывательной формой «в слове х буква «а» встречается не более двух раз» на множествах М1, М2 и М соответственно: М1 = {конь;

стол;

зал;

чаша;

баран};

М2 = {мир;

чай;

ваза};

М3 = {карандаш;

карнавал}. Составьте таблицу для каждого из предикатов Р1, Р2 и Р3. Выпишите множества их значений истинности. (1 балл) 2. Найдите декартовы произведения А В и В А следующих множеств: 1) А = {1;

2;

3;

4};

В = {5;

6};

2) А = {a;

b;

c};

B = {b;

c;

d}. (1 балл) 3. Найдите множества истинности следующих предикатов: 1) «х кратно 3»;

Мх = {1;

2;

3;

4;

5;

6;

7;

8;

9};

2) «х кратно 3»;

Мх = {3;

6;

9;

12};

3) «х кратно 3»;

Мх = {2;

5;

7};

4) «у2 + 3у + 2 = 0»;

Му = R;

5) « у 2 + 1 0 »;

Му = R;

6) «siny 2»;

Му = R. (1 балл) 4. Изобразите на координатной прямой множества истинности предикатов, заданных на R следующими высказывательными формами: 1) «x 2»;

2) « х = 1 »;

3) « х 1 »;

4) « х 1 »;

5) « х 2 1 »;

6) « х + 3 1 »;

7) « х 2 + 2 х + 1 = 0 »;

x 8) « х + 6 х + 9 0 »;

9) « х + 6 х 16 0 »;

10) « = x ». (3 балла) 2 x 5. Определите, равносильны ли следующие высказывательные формы, если переменные принимают значения из множества R;

Q;

Z;

N: 1) х 2 = 1 ;

х2 ( х 2 )( х + 0,5)( х 1)( х + 1) = 0 ;

2) = х 2;

sin x 1 ;

3) x 0;

х2 = 0.

х+ (3 балла) 6. Верны ли следующие высказывания: 1) «х – мать у» «у – дочь х»;

2) «х – мать у» «у – дочь или сын х»;

3) «х – брат у» «х и у – родственники»;

4) «х – брат или сестра у» «у – брат или сестра х»;

5) «х – сын у и у – сын z» «z – дед х». (3 балла) 7. Предикат Р задан высказывательной формой «х – простое число» на множестве М = {2;

3;

4;

5;

6;

7;

8;

9};

предикат Q задан отрицанием этой формы. Найдите множества истинности предикатов Р и Q;

выразите множество истинности предиката Q через множество истинности предиката Р и множество М. (1 балл) 8. Изобразите на координатной плоскости множества истинности предикатов, заданных на R следующими высказывательными формами: 1) ( x 2) ( x 3) ;

y x + 1, 2) ( x 3) ( x 2) ;

3) 3 4) ( x 0) ( y 0) ;

5) ( x 2 + y 2 = 1) ( x 0) ;

6) y 2 x 2;

( x + y = 1) ( xy = 0). (4 балла) 2 9. Определите, следует ли одна высказывательная форма из другой, если Мх = R: 1) х 3;

x 2 3x + 2 = 0 ;

2) x 4 = 16 ;

x 2 = 2 ;

3) x2 + x 6 = 0 ;

( x 1)( x 2)( x 3) = 0 ;

4) х 1 0 ;

( x 2)( x 5) = 0 ;

5) sin x = 2 ;

x 2 + 5 = 0 ;

6) x 2 + 5 x 6 0 ;

x + 1 = 1 + x. (4 балла) 10. Установите, какими свойствами обладает каждое из отношений, заданных в таблице (5 баллов):

Название Название Множество М Множество М отношения отношения Натуральных Прямых на 1) Делится на 6) Иметь общую точку чисел плоскости Действительных Отличаться ровно Слов русского 2) 7) чисел одной буквой языка Действительных Многоугольников 3) 8) Равновеликость чисел на плоскости Подмножеств Быть Плоскостей в 4) трехэлементного 9) Перпендикулярность подмножеством пространстве множества Жителей Формул логики 5) Быть дочерью 10) Следование Кургана высказываний 11. Можно ли расклассифицировать: 1) натуральные числа – на четные и нечетные;

2) числовые функции числового аргумента – на четные и нечетные;

3) натуральные числа – на простые и составные;

4) действительные числа – на положительные и отрицательные;

5) треугольники – на прямоугольные, косоугольные и равнобедренные;

6) четырехугольники – на трапеции, параллелограммы, прямоугольники и квадраты? Почему? (3 балла) 12. Пусть U – множество натуральных чисел, не превосходящих 40;

Р1 – свойство быть квадратом натурального числа;

Р2 – свойство быть нечетным числом;

Р3 – свойство быть числом, кратным 3. Расклассифицируйте элементы множества U по основаниям: 1) Р1;

2) Р1 и Р2;

3) Р1, Р2 и Р3.

Опишите каждую из классификаций высказывательной формой.

Охарактеризуйте словами каждое из подмножеств множества U, образовавшихся при классификациях 1), 2) и 3). (5 баллов) 13. Какие отношения из упражнения 10 являются отношениями эквивалентности;

отношениями порядка? (1 балл) Повышенный уровень 14. Задайте множество значений переменных так, чтобы предикаты, заданные следующими высказывательными формами, имели одно и то же множество истинности: 1) «х делится на 2»;

«х делится на 3»;

2) х 2 + 5 х + 6 = 0;

х = 2 ;

3) у = х;

у = х ;

4) у = х ;

у = х ;

5) «х – ромб»;

«диагонали х взаимно перпендикулярны». (4 балла) 15. Задайте множество значений переменных так, чтобы данные высказывательные формы были равносильны на этом множестве: 1) «х кратно 3»;

«х кратно 5»;

2) «у – четное число»;

«у – простое число»;

3) х 3 1 = 0 ;

х 2 + 2 х 3 = 0 ;

4) «z – ромб»;

«диагонали в z взаимно перпендикулярны». (4 балла) 16. Найдите множество значений р, при которых данные формы равносильны на М: 1) х 2 + рх + 1 = 0 ;

х = 1;

М = Q;

2) х p ;

x 2 9 0 ;

М = Q;

3) x 1 ;

lg x p ;

М = (0;

+) ;

4) x 2 + 2 x + 1 = ( x + 1) 2 ;

х p ;

М = R;

5) х 0 ;

х 2 + рх + 4 = 0 ;

М = R.

(4 балла) 17. Изобразите на координатной плоскости множества истинности следующих предикатов (Мх = Му = R): 1) х у = 0 ;

2) x y 0 ;

3) x y 0 ;

4) y 2 x 4, х + у 4, x2 y2 = x+ y;

5) 6) 7) ( x 5) ( x 1) ;

8) y x + 2, x y х + у 2 1;

y 2 х + 3;

( x 2 + y 2 1) ( xy 0). (5 баллов) 18. Задайте множество М значений переменной так, чтобы на этом множестве вторая форма следовала из первой: 1) «х кратно 3»;

«х четно»;

2) х2 = 1;

х – = 0;

3) «х нечетно»;

«х – квадрат натурального числа»;

4) «х – трехсложное слово»;

«в слове х буква «а» встречается не более двух раз»;

5) «х – русский ученый»;

«х – математик». (4 балла) 19. Установите, какими свойствами обладает каждое из отношений, заданных на R следующими высказывательными формами: а) х + у = 2;

б) х – у = 2;

в) |х – у| = 2;

г) ху 0 ;

д) |х| = |у|. Какие из них являются отношениями эквивалентности или отношениями порядка? (5 баллов) 20. Среди 150 школьников марки собирают только мальчики;

67 человек собирают марки СССР, 48 – марки Африки, 34 – марки Америки, 11 – только марки СССР, 7 – только Африки и 2 – только Америки. Один только Петя Галкин собирает марки СССР, Америки и Африки. Какое максимальное число девочек может быть среди 150 школьников? (5 баллов) 21. Выпишите классы эквивалентности, образующиеся при разбиении множества {-4;

-3;

-2;

-1;

0;

1;

2;

3;

4}, порожденного отношением |х| = |у|. ( балла) Дополнительно: [4] Базовый уровень: № 7.1, 7.2, 7.6 (а, в, д, ж, и), 7.7 (а, в, д, ж, и), 7.9.

Повышенный уровень: 7.8 (а, в, д, ж, и), 7.10 (б, г, е), 7.11 (б, г, е), 7.12 (б, г, е, з), 7.21 (а, б, г, д).

Тема 8. Применение логики предикатов. Исчисление предикатов Цели занятия После изучения темы студент должен:

Знать: понятие и виды кванторов (общности и существования);

краткую запись предложения, формализованного с помощью квантора;

какие переменные называются связанными, а какие свободными;

какая операция называется квантификацией, ее свойства;

правило построения отрицания предложений с кванторами;

понятие численного квантора.

Иметь представление: о том, как можно записать предложение с квантором;

как правильно строить отрицание предложение с кванторами;

о двойственности кванторов;

как заменить предложение с численными кванторами на равнозначное предложение, не содержащее числительных и состоящее только из логических терминов и знака «=», обозначающего тождество (совпадение) объектов.

Уметь: читать предложения, содержащие кванторы;

символически записывать предложения, содержащие кванторы;

определять значения истинности предложений, в которых кванторами связана одна или две переменных;

формулировать отрицания предложений с кванторами;

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

Задачи Базовый уровень 1. Запишите следующие предложения на обычном языке, заменив символические обозначения кванторов общности и существования их словесными выражениями. Определите значения истинности данных высказываний. (Мх = Му = R): 1) х( х 2 1 = ( х 1)( х + 1)) ;

2) х( х 0) ;

3) х( х 0) ;

4) у (5 + у = 5) ;

5) у ( у 2 + у + 1 = 0) ;

6) у ( у 2 + у + 1 0) ;

7) х( х 3 x 2 ) (3 балла) 2. Запишите следующие предложения, используя символы кванторов: 1) «Существует число х такое, что х + 10 = 2 »;

2) «По крайней мере одно число у является корнем уравнения ау 2 + by + c = 0 »;

3) «Каково бы ни было число z, z + 0 = z »;

4) «Уравнение f ( x) = 0 имеет хотя бы один корень»;

5) «Любое число либо положительно, либо отрицательно, либо равно нулю». (1 балл) 3. Запишите символически следующие высказывания и определите их значения истинности: 1) «Всякое число, умноженное на нуль, есть нуль»;

2) «Произведение любого числа и единицы равно этому числу»;

3) «Существует число, которое больше своего квадрата»;

4) «Квадрат любого числа неотрицателен»;

5) «Модуль любого числа положителен». (2 балла) 4. Свяжите переменную квантором так, чтобы получилось истинное высказывание (если возможно, сделайте это двумя способами): 1) «4х + 5 – простое число»;

2) cos y 0 ;

3) «В четырехугольнике z все углы – прямые»;

4) «Простое число р – натуральное»;

5) «Простое число р – четное»;

6) x sin 2 x + cos 2 x = 1 ;

7) x = x ;

8) lg x 2 = 2 lg x ;

9) = 1 ;

10) «Все пути из пункта у x ведут на север». (3 балла) 5. Запишите символически следующие предложения, включив указание о множестве значений переменной в запись квантора: 1) «Уравнение f ( x) = ( x) имеет положительный корень»;

2) «Существует рациональное число, квадрат которого равен а»;

3) «Всякое натуральное число либо четно, либо нечетно»;

4) «Всякое рациональное число представимо в виде дроби p, где р – целое число, а q – натуральное»;

5) «Некоторые натуральные q числа кратны 7». (3 балла) 6. Следующие предложения запишите в виде конъюнкций либо дизъюнкций:

1) «Каждое слагаемое суммы a + b + c четно»;

2) «Существует натуральный корень уравнения 2х = р, не превосходящий 4»;

3) «Среди чисел, больших 1758 и меньших 1963, найдется простое»;

4) «Множеству М принадлежат все буквы слова «цирк». (3 балла) 7. Определите, при каких значениях свободных переменных следующие высказывательные формы становятся истинными высказываниями (Мх = Му = Мz = R): 1) х( ху = х) ;

2) у ( х + у = у ) ;

3) х( ху = 0) ;

4) х( ху = 1) ;

5) ху ( ху = z ). (2 балла) 8. Сформулируйте следующие высказывания с помощью квантора существования или общности: 1) «Не всякое уравнение имеет действительный корень»;

2) «Не для любого х lg x 1 »;

3) «Не все умеют играть в шахматы»;

4) «Не каждое простое число нечетно»;

5) «Не всякая река впадает в море»;

6) «Не существует числа х такого, что х + 1 = х»;

7) «Нет человека, не имеющего матери»;

8) «Не найдется числа, удовлетворяющего уравнению х 2 + 1 = 0 » 9) «Ни один человек не бессмертен». (5 баллов) 9. Запишите следующие предложения в форме, не содержащей числительных:

1) «Уравнение ax = b имеет хотя бы один корень»»;

2) «Уравнение ax = b имеет не более чем один корень»;

3) «Уравнение ax = b имеет один и только один корень»;

4) «Множество М содержит по меньшей мере один элемент»;

5) «Множество М содержит не более одного элемента»;

6) «Множество М содержит ровно один элемент»;

7) «Уравнение f ( x) = 0 имеет не более двух корней»;

8) «Уравнение f ( x) = 0 имеет по меньшей мере два корня»;

9) «Уравнение f ( x) = 0 имеет два и только два корня»;

10) «Множество М содержит два элемента»;

11) «Множество М содержит ровно три элемента».

(3 балла) 10. Заполните пропуски численными кванторами так, чтобы получились истинные высказывания: 1) «Каждой прямой принадлежат … две различные точки»;

2) «Каждая плоскость содержит … три точки, не лежащие на одной прямой»;

3) «Через каждые три точки, не принадлежащие одной прямой, проходит … плоскость»;

4) «Две плоскости, имеющие общую точку, имеют … общую прямую, проходящую через эту точку»;

5) «Две различные прямые пересекаются в … точке»;

6) «Через две данные пересекающиеся прямые проходит … плоскость»;

7) «Простое число имеет … различных делителя». (2 балла) 11. Запишите символически: 1) определение «Последовательность (ап) называется ограниченной, если существует такое число М, что модуль любого члена последовательности не превосходит этого числа»;

2) необходимое и достаточное условие истинности утверждения «Последовательность (ап) не является ограниченной»;

3) определение «Точка х0 из области определения функции f называется точкой максимума этой функции, если существует такая -окрестность этой точки, что для всех х из этой окрестности f ( x) f ( x0 ) »;

4) необходимое и достаточное условие того, что точка х0 из области определения функции f не является точкой максимума этой функции. (5 баллов) Повышенный уровень 12. Запишите следующие высказывания на обычном языке и определите их значения истинности (переменные принимают значения из R): 1) х ху (( х + у ) 2 = х 2 + 2 ху + у 2 ) ;

2) ху = 1 ;

3) ух( ху = 0) ;

4) хр (2 х 1 = рх) ;

у 5) (Т 0)(х 0)( х = ( х + Т ) ) ;

6) (х 0)(Т 0)( х 2 = ( х + Т ) 2 ) ;

6) 2 хр (2 х 1 = рх). (4 балла) 13. Запишите символически следующие высказывания и определите их х2 у значения истинности: 1) «Для любых чисел х и у = х + у »;

2) «Для х у любых чисел а и b ab = ba»;

3) «Для любых чисел х и у х 2 у 2 = ( х у )( х + у ) »;

4) «Для любых чисел а и b a – b = b – a»;

5) «Для всякого числа а существует такое число b, что a – b = b – a»;

6) «Существуют такие числа а и b, что a – b = b – a»;

7) «Для любых чисел х и у существует такое число z, что х + у = z»;

8) «Существует такое число z, что для любых чисел х и у х + у = z»;

9) «Существуют такие числа х и z, что для всякого у ху = z»;

10) «Не существует наибольшего натурального числа». (4 балла) 14. Определите, какие из следующих высказываний истинны (все переменные принимают значения из R): 1) abc((x(ax 2 + bx + c = 0)) b 2 4ac 0) ;

2) а((х(ах = 2)) а 0) ;

3) x(( x 2 x 1) x x) ;

4) х( x 2 x ( x 1 x 0)) ;

5) x(( x 2 x 3) 2 x 3) ;

6) ab((x( x a x b)) a b) ;

7) x(( x 1 x 2) x = x). (4 балла) 15. Сформулируйте отрицания следующих высказываний в утвердительной форме (то есть так, чтобы отрицание данного высказывания не начиналось со слов «неверно, что» или «не»): 1) «Из всякого положения есть выход»;

2) «Во всяком городе есть район, во всех домах которого не менее шести этажей»;

3) «В каждой стране найдется город, у всех жителей которого один и тот же цвет глаз»;

4) «В каждом городе есть район, в каждой школе которого есть класс, в котором ни один человек не занимается спортом»;

5) «Существует книга, в которой есть страница, в каждой строке которой найдется хотя бы одна буква «а». (7 баллов) 16. Сформулируйте отрицания следующих высказываний в утвердительной форме: 1) «По меньшей мере один объект обладает свойством Р»;

2) «Не более чем один объект обладает свойством Р»;

3) «Один и только один объект обладает свойством Р»;

4) «По меньшей мере два объекта обладают свойством Р»;

5) «Не более чем два объекта обладают свойством Р»;

6) «Два и только два объекта обладают свойством Р». Запишите эти отрицания символически, используя только логические символы и знак равенства. ( баллов) Дополнительно: [4] Базовый уровень: 7.3 (б, в, г, д, е, ж, з, к, л), 7.4 (а, б, в, г, д, з), 7.19, 7.20, 7.26, 7.28, 7.30, 7.32.

Повышенный уровень: 7.27, 7.33, 7.34, 7.35.

ТЕМЫ РЕФЕРАТОВ 1. Аристотель и его вклад в создание логики.

2. Законы и формы мышления.

3. Этапы развития логики.

4. Создатели математической логики – Г.Лейбниц, Д. Буль, О. де Морган.

5. Связь логики и теории множеств.

6. Логические основы ЭВМ.

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

8. Логика и язык.

9. Логика категорических высказываний.

10. Доказательство и опровержение.

11. Индуктивные рассуждения.

12. Логические парадоксы.

13. Л. Кэрролл и его вклад в развитие логики.

Объем реферата 3-5 страниц печатного текста формата А4 (не включая титульный лист и список использованных источников). Шрифт Times New Roman, 14 кегль. Одинарный интервал.

ТЕМЫ КУРСОВЫХ РАБОТ 1. Метод резолюций и его применение в алгебре высказываний и алгебре предикатов.

2. Аксиоматические системы.

3. Минимальные и кратчайшие КНФ и ДНФ.

4. Применение методов математической логики в теории формальных языков.

5. Формальные грамматики как логические исчисления.

6. Методы решения текстовых логических задач (не менее 10 задач на каждый метод).

7. Системы логического программирования.

Курсовая работа должна состоять из 2 частей: теоретического содержания темы и набора задач по теме (не менее 20) с решениями.

Список литературы 1. Барвайс Дж. (ред.) Справочная книга по математической логике. – М.:

Наука, 1982.

2. Братчиков И.Л. Синтаксис языков программирования. – М.: Наука, 1975.

3. Гиндикин С.Г. Алгебра логики в задачах. – М., 1972.

4. Игошин В.И. Задачник-практикум по математической логике. – М.:

Просвещение, 1986.

5. Игошин В.И. Математическая логика и теория алгоритмов. – Саратов: Изд во Сарат. ун-та, 1991.

6. Ин Ц., Соломон Д. Использование Турбо-Пролога. – М.: Мир, 1993.

7. Клини С. Введение в метаматематику. – М., 1957.

8. Клини С. Математическая логика. – М.: Мир, 1973.

9. Ковальски Р. Логика в решении проблем. – М.: Наука, 1990.

10. Кэрролл Л. История с узелками/ Пер. с англ. – М., 1973.

11. Кэрролл Л. Логическая игра/ Пер. с англ. – М., 1991.

12. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М., 1975.

13. Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций.

Задачник-практикум и решения: Учебное пособие. 3-е изд., испр. – СПб:

Издательство «Лань», 2008. – 288 с.

14. Лыскова В.Ю. Логика в информатике/ В.Ю. Лыскова, Е.А. Ракитина. - М.:

Лаборатория Базовых Знаний, 2004. – 160 с.

15. Математическая логика / Под общей редакцией А.А. Столяра и др. – Минск:

Высшая школа, 1991.

16. Мендельсон Э. Введение в математическую логику. – М.: Наука, 1984.

17. Мощенский В.А. Лекции по математической логике. – Минск, 1973.

18. Никольская И.Л. Знакомство с математической логикой. – М.: Московский психолого-социальный институт: Флинта, 1998. – 128 с.

19. Никольская И.Л. Математическая логика. – М., 1981.

20. Новиков П.С. Элементы математической логики. – М.: Наука, 1973.

21. Тей А., Грибомон П. и др. Логический подход к искусственному интеллекту.

Т. 1. – М.: Мир, 1990.

22. Тей А., Грибомон П. и др. Логический подход к искусственному интеллекту.

Т. 2. – М.: Мир, 1998.

23. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. – М.: Наука, 1983.

24. Черч А. Введение в математическую логику. – М.: Мир, 1960.

ВОПРОСЫ ДЛЯ ЗАЧЕТА (ЭКЗАМЕНА) 1. Высказывания и высказывательные формы. Значение истинности высказывания. Логические связки и логические операции.

2. Формулы алгебры высказываний. Формализация высказываний.

Составление таблиц истинности для формул.

3. Классификация формул алгебры высказываний. Основные тавтологии и их значение.

4. Равносильность формул алгебры высказываний. Свойства равносильности. Равносильные преобразования, упрощение формул.

5. Обратные и противоположные предложения. Необходимые и достаточные условия. Структура определений.

6. Отношение следования между формулами алгебры высказываний.

Свойства. Правильные и неправильные аргументы. Сокращенный способ проверки аргументов.

7. Нормальные формы. Совершенная конъюнктивная нормальная форма.

Применение.

8. Нормальные формы. Совершенная дизъюнктивная нормальная форма.

Применение.

9. Переключательные схемы. Описание переключательных схем с помощью формул алгебры высказывания. Анализ, упрощение и синтез переключательных схем.

10. Предикаты и способы их задания. Множество истинности предиката.

11. Равносильность высказывательных форм. Логические операции над предикатами. Следование и включение.

12. Свойства и отношения. Классификация. Бинарные отношения и их свойства.

13. Кванторы общности и существования. Квантификация многоместных высказывательных форм.

14. Отрицание предложений с кванторами. Численные кванторы.

Символическая запись определений и теорем.

СПРАВОЧНЫЕ МАТЕРИАЛЫ Тема 1. Высказывания и операции над ними. Формулы алгебры высказываний. Классификация формул.

Опорный конспект «Высказывания и операции над ними».

Алгебра высказываний исследует высказывание (A, B, C, D… или A1, A2, A3…) (предложение, которое либо истинно, либо ложно) 1 (Р) – значение истинности высказывания Р 1) пропозициональные переменные: Х, Y, Р, Q, R… Алфавит языка 2) символы логических операций:,,,, ;

логики 3) технические знаки: (, ), [, ].

высказываний Таблицы истинности – указывают логическое значение формулы при любой ее интерпретации Таблица истинности операции отрицания высказывания А1: «Волга впадает в Каспийское море»

(Р) ( Р ) 0 А1 : «Неверно, что Волга впадает в Каспийское море»

1 Таблица истинности операции конъюнкции двух высказываний (Р) (Q) ( P Q ) А2: «Саратов находится на берегу Невы»

0 0 0 А3: «Все люди смертны»

0 1 A2 A3 :«Саратов находится на берегу Невы, и все 1 0 люди смертны»

1 1 Таблица истинности операции дизъюнкции двух высказываний (Р) (Q) ( P Q ) А3: «Все люди смертны»

0 0 0 А4: «7 4»

0 1 A3 A4 : «Все люди смертны или 7 4»

1 0 1 1 Таблица истинности операции импликации двух высказываний (Р) (Q) (РQ) 0 А1: «Волга впадает в Каспийское море»

0 0 А4: «7 4»

0 1 А1 А4: «Если Волга впадает в Каспийское море, то 1 0 7 4»

1 1 Таблица истинности операции эквивалентности двух высказываний (Р) (Q) (РQ) А4: «7 4»

0 0 А2: «Саратов находится на берегу Невы»

0 1 А4 А2: «7 4 тогда и только тогда, когда Саратов 1 0 1 1 находится на берегу Невы»

Алгоритм построения таблицы истинности 1. Вычислить количество строк и столбцов в таблице истинности.

Пусть в формуле п различных переменных и k операций. Переменные считаем каждую только один раз, а символы операций – все, сколько есть.

Тогда число строк в таблице равно 2п + 1 (число наборов значений переменных плюс строка заголовка), а число столбцов в таблице равно n + k.

2. Начертить таблицу.

3. Заполнить строку заголовка.

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

4. Заполнить оставшиеся строки таблицы, начиная с первого столбца.

При вычислении значений промежуточных формул, надо помнить, что в каждой операции участвует не более двух формул (может быть и не элементарных).

Тема 2. Логическая равносильность формул ОСНОВНЫЕ РАВНОСИЛЬНОСТИ ЛОГИКИ ВЫСКАЗЫВАНИЙ 1. M – закон тождества.

M 2. M 1 – закон исключенного третьего M 3. M 0 – закон противоречия M 4. 0 M M 5. M 6. 1 M 7. 1 M M 8. M – закон двойного отрицания M 9. M N N M – коммутативность конъюнкции 10. M N N M – коммутативность дизъюнкции 11. ( M N ) G M ( N G ) – ассоциативность конъюнкции 12. ( M N ) G M ( N G ) – ассоциативность дизъюнкции 13. M ( N G ) ( M N ) ( M G ) – дистрибутивность конъюнкции 14. M ( N G ) ( M N ) ( M G ) – дистрибутивность дизъюнкции 15. M M M ;

M M M – законы идемпотентности 16. M ( N M ) M ;

M ( N M ) M – законы поглощения 17. M N M N ;

M N M N – законы де Моргана 18. M N M N – закон, выражающий импликацию через дизъюнкцию 19. M N N M – закон контрапозиции 20. M N ( M N ) ( N M ) ( M N ) ( N M ) ( M N ) ( M N ) – законы, выражающие эквиваленцию через другие логические операции Вспомогательные равносильности, применяемые при упрощении формул:

1. M ( M N ) M N 2. M ( M N ) M N 3. M ( M N ) M N 4. M ( M N ) M N 5. M N M N Тема 3. Нормальные формы для формул алгебры высказываний Правило отыскания совершенной дизъюнктивной (конъюнктивной) нормальной формы для данной формулы с помощью таблицы истинности:

1. Составить таблицу истинности для данной формулы.

2. Выбрать все те наборы значений ее переменных, на которых формула принимает значение 1 (0).

3. Для каждого такого набора выписать совершенный конъюнктивный (дизъюнктивный) одночлен, принимающий значение 1 (0) на этом наборе значений и только на нем.

4. Полученные совершенные конъюнктивные (дизъюнктивные) одночлены соединить знаками дизъюнкции (конъюнкции).

Характерные признаки СДНФ (СКНФ):

1) различны все члены дизъюнкции (конъюнкции);

2) различны все члены каждой конъюнкции (дизъюнкции);

3) ни одна конъюнкция (дизъюнкция) не содержит одновременно переменную и ее отрицание;

4) каждая конъюнкция (дизъюнкция) содержит все переменные, входящие в формулу F.

Общее правило приведения формулы к СДНФ (СКНФ):

Для того чтобы привести формулу F, не являющуюся тождественно ложной (тождественно истинной), к СДНФ (СКНФ), достаточно:

1) привести ее к какой-нибудь ДНФ (КНФ);

2) удалить члены дизъюнкции (конъюнкции), содержащие переменную вместе с ее отрицанием (если таковые имеются);

3) из одинаковых членов дизъюнкции (конъюнкции) (если такие имеются) удалить все, кроме одного;

4) из одинаковых членов каждой конъюнкции (дизъюнкции) удалить все, кроме одного;

5) если в какой-нибудь конъюнкции (дизъюнкции) не содержится переменной хi из числа переменных, входящих в искомую формулу, добавить к этой конъюнкции (дизъюнкции) член xi xi ( хi xi ) и применить соответствующий дистрибутивный закон;

6) если в полученной дизъюнкции (конъюнкции) окажутся одинаковые члены, то воспользоваться предписанием № 3.

Полученная формула и является СДНФ (СКНФ) данной формулы.

Опорный конспект Понятие нормальных форм Дизъюнктивной нормальной Конъюнктивной формой называется дизъюнкция нормальной формой конъюнктивных одночленов называется конъюнкция дизъюнктивных одночленов Совершенные нормальные формы Дизъюнктивный одночлен Конъюнктивный одночлен называется совершенным, если в называется совершенным, него от каждой пары Х i, X i входит если в него от каждой пары Х i, X i входит только один только один представитель ( Х i или представитель ( Х i или X i ).

X i ).

Теорема о представлении формул алгебры высказываний Теорема: Каждая не тождественно Теорема: Каждая формула алгебры ложная формула алгебры высказываний от n переменных, не высказываний от n аргументов имеет являющаяся тавтологией имеет единственную (с точностью до единственную (с точностью до перестановки дизъюнктивных перестановки конъюнктивных одночленов) совершенную одночленов) совершенную дизъюнктивную нормальную форму. конъюнктивную нормальную форм.

Тема 4. Понятие логического следствия. Виды теорем Опорный конспект Формула H называется логическим следствием формул F1, …, Fm, если формула H превращается в истинное высказывание при всякой такой подстановке вместо всех ее пропозициональных переменных X1, …, Xn конкретных высказываний, при которой в истинное высказывание превращаются все формулы F1, …, Fm.

Признаки Теорема: Формула H будет Теорема: Для любых формул логическим следствием F1, F2, … Fm, H (m2) формулы F тогда и только следующие утверждения тогда, когда формула FH равносильны:

а) F1, F2, … Fm H;

является тавтологией.

б) F1 /\ F2 /\ … /\ Fm H;

в) (F1 /\ F2 /\ … /\ Fm)H – тавтология.

Свойства Отношение логического следования между формулами алгебры высказываний обладает следующими свойствами:

F1, F2, … Fm Fm, Если F1, F2, … Fm Gj, для для i = 1, 2, … m j = 1, 2, … p и G1, G2, … Gp H, то F1, F2, … Fm H Способ проверки логического следования методом от противного.

Требуется выяснить, является ли формула H логическим следствием формул F1, … Fm, т.е. F1, F2,..., Fm H. Предположим, что H не есть логическое следствие формул F1, F2, … Fm. Значит, существуют такие конкретные высказывания A1, … An, что высказывание H(A1, … An) ложно, в то время как все высказывания F1(A1, … An), … Fm(A1, … An) истинны. Если при этом удается найти распределение нулей и единиц между значениями переменных X1, … Xn, соответствующее сделанному предположению, то предположение верно. Если же возникает противоречие, то предположение неверно.

Тема 5. Применение алгебры высказываний Правило получения всех неравносильных посылок из данных следствий:

1. Составить конъюнкцию формализованных посылок;

2. Привести конъюнкцию формализованных посылок к СКНФ;

3. Выписать все члены этой СКНФ, а также всевозможные дизъюнкции этих членов.

Полученное множество формул и является искомым.

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

1. Составить объединенную таблицу истинности для формул, соответствующих посылкам;

2. Выделить строки, в которых все посылки истинны;

3. В выделенных строках подчеркнуть значения переменных, которые должны войти в искомую формулу;

4. Если какие-нибудь наборы этих значений повторяются, вычеркнуть лишние;

5. По оставшимся наборам составить СДНФ формулы, которая и является искомой.

Тема 7. Логика предикатов Правила классификации:

При правильной классификации:

1) пересечение любых двух классов пусто;

2) объединение всех классов равно множеству, элементы которого классифицируются.

Свойства бинарных отношений 1. Рефлексивность ( (х М )( xRx) ) 2. Симметричность ( (x M )(y M )( xRy yRx) ) 3. Транзитивность ( (x M )(y M )(z M )( xRy yRz xRz ) ) 4. Антирефлексивность ( (х М )( xRx) ) 5. Антисимметричность ( (x M )(y M )( xRy х у yRx) ) 6. Связанность ( (x M )(y M )( x y xRy yRx) ) Тема 8. Применение логики предикатов. Исчисление предикатов Правило построения отрицания предложения с кванторами Чтобы построить отрицание предложения, начинающегося с кванторов, достаточно каждый квантор заменить двойственным, а отрицание перенести на предложение, стоящее за кванторами.

Чернышова Анастасия Валерьевна МАТЕМАТИЧЕСКАЯ ЛОГИКА Методические указания для практических занятий для студентов первого и второго курсов специальностей «Математика» и «Информатика с дополнительной специальностью Математика» (010101, 050202) Редактор: Н.М. Устюгова Подписано к печати Формат 60 84 1/16 Бумага типа № Печать трафаретная Усл. печ. л. 2,5 Уч.- изд. л.2, Заказ Тираж 80 экз. Цена свободная РИЦ Курганского государственного университета.

640669, г. Курган, ул. Гоголя, 25.

Курганский государственный университет.



 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.