Информатика и вычислительная техника


Основные сведения из алгебры логики - часть 2


Функция 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
  xi.

Конъюнкцией, или логическим умножением двух высказываний х и у, называется логическая функция Р, истинная только в том случае, когда истинны одновременно х и у. Таблица истинности для конъюнкции имеет вид:

Конъюнкция обозначается знаком & , который читается как "И".




Начало  Назад  Вперед