dm_tema_3
.pdfДискретная математика Тема 3. Алгебра логики
Е.А.Перепелкин
АлтГТУ
2012
Е.А.Перепелкин (АлтГТУ) |
Дискретная математика. Тема 3 |
2012 |
1 / 57 |
3. Алгебра логики |
3.1 Логические операции |
3.1 Логические операции
Определение
Высказывание это повествовательное утверждение, относительно которого можно однозначно сказать, что оно является истинным или ложным.
Пример
Утверждение Площадь круга равна R2, ãäå R радиус круга
является высказыванием.
Утверждение Это утверждение ложно высказыванием не является, т.к. оно логически противоречиво. Относительно данного утверждения нельзя сказать, что оно является истинным или ложным.
Е.А.Перепелкин (АлтГТУ) |
Дискретная математика. Тема 3 |
2012 |
2 / 57 |
3. Алгебра логики |
3.1 Логические операции |
Из заданного множества высказываний можно получить новые высказывания, применяя логические связки логические операции:и , или , если, то , тогда и только тогда, когда и др. Множество высказываний и множество логических операций над высказываниями образуют алгебру высказываний алгебру логики. Пусть A è B два произвольных высказывания.
Определение
Операция и , логическое умножение, конъюнкция, обозначается: AB, A ^ B, A&B. Высказывание A ^ B является истинным тогда и только тогда, когда истинными являются высказывания A è B.
Е.А.Перепелкин (АлтГТУ) |
Дискретная математика. Тема 3 |
2012 |
3 / 57 |
3. Алгебра логики |
3.1 Логические операции |
Определение
Операция или , логическое сложение, дизъюнкция, обозначается: A + B, A _ B, A!B. Высказывание A _ B является ложным тогда и
только тогда, когда оба высказывания A è B являются ложными.
Определение
Операция отрицание , не , инверсия , обозначается :
A, B.
Высказывание
A является истинным, если B ложно, и является ложным, если A истинно.
Е.А.Перепелкин (АлтГТУ) |
Дискретная математика. Тема 3 |
2012 |
4 / 57 |
3. Алгебра логики |
3.1 Логические операции |
Определение Операция следование , импликация , обозначается A ! B, A ) B. Высказывание A ! B является ложным тогда и только тогда, когда A истинно, а B ложно.
Определение
Операция эквивалентность , обозначается A B, A , B. Высказывание A B является истинным тогда и только тогда, когда A è B оба истинны или оба ложны.
Е.А.Перепелкин (АлтГТУ) |
Дискретная математика. Тема 3 |
2012 |
5 / 57 |
3. Алгебра логики |
3.1 Логические операции |
Таблицы истинности основных логических операций:
A |
B |
A ^ B |
|
A |
B |
A _ B |
|
A |
B |
A ! B |
è |
è |
è |
|
è |
è |
è |
|
è |
è |
è |
|
|
|
|
|
|
|
|
|
|
|
è |
ë |
ë |
|
è |
ë |
è |
|
è |
ë |
ë |
|
|
|
|
|
|
|
|
|
|
|
ë |
è |
ë |
|
ë |
è |
è |
|
ë |
è |
è |
|
|
|
|
|
|
|
|
|
|
|
ë |
ë |
ë |
|
ë |
ë |
ë |
|
ë |
ë |
è |
|
|
|
|
|
|
|
|
|
|
|
A |
B |
A B |
|
A |
|
|
A |
||||
è |
è |
è |
|
è |
ë |
|
|
|
|
|
|
è |
ë |
ë |
|
ë |
è |
|
|
|
|
|
|
ë |
è |
ë |
|
|
|
|
|
|
|
|
|
ë |
ë |
è |
|
|
|
|
|
|
|
|
|
Е.А.Перепелкин (АлтГТУ) |
Дискретная математика. Тема 3 |
2012 |
6 / 57 |
3. Алгебра логики |
3.2 Булевы функции |
3.2 Булевы функции
Сложные высказывания записываются в виде формул алгебры высказываний. Например,
A _ B ! C ; (A ! B) _ C (A ^ B):
Пример Определим высказывания:
A : x < y; B : y < z; C : x < z:
Тогда сложное высказывание Если x < y è y < z, òî x < z можно записать в виде формулы алгебры высказываний
A ^ B ! C :
Е.А.Перепелкин (АлтГТУ) |
Дискретная математика. Тема 3 |
2012 |
7 / 57 |
3. Алгебра логики |
3.2 Булевы функции |
Формулы алгебры высказываний есть логические (булевы) функции. Значения и аргументы этих функций принимают только два значения:и и л . Эти логические константы обозначают соответственно 1 и 0.
Определение
Булева функция n аргументов f (x1; x2; : : : ; xn) есть функция
f : E n ! E ;
ãäå E = f0; 1g.
Е.А.Перепелкин (АлтГТУ) |
Дискретная математика. Тема 3 |
2012 |
8 / 57 |
3. Алгебра логики |
3.2 Булевы функции |
Существует 2n различных булевых векторов размера n. Булева функция каждому булеву вектору ставит в соответствие 0 или 1.
Поэтому существует
22n
различных булевых функций. При n = 2 число различных булевых функций равно 16.
Е.А.Перепелкин (АлтГТУ) |
Дискретная математика. Тема 3 |
2012 |
9 / 57 |
3. Алгебра логики |
3.2 Булевы функции |
Основные булевы функции двух аргументов:
x1 ^ x2 |
конъюнкция |
||
x1 _ x2 |
дизъюнкция |
||
x1 |
! x2 |
импликация |
|
x1 |
x2 |
обратная импликация |
|
x1 |
x2 эквивалентность |
x1 x2 сумма по модулю 2 (отрицание эквивалентности) x1jx2 штрих Шеффера (отрицание конъюнкции, не-и ) x1 # x2 стрелка Пирса (отрицание дизъюнкции, не-или )
Е.А.Перепелкин (АлтГТУ) |
Дискретная математика. Тема 3 |
2012 |
10 / 57 |