Функция f(x1, x2, ..., хn), определяемая на наборах входных двоичных переменных х1, x2, ..., хn и принимающая в качестве возможных значений 0 или 1, называется логической функцией. Примем без доказательства, что общее число различных логических функций от n аргументов равно 22n. Например, для n = 1, 2, 3 и т.д. их будет соответственно 4, 16, 256 и т.д.
Над логическими переменными в алгебре логики производятся логические операции, основными из которых являются операции отрицания, дизъюнкции и конъюнкции.
Операции отрицания соответствует логическая функция одного аргумента, которая истинна, если аргумент ложен, и ложна, когда аргумент истинен. Операцию отрицания называют также операцией НЕ или инверсией.
105
Данная операция обозначается чертой, которая ставится над аргументом, например, х.
Для представления логических операций удобно пользоваться таблицами истинности, в которых возможным наборам аргументов ставятся в соответствие значения функций. Табличное представление операции отрицания имеет вид:
Очевидным является следующее свойство операции отрицания x = х.
В отличие от операции отрицания для операций дизъюнкции и конъюнкции уже требуется, как минимум, два аргумента.
Дизъюнкцией двух высказываний х и у называется логическая операция, в результате которой образуется логическая функция F, истинная в том случае, если хотя бы одно из высказываний х или у истинно. В соответствии с этим определением таблица истинности для дизъюнкции имеет вид:
Дизъюнкция обозначается знаком ? , который читается как "ИЛИ", т.е. F = x ? y.
Часто данную операцию называют операцией логического сложения. В общем случае эта операция может быть определена для любого числа аргументов: x1 ? x2 ? x3 ? ... =
| n |
| ? |
| i = 1 |
Конъюнкцией, или логическим умножением двух высказываний х и у, называется логическая функция Р, истинная только в том случае, когда истинны одновременно х и у. Таблица истинности для конъюнкции имеет вид:
Конъюнкция обозначается знаком & , который читается как "И".