Рейтинг:  4 / 5

Звезда активнаЗвезда активнаЗвезда активнаЗвезда активнаЗвезда не активна
 

Внимание! Следующий материал написан не мной, а профессором кафедры алгебры и геометрии и дискретной математики Южного Федерального Университета - Я. М. Ерусалимским, в его книге Дискретная Математика. Я лишь приведу из его книги только тот материал, который нужно понять для дальнейшего обучения программирования. Если Вы хотите, то можете скачать его книгу и познакомиться с ней более подробно.

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

Как и во всей математике, в нашем курсе, в каждом его разделе существуют основные понятия, с которых все начинается. Считается, что у каждого из нас существуют интуитивные представления о них. В этих интуитивных представлениях спрессован исторический опыт человечества в области математических знаний. Основные понятия не определяются, для них даются квазиопределения, как правило содержащие отсылки к другим неопределенным понятиям и объектам. В первой главе таким основным неопределяемым понятием является высказывание.

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

Пример 1.1. «2x2 = 4». .(Дважды два равно четырем.)

Пример 1.2. «2 < 3».

Пример 1.3. Река Дон в 2002 году н. э. впадает в Каспийское море.

Пример 1.4. «х < 2, х принадлежит R». (Вещественное число х меньше чем два.)

Пример 1.5. Площадь отрезка меньше длины куба.

Пример 1.6. Является ли х = 3 корнем уравнения х2 — 5х = 0?

Пример 1.7. 3>=5.

В приведенных примерах высказываниями являются 1.1, 1.2, 1.3, 1.7. Причем 1.1 и 1.2 — истинные высказывания, а 1.3 и 1.7 — ложные. Пример 1.5 — это пример связного повествовательного предложения, которое не является высказыванием, так как о нем нельзя сказать, истина оно или ложь (из-за отсутствия в этом предложении какого-либо смысла). 1.6 не является высказыванием, так как не является повествовательным предложением. Предложение примера 1.4 не является высказыванием, несмотря на свою повествовательность, связность и осмысленность. В нем содержится переменная, и из-за ее присутствия это предложение обладает свойством превращаться в высказывание при фиксации значения этой переменной. Если через Р(х) обозначить предложение примера 1.4, то Р(—1) — истинное высказывание, Р(3) — ложное высказывание. Ясно, что объекты такого типа являются обобщением понятия высказывания. К изучению этих объектов мы приступим позже в главе 2.

В дальнейшем нас будет интересовать не то, о чем идет речь в высказывании (его содержательная часть), а лишь какое значение истинности («истина», «ложь») оно имеет. В алгебре высказываний все высказывания, имеющие одинаковые значения истинности, взаимно заменяемы, т. е. мы имеем два класса высказываний: класс истинных высказываний и класс ложных высказываний.

Введем следующие обозначения: если а — высказывание, то через а^ будем обозначать его значение истинности.

Если а — истинное высказывание, то а^ = 1 (истина, true).(и, t).

Если а — ложное высказывание, то а^ = 0 (лож, false).(л, f).

(Здесь и далее в скобках приводятся другие встречающиеся в литературе обозначения.)

Таким образом, может рассматриваться как отображение множества высказываний в двухэлементное множество {0; 1}.

Определение 1.1 Два высказывания а и b будем называть равносильными (и писать а = b), если a^ — b^,т. е.

а = b <=> а^ = b^ (В сереидне знак "<=>" обозначает тогда и только тогда, когда)

Логические операции над высказываниями

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

Отрицание

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

Определение 1.2 Отрицание высказывания а — высказывание, обозначаемое ¬а и определяемое следующей таблицей:

a ¬а
0 1
1 0


Очевидно, имеет место свойство:

¬¬а = а.

Оно называется законом двойного отрицания.

Перейдем теперь к определению бинарных (т. е. применяемых к паре высказываний) операций алгебры высказываний.

Конъюнкция

Конъюнкция (логическое умножение) соответствует союзу «и» в русском языке, т. е. конструкции «... и ххх».

Определение 1.3 Конъюнкцией высказываний а и b называется высказывание, обозначаемое а/\Ъ (a * b, ab, а&b) и определяемое следующей таблицей:

a^ b^ (a*b)^
0 0 0
0 1 0
1 0 0
1 1 1


т. е. конъюнкция a & b истинна тогда и только тогда, когда истинны оба высказывания а, b.

Имеют место следующие свойства:

а) a & b = b & а — коммутативный закон

б) а & 1 = а (законы «О» и «1» для конъюнкции)

в) а & 0 =0  (законы «О» и «1» для конъюнкции)

г) а & а = а — закон идемпотентности.

Дизъюнкция

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

Определение 1.4 Дизъюнкцией высказываний а, b называется высказывание, обозначаемое а V b и определяемое следующей таблицей:

a^ b^ (aVb)^
0 0 0
0 1 1
1 0 1
1 1 1


т. е. дизъюнкция а V b ложна тогда и только тогда, когда ложны оба высказывания а, Ь.

Имеют место следующие свойства:

а )а\/b = bVа — коммутативный закон

б) а V 1 = 1 (законы «О» и «1» для дизъюнкции)

в) а V 0 = а (законы «О» и «1» для дизъюнкции)

г) а V а = а — закон идемпотентности.

Эквиваленция

Эквиваленция (равносильность) соответствует конструкции «... равносильно ххх » («... тогда и только тогда, когда ххх »).

Определение 1.5 Эквиваленцией высказываний а, b называется высказывание, обозначаемое а ~ b (а <-> b) и определяемое следующей таблицей:

a^ b^ (a~b)^
0 0 1
0 1 0
1 0 0
1 1 1

т е. эквиваленция а~b истинна тогда и только тогда, когда образующие ее высказывания а, b имеют равные значения истинности.

 Очевидно, имеют место следующие свойства:

а) а~b = b~а — коммутативный закон; 

б) a ~ b =¬а ~ ¬b;

в) а ~ 1 = а;

г) а ~ 0 = ¬а.

Импликация

Импликация соответствует конструкции «Если ..., то ххх »(«Из ... следует ххх.»).

Определение 1.6 Импликацией высказываний а, b называется высказывание, обозначаемое а —> b (а =>b) и определяемое следующей таблицей:

a^ b^ (a->b)^
0 0 1
0 1 1
1 0 0
1 1 1

т е. импликация а ->b ложна тогда и только тогда, когда а истина, a b — ложь.

Высказывания, образующие импликацию а —> Ь, имеют специальные названия: а — посылка (гипотеза, антецедент), b — заключение (вывод, консеквент).

При первоначальном знакомстве с логическими операциями кажется, что все они, кроме импликации, введены довольно естественно, а восприятию введенного определения импликации наше сознание сопротивляется. Однако, можно привести пример, показывающий, что такое определение импликации соответствует нашей интуитивной логике и конструкции «Если ..., то хxх », которой мы пользуемся в математике очень часто. Вспомним одну теорему из арифметики —Q(x) = «Если натуральное число х делится на 4, то оно (натуральное число X) делится на 2.». В справедливости этой теоремы мы не сомневаемся, т. е. какое натуральное число х мы ни зафиксируем в Q(x), мы получим истинное высказывание. Обозначим A(x) = «Натуральное число х делится на 4.», В(х) — «Натуральное число х делится на 2.».

Тогда имеем

Q(x) = А(х) —? В(х). (1.1)

Фиксируя в (1.1) значения x = 8, 2, 3, мы реализуем строки 1 —> 1, 0 —? 1, 0 —> 0. Ясно, что не удается для (1.1) подобрать такое значение х, чтобы реализовалась ситуация 1 —» 0 (так как справедлива приведенная теорема, т. е. Q(x) = А(х) —> В(х) = 1).

Очевидно, имеют место свойства:

а) а —> b <> b —> а;      в)0—>а = 1      д) а—>1 = 1;

б) а —> a = 1;         г) 1 —> а = а;      е) а —> 0 = а.

Заметим, что в обычном языке в предложении вида «Если А, то В.» А и В содержательно (контекстно) связаны. Это совершенно необязательно в нашем определении импликации, т. е. мы имеем право рассматривать импликации вида: «Если сегодня четверг, то 2 х 2 = -5.», которая истинна во все дни, кроме четверга, а в четверг ложна.

В большинстве алгоритмических языков имеется логический оператор «if Р then S», использование которого несколько отличается от определения импликации, а именно, если Р — истина, то отрезок S программы выполняется, а если Р — ложь, то отрезок S программы опускается (не выполняется).

Пример 1.10. Каково значение переменной х после выполнения следующего фрагмента программы

if х < 2 then х := Зх;

если до начала его выполнения а) х — 1; б) х = 4?

Ответ: а) х = 3; б) х = 4.

С импликацией а —? b связывают еще две импликации: b —? а, ¬b —> ¬а. Первую из них называют обращением а —> b, вторую — контра позицией импликации а —> b.

Пример 1.11. Найти обращение и контрапозицию следующей импликации:

«Если сегодня четверг, то 2 х 2 = 4.»

Решение: Обращение исходной импликации имеет вид: «Если 2 х 2 = 4, то сегодня четверг.», а контрапозиция: «Если 2x2<>4,  то сегодня не четверг.».

Зависимости между операциями

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

Теорема 1.1 Справедливы следующие равносильности:

a —> b = ¬ а V b

а ~ b = (а —> b)(b —> a) = (¬a V b) * (а V ¬ b) =(a*b)V(¬a*¬b)

Любую из этих равносильностей можно доказать с помощью таблицы истинности.

Из приведенных равносильностей видно, что —> и ~ выражаются через V, *, ¬ дальнейшем будет показано, что через V, *, ¬ можно выразить любую операцию алгебры высказываний. Поэтому мы основное внимание уделим изучению свойств этих операций, которые принято называть булевскими (булевыми) операциями алгебры высказываний.

Теорема 1.2 Справедливы следующие 19 равносильностей для булевых операций алгебры высказываний:

0. ¬¬a=a — закон двойного отрицания

1.aVb =bVa — коммутативные законы

2. а*b = b*a — коммутативные законы

3. а V (b V с) = (a V b) V с -ассоциативные законы

4. а * (b * с) = (а * b) * с -ассоциативные законы

5. а V (b * с) = (а V b) * (а V с) — дистрибутивные законы

6. а * (b V с) = (а * b) V (а * с) — дистрибутивные законы
7. а V а = а

8. а * а = а

9. ¬(a V b) = ¬a*¬b -Законы Деморгана

10. ¬(a * b) = ¬a V ¬ b -Законы Деморгана

11.a V 1 = 1 - Законы нуля и единицы

12. а * 0 = 0 - Законы нуля и единицы

13. а V 0 = а - Законы нуля и единицы

14. a * 1 = a - Законы нуля и единицы
15. а V (а * b) = а - Законы поглащения

16. а * (а V b) = а - Законы поглащения

17. а V ¬а = 1 — закон исключенного третьего

18. а * ¬а.= 0 — закон противоречия

? Любую из них можно доказать с помощью таблицы истинности. <

Логические и битовые операции

В компьютерах основной единицей информации является бит. Бит принимает два возможных значения 0 или 1, иными словами, бит — одноразрядное двоичное число. Для обозначения значения истинности высказывания мы также использовали 0,1. Таким образом, если а — высказывание, то его значение истинности а — бит информации. Переменная, принимающая значения во множестве {0,1}, обычно называется булевой переменной. Т. е. булева переменная — это такая переменная, задание значения которой определяет один бит информации.

Компьютерные битовые (или логические) операции соответствуют операциям над высказываниями (вернее, над их значениями истинности). Приведем таблицы, определяющие операции ¬, or (V), and (&, *), xor:

x ¬x
0 1
1 0
or 0 1
0 0 1
1 1 1

and 0 1
0 0 0
1 0 1

xor 0 1
0 0 1
1 1 0

Определение 1.7 Битовой строкой длины n (n принадлежит N) называется последовательность длины n, элементами которой являются биты.

Например, 0110010 — битовая строка длины 7. Битовые операции естественным образом (поэлементно) распространяются на битовые строки равной длины. Их обозначения: bitwise ¬, bitwise or, bitwise and, bitwise xor.

ГЛАВА 2

Алгебры предикатов и множеств.

Отображения
2.1. Предикаты. Логические операции над

предикатами. Кванторы

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

Определение 2.1 Пусть x1,x2,...,xn — символы переменных произвольной природы. Эти переменные будем называть предметными. Пусть наборы переменных (х1, х2, ... ,xn) принадлежат (выбираются из) множеству Q, которое будем называть предметной областью. Предикатом местности n (n-местным предикатом), определенным на предметной области Q, называют отображение Q во множество высказываний.

Прежде чем перейти к рассмотрению примеров, дадим квазиопределение n-местного предиката:

Определение. «Связное повествовательное предложение, содержащее n переменных и обладающее следующим свойством: при фиксации значений всех переменных о нем (предложении) можно сказать, истинно оно или ложно».

Пример 2.1. D(x1,x2)= «Натуральное число х1 делится (без остатка) на натуральное число x2.» — двуместный предикат, определенный на множестве пар натуральных чисел N х N.

Очевидно, ^D(4,2) = 1, ^D(3,5) = 0.

Пример 2.2. Q(x) — «х2 < -1,1 € R.» — одноместный предикат, определенный на R.

Ясно, что Q(-1) = 0, и вообще предикат Q(x) — тож-дественно ложен, т. е. ^Q(x) = 0.

Пример 2.3. R(х,у,z) =«х2 + у2 <= z; х,у, z € R.» — трехместный предикат, определенный на R3.

R(1,1,-2) = 0, R(1,1,2) = 1.

Пример 2.4. S(x, у) =«sin 2ху > -3; х,у € R.» — тождественно истинный двуместный предикат.

Пусть Р(х1,x2,... ,хn) — n-местный предикат, определенный на Q. Свяжем с ним два множества (подмножества Q), определенные следующим:

P-1({1})={(x1,x2, ..., xn) принадлежит Q|^P(x1,x2, ..., xn)=1} — множество истинности предиката Р,

P-1({1})={(x1,x2, ..., xn) принадлежит Q|^P(x1,x2, ..., xn)=0} — множество ложности предиката Р.

Определение 2.2 Предикат Р, определенный на Q. называется тождественно истинным, если

Р-1({1}) = Q(Р-1({0}) = 0);

тождественно ложным, если

P-1({0}) = Q(Р-1({1}) = 0);

нетривиально выполнимым, если

P-1({1})<>0 u P-1({0})<>0