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