Элементы алгебры логики icon

Элементы алгебры логики


НазваниеЭлементы алгебры логики
Размер9.11 Kb.
ТипДокументы

Информатика 2011 - Тема 2 – Элементы алгебры логики

Элементы алгебры логики


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

Дж. Буль – английский математик 19 века. Булева алгебра оперирует с логическими переменными, которые могут принимать только 2 значения: истина и ложь, обозначаемые соответственно 1 и 0.

 Совокупность значений логических переменных , ,…, называется набором переменных. Набор логических переменных удобно изображать в виде n-разрядного двоичного числа, каждый разряд которого равен значению одной из переменных. Количество наборов логических переменных в n двоичных разрядах равно 2n.

 Логической функцией от набора логических переменных f(,…, ) называется функция, которая может также принимать только 2 значения: истина или ложь.

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

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

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

^ Наиболее часто используемая система логических функций: инверсия (, отрицание, NOT), конъюнкция (Ù, логическое умножение, AND, &), дизъюнкция (, логическое сложение, OR).


Конъюнкция

x1

x2

x1Ùx2

0

0

0

0

1

0

1

0

0

1

1

1






Инверсия

x

 x

0

1

1

0




Дизъюнкция

x1

x2

x1Úx2

0

0

0

0

1

1

1

0

1

1

1

1


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

f(x1, x2, x3) = (x1Ùx2 Ú x2Úx3) Ùx1Ú`x3;

f(0, 1, 1) = (0Ù1Ú1Ú1) Ù0Ú`1= 0;

f(1, 0, 1) = (1Ù0Ú0Ù1)Ù1Ú`1 =1.

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

  1. Коммуникативный закон (переместительный):

x1Úx2=x2Úx1

x1Ùx2=x2Ùx1

  1. Ассоциативный закон (сочетательный):

x1Ú(x2Úx3) = (x1Úx2)Úx3

x1Ù(x2Ùx3) = (x1Ùx2)Ùx3

  1. Дистрибутивный закон (распределительный):

x1Ù(x2Úx3) = (x1Ùx2)Ú(x1Ùx3)

x1Ú(x2Ùx3) = (x1Úx2)Ù(x1Úx3)

  1. Правила де Моргана:

x1Úx2 = `x1Ù`x2

x1Ùx2 = `x1Ú`x2

  1. Правила операций с константами:

`0 = 1; `1 = 0; xÙ1 = x; xÙ0 = 0; xÚ0 = x; xÚ1 = 1.

  1. Правила операций переменной с ее инверсией:

xÚ`x = 1;

xÙ`x = 0;

  1. Закон поглощения:

x1Ú(x1Ùx2) = x1;

x1Ù(x1Úx2) = x1.

  1. Закон идемпотентности:

xÚx = x;

xÙx = x;

9. Закон двойного отрицания:

x = x.

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

Похожие:

Элементы алгебры логики iconЭлементы алгебры логики
Для описания логики функционирования аппаратных и программных средств компьютера используется алгебра логики или булева алгебра
Элементы алгебры логики iconЛекции 32часа. Отчетность зачет. Литература
Основные элементы логических функции алгебры логики (или-or,и-and, и- не -and-not, и- или -не-and-or-not)
Элементы алгебры логики icon1. дм функции алгебры логики. Реализация функций формулами. Канонические нормальные формы представления функций
Ф-ия алгебра логики, если переменные x1,…, xn определены на E2 и зн ия ф-ии f на любом наборе переменных принадлежат E2
Элементы алгебры логики iconВариант 3 Задани Составьте таблицы истинности формул. ( ↓ y) │(y ٧ ),( ) ( ) Задание
Задани Найдите минимальные днсф и кнсф булевой функции, заданной вектором своих значений, тремя методами: путем упрощения с помощью...
Элементы алгебры логики iconБИЛЕТ № 1 по курсу «Логико-математические модели в естествознании и экологии»
Понятие логической алгебры и его использование в искусственном интеллекте. Чем логика отличается от алгебры? Алгебраические модели...
Элементы алгебры логики iconУчебник логики Глава I определение и задачи логики определение логики
То мышление, при помощи которого достигается истина, должно быть названо правильным мышлением. Таким образом, логика может быть определена...
Элементы алгебры логики icon1. мл формулы логики предикатов. Общезначимые, выполимые формулы. Основные эквивалентности логики предикатов. Нормальные формы. Логическое следование
Мл формулы логики предикатов. Общезначимые, выполимые формулы. Основные эквивалентности логики предикатов. Нормальные формы. Логическое...
Элементы алгебры логики iconА. О. Маковельский история логики книга
Во второй части исследуются логические теории эпохи феодального общества, в третьей части—логические концепции Нового времени (Декарт,...
Элементы алгебры логики iconЛекция 6 нелинейные реактивные элементы нелинейные индуктивные элементы
Нелинейные индуктивные элементы представляют собой катушки, намотанные на сердечник из ферромагнитного материала
Элементы алгебры логики iconУчебник логики Глава I определение и задачи логики
То мышление, при помощи которого достигается истина, должно быть названо правильным мышлением. Таким образом, логика может быть определена...
Элементы алгебры логики iconНаука о правильности мышления. Предметом логики являются
Этап начало 20 века. Значение логики: Логика развивает логическое мышление человека. Она позволяет глубже отражать окружающий мир,...
Вы можете разместить ссылку на наш сайт:
Документы


При копировании материала укажите ссылку ©ignorik.ru 2015

контакты
Документы