Билет 8

Оглавление

Алгебра логики — раздел математики, изучающий высказывания, рассматриваемые с точки зрения их логических значений (истинности или ложности) и логических операций над ними.

Под логическим высказыванием понимается любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно. Например, логическим высказыванием будет “Земля третья планета от Солнца”, но не является таковым “Морозная в этом году зима”.

Важность знакомства с двоичными алгебрами заключаете следующем. Во-первых, они являются математической основой строения всех логических схем компьютеров, обрабатывающих информацию в двоичной системе счисления. Во-вторых, они служат математической основой решения сложных логических задач.

 двоичные переменные и функции

двоичными называют переменные, способные принимать только два значения: 0 и 1. Двоичные функции — это функции двоичных переменных. Они также принимают только два значения — 0 и 1. Двоичные переменные и функции называют булевыми переменными и булевыми функциями (БФ).

Конечность области определения и области значений БФ позволяют задавать эти функции не только формулами, но и таблично. В виде таблицы БФ задают значениями 0 или 1 на каждом из наборов значений ее аргументов. Такие таблицы называют таблицами истинности (в алгебре логики в таких таблицах вместо 0  пишут Л — ложь, вместо 1 пишут И — истина).

Инверсия — функция одного аргумента. Логическая операция над аргументом отрицание. Часто отождествляют функцию с операцией и говорят: «функция отрицание или «операция ин версия» . Однако при строгом формальном подходе отождествлять результат с действием нежелательно.

Знак операции — черта над аргументом, например,  или х.

Такая запись читается: «не х» или «отрицание х». В языках программирования также широко используются логические операции, реализующие булевы функции. Функция инверсия аргумента х записывается так: N0Т х.

Функцию инверсия в схемах компьютера реализует логический элемент инвертор (элемент НЕ). Схема инвертора показана на рис. Работает инвертор так: если на входе 0, то на выходе 1, если на входе 1, то на выходе 0.

Моделью ячейки, реализующей функцию НЕ, может служить размыкающий контакт реле. При срабатывании реле цепь, в которую входит такой контакт, будет размыкаться. Таким образом, инверсия единицы равна нулю, инверсия нуля - единице, а двойная инверсия не изменяет значения переменной.

Конъюнкция — это такая булева функция, которая равна единице тогда и только тогда, когда все аргументы функции равны единице.

Другое определение — это такая функция, которая равна нулю, если хотя бы один аргумент функции равен нулю.

Логическое умножение (конъюнкция) обозначается точкой или символом ^ либо вообще в буквенных выражениях никак не обозначается. Функцию И реализуют, например, соединенные последовательно замыкающие контакты нескольких реле. Цепь в этом случае будет замкнута только тогда, когда сработают все реле.

Функцию конъюнкция получаем как результат операции логическое умножение. Знак операции: & или ^ (в теоретических работах по алгебре логики). В формулах, как и в обычной алгебре, знак чаще всего опускается.

Запись в языках программирования: х₁ AND х₂.

Функцию конъюнкция реализует логический элемент конъюнктор (элемент И). Условное обозначение конъюнктора в логических схемах показано на рис.

Используя принцип суперпозиции (подстановку функции в качестве аргументов в другую функцию), функцию конъюнкция можно обобщить на n аргументов: f(х_1, х₂ , ..., хn ) = х_1, х₂ , ..., хn

В качестве содержательного примера реализации функции конъюнкция рассмотрим схему голосования «только все!» На рис. показана цепь с N кнопками, позволяющими включать индикаторную лампочку. На электрических выключателях принято отмечать: 0 — выключено и 1 — включено. Лампочка засветится только в случае, если будут замкнуты  все ключи, то есть на все N входов будут «поданы» единицы. Такая схема реализует функцию конъюнкция.

Дизъюнкция — это такая двоичная функция, которая равна нулю тогда и только тогда, когда все аргументы функции равны нулю, другое определение: дизъюнкция — это такая функция, которая равна единице, если хотя бы один аргумент равен единице.

Функции дизъюнкции соответствует операция логическое сложение. Знак операции:   Пример записи формулы функции дизъюнкция: f (х₁, х₂ ) = =х₁  х₂. Читается формула так: «х₁ или х₂».

Запись на языках программирования: «х₁ OR х₂».

Функцию дизъюнкция реализует логический элемент дизъюнктор (элемент ИЛИ).

В качестве примера реализации функции дизъюнкция рассмотрим схему голосования «хотя бы один». На рис. показана цепь с N кнопками, позволяющими включать индикаторную лампочку. Лампочка засветится в случае, если будет замкнут хотя бы один ключ, то есть схема реализует функцию дизъюнкция.

Логическое сложение (дизъюнкция) обозначается символом "+" или V (первая буква латинского слова vel-или). В качестве примера цепи, реализующей: функцию ИЛИ, можно привести параллельное соединение замыкающих контактов нескольких реле. Цепь, в которую входят эти контакты, будет замкнута, если сработает хотя бы одно реле рис. Таким образом, логическая сумма равна единице тогда, когда равно единице одно или несколько слагаемых.

Таблицы истинности			Условное обозначение дизъюнктора	Работа дизъюнктора
А	В	А или В
0	0	0
1	0	0
0	1	0
1	1	1