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

Алгебра высказываний – самый простой раздел математической логики, лежащий в основе всех остальных ее разделов. Язык алгебры высказываний является одним из простейших языков математики. Основными объектами рассмотрения здесь являются высказывания.

§1. Высказывания и операции над ними.

Понятие «высказывание» является первичным, оно не определяется, а поясняется. Под высказыванием понимают повествовательное предложение, о котором можно судить, истинно оно или ложно. Вопросительные и восклицательные предложения высказываниями не являются. Также не являются высказываниями и определения.

Высказывания будем обозначать заглавными латинскими буквами: A, B, C, …, X, Y,Z, …

Н

 1, если высказывание А истинно,

(A)= 

 0, если высказывание А ложно.

а совокупности всех высказываний определяется функция истинности, принимающая значение в двухэлементном множестве {0;1}:

Значение (A) называется логическим значением или значением истинности высказывания А. В дальнейшем будем отождествлять высказывания с их значениями истинности. Если высказывание А истинно, то то будем писать следующим образом: А=1; если высказывание А ложно, то: А=0.

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

отрицание: А (читается «не А» (используется также обозначение «Ā»);

конъюнкция: АВ (читается «А и В»)(используется также обозначение А&В);

дизъюнкция: АВ (читается «А или В»);

импликация: АВ (читается “если А, то В”, или “из А следует В”, или “А достаточно для В” или “В необходимо для А”);

эквиваленция: АВ (читается «А равносильно В», или «А тогда и только тогда, когда В», или «А необходимо и достаточно для В»).

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

А	В	А	АВ	АВ	АВ	АВ
0	0	1	0	0	1	1
0	1	1	0	1	1	0
1	0	0	0	1	0	0
1	1	0	1	1	1	1

Упражнения.

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

Определите какие из высказываний истинные, а какие ложные.

а) Минск – столица Белоруссии.

б) Каждое целое число является и числом рациональным.

в) X²>0.

г) Треугольник АВС подобен треугольнику А`В`С`.

д) Луна есть спутник Марса.

е) Кислород-газ.

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

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

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

к) Железо тяжелее свинца.

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

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

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

о) Для каждого действительного числа х х+1>0.

п) х+1>0.

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

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

а) 3 есть простое число, и 9 есть составное число.

б) Петр встанет, и он или Иван уйдет.

в) Петр встанет и уйдет, или Иван уйдет.

г) Студент не может заниматься, если он устал или голоден.

д) Если Петр опоздал и не пойдет на первый час лекции, то он не будет доволен, а если он не опоздает, он доволен.

е) Для того, чтобы натуральное число а было нечетным, достаточно, чтобы а было простым и большим двух.

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

3. Пусть А высказывание «сегодня светит солнце», В – «сегодня идет снег», С – «сегодня пасмурно» и D – «вчера было ясно». Переведите на обычный язык следующие высказывания:

а) АC; в) А(ВС); д)АD;

б) ВС; г)А(СВ); е) (ВС)А.

4. Установите, какие из высказываний в следующих парах являются отрицаниями друг друга и какие – нет (объясните почему):

а) 2<0, 2>0.

б) 6<9, 69.

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

г) «Натуральное число n четно», «Натуральное число n нечетно».

д) «Функция F нечетна», «Функция F четна».

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

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

5. Следующие высказывания запишите без знака отрицания:

а) (а<b); б) (ab); в) (а>b); г)(a≤b).

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

а) Ленинград расположен на Неве и 2+3=5.

б) 7-простое число и 9-простое число.

в) 7-простое число или 9-простое число.

г) 2•2=4, и 2•2≤5, и 2•2≥4.

д) 2•2=4 или белые медведи живут в Африке.

е) Если 12 делится на 6, то 12 делится на 3.

ж) Если 11 делится на 6, то 11 делится на 3.

з) Если 15 делится на 6, то 15 делится на 3.

и) Если 15 делится на 3, то 15 делится на 6.

к) Если Саратов расположен на Неве, то белые медведи обитают в Африке.

л) 12 делится на 6 тогда и только тогда, когда 12 делится на 3.

м) 15 делится на 5 тогда и только тогда, когда 15 делится на 4.

7. Определите значения истинности высказываний А, B, C, D и E в следующих предложениях, из которых первые четыре истинные, а последние пять ложные:

а) А(2•2=4).

б) С(2•2=5).

в) Если 4 – четное число, то А.

г) Если B, то 4-нечетное число.

д) В(2•2=4).

е) D(2•2=5).

ж) Е(2•2=5).

з) Если 4-четное число, то С.

и) Если D, то 4 – нечетное число.

8. Сформируйте и запишите в виде конъюнкции или дизъюнкции условие истинности каждого предложения (а и b – действительные числа):

a) a•b0 г) ж) |a|>3

б) а•b=0 д) |a|=3 з) а²+b²0

в) a²+b²=0 е) |а|<3 и)

9. Пусть через А обозначено высказывание «9 делится на 3», а через В высказывание «8 делится на 3». Определите значения истинности следующих высказываний:

а) АВ г)ВА ж) АВ

б) ВА д)АВ з)А­В

в)АВ е)ВА и) АВ

10. Определите значения истинности высказываний А, В, С и D в следующих предложениях, из которых первые два истинные, а последние два ложные:

а) А(2<3);

б) В(2>3);

в) С(2<3);

г) D(2>3).

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

а) (АВ)С, C=1;

б) А(ВС), ВС=0;

в) А(ВС), В=0;

г)(АВ)(АВ), А=1;

д) (АВ)(ВА), В=1;

е) (АВ)(АС), А=0;

ж) (PQR)(PQ), PQR=0.

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

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

б) ложно тогда и только тогда, когда оба данных высказывания истинны.

13. Из трех данных высказываний А, В, С постройте составное высказывание, которое истинно, когда истинно какое-либо одно из данных высказываний, и только в этом случае.

14. Пусть высказывание АВ истинно. Что можно сказать о логическом значении высказывания (АВ)(АВ)?

15. Если высказывание АВ истинно (ложно), то что можно сказать о логическом значении высказываний:

а) АВ; б)АВ; в)АВ; г)ВА ?

16. Существуют ли три таких высказывания А, В, С, чтобы одновременно высказывание АВ было истинным, высказывание АС – ложным и высказывание (АВ)С – ложным?

17. Докажите теорему об обратимости системы импликаций (принцип полной дизъюнкции): если истинны высказывания А₁В₁, А₂В₂, …, А_кВ_к, А₁А₂…А_к, (B_iB_j), ij, i,j=1,2,…,k, то истинны и высказывания В₁А₁, В₂А₂…В_кА_к.