Логические операции

НЕ отрицание

А истинно, когда А ложно и ложно, когда А истинно.

И конъюнкция или логическое умножение

Высказывание А • В истинно тогда и только тогда, когда оба высказывания А и В истинны.

ИЛИ дизъюнкция или логическое сложение Высказывание А + В ложно тогда и только тогда, когда оба высказывания А и В ложны.

ЕСЛИ-ТО импликация Высказывание А → В ложно тогда и только тогда, когда А истинно, а В ложно.

РАВНОСИЛЬНО эквиваленция или двойная импликация

Высказывание А ↔ В истинно тогда и только тогда, когда значения А и В совпадают.

Логический элемент компьютера — это часть электронной логической схемы, которая реализует элементарную логическую функцию.

Таблица истинности - это табличное представление логической схемы (операции), в котором перечислены все возможные сочетания значений истинности входных сигналов (операндов) вместе со значением истинности выходного сигнала (результата операции) для каждого из этих сочетаний.

Иначе говоря, булева функция – это функция, и аргументы и значение которой принадлежит множеству { 0, 1 }. Множество { 0, 1 } мы будем в дальнейшем обозначать через B.

Булеву функцию от n аргументов можно рассматривать как n -местную алгебраическую операцию на множестве B. При этом алгебра <B; >, где  – множество всевозможных булевых функций, называется алгеброй логики.

Конечность области определения функции имеет важное преимущество – такие функции можно задавать перечислением значений при различных значениях аргументов. Для того, чтобы задать значение функции от n переменных, надо определить значения для каждого из 2 ⁿ наборов. Эти значения записывают в таблицу в порядке соответствующих двоичных чисел. В результате получается таблица следующего вида:

Раз у нас есть стандартный порядок записывания наборов, то для того, чтобы задать функцию, нам достаточно выписать значения f (0,0,...,0,0), f (0,0,...,0,1), f (0,0,...,1,0), f (0,0,...,1,1),..., f (1,1,...,0,0), f (1,1,...,0,1), f (1,1,...,1,0), f (1,1,...,1,1). Этот набор называют вектором значений функции.

Таким образом, различных функций n переменных столько, сколько различных двоичных наборов длины 2 ^{n *}. А их 2 в степени 2 ⁿ.

Множество B содержит два элемента – их можно рассматривать как булевы функции от нуля (пустого множества) переменных – константу 0 и константу 1.

Функций от одной переменной четыре: это константа 0, константа 1, тождественная функция, т.е. функция, значение которой совпадает с аргументом и так называемая функция `` отрицание ''. Отрицание будем обозначать символом как унарную операцию. Приведём таблицы этих четырёх функций:

Как видим, функции от некоторого числа переменных можно рассматривать как функции от большего числа переменных. При этом значения функции не меняется при изменении этих ``добавочных'' переменных. Такие переменные называются фиктивными, в отличие от остальных – существенных. Определение 2 (Фиктивные и существенные переменные). Переменная x_i называется фиктивной (несущественной) переменной функции f (x ₁ ,···,x_n), если

f (x ₁ ,···,x_{i- 1},0 ,x_{i+ 1} ,···,x_n) = f (x ₁ ,···,x_{i- 1},1 ,x_{i+ 1} ,···,x_n)

для любых значений x ₁ ,···,x_{i- 1} ,x_{i+ 1} ,···,x_n. Иначе переменная x_i называется существенной.