Алгебра логики. История возникновения. Основные положения

Федеральное агентство по образованию Российской Федерации

Государственное образовательное учреждение высшего профессионального образования

«Южно-Уральский государственный университет»

Факультет «Механико-технологический»

Кафедра «Автоматизация механосборочного процесса»

 

 

 

 

 

 

 

 

Алгебра логики. История возникновения. Основные положения. 
 
РЕФЕРАТ 
по дисциплине «Информатика»

 

 

 

 

 

 

 

 

Проверил, (доцент) 
_______________ Абросимов Е.Н. 
_______________ 20__ г. 

Автор работы 
студент группы МТ-177 
_______________ Безменов К.Э. 
_______________ 20__ г. 
 
Реферат защищен 
с оценкой (прописью, цифрой) 
_____________________ 
_______________ 20__ г.

 

Аннотация

Безменов К.Э., Алгебра логики. История возникновения. Основные положения., Челябинск: ЮУрГУ, МТ-177, 2012, 20 с, 4 рис., 4 табл., библиографический список – 5 наим.

Цель реферата – выяснить суть алгебры логики, основных методов работы с логическими операторами, роль логики в вычислительной технике и информатике. Для выполнения этой работы потребовалось найти методические материалы по теме, решить некоторые опытные задачи и сделать выводы. Предмет исследования - операции над логическими функциями.

 

Оглавление

 

 

 

 

 

Введение

 

Понятие логики как науки появилось ещё в  XIX в., т.е. задолго до появления науки информатики и компьютеров. Элементы математической логики можно найти уже в работах древнегреческих философов. В XVII в. Г. В. Лейбниц высказал идею о том, что рассуждения могут быть сведены к механическому выполнению определенных действий по установленным правилам. Однако как самостоятельный раздел математики логика начала формироваться только с середины XIX в..

Для того чтобы рассуждать, человеку необходим какой-либо язык. Не удивительно, что математическая логика начиналась с анализа того, как говорят и пишут люди на естественных языках. Этот анализ привёл к тому, что выяснилось существование формулировок, которые невозможно разделить на истинные и ложные, но, тем не менее, выглядят осмысленным образом. Это приводило к возникновению парадоксов, в том числе в одной из фундаментальных наук математики. Тогда было решено создать искусственные формальные языки, лишённого «вольностей» языка естественного.

1. ВОЗНИКНОВЕНИЕ ЛОГИКИ

 

Понятие логики как науки появилось ещё в  XIX в., т.е. задолго до появления науки информатики и компьютеров. Элементы математической логики можно найти уже в работах древнегреческих философов. В XVII в. Г. В. Лейбниц высказал идею о том, что рассуждения могут быть сведены к механическому выполнению определенных действий по установленным правилам. Однако как самостоятельный раздел математики логика начала формироваться только с середины XIX в..

Для того чтобы рассуждать, человеку необходим какой-либо язык. Не удивительно, что математическая логика начиналась с анализа того, как говорят и пишут люди на естественных языках. Этот анализ привёл к тому, что выяснилось существование формулировок, которые невозможно разделить на истинные и ложные, но, тем не менее, выглядят осмысленным образом. Это приводило к возникновению парадоксов, в том числе в одной из фундаментальных наук математики. Тогда было решено создать искусственные формальные языки, лишённого «вольностей» языка естественного.

 

2. БУЛЕВЫ ФУНКЦИИ

 

Пусть имеется некоторый набор высказываний, о которых можно говорить определённо, что они истинные или ложные. Обозначим их латинскими буквами A, B, C, D … .

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

- знак дизъюнкции v

- знак конъюнкции & (иногда используется ^)

Таким образом, из утверждений A, B с помощью знаков дизъюнкции и конъюнкции получим новые утверждения:

- A v B («A или B»)

- A & B («A и B»)

Утверждение A v B считается истинным тогда и только тогда, когда истинно хотя бы одно из исходных утверждений; утверждение A & B – когда истинны оба утверждения.

Дизъюнкцию и конъюнкцию можно рассматривать как особые операции, определённые не на числах, а на логических значениях ИСТИНА и ЛОЖЬ. Для этих операций существуют таблицы, подобные таблице умножения. (табл. 1, 2)

                                                  Таблица 1

A	B	A v B
ИСТИНА ИСТИНА ЛОЖЬ ЛОЖЬ	ИСТИНА ЛОЖЬ ИСТИНА ЛОЖЬ	ИСТИНА ИСТИНА ИСТИНА ЛОЖЬ

 

Таблица 2

A	B	A & B
ИСТИНА ИСТИНА ЛОЖЬ ЛОЖЬ	ИСТИНА ЛОЖЬ ИСТИНА ЛОЖЬ	ИСТИНА ЛОЖЬ ЛОЖЬ ЛОЖЬ

                                                        

Логические значения ИСТИНА и ЛОЖЬ называют также булевыми значениями – в честь английского математика Джорджа Буля, который в XIX в. заложил основы современной математической логики. Функции с булевыми аргументами называют булевыми функциями. Всего булевых функций от 2 переменных – 16. Для всех булевых функций от двух переменных имеются соответствующие конструкции на русском языке. В информатике в основном используются следующие булевы функции:

- логическое ИЛИ (дизъюнкция)

- логическое И (конъюнкция)

- логическое отрицание («НЕ», обозначается ~ и противоположно своему аргументу)

- исключающее ИЛИ

Из этих основных складываются комбинированные функции: ИЛИ-НЕ, И-НЕ. Именно они получили наибольшее распространение в логической электронике, в компьютерах.

 

3. СПОСОБЫ ЗАДАНИЯ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ

 

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

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

Таблица истинности содержит 2n строк, n+m  столбцов (количество входов n+количество выходов m).

Например: пусть требуется задать функцию двух переменных, т.е. дискретное устройство на два входа и на один выход, следовательно, число столбцов = 2+1, а число строк = 4. (табл. 3)

Таблица 3

x	y	A
0	0	0
1	0	0
0	1	0
1	1	1

 

  

 

 

 

 

 

 

Таблицы истинности возможно составить по условиям задания. Задание на управление для выше приведенного примера может выглядеть следующим образом: лампа А горит только тогда, когда одновременно нажаты обе кнопки x и y.

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

Словесно-аналитический способ задания функции алгебры логики. При этом способе функция задается в виде аналитического выражения.В левой части высказывания указывается действие управляемого привода (или исполнительного устройства), а в правой части- условие, при котором выполняется это действие.

Аналитическое выражение задается в возможно более краткой форме. Некоторые подразумеваемые слова могут опускаться, например, такие как «кнопка», «нажать», «активен» и другие. Название датчиков и кнопок возможно заменять их схемным обозначением. При этом указание на датчик означает то, что этот датчик изменил свое состояние на активное (логическая 1). Ударение делается на союзы предложения, которые, в большинстве случаев, указывают на логическое действие.

Графические способы. Для графического описания логических взаимодействий можно использовать разные способы, предлагаемые стандартом IEC 848: шаговая, временная диаграмма, логические функциональные схемы, функциональный план.

При взаимодействии нескольких приводов наиболее наглядным средством установления логических взаимосвязей является шаговая диаграмма. (рис. 1) 

 

 

 

 

 

 

 

 

 

 

Рисунок 1

 

 

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

 

 

             

Рисунок 2

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

Из диаграммы следует, что лампа Н1 «горит» тогда, когда нажата кнопка S1 и не нажата кнопка S2.

Лампа Н2 «горит» тогда, когда нажата кнопка S2 и не нажата кнопка S1.

Логические функциональные блок-схемы состоят из логически связанных между собой отдельных функциональных блоков, которые являются обозначениями элементарных логических функций. (рис. 3)

 

 

 

 

 

 

 

 

 

Рисунок 3 

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

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

 

 

 

 

          

Рисунок 4

Математическое представление алгебры логики. Элементарные логические действия можно представить с помощью специальных или арифметических символов (AND:Ù, · ;OR: Ú, +; NO:a`), обозначающих логические действия. Используя законы алгебры логики, возможны преобразования математических выражений логических функций.

Представление логического взаимодействия в электротехнике. Логические взаимодействия сигналов возможно реализовать через определенное соединение контактов. Существует язык программирования, который использует логические свойства соединения контактов.

 

4. ПРЕОБРАЗОВАНИЕ ВЫРАЖЕНИЙ, СОСТОЯЩИХ ИЗ БУЛЕВЫХ ФУНКЦИЙ

 

В математической логике преобразование выше указанных выражений проводится для различных целей – от упрощения исходного до доказательства утверждений. В информатике же оно используется в основном для упрощения, ведь при производстве цифровой электроники, как и любого другого товара, требуются наименьшие затраты. Для упрощения булевых выражений используются те же методы, что и при упрощении алгебраических. Для начала была проведена аналогия между алгебраическими операторами от двух аргументов (сложение, вычитание, умножение и т.д.) и булевыми. Было выяснено, что умножение и логическое «И» обладают сходными свойствами:

            - от перестановки мест аргументов результат не изменяется

A & B = B & A

- существует следующий закон

A & (B & C)  = (A & B) & C

Также существуют некоторые тождества, опирающиеся на особые свойства функции, например:

1) A & (~A) = ЛОЖЬ

2) (~A) & (~B) = ~ (A v B)

Аналогично, сложение и логическое «ИЛИ»:

- от перестановки мест аргументов  результат не изменяется

A v B =  B v A

- существует следующий закон

(A v B) v С = A v (B v C)

- можно выносить общий множитель за скобки

(A & B) v (С & B) = B & (A v C)

И также некоторые собственные законы:

1) A v (~A) = ИСТИНА

2) (~A) v (~B) = ~ (A & B)

Когда вычисляется значение булевого выражения, то выполняется определённая очерёдность действий: на очерёдность влияют скобки, сначала считаются «И», затем «ИЛИ». Благодаря этой очерёдности возможно создание электронных цифровых схем.

 

 

5. НАХОЖДЕНИЕ ИСХОДНОГО ВЫРАЖЕНИЯ

 

В отличие от алгебраических выражений, булевы можно восстановить, зная их аргументы и соответственные им значения. Пусть нам дана булева функция от 3 переменных (табл. 4):