6 перечислите основные функции алгебры логики

Алгебра логики (булева алгебра).

Алгебра
логики. Функции алгебры логики. Таблицы
истинности. Пропозициональные формулы.
Равносильные формулы. Основные тождества
алгебры логики. Двойственные функции.
Полные системы связок. Конъюнктивные
и дизъюнктивные нормальные формы.
Совершенные КНФ и ДНФ. Тавтологии.
Противоречия. Проблема разрешимости в
алгебре логики. Логические следствия.
Основные схемы доказательств.

Алгебра логики

Алгебраическая
система
(алгебра) – пара <G,
M>, где G —
это множество элементов (носитель),
а M – множество операций,
заданных на G (сигнатура).

(n-арная
операция на G задаёт
отображение

на G)

Определение:
Алгебраическая система, образованная
множеством B = {0,1} вместе
со всеми возможными операциями на нем,
называется алгеброй логики.

Функцией
алгебры логики
(или логической
функцией) от
n
переменных
называется n-арная
операция на В. Эта функция может принимать
значения 0 или 1. (т.о. задаёт отображение
B^n -> B)

Чаще
всего под алгеброй логики понимают
алгебру, сигнатура которой включает 3
операции: отрицание, конъюнкцию и
дизъюнкцию.

Основные функции алгебры логики:

x1

u1

u2

u3

u4

0

0

0

1

1

1

0

1

0

1

Унарные:

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

u3
Отрицание:

(читается: не-А)

Бинарные:

Всего
существует 16 бинарных функций алгебры
логики:

x1

x2

b1

b2

b3

b4

b5

b6

b7

b8

b9

b10

b11

b12

b13

b14

b15

b16

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

b2
Конъюнкция:

(читается А и В)

b8
Дизъюнкция:

(А или В)

b12
Импликация:

(из А следует В)

Результат
импликации ложен только тогда, когда
исходное (А) высказывание ложно, а
результат (B) истинен.

Примеры:
(x делится на 4) -> (x
делится на 2), Если 2*2 = 5 то 2*2 = 4

b10
Эквиваленция:

,


равносильно В)

Результат
эквиваленции есть истина, если A
и B одновременно истины
либо ложны (Иными словами, если A=B)

b7
сложение по модулю или
неравнозначность, x1x2

Результат
сложения по модулю истинен, если истинно
лишь одно из A и B
(То есть, если A
B)

b9
cтрелка Пирса
x1x2
(«или-не»). Результат этой операции
равносилен последовательному применению
операций дизъюнкции и отрицания

b15
штрих Шеффера обозначается x1x2,
«и-не». Результат этой операции
равносилен последовательному применению
операций конъюнкции и отрицания.
Соответственно, результирующее
высказывание будет ложным, только если
входящие в него высказывания одновременно
истинны. Штрих Шеффера — это операция
замечательная тем, что её одной
(необходимое количество раз применённой)
достаточно, чтобы записать любое
сложное высказывание. Является основной
операцией в электронике.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #

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

Предисловие

Учебное пособие предназначено для студентов-бакалавров, по направлениям «Информатика и вычислительная техника», «Программная инженерия», «Информационная безопасность», студентов, обучающихся по специальности «Применение и эксплуатация автоматизированных систем специального назначения» и схожим направлениям и специальностям на начальном периоде обучения.

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

Для изучения данного учебного пособия, с одной стороны, не требуется каких-либо специальных знаний, но, с другой стороны, пособие призвано показать, как традиционные понятия и алгоритмы, преломляются при проектировании реальных вычислительных устройств в зависимости от тех целей, которые перед этим устройством ставятся: минимизация оборудования или используемой элементной базы, минимизация времени выполнения какой-либо команды или упрощения используемого устройства управления, АЛУ и других критериев.

В пособии приводятся основные понятия алгебры логики. Особое внимание уделяется тем элементарным логическим функциям, которые находят наибольшее распространение в ЭВМ: конъюнкция, дизъюнкция, штрих Шеффера, стрелка Пирса, сумма по модулю два и их основным эквивалентностям.

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

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

При рассмотрении арифметических основ ЭВМ даны понятия системы счисления, определены правила перевода смешанных чисел между различными системами счисления. Особое внимание уделено часто встречающемуся в вычислительной технике механизму быстрого перевода чисел между системами счисления с основаниями, связанными между собой соотношениями p = q±2, например, 16=24. Представлены диапазоны, погрешности и, соответственно, области применения чисел с фиксированной запятой, фиксированной точкой, плавающей запятой.

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

Весь материал проиллюстрирован большим количеством примеров, которые позволят на практике закрепить изложенные в пособии теоретические положения.

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

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

1.2 Булевы функции

Основным объектом дискретной математики являются булевы функции. Предпосылкой их введения служат высказывания, которые составляют основную базу для построения теории булевых функций.

1.1 Логические операции. Алгебра логики – самый простой раздел математической логики. Язык алгебры логики является одним из простейших языков математики. Основными объектами данного раздела являются высказывания. Понятие «высказывание» является первичным, оно не определяется, а поясняется. Под высказыванием понимают предложение, о котором можно сказать одно из двух: истинно оно или ложно. Например, высказывание «2+3=5» – истинное, высказывание «существует действительное число Х такое, что

Х2 = –1» ложное. Очевидно, не каждое предложение является высказыванием. Например, предложения: «Когда ты был дома?», «Пойдем со мной!» не являются высказываниями. Высказывания будем обозначать малыми латинскими буквами X, y, z,…, а их значения, т. е. истину и ложь, соответственно 1 и 0. Из двух данных высказываний с помощью связок «не», «и», «или», «если … то», «тогда и только тогда, когда …» можно образовать новые высказывания. Например, из высказываний «число 2 простое», «число 2 четное» с помощью указанных выше связок получаем высказывания «число два простое и четное», «число 2 непростое», «число 2 простое или четное». Высказывание «если π иррационально, то π2 тоже иррационально» получается связыванием двух высказываний связкой «если … то». Эти операции соответствуют упомянутым выше связками, употребляемым в обычной речи.

Рассмотрим примеры логических операций.

1. Логическая операция, соответствующая связке «и», называется Конъюнкцией и обозначается &. В некоторых книгах эту операцию обозначают символом . Пусть X и y – высказывания. Высказывание X×y назовем конъюнкцией X И Y. Данное высказывание истинно тогда и только тогда, когда истинны оба высказывания X и Y.

Соответствующее определение запишем в виде таблицы истинности

X

Y

Xy

0

0

0

0

1

0

1

0

0

1

1

1

Определение конъюнкции двух высказываний естественным образом распространяется на любое конечное число высказываний.

Конъюнкция X1x2…xn, которую мы кратко обозначим через , истинна тогда и только тогда, когда истинны все высказывания.

2. Логическая операция, соответствующая связке «или», называется Дизъюнкцией и обозначается .

Пусть X и Y – высказывания. Высказывание XÚY назовем дизъюнкцией X и Y. Данное высказывание истинно тогда и только тогда, когда хотя бы одно из высказываний X и Y истинно.

Данное определение запишем в таблицы истинности.

X

Y

XY

0

0

0

0

1

1

1

0

1

1

1

1

Определение дизъюнкции двух высказываний естественным образом распространяется на любое конечное число высказываний. Дизъюнкция XX2 Ú … Ú XN, которую мы кратко обозначим через , истинна тогда и только тогда, когда хотя бы одно из высказываний X1, X2, …, XN истинно.

3. Логическая операция, соответствующая связке «не», называется Отрицанием.

Отрицание высказывания X записывается так: и определяется следующей таблицей истинности:

X

0

1

1

0

4. Логическая операция, соответствующая связке «если … то», называется Импликацией. Эту операцию будем обозначать символом _. При этом высказывание «если X, то Y» записывается в виде x_Y. Высказывание X называется посылкой импликации, Y – ее заключением. Импликация двух высказываний X и Y задается следующей таблицей истинности:

X

Y

X_Y

0

0

1

0

1

1

1

0

0

1

1

1

Из определения импликации вытекает, что:

· импликация с ложной посылкой всегда истинна;

· импликация с истинным заключением всегда истинна;

· импликация ложна тогда и только тогда, когда посылка истинна, а заключение ложно.

5. Логическая операция, соответствующая связке «тогда и только тогда, когда …» называется Эквивалентностью и обозначается символом n.

Пусть X и Y – высказывания. Высказывание XNY назовем эквивалентностью X и Y. Данное высказывание истинно тогда и только тогда, когда оба высказывания X и Y или истинны или ложны.

Данное определение запишем в виде таблицы истинности:

X

Y

XNY

0

0

1

0

1

0

1

0

0

1

1

1

1.2 Булевы функции. Пусть исходный алфавит переменных.

Функцией алгебры логики От переменных называется функция, принимающая значения 1, 0 и аргументы которой также принимают значения 1, 0.

Обычно функции алгебры логики называют булевыми функциями. Название «булевы функции» возникло в связи с использованием функций рассматриваемого типа в алгебре логики, начало которой было положено трудами ирландского ученого 19 века Дж. Буля. Областью определения булевой функции от n переменных служат совокупность всевозможных n-мерных упорядоченных наборов , где .

Следует отметить, что любой такой набор можно рассматривать как представление некоторого целого неотрицательного числа в двоичной системе счисления. Например, набору (0,1,0,1) соответствует число , а набору (1,1,1) – число .

Все наборы размерности n нумеруются целыми числами от 0,2n-1. Отсюда нетрудно заметить, что число таких наборов равно 2n.

Всякая булева функция от n переменных может быть задана с помощью таблицы истинности:

Таблица 1

X1

X2

XN-1

XN

F(X1,X2,…,XN-1,XN)

0

0

0

0

F (0,0,…,0,0)

0

0

0

1

F (0,0,…,0,1)

0

0

1

0

F (0,0,…,1,0)

1

1

1

1

F (1,1,…,1,1)

Данная таблица состоит из 2n строк, причем в ней все наборы расположены в порядке возрастания их номеров.

Очевидно, что булевы функции от n переменных однозначно определяются своими последними столбцами из таблицы 1, т. е. наборами из 2n нулей и единиц. Следовательно, различных булевых функций от n переменных будет столько, сколько имеется различных наборов длины 2n, а их число равно . Итак, мы доказали следующую теорему:

Теорема 1. Имеется точно Булевых функций от Переменных.

В алгебре логики особое значение имеют следующие булевы функции, которые называют элементарными булевыми функциями.

— константа 0;

— константа 1;

— тождественная функция;

— отрицание х;

— конъюнкция X и y;

— дизъюнкция х и у;

— импликация х и у;

— эквивалентность х и у;

— сложение х и у по mod2;

— функция Шеффера;

— стрелка Пирса.

Последние три функции задаются следующими таблицами истинности:

0

0

0

1

1

0

1

1

1

0

1

0

1

1

0

1

1

0

0

0

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

Переменная XI в функции называется Фиктивной, если = при любых значениях остальных переменных. В этом случае функция , по существу, зависит от (n-1) – переменной, т. е. представляет собой функцию от (n-1) переменной. Говорят, что функция g получается из функции f удалением фиктивной переменной, а функция f получается из g введение фиктивной переменной, причем эти функции являются равными.

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

< Предыдущая   Следующая >

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *