Основные определения и понятия

Министерство образования и науки РФ

НИ Иркутский государственный технический университет

МАТЕМАТИЧЕСКая ЛОГИКа

Методические указания к практическим занятиям

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

Иркутск 2010

«Методические указания к практическим занятиям «Математическая логика» предназначено для студентов специальностей АСУ, ИСТ

факультета Кибернетики. Составитель Л.Л. Носырева.

Иркутск, 2010, 56 - с.

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

Библ. 11 назв.

Рецензент: Белых Татьяна Ивановна, доцент кафедры информатики и кибернетики БГУЭП

Занятие №1

Тема: Алгебра высказываний.

Основные определения и понятия.

I.Ответьте на следующие вопросы:

1. Что называется высказыванием? Приведите примеры.

2. Какие операции можно выполнять над высказываниями? Как определяются эти операции?

3. Что называется формулой алгебры высказываний? Приведите примеры.

4. Как определить истинностное значение сложного высказывания?

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

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

7. Дайте определение тавтологии, противоречия, выполнимой формулы.

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

II.Выполните следующие упражнения:

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

а) Иркутск - областной город;

б) Москва – столица СССР;

в) ;

г) ;

д) для всякого числа x: ;

е) ;

ж) ;

з) существует действительное число х такое, что .

2. Пусть A и B есть соответственно высказывания: «Углы α и β – вертикальные» и «Углы α и β равны». Прочитать следующие высказывания:

а) ;

б) ;

в) ;

г) ;

д) ;

е) .

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

а) если число a делится на 2 и не делится на 3, то оно не делится на 6;

б) произведение двух чисел равно нулю тогда и только тогда, когда одно из них равно нулю;

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

г) число a является корнем системы m уравнения с одним неизвестным тогда и только тогда, когда оно является корнем каждого из системы уравнений;

д) если мистер Джонс счастлив, то миссис Джонс несчастлива, и если мистер Джонс несчастлив, то миссис Джонс счастлива;

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

4. Из двух данных высказываний A и B построить составное высказывание с помощью операций отрицания и конъюнкции, которое было бы:

а) истинным тогда и только тогда, когда оба высказывания A и B ложны;

б) ложно тогда и только тогда, когда оба высказывания A и B истинны;

в) ложно тогда и только тогда, когда A-истинно, а B – ложно.

5. Известно, что высказывание истинно. Можно ли утверждать, что и высказывание истинно?

6. Построить таблицы истинности для формул:

а) ;

б) ;

в)

г) ;

д) ;

е) ;

ж) ;

з) ;

и) .

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

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) .

8. Доказать, что следующие формулы - тавтологии:

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) ;

з) ;

и) .

9. При каких значениях A, B, C, D следующие формулы ложны:

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) ;

з) ;

и) ;

к) .

10. Известно, что, , , – тавтология, докажите, что тогда:

а) - тавтология;

б) - тавтология;

в) - тавтология;

г) - тавтология;

д) - противоречие;

е) - противоречие;

ж) - тавтология;

з) - тавтология.

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

а) и ;

б) и ;

в) и ;

г) и ;

д) и ;

е) и ;

ж) и ;

з) и ;

и) и ;

к) и .

12. Докажите справедливость следующих равносильностей:

а) тождества: ;

б) идемпотентности: и ;

в) коммутативности: и ;

г) ассоциативности: и ;

д) дистрибутивности:

и ;

е) двойного отрицания: ;

ж) де Моргана: и ;

з) , и , ;

и) противоречия: ;

к) исключенного третьего: ;

л) замены эквиваленции: ;

м) поглощение: и ;

н) склеивания: и ;

о) контропозиции: ;

п) силлогизма: ;

р) прямого вывода (заключения): .