[20.07 ждём вас!] Конференция «Цифровые компетенции современного педагога» Подтвердить участие→
Конкурс разработок «Пять с плюсом» июль 2021
Добавляйте свои материалы в библиотеку и получайте ценные подарки
Конкурс проводится с 1 июля по 31 июля

Лекция "Алгебра логики"

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

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

Введение в логику

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

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

Слово «логика» происходит от греческого слова «logos», что означает «мысль, мышление, смысл, разум»[4]. Как наука, логика сформировалась в Древней Греции. Ее основателем является древнегреческий философ Аристотель (384-322 гг. до н. э.). В своих логических трудах, получивших общее название «Органон», Аристотель впервые обстоятельно проанализировал и описал основные логические формы и правила рассуждений [6].Логика Аристотеля – это так называемая формальная логика. Формальная логика связана с анализом наших обычных содержательных рассуждений, выражаемых разговорным языком[5].

Со временем логика формальная перешла в логику математическую. Она отличалась тем, что в ней не использовались словесные формы записи рассуждений. Все большее значение принимали символическое (с помощью чисел, букв, символов) выражение этих рассуждений [6]. Отцом основателем математической логики является выдающийся немецкий философ-математик Г.В. Лейбниц. Он предложил применить бинарную, то есть двоичную, систему счисления для целей вычислительной математики [3]. В XIX в. Появился раздел математической логики – алгебра логики, которая оперирует с двоичными переменными, принимающие только два значения – «истина» или «ложь». Данный раздел логики и является объектом нашего исследования.

Формальная логика

 

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

Примеры высказываний: «Звезды видны на небе только ночью», «Земля покоится на трех книгах», «В Ленинградскойобласти летом температура не достигает отметки -20˚С», «Ель летом зеленая».

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

  •                 С помощью языка математических символов –«5×5˃16»
  •                 С помощью физических формул – «S = V × T» и т.д.

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

«Не играй с огнем!», «Ты спокоен?», «Все в порядке?»

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

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


Логические связки и кванторы

Название логических связок и кванторов

Примеры высказываний

…и...

…а…

…но…

Конъюнкция

(логическое умножение)

Налетел ветер, и пошел дождь

... или …

либо …, либо …

или …, или ...

Дизъюнкция соединительная(логическое сложение)

За отличную учебу в школе я получу золотую или серебряную медаль

либо …, либо…

либо только…, либо только…

только … или только ….

Дизъюнкция разъединительная(строгая дизъюнкция)

Я поеду только в дом отдыха или на турбазу

не;

неверно, что …

 

Инверсия(логическое отрицание)

Мы не умеем читать.

Неверно, что Земля –спутник Венеры

Если …, то …

из ... следует …

… достаточно для …

Импликация

(логическое следование)

Если будет солнечно,

то мы отправимся на пляж

… только и только тогда, когда …

…если и только если …

…необходимо и достаточно …

Эквивалентность

(логическое равенство)

 

Я поеду в Таиланд тогда и только тогда, когда приобрету путевку

все, всякий, каждый

 

 

Квантор общности

 

 

Все люди любят мир.

Каждый ребенок мечтает вырасти

некоторые; существуют

 

Квантор существования

Некоторые коты – черные.

Существуют ядовитые растения

 

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

В алгебре логики простые высказывания заменяют логическими переменными, которые обозначаются буквами латинского алфавита, причем значениями переменных могут быть только 0 и 1 [1]. Логические связки заменяются соответствующими им математическими символами. При этом сложное высказывание превращается в логическую функцию[9].

Логической функцией F от набора логических переменных (a,b,c …) называется функция, которая может принимать только два значения: 0 и 1.

Таблица истинности функции зависит от количества переменных этой функции и содержит наборов переменных. Для функции F (a,b), таблица истинности состоит из 4 наборов переменных. Логические значения называют так же значениями истинности. В алгебре логики в качестве операций используются конъюнкция, дизъюнкция, строгая дизъюнкция, инверсия, импликация и эквивалентность. Рассмотрим подробнее эти операции.

Конъюнкция – логическая операция, по смыслу максимально приближенная к союзу «и». Синонимы: логическое «И», логическое умножение, иногда просто «И» [4]. Обозначается ^, ·,&.

Пример высказывания: «Светит солнце, и дует легкий ветерок». Логические переменные: а = «Светит солнце» и b = «Дует легкий ветерок». Функция:

 

 


F(a, b) = a ^ b

 

a

b

a ^ b

0

0

0

0

1

0

1

0

0

1

1

1

 

Дизъюнкция– логическая операция, по своему применению максимально приближённая к союзу «или» в смысле «или то, или это, или оба сразу».

Пример высказывания: «Работодатель – физическое лицо либо юридическое лицо». Логические переменные a = «физическое лицо»;b = «юридическое лицо».  Функция:

F(a, b) = a˅ b

a

b

a ˅ b

0

0

0

0

1

1

1

0

1

1

1

1

 

Строгая дизъюнкция –суждение, в котором связка «или» употребляется в разделительном значении.Обозначение:.

Пример: «Фрукты используются либо в сыром либо в консервированном виде». Логические переменные: а=«Фрукты используются в сыром виде» и b = «Фрукты используются в консервированном виде». Функция:

 

 

F(a, b) = ab

 

a

b

a b

0

0

0

0

1

1

1

0

1

1

1

0

 

Инверсия – если исходное выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное выражение ложно, то результат отрицания будет истинным. Данная операция означает, что к исходному логическому выражению добавляется частица не или слова неверно, что. Обозначения: ̄,˥

Пример высказывания: « Я не буду пропускать уроки». Логическая переменная: а = « Я буду пропускать уроки». Функция:

F(a) = ˥ а.

а

˥ а

0

1

1

0

 

Импликация – связывает два простых логических выражения, из которых первое является условием (а), а второе (b)– следствием из этого условия. Результатом Импликации является ЛОЖЬ только тогда, когда условие (а) истинно, а следствие (b) ложно. Обозначается символом  "следовательно"  и  выражается словамиесли…, то…Обозначения:

Пример высказывания: « Если в субботу к нам приедет бабушка, то мы устроим праздник». Здесь логическая переменная а = «Если в субботу к нам приедет бабушка» является условием, алогическая переменная b = «Мы устроим праздник» – заключением.

F(a, b) = а b

a

b

а b

0

0

1

0

1

1

1

0

0

1

1

1

 

Эквивалентность– определяет результат сравнения двух простых логических выражений а и b. Результатом эквивалентности является новое логическое выражение, которое будет истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны. Обозначения:,.

Пример высказывания: «При делении одного числа на другое в результате получается ноль тогда и только  тогда, когда делимое равно нулю». Логические переменные: а = «При делении одного числа на другое в результате получается ноль» b = «Делимое равно нулю». Функция:

F(a, b) = а b

a

b

а b

0

0

1

0

1

0

1

0

0

1

1

1

 

 

 

Вычисления функций по таблицам истинности

 

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

Рассмотрим сложное высказывание: «Аня промочила ноги, и у нее заболело горло». Здесь связка «и» определяет конъюнктивную связь двух высказываний. Составим таблицу истинности.

 

Аня промочила ноги

У нее заболело горло

Аня промочила ноги, и у нее заболело горло

Ложь

Ложь

Ложь

Ложь

Истина

Ложь

Истина

Ложь

Ложь

Истина

Истина

Истина

 

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

Вычисление значение функции по таблице истинности:

 

 

 


F(a, b) = ˥ (а ^ b) ^ (a ^ ˥b)

a

b

а ^ b

˥ (а ^ b)

˥ b

(a ^ ˥ b)

F(a, b)

0

0

0

1

1

0

0

0

1

1

0

0

0

0

1

0

1

0

1

1

0

1

1

1

0

0

0

0

 

Из таблицы истинности видно, что при любых наборах логических переменных функция F(a, b) тождественно равна нулю.

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

Законы и функции алгебры логики

 

Применение законов логики позволяет сокращать количество переменных в логических выражениях. Сокращенные с помощью законов логики логические выражения называют минимизированными.

 

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

Закон

Представление в алгебре логики

1

Переместительный (коммуникативный)

a ^ b = b ^ a; b ˅ a = a ˅ b

2

Сочетательный (ассоциативный)

a ˅ (b ˅ c) = (a ˅ b) ˅ c;                              (a ^ b) ^ c = a ^ (b ^ c)

3

Распределительный (дистрибутивный)

a ˅ (b ˅ c) = (a ^ b) ˅ (a ^ с);                    a ^ (b ^ c) = (a ˅ b) ^ (a ˅ с)

4

Законы де Моргана

˥ (а ^ b) = ˥ a ˅ ˥ b; ˥ (а ˅ b) = ˥ a ^ ˥ b

5

Закон двойного отрицания (инволюции)

 

˥ ˥ a = a

6

Операции с переменной и ее инверсией

a ^˥ a = 0: ^˥ a = 1

7

Свойство операций конъюнкции и дизъюнкции

a ˅ 1 = 1; a ^ 1 = a; a ˅ 0 = a; a ^ 0 = 0

8

Законы идемпотентности

a ˅ a = a; a ^ a = a

9

Законы поглощения

a ˅ (a ˅ b) = a; a ^ (a ^ b) = a

 

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

x

у

х | у

0

0

1

0

1

1

1

0

1

1

1

0

 

 

 

 

 

 

 

 

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

Еще одним важным законом алгебры логики является закон двойственности. Пусть формула A содержит только операции конъюнкции, дизъюнкции и отрицания. Для операции конъюнкции двойственной считается дизъюнкция, а для дизъюнкции – конъюнкция. Тогда по определению формулы A и A* называются двойственными, если формула A* получается из Aпутем замены в ней каждой операции на двойственную. Например, для формулы (хy) z двойственной формулой будет (хy) z. Для двойственных формул справедлива следующая теорема: если формулы Aи Bравносильны, то равносильны и двойственные им формулы, то есть A* = B*. Данную теорему оставим без доказательства.

С помощью законов логики можно осуществлять равносильные преобразования. Такие преобразования используются для доказательств, приведения формул к заданному виду, упрощения формул.

Под сложностью формул обычно понимается количество символов, используемых для ее записи. То есть формула α проще формулы , если α содержит меньше букв и логических операций. Например, для формулы ( (xy) xy) y можно записать следующую цепочку преобразований, приводящих ее к более простому виду:

( (xy) xy) y = (xyxy) y = (xy) y = y.

 

Логические элементы, схемы

 

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

1.Элемент И реализует конъюнкцию и поэтому его называют конъюнктором. Единица на выходе элементаИ будет только тогда,когда на всех входах будут единицы,отсюда ещё одно название – элемент совпадения.

 

a

b

a ^ b

0

0

0

0

1

0

1

0

0

1

1

1

 

 

 

 

 

 

2.Элемент ИЛИ реализует дизъюнкцию, поэтому его ещё называют дизъюнктором. Единица на выходе элемента ИЛИ будет тогда, когда хотя бы на одном входе будет единица.

a

b

a b

0

0

0

0

1

1

1

0

1

1

1

1

 

 

 

 

 

 

 

3.Элемент НЕ реализует инверсию, поэтому его ещё называют инвертором.

Единица на выходе элемента НЕ будет тогда, когда на входе будет ноль.

 

 

 

a

˥ a

0

0

1

0

 


 

 

 

 

На основе этих базовых логических элементов строятся другие логические элементы и схемы. Рассмотрим, например элементы И –НЕ и ИЛИ – НЕ.

4. Элемент И – НЕ состоит из элемента И и инвертора и осуществляет инверсию результата схемы  И. Ноль на выходе элемента И – НЕ будет только тогда,когда на всех входах будут единицы.Еще одно название элемента –элемент Шеффера.

a

b

˥ (a ^ b)

0

0

1

0

1

1

1

0

1

1

1

0

 

 


 

 

 

 

5.Элемент ИЛИ – НЕ состоит из элемента ИЛИ и инвертора и осуществляет инверсию результата схемы ИЛИ. Единица на выходе элемента будет тогда и только тогда,когда на всех водах будут нули.Еще одно название элемента –элемент Пирса.

 

 

 

a

b

˥ (a ^b)

0

0

1

0

1

0

1

0

0

1

1

0

 



 

 

Реальные логические элементы работают с реальными физическими сигналами. Существуют различные физические способы кодирования двоичной информации,но чаще всего за год 1 принимается более высокий уровень напряжения (от 2,5 до 5 В), чем  ноль (от 0 до 0,5 В).

Рассмотрим пример.

Схеме соответствует таблица истинности. Анализируя таблицу истинности, приходим к выводу, что следующая схема реализует импликацию.

 

 

 

 

 

 

a

b

˥ b

˥ b ^ a

˥ (˥ b ^ a)

0

0

1

0

1

0

1

0

0

1

1

0

1

1

0

1

1

0

0

1

 

 

 

 

 

Пример 2

Определить, какую функцию реализует схема

 

 

 

 

 

 

 

 

 

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

F (a, b, c) = ˥ (b ^ ˥ cac)

Пример 3

По заданной функции  F(a, b)=˥ a^ba^ ˥ba^bпостроить логическую схему.

Для построения логической схемы нам потребуется: 2 инвертора, 3 конъюктора, 2 дизъюнктора.

Функции:

F(a, b) = ˥ a ^ b,   F(a, b) =a ^ ˥ b

реализуется схемами:

 

 

 

 

 

 

 

  

Используя  указанные схемы, конъюктор и 2 дизъюнктора, получим схему функции

F(a, b) = ˥ a ^ b a ^ ˥ b a ^ b

 

 

 

 

 

 

 

 

 

Пример 4.

Рассмотрим схему элемента с памятью – триггера. Триггеры способны находиться в двух устойчивых состояниях и хранить 1 бит информации. Триггеры строятся на логических элементах Шеффера и Пирса. Устойчивая структура получается  соединением элементов с введением обратной связи Условное обозначение триггера представлено на схеме:

 

 

 

 

 

 

 

 

 

 

 

 

Триггер имеет два входа: R-вход – вход установки схемы в нулевом состояние, S- вход – вход записи единицы, установка в единичное состояние. При нулевом состоянии триггера  на входе Q нулевой сигнал (Q = 0), на выходе Q – единичный  (Q = 1). Это прямой или инверсный выходы триггера.

Зная работу элемента ИЛИ-НЕ, можно проследить работу триггера при подаче на установочные входы сигналов S = 1 и R = 1, запоминание и хранение поданной информации.

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

Поскольку один триггер может запомнить только один разряд двоичного кода, то для запоминания байта нужно 8 триггеров, для запоминания килобайтов, соответственно – 8× = 8192 триггеров. Современный микросхемы памяти объемом менее 1 содержат миллионы триггеров.

 

 

 

 

 

 

 

 

 

F = (b ^ a) (ba) (ba)

 

1

 

Информация о публикации
Загружено: 21 мая
Просмотров: 167
Скачиваний: 0
Анисимова Александра Вадимовна
Информатика, Прочее, Уроки

Проверьте знания своих учеников интересными заданиями

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

Скачать материал