Основные законы алгебры логики
Закон | Для ИЛИ | Для И |
Переместительный | ![]() | ![]() |
Сочетательный | ![]() | ![]() |
Распределительный | ![]() | ![]() |
Правила де Моргана | ![]() | ![]() |
Идемпотенции | ![]() | ![]() |
Поглощения | ![]() | ![]() |
Склеивания | ![]() | ![]() |
Операция переменной с ее инверсией | ![]() | ![]() |
Операция с константами | ![]() | ![]() |
Двойного отрицания | ![]() |
Основные соответствия элементов и операций булевых алгебр
Множества | Логические функции | Случайные события |
![]() | невозможное | |
U(универсальное) | достоверное | |
È (объединение) | v (дизъюнкция) | сумма |
Ç (пересечение) | & (конъюнкция) | произведение |
¾ (дополнение) | (отрицание) | противоположное |
Булевы функции 2-х переменных
Табл.3 содержит все булевы функции двух переменных. Функция gi имеет в качестве столбца значений двоичную запись числа i. Ниже приведены выражения этих функций формулами.
Таблица 3
X | Y | g0 | g1 | g2 | g3 | g4 | g5 | g6 | g7 | g8 | g9 | g10 | g11 | g12 | g13 | g14 | g15 |
I | |||||||||||||||||
1, |
g0 = 0 - константа О
g1 = X &У - конъюнкция
g2 = (X У) = X &У - отрицание импликации
g2= X- первая переменная
g4 = (у X) = X & У - отрицание обратной импликации
g5 = Y-вторая переменная
g6 = X©Y = X&YvX&Y - сумма по модулю 2
g7= Xv У - дизъюнкция
g 8 = (X & У) = Х v Y - отрицание конъюнкции
g 9 = X ~ У = X &Y v X &У - эквивалентность
g10 = Y - отрицание второй переменной
g11 = У X = X v У - обратная импликация
g12 = X - отрицание первой переменной
g13 = X У = X v У - импликация
g14 = X | У =Х v У =(Х&У) - штрих Шеффера
g15 = 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, т. е. является тождественно-истинной.