§ 2. Законы алгебры высказываний

1. Коммутативные законы

А  В  В  А

А  В  В  А

2. Ассоциативные законы

А  (В  С)  (А  В)  С

А  (В  С)  (А  В)  С

3. Дистрибутивные законы

А  (В  С)  (А  В)  (А  С)

А  (В  С)  (А  В)  (А  С)

4. А  А  А

А  А  А

5. А  И  А

А  И  И

6. А  Л  Л

А  Л  А

7. А   Л

А   И

8.

9.

10. А  В   В

11. А  В 

Докажем равенство 10: А  В   В. Для этого составим таблицу истинности.

А	В	А  В
И	И	И	Л	И
И	Л	Л	Л	Л
Л	И	И	И	И
Л	Л	И	И	И

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

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

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

Контрольные вопросы

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

2. Какие высказывания называют элементарными, а какие – составными?

3. Сформулируйте определения отрицания, конъюнкции, дизъюнкции, импликации, эквиваленции высказываний и составьте для данных операций над высказываниями таблицы истинности.

4. Какие высказывания называют равносильными?

5. Каким законам подчиняются операции над высказываниями?

§ 3. Предикаты и операции над ними

В математике часто встречаются предложения, содержащие одну или несколько переменных, например: «х+ 2 = 7», «город стоит на Волге». Эти предложения не являются высказываниями, т.к. о них нельзя сказать, истинны они или ложны. Однако при подстановке конкретных значений переменнойхони обращаются в истинные или ложные высказывания. Так, в первом примере прих= 5 получаем истинное высказывание, а прих= 3 – ложное высказывание.

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

По числу входящих в предикат переменных различают одноместные, двухместные и т.д. предикаты и обозначают А(х),В(х;у)…

Пример:А(х): «хделится на 2» – одноместный предикат,В(х;у): «прямаяхперпендикулярна прямойу» – двухместный предикат.

Следует иметь в виду, что в предикате переменные могут содержаться неявно: «число делится на 2», «студент получил отличную оценку на экзамене по математике».

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

Определение. Множеством (областью) определения предиката называется множествоХ, состоящее из всех значений переменных, при подстановке которых в предикат последний обращается в высказывание.

Так, предикат «х > 2» можно рассматривать на множестве натуральных чисел или действительных чисел.

Каждый предикат А(х),хХопределяет множествоТ Х, состоящее из элементов, при подстановке которых в предикатА(х) вместохполучается истинное высказывание.

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

Пример. Рассмотрим предикатА(х): «х< 5», заданный на множестве натуральных чисел.Т= {1; 2; 3; 4}.

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

Пусть Т_А– область истинности предикатаА(х),Т_В– область истинности предикатаВ(х).

Определение.КонъюнкциейпредикатовА(х) и В(х) называется предикатА(х)В(х), который истинен для тех и только тех значенияххХ, для которых оба предиката истинны.

Покажем, что Т_{А  В} =Т_А Т_В.

Доказательство. 1) Пустьа Т_{А  В} А(а)В(а) – истинное высказывание. По определению конъюнкции имеем:А(а) – истинно,В(а) – истинноа Т_А а Т_В а Т_А Т_В Т_{А  В} Т_А Т_В.

2) Пусть b Т_А Т_В b Т_А b Т_В А(b) – истинно,В(b) – истиннопо определению конъюнкцииА(b)В(b) – истинное высказываниеb Т_{А  В}  Т_А Т_В Т_{А  В}.

Т.к. Т_{А  В} Т_А Т_В иТ_А Т_В Т_{А  В}, то по свойству равенства множествТ_{А  В} =Т_А Т_В, что и требовалось доказать.

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

Пример. Рассмотрим предикатыА(х): «х< 10»,В(х): «хделится на 3», заданные на множестве натуральных чисел. Найдем область истинности предикатаА(х)В(х): «х< 10 и делится на 3».

Т_А = {1; 2; 3; 4; 5; 6; 7; 8; 9; 10},Т_В = {3; 6; 9; 12; 15; …}, тогдаТ_{А  В} = {3; 6; 9}.

Определение.ДизъюнкциейпредикатовА(х) и В(х) называется предикатА(х)В(х), который истинен для тех и только тех значенияххХ, для которых истинен хотя бы один из предикатов.

Можно доказать (самостоятельно), что Т_{А  В} =Т_А Т_В.

Пример. Рассмотрим предикатыА(х): «хделится на 2 »,В(х): «хделится на 3», заданные на множестве натуральных чисел. Найдем область истинности предикатаА(х)В(х): «хделится на 2 или на 3».

Т_А = {2; 4; 6; 8; 10;…},Т_В = {3; 6; 9; 12; 15; …},Т_{А  В} = {2; 3; 4; 6; 8; 9; …}.

Определение.ОтрицаниемпредикатаА(х) называется предикат . Он истинен для тех и только тех значенияххХ, для которых предикатА(х) ложен и наоборот.

Заметим, что =.

Определение.ИмпликациейпредикатовА(х) иВ(х) называется предикатА(х)В(х) (читают: «ЕслиА(х), тоВ(х)»). Он обращается в ложное высказывание при тех значенияххХ, для которых предикат А(х) истинен, а предикатВ(х) ложен.

Из определения имеем, что предикат А(х)В(х) ложен на множествеТ_А, а следовательно истинен на дополнении к этому множеству. Воспользовавшись законами операций над множествами, имеем:.