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

Закон	Для ИЛИ	Для И
Переместительный
Сочетательный
Распределительный
Правила де Моргана
Идемпотенции
Поглощения
Склеивания
Операция переменной с ее инверсией
Операция с константами
Двойного отрицания

Основные соответствия элементов и операций булевых алгебр

Множества	Логические функции	Случайные события
		невозможное
U(универсальное)		достоверное
È (объединение)	v (дизъюнкция)	сумма
Ç (пересечение)	& (конъюнкция)	произведение
¾ (дополнение)	(отрицание)	противоположное

Булевы функции 2-х переменных

Табл.3 содержит все булевы функции двух переменных. Функция g_i имеет в качестве столбца значений двоичную запись числа i. Ниже приведены выражения этих функций формулами.

Таблица 3

X

Y

g0

g1

g2

g3

g4

g5

g6

g7

g8

g9

g10

g11

g12

g13

g14

g15

I

1,

g₀ = 0 - константа О

g₁ = X &У - конъюнкция

g₂ = (X У) = X &У - отрицание импликации

g₂= X- первая переменная

g₄ = (у X) = X & У - отрицание обратной импликации

g₅ = Y-вторая переменная

g₆ = X©Y = X&YvX&Y - сумма по модулю 2

g₇= Xv У - дизъюнкция

g ₈ = (X & У) = Х v Y - отрицание конъюнкции

g ₉ = X ~ У = X &Y v X &У - эквивалентность

g₁₀ ⁼ Y - отрицание второй переменной

g₁₁ = У X = X v У - обратная импликация

g₁₂ = X - отрицание первой переменной

g₁₃ = X У = X v У - импликация

g₁₄ = X | У =Х v У =(Х&У) - штрих Шеффера

g₁₅ = 1 - константа 1

Составление таблиц истинности для логических формул

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

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

Пример.Составим таблицу истинности для формулы , которая содержит две переменные: х и у. В первых двух столбцах таблицы запишем че­тыре возможные пары значений этих переменных, в последующих столбцах — значения промежуточных формул и в последнем столбце — значение формулы. В результате получим табл.4.

Таблица 4

Переменные	Промежуточные логические формулы	Формула
X	У	X

Из табл.4 видно, что при всех наборах значений переменных х и у формула принимает значение 1, т. е. является тождественно-истинной.