Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
НЕ отрицание
А истинно, когда А ложно и ложно, когда А истинно.
И конъюнкция или логическое умножение
Высказывание А • В истинно тогда и только тогда, когда оба высказывания А и В истинны.
ИЛИ дизъюнкция или логическое сложение Высказывание А + В ложно тогда и только тогда, когда оба высказывания А и В ложны.
ЕСЛИ-ТО импликация Высказывание А → В ложно тогда и только тогда, когда А истинно, а В ложно.
РАВНОСИЛЬНО эквиваленция или двойная импликация
Высказывание А ↔ В истинно тогда и только тогда, когда значения А и В совпадают.
Логический элемент компьютера — это часть электронной логической схемы, которая реализует элементарную логическую функцию.
Таблица истинности - это табличное представление логической схемы (операции), в котором перечислены все возможные сочетания значений истинности входных сигналов (операндов) вместе со значением истинности выходного сигнала (результата операции) для каждого из этих сочетаний.
Иначе говоря, булева функция – это функция, и аргументы и значение которой принадлежит множеству { 0, 1 }. Множество { 0, 1 } мы будем в дальнейшем обозначать через B.
Булеву функцию от n аргументов можно рассматривать как n -местную алгебраическую операцию на множестве B. При этом алгебра <B; >, где – множество всевозможных булевых функций, называется алгеброй логики.
Конечность области определения функции имеет важное преимущество – такие функции можно задавать перечислением значений при различных значениях аргументов. Для того, чтобы задать значение функции от n переменных, надо определить значения для каждого из 2 n наборов. Эти значения записывают в таблицу в порядке соответствующих двоичных чисел. В результате получается таблица следующего вида:
Раз у нас есть стандартный порядок записывания наборов, то для того, чтобы задать функцию, нам достаточно выписать значения 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 n.
Множество B содержит два элемента – их можно рассматривать как булевы функции от нуля (пустого множества) переменных – константу 0 и константу 1.
Функций от одной переменной четыре: это константа 0, константа 1, тождественная функция, т.е. функция, значение которой совпадает с аргументом и так называемая функция `` отрицание ''. Отрицание будем обозначать символом как унарную операцию. Приведём таблицы этих четырёх функций:
Как видим, функции от некоторого числа переменных можно рассматривать как функции от большего числа переменных. При этом значения функции не меняется при изменении этих ``добавочных'' переменных. Такие переменные называются фиктивными, в отличие от остальных – существенных. Определение 2 (Фиктивные и существенные переменные). Переменная xi называется фиктивной (несущественной) переменной функции f (x 1 ,···,xn), если
f (x 1 ,···,xi- 1,0 ,xi+ 1 ,···,xn) = f (x 1 ,···,xi- 1,1 ,xi+ 1 ,···,xn)
для любых значений x 1 ,···,xi- 1 ,xi+ 1 ,···,xn. Иначе переменная xi называется существенной.
Дата публикования: 2015-01-23; Прочитано: 326 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!