- •Конспект лекций по дисциплине «основы дискретной математики»
- •Лекция № 1. Дискретное и непрерывное
- •Лекция № 2. Системы счисления
- •Лекция № 3. Фракталы
- •3.1. Канторово множество
- •3.2. Ковер Серпинского и снежинка Коха
- •3.3. Стохастические фракталы
- •3.4. Энтропийная размерность
- •3.5. Фрактал Мандельброта
- •Лекция № 4. Основы математической логики
- •Набор истинностных значений 0001 в первой строке таблицы соответствует результатам операций:
- •Основные эквивалентности:
- •X(баскетболист(X)высокий(X))
- •X(личность(х)любит(х, грибы))
- •X любит(х, платить(налоги))
- •X(человек(X)смертный(X)),
- •Лекция № 5. Множества и подмножества
- •Лекция № 6. Математическая индукция
- •Лекция № 7. Комбинаторика
- •Лекция № 8. Числа фибоначчи и простые числа
- •Лекция № 9. Кодирование
- •Лекция № 10. Шифрование
Набор истинностных значений 0001 в первой строке таблицы соответствует результатам операций:
0 0 = 0;
0 1 = 0;
1 0 = 0;
1 1 = 1.
Как известно, в арифметике вначале выполняются операции умножения или деления, а затем – сложения или вычитания. Логические связки также подчиняются подобному правилу. Приоритет применения связок возрастает в следующем порядке: ,,, . Чтобы изменить этот порядок, то, как и в арифметике, необходимо использовать скобки.
Переменные и формулы в исчислении высказываний
Переменная, значениями которой являются высказывания, называется пропозициональной переменной. Понятие пропозициональной формулы вводится по индукции:
выражение, состоящее только из пропозициональной переменной, является пропозициональной формулой;
если A и B – пропозициональные формулы, то каждое из выражений A, (AB), (AB), (AB) и (AB) – пропозициональная формула;
последовательность символов только тогда является пропозициональной формулой, когда она построена в соответствии с 1) и 2).
Пример 4.2. Примеры пропозициональных формул:
P ((AB) C ,
Q ((AC) (A B)).
Булевы функции
Функция , у которой аргументы пробегают множество {0,1} и которая принимает значение из того же множества {0,1}, называетсяфункцией алгебры логики или булевой функцией.
Особое значение имеют так называемые элементарные булевы функции. Двухместными элементарными булевыми функциями являются конъюнкция, дизъюнкция, импликация, сумма по модулю 2, эквиваленция, штрих Шеффера и стрелка Пирса. Символы А и B из табл. 4.2 следует в этом случае толковать как булевы переменные {0,1}.
Имеются две одноместные булевы функции, зависящие от x: тождественная функция иотрицание . Это элементарные функции (табл. 4.3).
Таблица 4.3
x | ||
0 |
0 |
1 |
1 |
1 |
0 |
Имеются две нуль-местные элементарные булевы функции: это константы 0 и 1. Каждой пропозициональной формуле можно сопоставить булеву функцию. Булева функция , сопоставленная пропозициональной формулеA, называетсяфункцией истинностиформулыA. Любую такую функцию можно описать с помощью соответствующейтаблицы истинности(примеры – табл. 4.3, табл. 4.4, табл. 4.5).
Пусть и– функции истинности формул P и Q; пусть {} – множество тех переменных, которые встречаются хотя бы в одной из функций и. Пропозициональные формулыP и Q называются эквивалентными, если на всяком наборе () значений переменных значения функций исовпадают (эквивалентность обозначают как:PQ).
Пример 4.3. Покажем эквивалентность выражений
PAB и QAB.
Для этого построим таблицу истинности (табл. 4.4).
Таблица 4.4
A |
B |
(A, B) PAB |
(A, B) QAB |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
Поскольку (A, B) = (A, B), то P Q.
Пример 4.4. Покажем эквивалентность выражений
PA(BC) и Q(AB)(AC).
Для этого снова построим таблицу истинности (табл. 4.5).
Таблица 4.5
A |
B |
C |
(A, B, C) PA(BC) |
(A, B, C) Q(AB)(AC) |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
Поскольку (A, B, C) =(A, B, C), то P Q. Как можно видеть, в примере 4.3 используются двухместные функции истинности, а в примере 4.4 – трехместные.