dm_tema_3

Дискретная математика Тема 3. Алгебра логики

Е.А.Перепелкин

АлтГТУ

2012

3.1 Логические операции

Определение

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

Пример

Утверждение Площадь круга равна R2, ãäå R радиус круга

является высказыванием.

Утверждение Это утверждение ложно высказыванием не является, т.к. оно логически противоречиво. Относительно данного утверждения нельзя сказать, что оно является истинным или ложным.

Из заданного множества высказываний можно получить новые высказывания, применяя логические связки логические операции:и , или , если, то , тогда и только тогда, когда и др. Множество высказываний и множество логических операций над высказываниями образуют алгебру высказываний алгебру логики. Пусть A è B два произвольных высказывания.

Определение

Операция и , логическое умножение, конъюнкция, обозначается: AB, A ^ B, A&B. Высказывание A ^ B является истинным тогда и только тогда, когда истинными являются высказывания A è B.

Определение

Операция или , логическое сложение, дизъюнкция, обозначается: A + B, A _ B, A!B. Высказывание A _ B является ложным тогда и

только тогда, когда оба высказывания A è B являются ложными.

Определение

Операция отрицание , не , инверсия , обозначается :

A, B.

Высказывание

A является истинным, если B ложно, и является ложным, если A истинно.

Определение Операция следование , импликация , обозначается A ! B, A ) B. Высказывание A ! B является ложным тогда и только тогда, когда A истинно, а B ложно.

Определение

Операция эквивалентность , обозначается A B, A , B. Высказывание A B является истинным тогда и только тогда, когда A è B оба истинны или оба ложны.

Таблицы истинности основных логических операций:

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 :

Формулы алгебры высказываний есть логические (булевы) функции. Значения и аргументы этих функций принимают только два значения:и и л . Эти логические константы обозначают соответственно 1 и 0.

Определение

Булева функция n аргументов f (x1; x2; : : : ; xn) есть функция

f : E n ! E ;

ãäå E = f0; 1g.

Существует 2n различных булевых векторов размера n. Булева функция каждому булеву вектору ставит в соответствие 0 или 1.

Поэтому существует

22n

различных булевых функций. При n = 2 число различных булевых функций равно 16.

Основные булевы функции двух аргументов:

x1 x2 сумма по модулю 2 (отрицание эквивалентности) x1jx2 штрих Шеффера (отрицание конъюнкции, не-и ) x1 # x2 стрелка Пирса (отрицание дизъюнкции, не-или )