Алгебра логики. Понятие логической функции. Примеры логических функций одной и двух переменных. Формулы алгебры логики. Равносильность формул

Алгебра логики – алгебра, образованная множеством B = {0, 1} и всеми логическими операциями, определёнными на этом множестве .

Логическая функция – n-арная операция заданная на множестве B или функция f (x₁, …, x_n), принимающая значения из B, когда её аргументы пробегают B.

Список переменных функции – упорядоченный набор (x₁, …, x_n).

x	j₁	j₂	j₃	j₄

Примеры логических функций одной и двух переменных:

Функции одной переменной: n=1, ₂2¹=4

j₁ – фиктивная константа 0;

j₂ – тождественная функция;

j₃ – отрицание;

j₄ – фиктивная константа 1.

x₁	x₂	j₂	j₇	j₈	j₉	j₁₀	j₁₄	j₁₅

Функции двух переменных: n=2 ₂2² = 16

j₂ – конъюнкция (&);

j₇ – сложение по модулю 2 (Å);

j₈ – дизъюнкция (Ú);

j₉ – стрелка Пирса (¯);

j₁₀ – эквиваленция («);

j₁₄ – импликация (®);

j₁₅ – штрих Шеффера (|).

Константа 0, 1

х1, х2 фиксированные

отрицание х1, х2

Формулы алгебры логики:

Алфавит алгебры логики содержит:

· логические переменные x₁…x_n,

· логические операции (связки),

· скобки.

Слово в алфавите алгебры логики называется формулой, если оно удовлетворяет след условиям:

1) x₁…x_n – простейшие формулы,

2) А,В–формулы, то – формулы,

3) других формул нет

Подформулой формулы А называется любое подслово слова А которое является формулой.

Соглашения: разрешается опускать знак конъюнкции (&) и скобки, которые могут быть однозначно восстановлены.

Упорядоченный набор переменных <x₁…x_n> называется списком переменных формулы А. Список может содержать фиктивные переменные. Если каждой переменной сопоставить 0 или 1 то получиться упорядоченное множество называемое оценкой списка переменных. Если каждой оценке (кол-во оценок 2ⁿ) сопоставить значение формулы – то получим логическую функцию заданную в виде таблицы (истинности).

Равносильность формул:

Формулы A и B, зависящие от списка переменных (x₁, …, x_n), называются равносильными, если на любой оценке списка переменных они принимают одинаковые значения.

Равносильность – отношение эквивалентности между формулами.

Основные равносильности:

1) Коммутативность: A & B º B & A; A Ú B º B Ú A;

2) Ассоциативность: (A & B) & С º A & (B & С); (A Ú B) Ú С º A Ú (B Ú С);

3) Дистрибутивность: & отн-но Ú: A & (B Ú С) º (A & B) Ú (A & С); Ú отн &: A Ú (B & С) º (A Ú B) & (A Ú С);

4) Закон идемпотенции: A & A º A; A Ú A º A;

5) Законы де Моргана: Ø (A & B) º ØA Ú ØB; Ø (A Ú B) º ØA & ØB;

6) Законы поглощения: A & (A Ú B) º A; A Ú (A B) º A;

7) Законы расщепления: A º (A Ú B) & (A Ú ØB); A º (A & B) Ú (A & ØB);

8) Свойство нуля: A & 0 º 0; A Ú 0 º A;

9) Свойство единицы: A & 1 º A; A Ú 1 º 1;

10) Закон противоречия: A & ØA º 0;