Алгебра логики – алгебра, образованная множеством B = {0, 1} и всеми логическими операциями, определёнными на этом множестве .
Логическая функция – n-арная операция заданная на множестве B или функция f (x1, …, xn), принимающая значения из B, когда её аргументы пробегают B.
Список переменных функции – упорядоченный набор (x1, …, xn).
x | j1 | j2 | j3 | j4 |
Примеры логических функций одной и двух переменных:
Функции одной переменной: n=1, 221=4
j1 – фиктивная константа 0;
j2 – тождественная функция;
j3 – отрицание;
j4 – фиктивная константа 1.
x1 | x2 | j2 | j7 | j8 | j9 | j10 | j14 | j15 |
Функции двух переменных: n=2 222 = 16
j2 – конъюнкция (&);
j7 – сложение по модулю 2 (Å);
j8 – дизъюнкция (Ú);
j9 – стрелка Пирса (¯);
j10 – эквиваленция («);
j14 – импликация (®);
j15 – штрих Шеффера (|).
Константа 0, 1
х1, х2 фиксированные
отрицание х1, х2
Формулы алгебры логики:
Алфавит алгебры логики содержит:
· логические переменные x1…xn,
· логические операции (связки),
· скобки.
Слово в алфавите алгебры логики называется формулой, если оно удовлетворяет след условиям:
1) x1…xn – простейшие формулы,
2) А,В–формулы, то – формулы,
3) других формул нет
Подформулой формулы А называется любое подслово слова А которое является формулой.
Соглашения: разрешается опускать знак конъюнкции (&) и скобки, которые могут быть однозначно восстановлены.
Упорядоченный набор переменных <x1…xn> называется списком переменных формулы А. Список может содержать фиктивные переменные. Если каждой переменной сопоставить 0 или 1 то получиться упорядоченное множество называемое оценкой списка переменных. Если каждой оценке (кол-во оценок 2n) сопоставить значение формулы – то получим логическую функцию заданную в виде таблицы (истинности).
Равносильность формул:
Формулы A и B, зависящие от списка переменных (x1, …, xn), называются равносильными, если на любой оценке списка переменных они принимают одинаковые значения.
Равносильность – отношение эквивалентности между формулами.
Основные равносильности:
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;
11) Закон исключённого третьего: A Ú ØA º 1;
12) Закон снятия двойного отрицания: ØØA º A.