Упражнения

Глава 2.

Элементы математической логики.

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

Наша речь состоит из высказываний. Высказывания могут быть простыми, как например: дважды два четыре, 6 делится на 3 и т.д.; или сложными, составными, такими, как 2х2=5 или 6 делится на 3.

Высказывание либо истинно, либо ложно, и не может быть истинным и ложным одновременно (закон исключения третьего), хотя в реальной жизни это возможно. Например, высказывание “ N – хороший человек” может быть одновременно и истинным и ложным в зависимости от того, чье мнение выражает это высказывание.

Сложные, составные, высказывания строятся из простых с помощью логических, или сентенциональных, связок. Их всего 5. Это не, и, или, если…, то (или влечет), тогда и только тогда, когда.

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

Первое систематическое рассмотрение этих вопросов можно найти уже в сочинениях Аристотеля, однако математические подходы впервые были указаны Джорджем Булем (1854 г.). Современные более тонкие методы выработаны уже в наше время усилиями специалистов по математической логике.

Мы будем использовать строчные латинские буквы a, b, x, y, p, q и т.д. в качестве символов неопределённых высказываний. Эти высказывания могут быть как простыми, так и составными. Эти переменные могут принимать 2 значения, которые мы будем обозначать как 1 (истинно) или 0 (ложно).

Основные логические операции (связки)

И их таблицы истинности.

1. Отрицание. Читается не а (неверно, что а). Обозначается а̅ (иногда а). Истинно тогда и только тогда, когда а ложно.

2. Логическое произведение (конъюнкция). Обозначается a Ù b (иногда просто ab), читается а “и” b. В обычной речи в качестве синонимов используют слова “a”, “но”. Истинно только в том случае, если истинны оба высказывания.

3. Логическая сумма (дизъюнкция). Обозначается аÚb.Читается а “или” b. Высказывание ложно только в том случае, когда ложны оба высказывания. Отметим, что союз “или” употребляется не в разделительном смысле.

4. Импликация. Обозначается а®b. Читается “если а, то b”; а – посылка, b – заключение. Ложно только в случае, если посылка а истинна, а заключение b ложно. Заметим, что здесь не предполагается причинно-следственная связь.

5. Эквиваленция(двойная импликация). Обозначается а«b.Читается “а тогда и только тогда, когда b”. Истинно только когда а и b принимают одинаковые истинностные значения.

Таблица истинности основных логических операций

а	b	aÚb	aÙb	a®b	a«b	`а

Упражнения.

1. Запишите символически следующие сложные предложения, обозначив буквами простые компоненты (т.е. высказывания, не содержащие связок)

a. Если завтра будет дождь, то я выйду из дома, взяв зонтик, или останусь дома.

b. Если я устал или голоден, то не могу заниматься.

c. Если утром я не просплю и успею к первой паре, то получу зачёт, а если просплю или не успею, то зачёт не получу.

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

e. Число делится на 10 тогда и только тогда, когда оно делится на 5 и четно.

Решение:

a. p – завтра будет дождь, q – я выйду из дома, r – я возьму зонтик

(p®qrÚ`q)

b. p – я устал, q – я голоден, r – могу заниматься

(pÚq®`r)

c. p – утром я просплю, q – успею к первой паре, r – сдам зачёт ((`pÙq®r)Ù(pÚ`q®`r))

d. p – существует предел каждой функции, q –существует предел суммы, r – предел суммы равен сумме пределов, s – существует предел хотя бы одного слагаемого ((p®qÙr)Ù(`p®`s))

e. p – число делится на 10, q –число делится на 5, r – число четно

(p«qÙr)

2. Пусть p – сегодня светит солнце, q – сегодня идёт дождь, r – сегодня идет снег, s – вчера был ветер

Переведите на русский язык следующие формулы:

a. (p®(rÙs))

b. (s«pÙ`q)

c. (p«(rÙ`s)Ú`q)

d. ((p«`q)Ù(`rÚs))

Решение:

a. Если сегодня светит солнце, то идёт снег и вчера был ветер

b. Тогда и только тогда сегодня светит солнце, и нет дождя, если вчера был ветер

c. Тогда и только тогда сегодня светит солнце, когда или нет дождя, или идёт снег, а вчера не было ветра

d. Тогда и только тогда светит солнце, когда нет дождя, и, либо вчера был ветер, либо сегодня не идёт снег

3. Пусть р – Маша любит Сашу, q – Саша любит Машу

Запишите символически следующие сложные предложения, обозначив буквами простые компоненты:

a. Саша и Маша любят друг друга

b. Неверно, что Саша и Маша любят друг друга

c. Саша и Маша друг друга не любят

d. Саша любит Машу, но та не отвечает ему взаимностью

Решение:

a. (pÙq)

b. ( =`pÚ`q)

c. (`pÙ`q)

d. (qÙ`p)