2.3Основные законы математической логики

В алгебре логики выполняются следующие основные законы, позволяющие производить тождественные преобразования логических выражений:

– переместительный закон: X V Y = Y V X,

X & Y = Y & X;

­– сочетательный закон: ( X V Y ) V Z = X V ( Y V Z ),

( X & Y ) & Z = X & ( Y & Z );

­– распределительный закон: ( X V Y ) & Z = ( X & Z ) V ( Y & Z ),

( X & Y ) V Z = ( X V Z ) & ( Y V Z );

­– законы де Моргана: ¬ ( X V Y ) = ¬ X & ¬ Y,

¬ ( X & Y ) = ¬ X V ¬ Y;

­– закон идемпотенции: X V X = X,

X & X = X;

­– закон поглощения: ( X & Y ) V X = X,

( X V Y ) & X = X;

­– закон cклеивания: ( X & Y ) V ( ¬ X & Y ) = Y,

( X V Y ) & ( ¬ X V Y ) = Y;

­– правило операции переменной с ее инверсией: ¬ X V X = 1,

¬ X & X = 0;

­– правило операции с константами: X V 0 = X,

X V 1 = 1,

X & 0 = 0,

X & 1 = X;

­– закон двойного отрицания: ¬ ¬ X = X.

2.4 Преобразование логических функций

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

Пример 5.2 Упростите логическую функцию ¬(x v y)&(x&¬y).

а) Применяем закон де Моргана: ¬(x v y)&(x&¬y)= ¬x&¬y&(x&¬y).

б) Применяем сочетательный закон: ¬x&¬y&(x&¬y) = ¬x&x&¬y&¬y.

в) Применяем правило операций переменной с её инверсией:

¬x&x&¬y&¬y = 0&¬y&¬y.

г) Применяем два раза правило операций с константами: 0&¬y&¬y = 0&¬y=0.

Пример 5.3 Упростите логическую функцию x&¬y v ¬x&y&z v x&z).

а) Вводим вспомогательный логический сомножитель (¬y v y):

x&¬y v ¬x&y & z v x & z = x & ¬y v ¬x & y & z v x & z & (¬y v y).

б) Применяем распределительный закон к последнему слагаемому:

x&¬y v ¬x&y&z v x&z&(¬y v y) = x&¬y v ¬x&y&z v x&y&z v x&¬y&z.

в) комбинируем два крайних и два средних логических слагаемых:

x&¬y v ¬x&y&z v x&y&z v x&¬y&z = (x&¬y v x&¬y&z) v (¬x&y&z v x&y&z).

г) используем закон поглощения:

(x&¬y v x&¬y& z) v (¬x&y&z v x&y&z)= (x&¬y v y&z)

3 Задания

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

а) Не можете ли вы передать мне соль?

б) Некоторые лекарства опаснее самих болезней.

в) Сегодня солнечно.

2. Составьте отрицания к данным высказываниям:

а) Все дни в августе были солнечными

б) Не все птицы летают

в) Все растения съедобные

3. Переведите данные высказывания на язык логики.

а) Дождь неожиданно начался и быстро закончился.

б) Обычно в 6 часов я иду гулять с собакой или смотрю телевизор.

в) Если завтра будет холодно, я не пойду гулять.

4. Построить таблицу истинности и определить является функция выполнимой, тавтологией или противоречием: (ВА)   (АВ)  (А v В).

5. Упростите выражение: (ВА)   (АВ)  (А v В).

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

1. Что такое математическая логика, высказывание? Приведите примеры.

2. Дайте определения логической переменной, логической операции, логическому выражению.

3. Назовите логические операции, их обозначение и приведите примеры.

4. Приведите таблицу истинности для логических операций.

5. Какие правила и законы логики Вы знаете?