3_Алгебра_логики (Мацнев А.П. - Математическая логика и теория алгоритмов - 2004), страница 2

х₁ & х₂, х₁ · х₂ (часто х₁ х₂), х₁ Λ х₂;

φ₇(х₁, х₂) - дизъюнкция (логическое сложение, операция ИЛИ), обозначается:

х₁ ٧ х₂, иногда х₁ + х₂ и т.п.

Логические функции трех и более переменных обычно за­даются (наряду с таблицами истинности) также формулами бинарных операций. Например, выражение f (х₁, х₂, х₃) = (х₁ ٧ х₂) → (х₁ & х₃) означает, что функция трех переменных f задана формулой, состоящей из символов этих перемен­ных х₁, х₂, х₃, над которыми выполняются одна унарная операция отрицания и три бинарные операции: дизъюнкция (٧), импликация (→) и конъюнкция (&).

Наиболее употребляемыми являются операции: ¬, ٧, &, →, ~, mod2, |, ↓. Значение любой логической формулы, со­держащей знаки этих операций, можно вычислить для лю­бого набора значений переменных, используя табл. 3.1 и 3.2.

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

Эквивалентными, или равносильными, называются фор­мулы, представляющие одну и ту же функцию (эквивалент­ность формул в алгебре логики обозначается знаком = ).

Стандартный метод установления эквива­лентности двух формул:

1) по каждой формуле восстанавливается таблица истин­ности;

2) полученные таблицы сравниваются по каждому набо­ру значений переменных, (стандартный метод требует 2 • 2ⁿ вычислений).

3.3 Основные законы алгебры логики

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

Алгебра логики строится на определенной системе аксиом.

Постулаты алгебры логики

1. Существуют такие 0 и 1, что =1 и =0. Необходимо отме­тить, что цифры 0 и 1 не выражают здесь количественных соотношений и являются не числами, а символами и, следовательно, алгебра логики является не алгеброй чисел, а алгеброй состояний.

2. Переменная может принимать лишь одно из двух возможных значений

x = 0, если, x  1

x = 1 если, x 0

3. Действия с константами

0  0 = 0 1  1 = 1

1  1 = 1 0  0 = 0

1  0 = 0 0  1 = 1

0  1 = 0 1  0 = 1

Каждая из приведенных аксиом состоит из двух частей, что соответ­ствует правилу инверсии, которое заключается в том, что любая аксиома может быть преобразована в другую одновременной заменой цифра 0 на цифру 1 и операции умножения на сложение, и наоборот.

На основании этих аксиом выводятся все теоремы, выражающие основ­ные законы алгебры логики.

Законы алгебры логики. Теоремы одной переменной

1. Закон, тождества Х=Х. Необходимо, чтобы мысль, заключенная в высказывании не менялась в течение всего рассуждения.

2. Закон нулевого множества:

0  а = 0

0  а = а

0  а  b  …  x = 0

Т.е. произведение любого числа переменных обращается в нуль, если какая-либо одна переменная имеет значение "0" независимо от значения других переменных.

3. Закон универсального множества:

1  а = а

1  а = 1

1  а  b  …  z = 1

4. Закон тавтологии, повторения (идемпотентности):

а  а …  а = а

а  а  …  а = а

Истина, повторенная несколько раз, все равно, остается только истиной.

5. Закон двойной инверсии (инволютивности): . Отрицание отрицания равносильно утверждению.

6. Законы дополнительности:

а) закон логического противоречия . Произведение любой пере­менной и ее отрицания всегда ложно (утверждение "речка дви­жется и не движется" всегда ложно);

б) закон исключенного третьего . Сумма любой переменной и ее отрицания всегда истинна: "Студент или сдаст экзамен или не сдаст". "Паду ли я стрелой пронзенный, иль мимо пролетит она".

Теоремы для двух и трех переменных

7. Коммутативные (переместительные) законы:

а  b = b  а

а  b = b  а

От перемены мест слагаемых сумма не меняется.

8. Ассоциативные (сочетательные) законы:

а  (b  c) = (a  b)  c ассоциативность конъюнкции.

а  (b  c) = (а  b)  c ассоциативность дизъюнкции.

Для записи умножения или сложения скобки можно опустить.

9. Дистрибутивные (распределительные) законы:

а) умножение относительно сложения

а  (b  c) = а  b  а  c

а (b + с) = аb + ас (в обычной алгебре)

б) сложение относительно умножения

a  b  c = (a  b)  (a  c)

a+bc  (a+b) (a+c) (в обычной алгебре)

10. Законы инверсии (правило де Моргана)

11. Обобщение законов де Моргана, предложенное Шенноном:

т.е. инверсия дизъюнкции и конъюнкции получается заменой каждой переменной ее инверсией и одновременно взаимной заменой символов суммы и произведения.

12. Законы поглощения

13. Закон контрапозиции . Согласно закону контрапозиции два высказывания вида и одновременно истинны или одновременно ложны. Вместо заданной теоремы можно доказать обратно противоположную теорему. Например. "Если m² нечетно, то m - нечетно". Докажем что если m четно, то m² четно. Действительно, если m = 2n, то m² = 4n².

14. Закон транзитивности импликации (закон силлогизма).

(а  b)  (b  с) ( а  с)

15. Закон транзитивности эквиваленции.

(а  b)  (b  с) ( а  с)

16. Закон противоположности.

(а  b)  (а b)

17. Законы склеивания (распространения).

3.4 Тавтологии. Равносильные формулы

ПФ, значения которых для любого набора переменных есть 1 (соответственно 0) будем называть тождественно истинными формулами, или тавтологиями (тождественно-ложными ПФ или противоречием).

Тавтологии играют в логике особо важную роль как формулы, отражающие логическую структуру предложений, истинных в силу одной только этой структуры. Для доказательства того, что ПФ является тавтологией доста­точно построить таблицу истинности для этой ПФ. Перечислим некоторые основные тавтологии или законы логики. Обозначим | = А, что А тавтология. Справедливость | = и  вытекает из определений:

1. | = х  х - закон тождества

2. | =  0 - закон противоречия

3. | = 1 - закон исключенного третьего

4. | =  х - закон двойного отрицания

5. | = = - закон идемпотентности

6. -законы де Моргана

7. | = - закон контрапозиции

8. | = - закон транзитивности импликации (закон силлогизма)

9. | = - закон противоположности

10.| = - закон транзитивности эквиваленции

Законы 1-3 выражают законы формальной логики, выведенные Аристо­телем. Закон тождества требует, чтобы мысль, заключенная в высказыва­нии не изменялась в течении всего рассуждения. Закон противоречия говорит, что одна и та же мысль не может быть одновременно и истин­ной и ложной.

В силу законов идемпотентности в алгебре логики нет показателей степени и коэффициентов (idem - "то же", potentia - сила).

Смысл законов де Моргана можно выразить так: отрицание дизъюнк­ции равно конъюнкции отрицаний и vice versa. Согласно закону контрапозиции два предложения вида и одновременно истинны или одновременно ложны.

Две ПФ и назовем равносильными, если для любых наборов они принимают одинаковые значения.

Это обозначается АВ и читается "А равносильно В" (равно­сильность рефлексивна, симметрична и транзитивна).

Теорема 1. А  В тогда и только тогда, когда | = А  В. Убедимся, что теорема верна, если докажем необходимость: если АВ, то | = А  В; достаточность: если | = А  В, то А  В. Справедливость этих утверждений вытекает непосредственно из оп­ределений.

Принцип двойственности: Если две формулы, (не содержащие знаков , и ) равносильны, то двойственные ил формулы равносильны.

Две формулы называются двойственными, если каждую из них можно получить из другой заменой ,  , 1, 0 соответственно на  , , 0 и 1 (X  0 = Х  1).

Обратные и противоположные теоремы. Для каждого предложения, формализованного импликацией А  В, можно составить три таких пред­ложения В  А, и . Предложение В  А называется об­ратным данному, предложения противоположным данному и обратно противоположным. Для всякой теоремы вида "если А, то В" можно сформулировать обратное ей предложение "если В, то А". Однако не для всякой теоремы предложение ей обратное является истинным. Например: "если два прямоугольника конгруэнтны, то их площади равны", обратное: "Если площади двух прямоугольников равны, то они конгруэнтны" - неверно. Если А  В теорема, то А есть достаточное условие В, а В необходимое условие А. Если оба взаимообратных предложения А  В и В  А теоремы, т.е. предложение А  В теорема, то В является необходимым и достаточным условием А, а А достаточным и необходимым условием В (если два квадрата конгруэнтны...). Если А  В теорема, а В  А нет, то А - достаточное, но не необходимое условие В, а В - необходимое, но не достаточное условие А.

Для всякой теоремы А  В, можно составить противоположное пред­ложение , которое может быть истинным, но может и не быть истин­ным. Чтобы убедиться в этом, надо составить таблицу истинности.

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

3.5 Полнота системы логических функций. Базис

При использовании аналитических форм представления логических функции широко используется принцип суперпозиции, заключающийся в за­мене одних аргументов данной функции другими. Например, если аргументы функции Z = Z(X, Y) являются в свою очередь функциями других аргумен­тов X = Х(a, b) и Y = Y(c, d), то можно записать Z = Z(a, b, c, d).