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

ЛОГИКА - это наука правильно рассуждать, наука о формах и законах человеческого мышления. ЛОГИКА - это наука правильно рассуждать, наука о формах и законах человеческого мышления. Логика годах до н.э. Логика наука древняя. Ее основоположником считают древнегреческого мыслителя Аристотеля, жившего в годах до н.э.

Рене Декарт ( ) Рене Декарта. С разработанных в античности логических методов начиналась философия и математика Рене Декарта. Фактически Декарт рекомендовал логике науке о мышлении - логике руководствоваться общепринятыми в математике принципами.

Алгебра логики ( Алгебра логики (другое название - Булева алгебра) - это область дискретной математики. Она оперирует величинами, которые могут принимать два значения (булевых значения): 0,1 F,T false, true ложь, истина Л,И

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

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

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

Понятие высказывания Высказывание – Высказывание – это повествовательное предложение, о котором можно сказать истинно оно или ложно. Высказывание – Высказывание – это языковое образование, в отношении которого имеет смысл говорить о его истинности или ложности (Аристотель).

Примеры высказываний: А. А. «Число 2 является иррациональным». Б. Б. «Неверно, что число 2 является иррациональным». В. В. «Если число 2 является иррациональным, то число 2+1 также является иррациональным».

простым(элементарным), Высказывание называется простым (элементарным), если никакая его часть сама не является высказыванием. «x<12» высказывательными формами. Предложение «x<12» называют высказывательными формами.

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

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

Связка Ее название Ее обозначение Высказывание, получаемое с помощью связки. Его математическая запись И Конъюнкция, логическое умножение &, А и В А&В, А В, А В

конъюнкция таблицей истинности: Логическая операция конъюнкция определяется следующей таблицей истинности: P и q – простые числа pqр & q

Рассмотрим два высказывания: p={Завтра будет мороз} и q={Завтра будет идти снег} Очевидно, новое высказывание p&q={Завтра будет мороз и завтра будет идти снег }

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

Связка Ее название Ее обозначение Высказывание, получаемое с помощью связки. Его математическая запись Или Дизъюнкция, нестрогая дизъюнкция, логическое сложение, +А или В А В, А+В

дизъюнкция таблицей истинности: Логическая операция дизъюнкция определяется следующей таблицей истинности: P и q – простые числа pqp q

Рассмотрим два высказывания: p={Колумб был в Индии} и q={Колумб был в Египте} Новое высказывание p q ={Колумб был в Индии или был в Египте}

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

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

Связка Ее название Ее обозначение Высказывание, получаемое с помощью связки. Его математическая запись Либо… либо Исключающее ИЛИ, разделительная (строгая) дизъюнкция, сложение по модулю 2, не равнозначность, Δ Либо А, либо В А В, А Δ В

разделительная дизъюнкция Логическая операция разделительная дизъюнкция определяется следующей таблицей истинности: pqp q P и q – простые числа

Рассмотрим два высказывания: p={Кошка охотится за мышами} и q={Кошка сидит на диване} Новое высказывание: P q={Либо кошка охотится за мышами, либо сидит на диване }

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

Связка Ее название Ее обозначение Высказывание, получаемое с помощью связки. Его математическая запись Если…то Импликация, следование, Если А, то В А В, А В

pqp q таблица истинности Для импликации таблица истинности выглядит следующим образом: P и q – простые числа

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

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

Связка Ее название Ее обозначение Высказывание, получаемое с помощью связки. Его математическая запись Тогда и только тогда, когда Эквивалентн ость, равнозначность, ~, А тогда и только тогда, когда В А В, А~В, А В

pqp q таблица истинности Для эквивалентности таблица истинности выглядит следующим образом: P и q – простые числа

Рассмотрим возможные значения сложного высказывания, являющегося эквивалентностью: «Учитель утверждает, что 5 в четверти ученику он поставит тогда и только тогда, когда ученик получит 5 на зачете»

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

Связка Ее название Ее обозначение Высказывание, получаемое с помощью связки. Его математическая запись Не Отрицание, инверсия ̅, Не А, А

pне p отрицание таблицей истинности Логическая операция отрицание задается таблицей истинности: P и q – простые числа

Сводная таблица истинности: pqне pP & qP & qp q отрицание конъюнкция дизъюнкция не строгая дизъюнкция строгая импликация эквивалентность

Логические формулы. Законы алгебры логики. Величины и переменные. Булевыми величинами Булевыми величинами (или булевыми константами) называются два заранее выбранных разных символа. Булевыми переменными Булевыми переменными называются переменные, которые могут принимать булевы значения.

Границы применимости 1. Величина должна принимать два возможных состояния, но не более того. 2. В любой момент времени величина не может принимать оба состояния одновременно. 3. В любой момент времени величина не может принимать ни одного состояния. 4. Если рассматриваются несколько таких величин, то допускается, чтобы каждая из них принимала одно из двух состояний независимо. 5. Не допускается применять одну пару состояний для одной величины, а для другой - другую.

Логические переменные Логической переменной латинскими буквами x, y, x1, y1, xk, yk и т.д. Логической переменной называется переменная, значением которой может быть любое наперед заданное высказывание. Логические переменные обозначаются латинскими буквами как обычные алгебраические переменные x, y, x1, y1, xk, yk и т.д.

Определение логической формулы 1) 1) Любая логическая переменная, а также каждая из двух логических констант (постоянных) –0 и 1. 2) 2) Если А и В – формулы, то и (А*В) – тоже формулы, где знак «*» означает любую из логических бинарных операций. равносильными одинаковые значения. Формулы А и В называют равносильными, или эквивалентными, если на любом наборе значений переменных х 1, х 2,х 3, …, хn формулы А и В принимают одинаковые значения.

Законы алгебры логики Закон коммутативности 1) Закон коммутативности X & Y = Y & X X Y = Y X Закон ассоциативности 2) Закон ассоциативности (X & Y) & Z = X & (Y & Z) (X Y) Z = Y (X Z)

Закон поглощения 3) Закон поглощения X 0 = X X & 1 = X Закон дистрибутивности 4) Закон дистрибутивности X & (Y Z) = (X & Y) (X & Z) X (Y & Z) = (X Y) & (X Z)

Закон противоречия 5) Закон противоречия X & = 0 Закон исключенного третьего 6) Закон исключенного третьего X = 1 Закон идемпотентности 7) Закон идемпотентности X & X = X X X = X

Закон де Моргана 9) Закон де Моргана & X (X & Y) = X X & (X Y) = X Закон поглощения 10) Закон поглощения Закон двойного отрицания 8) Закон двойного отрицания = Х

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

АВ A B а) б) дизъюнкции Переключателям, соединенным параллельно, поставим в соответствие операцию дизъюнкции. (рис.а) конъюнкции. Переключателям, соединенным последовательно, поставим в соответствие операцию конъюнкции. (рис.б)

А В D C формулу проводит ток Каждой переключательной схеме можно поставить в соответствие формулу, истинную тогда и только тогда, когда схема проводит ток. Например, формула для схемы:

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

таблицы истинности Функции в булевой алгебре принято определять двумя способами. Первый - с помощью таблицы истинности. Например: xyzf (x, y, z)

xyF1F1 F2F2 F3F3 F4F4 F5F5 F6F6 F7F7 F8F8 F9F9 F 10 F 11 F 12 F 13 F 14 F 15 F Таблица истинности функций в булевой алгебре:

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

Унарные операции Отрицание: x~ x~ x Другие названия этой функции: "инверсия", "обращение", "НЕ", "логическое НЕ". Другие обозначения этой функции: X, ~X, NOT X, HE X

Тождественная функция: xx Ноль: x Единица: x

~(F), "~" константа или переменная сложная формула Общий формат выглядит как ~(F), где F - некоторая формула. Для вычисления значения формулы ~(F) надо вычислить значение формулы F, подставить его в таблицу истинности для операции "~" и получить требуемый результат. Если F - константа или переменная, то скобки можно опускать, а если какая-то более сложная формула, то нельзя. Например: ~ x, ~(~ x), ~1, ~(0), ~(x & ~y). нетривиальнаяотрицание. "~" Единственная нетривиальная функция - отрицание. Она изменяет значение параметра на противоположное: ~0 = 1, ~1 = 0. Знак "~" является знаком унарной операции и обозначает эту функцию.

Бинарные операции xy xy xyx

xyy xy~x xy~y Бинарные операции

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

Конъюнкция xyx&y Другие названия этой функции Другие названия этой функции: "И", "логическое И", "логическое умножение", "булево умножение". Другие обозначения этой функции Другие обозначения этой функции: X&&Y, X Y, X*Y, XY, X Y, X AND Y, X И У.

Больше xyx>y только когда не имеет Функция ">" дает 1 только когда первый операнд равен 1, а второй 0. Эта функция не имеет общеупотребительных названий или обозначений.

Меньше xyx<y только когда не имеет Функция "<" дает 1 только когда первый операнд равен 0, а второй 1. Эта функция не имеет общеупотребительных названий или обозначений.

Сложение по модулю "2" xyx y Другиеназвания этой функции: Другие обозначения этой функции: Другие названия этой функции: "исключающее ИЛИ", "логическое ЛИБО", "неравносильность", "неэквивалентность", "логическое сложение", "булево сложение". Другие обозначения этой функции: X XOR Y, X Y, X ЛИБО У

Дизъюнкция xyx y Другие названия этой функции Другие названия этой функции: "ИЛИ", "логическое ИЛИ". Другие обозначения этой функции: X Y, x OR y, X ИЛИ У, Х/ / Y

Стрелка Пирса xyx y Другие названия этой функции: Другие названия этой функции: "ИЛИ-НЕ". оба Эта функция дает 1 только когда оба операнда равны 0.

Равносильность xyx y Другие названия этой функции "равносильность". Другие названия этой функции: "равносильность". Другие обозначения этой функции Другие обозначения этой функции: X Y, X Y, X~Y, X Y

Обратная импликация xyx<=y Другие обозначения этой функции: только когда Эта функция дает 0 только когда первый операнд равен 0, а второй равен 1 X Y, X Y

Импликация xyx=>y Другие обозначения этой функции: только когда Эта функция дает 0 только когда первый операнд равен 1, а второй равен 0. X Y, X Y

Штрих Шеффера xyx|y Другие названия этой функции: Другие названия этой функции: "И-НЕ". Другие обозначения этой функции: Другие обозначения этой функции: ' (апостроф).

сводную таблицу В заключение приведем сводную таблицу всех бинарных логических операций: xy0x yx<y~xx>y~yx y

Сводная таблица Сводная таблица всех бинарных логических операций: XY х | y х & y x yyx=>yxx<=y xyxy

Правила вывода В алгебре логики действуют два правила вывода: 1. любую формулу равенство. 1. Если в обоих частях равенства заменить переменную на любую формулу (одну и ту же во всех местах, где встречается эта переменная), то получится равенство. Например, из равенства ~(x & y) = x | y xx & ~ y путем замены x на x & ~ y получим: ~((x & ~ y) & y) = (x & ~y) | y.

2. F на G или G на F 2. Если F = G, то в любом равенстве можно заменять F на G или G на F и в результате получится равенство. В отличие от предыдущего случая делать замену во всех местах необязательно. Например, пусть у нас есть два равенства: ~(x & y ) = x | y (1) ~(~ x) = x (2) (1) (2): Мы можем взять равенство (1) и в нем вместо x подставить ~(~x), поскольку эти две формулы объединены равенством (2): ~(~(~x) & y) = ~(~x) | y

Логические основы ЭВМ Простейшие преобразователи информации

Цифровой сигнал Цифровой сигнал – это сигнал, который может принимать только одно из двух установленных значений. Примеры таких значений: напряжения +5 В и +0,4 В; сила тока 20 мА и 1 мА; лампа горит или нет; кнопка нажата или нет и т. п.

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

Логический элемент «НЕ» (инвертор) «НЕ» Логический элемент «НЕ» (инвертор) выдает на выходе сигнал, противоположный сигналу на входе, т.е. на его выходе будет 1, если на вход поступит 0 и наоборот Физическая реализация: +5 В F Условное обозначение инвертора: ХХ

Логический элемент «И» (коньюнктор) Логический элемент «И» (коньюнктор) выдает на выходе значение логического произведения входных сигналов, т.е. на его выходе будет 1 тогда и только тогда, когда на все входы поступит 1 Физическая реализация: +5 В F Условное обозначение коньюнктора: Х & Y Х Y &

Логический элемент «ИЛИ» (дизъюнктор) Логический элемент «ИЛИ» (дизъюнктор) выдает на выходе значение логической суммы входных сигналов, т.е. на его выходе будет 1, если хотя бы на один из входов подается 1 Физическая реализация: +5 В F Условное обозначение дизъюнктора: Х V Y Х Y 1

Логические элементы «И-НЕ», «ИЛИ-НЕ» инвертором, дизъюнктором и конъюнктором отрицание конъюнкции и отрицание дизъюнкции. Наряду с инвертором, дизъюнктором и конъюнктором в логических схемах часто используются комбинированные логические элементы «И-НЕ» и «ИЛИ-НЕ», реализующие соответственно отрицание конъюнкции и отрицание дизъюнкции. Условные обозначения: «И-НЕ» Х & Y Х Y & «ИЛИ-НЕ» Х V Y Х Y 1

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

Задача 1 Дана структурная формула: F(X,Y) = X & Y. Постройте соответствующую ей функциональную схему. Х Y & F (X,Y) = X & Y Ответ:

Задача 2 Определите структурную формулу по заданной функциональной схеме: Х Y F (X,Y) & Ответ: F(X,Y) = X & Y.

Задача 3 Определите структурную формулу по заданной функциональной схеме: Определите структурную формулу по заданной функциональной схеме: Х Y F (X,Y) Ответ: F(X,Y) = X v Y.

Задача 4 Дана структурная формула: F(X,Y) = X & (X v Y). Постройте соответствующую ей функциональную схему. F (X,Y) = X & (X v Y) Ответ: Х Y & 1

Задача 5 Дана структурная формула: F(X,Y,Z) = X&Y&Z v (X v Y v Z)&Y. Постройте соответствующую ей функциональную схему. F (X,Y,Z) Ответ: Х Y & 1 & 1 Z

Задача 6 Дана структурная формула: F(X,Y)= (X+Y)+(Y*X) Постройте соответствующую ей таблицу истинности и функциональную схему: Ответ: 1. Таблица истинности: XYXYX+YY*X(X+Y)+(Y*X)

2. Функциональная схема: X Y 1 1 & F(X,Y)

Задача 7 Дана структурная формула: Дана структурная формула: F(X,Y,Z)=X+(Y*Z)+Y Постройте соответствующие ей таблицу истинности и функциональную схему: Постройте соответствующие ей таблицу истинности и функциональную схему:Ответ: 1. Таблица истинности: XYZXYY*ZX+(Y*Z)X+(Y*Z)+Y

2. Функциональная схема: & 1 1X Y Z F(X,Y,Z)

Задача 8 Дана структурная формула: F(X,Y,)= (X*Y)+(X*Y) F(X,Y,)= (X*Y)+(X*Y) Постройте соответствующие ей таблицу истинности и функциональную схему. Ответ: 1. Таблица истинности: XYXYX*Y (X*Y)+(X*Y)

2. Функциональная схема: F(X,Y) X Y & & 1