1.4. Алгебра логики
Алгебра логики (математическая логика или булева алгебра, или алгебра высказываний) используется в информатике для того, чтобы можно было определять истинность или ложность составных высказываний, не вникая в их содержание.
Каждое составное высказывание можно выразить в виде формулы (логического выражения), в которую войдут логические переменные, обозначающие высказывания, и знаки логических операций, обозначающие логические функции. Для записи составных высказываний в виде логических выражений на формальном языке (языке алгебры логики) в составном высказывании нужно выделить простые высказывания и логические связи между ними. Истинность или ложность составных высказываний можно определять чисто формально, руководствуясь законами алгебры высказываний, не обращаясь к смысловому содержанию высказываний.
В алгебре логики (высказываний) суждениям (простым высказываниям) ставятся в соответствие переменные (заглавные буквы латинского алфавита), которые могут принимать только два значе-
ния «истина ( true )» (1) и «ложь ( false )» (0). Пример : А − «2 × 2 = 4» − истина (1) А = 1
В − «2 × 2 = 5» − ложь (0) В = 0 8
Простые высказывания называются переменными , а сложные −
1.4.1. Основные логические операции
Логическое умножение (конъюнкция) – объединение 2-х (или нескольких высказываний) в одно с помощью союза » И «. Конъюнкция истинна тогда и только тогда, когда истинны входящие в нее простые высказывания. Обозначения: & , ^ , * , and .
Например, F = A&B, F = A^B, F = A × B, F = A and B. Ниже приведена таблица истинности для операции логического умножения.
Зачем нужна алгебра логики
Основные понятия алгебры логики, её применение в информатике. Решение задачи с расчетом стоимости стеклопакетов. Информационная и аналитическая модель задачи, технология решения задачи в MS Excel. Результаты компьютерного эксперимента и их анализ.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 22.01.2015 |
| Размер файла | 44,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФГБОУ ВПО
«Финансовый университет при правительстве российской федерации»
Кафедра Экономической теории
по дисциплине «Информатика»
на тему «Применение алгебры логики в информатике»
алгебра логика задача компьютерный
1. Теоретическая часть
1.1 Наука алгебра логики
1.2 Основные понятия алгебры логики
1.3 Применение алгебры логики в информатике
2. Практическая часть
2.1 Постановка задачи
2.1.1 Цель решения задачи
2.1.2 Условие задачи
2.2 Компьютерная модель решения задачи
2.2.1 Информационная модель решения задачи
2.2.2 Аналитическая модель решения задачи
2.2.3 Технология решения задачи
2.3 Результаты компьютерного эксперимента и их анализ
2.3.1 Результаты компьютерного эксперимента
2.3.2 Анализ полученных результатов
Список использованной литературы
Тема теоретической части курсовой работы: Применение алгебры логики в информатике. Алгебра логики является составной частью одного из современных быстро развивающихся разделов математики — математической логики. Математическая логика применяется в информатике, позволяет моделировать простейшие мыслительные процессы. Одним из занимательных приложений алгебры высказываний — решение логических задач.
В логических задачах исходными данными являются не только и не столько числа, а сложные логические суждения, подчас весьма запутанные. Эти суждения и связи между ними бывают иногда столь противоречивы, что для их разрешения привлекают вычислительные машины.
Цель данной курсовой работы состоит в изучении применения алгебры логики в информатике.
Для достижения цели необходимо ответить на следующие вопросы:
— наука алгебра логики
— основные понятия алгебры логики
— применение алгебры логики в информатике (к построению схем, обработке знаний и т.д.)
Практическая часть выполнена с использование MS Excel и MS Word.
Алгебра логики возникла в середине ХIХ века в трудах английского математика Джорджа Буля. Её создание представляло собой попытку решать традиционные логические задачи алгебраическими методами.
Отцом алгебры логики по праву считается английский математик 19-го столетия Джорж Буль (1815-1864). Именно он построил один из разделов формальной логики в виде некоторой «алгебры», аналогичной алгебре чисел, но не сводящейся к ней. Алгебра в широком смысле слова — наука об общих операциях, аналогичных сложению и умножению, которые могут выполняться не только с числами, но и над другими математическими объектами. Существуют алгебры натуральных чисел, многочленов, векторов, матриц, множеств и т.д.
Большой вклад в становление и развитие алгебры логики внесли Августус де Морган (1806-1871), Уильям Стенли Джевонс (1835-1882), П.С. Порецкий(1846 — 1907), Чарлз Сандерс Пирс (1839-1914), А.А. Марков (1903-1979), А.Н. Колмогоров (1903-1987) и др.
Долгое время алгебра логики была известна достаточно узкому классу специалистов. Прошло почти 100 лет со времени создания алгебры логики Дж. Булем, прежде чем в 1938 Клод Шеннон (1916-2001) показал, что алгебра логики применима для описания самых разнообразных процессов, в том числе функционирования релейно-контактных и электронно-ламповых схем.
Алгебра логики явилась математической основой теории электрических и электронных переключателей схем, используемых в ЭВМ. В компьютерных науках её предпочитают называть не алгеброй логики, а Булевой алгеброй — по имени её создателя.
Алгебра логики изучает свойства функций, у которых и аргументы, и значения принадлежат заданному двухэлементному множеству (например, <0,1>).Иногда вместо термина «алгебра логики» употребляют термин «двузначная логика».
Алгебра логики — предельно важная для цифровых компьютеров тема. И с точки зрения их устройства, схем техники, и с точки зрения их функционирования и программирования поведения.
Действительно, мало-мальски сложное действие невозможно без обратной связи, без анализа условий выполнения. Например, «ЕСЛИ нам хочется пить, ТО мы пьём, ИНАЧЕ мы даже не думаем об этом». «ЕСЛИ компьютер не работает И питание включено, ТО компьютер сгорел». «ЕСЛИ точка левее левой стороны квадрата ИЛИ правее правой, ТО точка расположена не в квадрате». «Ревёт ли зверь в лесу глухом, трубит ли рог, гремит ли гром. ». «Кошелёк или жизнь». Помимо манипуляций константами «да» и «нет» логические переменные могут являться результатом применения к числам операторов отношения (меньше, больше, равно и т.п.). В компьютерах булевы переменные представляются (кодируются) битами (разрядами двоичной системы счисления), где 1 означает истину, а 0 — ложь. Манипуляции высказываниями и их комбинациями используются для получения некоего единственного результата, который можно использовать, например, для выбора той или иной последовательности действий. Поскольку логические переменные кодируются по тем же принципам, что и числа, символы и прочая информация, то можно комбинировать операции логики с операциями арифметики для реализации различных алгоритмов.
Таким образом, алгебра логики (другое название — Булева алгебра) — это область математики. Она оперирует величинами, которые могут принимать два значения (булевых значения). Эти два значения могут быть обозначены как угодно, лишь бы по-разному. Самые распространенные варианты:
При применении булевой алгебры в вычислительной технике, булевы значения — это 0 и 1. Они представляют собой состояние ячейки памяти объёмом в 1 бит или наличие/отсутствие напряжения в электрической схеме. Алгебра логики позволяет строить сложные электронные узлы, элементы которых работают согласно этой математической теории. При применении булевой алгебры в логических построениях в математике, булевы значения — это «ложь» и «истина». Они определяют истинность или ложность некоторого высказывания. Под высказываниями понимаются математические формулы. При применении булевой алгебры в повседневных рассуждениях, булевы значения — это также «ложь» и «истина». Они представляют собой оценку истинности или ложности некоторого высказывания. Под высказываниями понимаются фразы, которые удовлетворяют строго определенному списку свойств.
Алгебра логики применяется:
1) для упрощения сложных логических формул и доказательств тождеств;
2) при решении логических задач;
3) в контактных схемах;
4) при доказательствах теорем;
5) в базах данных при составлении запросов.
1.2 Основные понятия алгебры логики
Объектом логики как науки выступает абстрактное мышление. Логика изучает абстрактное мышление как средство познания объективного мира, исследует формы и законы, в которых происходит отражение мира в процессе мышления. Основными формами абстрактного мышления являются:
Понятие — форма мышления, в которой отражаются существенные признаки отдельного предмета или класса однородных предметов: портфель трапеция ураганный ветер, (например, "дерево", "самолет") или группой слов, т.е. словосочетаниями, например, "студент гуманитарного института", "создатель художественных картин", "река Дон", "космический корабль" и др.
Суждение — мысль, в которой что-либо утверждается или отрицается о предметах. Суждения являются повествовательными предложениями, истинными или ложными. Они могут быть простыми и сложными: Весна наступила, и грачи прилетели.
Пример сложного суждения: "Наступила осень, и лебеди улетают". Оно состоит из двух простых суждений.
Умозаключение — прием мышления, посредством которого из исходного знания получается новое знание; из одного или нескольких истинных суждений, называемых посылками, мы по определенным правилам вывода получаем заключение. Есть несколько видов умозаключений. Все металлы — простые вещества. Литий — металл. Литий — простое вещество.
Все металлы — вещества. Железо — металл. Железо — вещество
Чтобы достичь истины при помощи умозаключений, надо соблюдать законы логики.
Формальная логика — наука о законах и формах правильного мышления.
Математическая логика изучает логические связи и отношения, лежащие в основе дедуктивного (логического) вывода.
Логика высказываний послужила основным математическим инструментом при создании компьютеров. Она легко преобразуется в битовую логику: истинность высказывания обозначается одним битом (0 — ЛОЖЬ, 1 — ИСТИНА); тогда операция ¬ приобретает смысл вычитания из единицы; ? — немодульного сложения; & (или ?) — умножения; — — равенства; ? — в буквальном смысле сложения по модулю 2 (исключающее Или — XOR); ? — непревосходства суммы над 1 (то есть A?B = (A + B) В
Законы алгебры логики
Алгебра логики это раздел математической логики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности), и логические операции над ними.
В алгебре логики принято отождествлять истинность высказывания с числом 1, а ложность — с числом 0 (А = 1 и С = 0 означает, что А истинно и что С ложно).
Что изучает алгебра логики?
Предметом изучения алгебры логики являются функции которые принимают лишь два значения: 0 или 1. Объединение простых высказываний в сложные в алгебре логики производится без учёта внутреннего содержания (смысла) этих высказываний.
К основным логическим операциям относятся операции: отрицания, логического умножения, или конъюнкции, логического сложения, или дизъюнкции, эквивалентности, импликации.
Любое сложное выражение, полученное из простых высказываний посредством основных логических операции, называется формулой алгебры логики.
Где используется алгебра логики?
Использование аппарата алгебры логики в теории устройств дискретного действия основано на том, что элементы этих устройств являются двух позиционными приборами, т. е. приборами, которые по условиям работы могут находиться лишь в одном из двух различных устойчивых состояний, например «контакт замкнут», «транзистор открыт».
Конъюнкция такого рода высказываний будет тогда средством выражения последовательного соединения элементов, а дизъюнкция — их параллельного соединения. На этом основана возможность применять средства алгебры логики к задачам анализа и синтеза переключателей схем. Алгебра логики используется в теории релейных схем, теории ЭВМ и в теории дискретных автоматов.
Что такое алгебра логики?
Алгебра логики (булева алгебра) – это раздел математики, возникший в XIX веке благодаря усилиям английского математика Дж. Буля. Поначалу булева алгебра не имела никакого практического значения. Однако уже в XX веке ее положения нашли применение в описании функционирования и разработке различных электронных схем. Законы и аппарат алгебры логики стал использоваться при проектировании различных частей компьютеров (память, процессор). Хотя это не единственная сфера применения данной науки.
Что же собой представляет алгебра логики?
Во-первых, она изучает методы установления истинности или ложности сложных логических высказываний с помощью алгебраических методов. Во-вторых, булева алгебра делает это таким образом, что сложное логическое высказывание описывается функцией, результатом вычисления которой может быть
либо истина, либо ложь (1, либо 0). При этом аргументы функции (простые высказывания) также могут иметь только два
значения: 0, либо 1.
Что такое простое
логическое высказывание? Это фразы типа «два больше одного», «5.8 является целым числом». В первом случае мы имеем истину, а во втором ложь. Алгебра логики не касается сути этих высказываний. Если кто-то решит, что высказывание «Земля квадратная» истинно, то алгебра логики это примет как факт. Дело в том, что булева алгебра занимается вычислениями результата сложных логических высказываний на основе заранее известных значений простых высказываний.
Логические операции. Дизъюнкция, конъюнкция и отрицание
Так как же связываются между собой простые логические высказывания, образуя сложные? В естественном языке мы используем различные союзы и другие части речи. Например, «и», «или», «либо», «не», «если», «то», «тогда». Пример сложных высказываний: «у него есть знания
и навыки», «она приедет во вторник,
либо в среду», «я буду играть
тогда, когда сделаю уроки», «5
не равно 6». Как мы решаем, что нам сказали правду или нет? Как-то логически, даже где-то неосознанно, исходя из предыдущего жизненного опыта, мы понимает, что правда при союзе «и» наступает в случае правдивости обоих простых высказываний. Стоит одному стать ложью и все сложное высказывание будет лживо. А вот, при связке «либо» должно быть правдой только одно простое высказывание, и тогда все выражение станет истинным.
Булева алгебра переложила этот жизненный опыт на аппарат математики, формализовала его, ввела жесткие правила получения однозначного результата. Союзы стали называться здесь логическими операторами.
Алгебра логики предусматривает множество логических операций. Однако три из них заслуживают особого внимания, т.к. с их помощью можно описать все остальные, и, следовательно, использовать меньше разнообразных устройств при конструировании схем. Такими операциями являются
конъюнкция (И),
дизъюнкция (ИЛИ) и
отрицание (НЕ). Часто конъюнкцию обозначают
&, дизъюнкцию —
||, а отрицание — чертой над переменной, обозначающей высказывание.
При конъюнкции истина сложного выражения возникает лишь в случае истинности всех простых выражений, из которых состоит сложное. Во всех остальных случаях сложное выражение будет ложно.
При дизъюнкции истина сложного выражения наступает при истинности хотя бы одного входящего в него простого выражения или двух сразу. Бывает, что сложное выражение состоит более, чем из двух простых. В этом случае достаточно, чтобы одно простое было истинным и тогда все высказывание будет истинным.
Отрицание – это унарная операция, т.к выполняется по отношению к одному простому выражению или по отношению к результату сложного. В результате отрицания получается новое высказывание, противоположное исходному.
Таблицы истинности
Логические операции удобно описывать так называемыми
таблицами истинности, в которых отражают результаты вычислений сложных высказываний при различных значениях исходных простых высказываний. Простые высказывания обозначаются переменными (например, A и B).
Логические основы компьютера
В ЭВМ используются различные устройства, работу которых прекрасно описывает алгебра логики. К таким устройствам относятся группы переключателей, триггеры, сумматоры.
Кроме того, связь между булевой алгеброй и компьютерами лежит и в используемой в ЭВМ системе счисления. Как известно она двоичная. Поэтому в устройствах компьютера можно хранить и преобразовывать как числа, так и значения логических переменных.
Переключательные схемы
В ЭВМ применяются электрические схемы, состоящие из множества переключателей. Переключатель может находиться только в двух состояниях: замкнутом и разомкнутом. В первом случае – ток проходит, во втором – нет. Описывать работу таких схем очень удобно с помощью алгебры логики. В зависимости от положения переключателей можно получить или не получить сигналы на выходах.
Вентили, триггеры и сумматоры
Вентиль представляет собой логический элемент, который принимает одни двоичные значения и выдает другие в зависимости от своей реализации. Так, например, есть вентили, реализующие логическое умножение (конъюнкцию), сложение (дизъюнкцию) и отрицание.
Триггеры и сумматоры – это относительно сложные устройства, состоящие из более простых элементов – вентилей.
Триггер способен хранить один двоичный разряд, за счет того, что может находиться в двух устойчивых состояниях. В основном триггеры используется в регистрах процессора.
Сумматоры широко используются в арифметико-логических устройствах (АЛУ) процессора и выполняют суммирование двоичных разрядов.
Name already in use
OAP / articles / t1l3.md
- Go to file T
- Go to line L
- Copy path
- Copy permalink
- Open with Desktop
- View raw
- Copy raw contents Copy raw contents
Copy raw contents
Copy raw contents
Логические основы алгоритмизации
Логика – это наука о формах и способах мышления (первые учения – Древний Восток).
Начало исследований в области формальной логики было положено Аристотелем в IV в. до н.э. Однако математические подходы к этим вопросам были впервые указаны Джорджем Булем, который положил в основу математической логики алгебру логики (булеву, а логические значения называют булевыми). Алгебра логики используется при построении основных узлов ЭВМ, например, таких как шифратор, сумматор и др.
Основными формами мышления являются понятие, высказывание и умозаключение.
Понятие – это форма мышления, фиксирующая основные, существенные признаки объекта (например, прямоугольник, компьютер).
Умозаключение – это форма мышления, с помощью которой из одного или нескольких суждений может быть получено новое суждение – заключение (например, все углы равнобедренного треугольника равны → это треугольник равносторонний).
Составляющей алгоритмов являются логические условия, вычисление значений которых происходит в соответствии с аксиомами алгебры логики.
Основу математической логики составляет алгебра высказываний.
Объектами, с которыми работает алгебра высказываний, являются повествовательные предложения, относительно которых можно сказать, истинны они или ложны.
Высказыванием называется утверждение, о котором можно определенно сказать, истинно оно или ложно. Высказываний одновременно истинных и ложных не бывает.
Приведем примеры высказываний:
- Москва — столица России
- число 27 является простым
- Волга впадает в Каспийское море
Высказывания 1 и 3 являются истинными. Высказывание 2 — ложным, потому что число 27 составное 27=333.
Следующие предложения высказываниями не являются:
- давай пойдем гулять
- 2*x>8
- ax2+bx+c=0
- который час?
Подчеркнем еще раз, что отличительным признаком высказывания является свойство быть истинным или ложным, последние четыре предложения этим свойством не обладают. Невозможно отнести неравенство 2 или уравнение 3 к высказываниям пока не определено значение x. При x=3 высказывание «23>8″ ложно, а при x=5 «25>8″ — истинно.
Условимся обозначать высказывания большими буквами и, следуя Джорджу Булю, истинное (true) высказывание A обозначим так, A=1. В том случае, когда A — ложное (false) высказывание, будем писать: A=0.
Функция ƒ(x1, x2, . xn) называется логической или булевой, если она, так же как и ее аргументы xi, может принимать только два значения: «истина» или «ложь».
По числу переменных различают логические функции одной, двух и многих переменных.
Логические функции могут быть описаны различными способами:
- в виде таблицы истинности;
- совершенными нормальными формами;
- в виде формулы.
Чаще всего встречаются табличная форма представления логической функции (в виде таблицы истинности) и ее аналитическое представление (например, в виде дизъюнктивных или конънктивных форм).
Из простых высказываний можно строить сложные, называемые составными высказывания, соединяя простые логическими операциями. Над простыми высказываниями определены следующие операции:
- логическое отрицание
- логическое умножение
- логическое сложение
- логическое следование или импликация
- эквивалентность
Рассмотрим некоторые из этих операций более подробно.
Инверсия (логическое отрицание — НЕ) — обозначение !.
Логическое сложение, умножение, следование и эквивалентность являются бинарными операциями («би» — два), потому что соединяют два операнда (два высказывания). В отличие от них, логическое отрицание является унарной операцией, потому что применяется лишь к одному высказыванию.
Присоединение частицы НЕ к сказуемому простого высказывания A называется операцией логического отрицания.
Результат будет истинным, если исходное высказывание ложно, и наоборот, ложным — если исходное высказывание истинно.
| A | !A |
|---|---|
| 0 | 1 |
| 1 | 0 |
Конъюнкция (логическое умножение — И) – обозначение & или &&
Результат будет истинным тогда и только тогда, когда оба исходных высказывания истинны.
| A | B | A & B |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
Для более легкого запоминания этой функции следует придерживаться правила: функция конъюнкции ложна, если ложен хотя бы один из ее операндов. Это правило действует для функции, содержащей произвольное число операндов. Если обозначать значение «истина» как «1», а значение «ложь» как «0», то эта функция будет похожа на математическую функцию умножения. Поэтому ее зачастую называют функцией логического умножения.
Отметим, что для конъюнкции, так же как и для следующей рассматриваемой функции – дизъюнкции – действуют ассоциативный (сочетательный) и коммуникативный (переместительный) законы.
В то же время для некоторых других логических функций тот или иной закон не действует. Некоторые из примеров таких функций мы рассмотрим ниже.
Чем отличается оператор & от &&:
- Оператор & всегда вычисляет оба операнда
- Оператор && вычисляет второй операнд, только если это необходимо.
Дизъюнкция (логическое сложение — ИЛИ) – обозначение | или ||.
Результат будет истинным тогда, когда истинно хотя бы одно из высказываний.
| A | B | A | B |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 1 |
Для более легкого запоминания этой функции следует придерживаться правила: функция дизъюнкции истинна, если истенен хотя бы один из ее операндов. Это правило действует для функции, содержащей произвольное число операндов. Если обозначать значение «истина» как «1», а значение «ложь» как «0», то эта функция для двух операндов будет похожа на математическую функцию поразрядного сложения. Поэтому ее зачастую называют функцией логического сложения. Хотя здесь следует иметь в виду, что в логическом сложении сигнал переноса в более старший разряд не вырабатывается.
Чем отличается оператор | от ||:
- Оператор | всегда вычисляет оба операнда
- Оператор || вычисляет второй операнд, только если это необходимо.
Сложе́ние по мо́дулю 2 (исключа́ющее «ИЛИ», логи́ческая неравнозна́чность) — обозначение ^.
| A | B | A ^ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Для операндов целочисленных типов оператор ^ вычисляет побитовое исключающее ИЛИ своих операндов.
Про функцию Сумма по модулю 2 поговорим здесь поподробнее, так она является основой для реализации устройств контроля и защиты информации.
Пример контроля
Пусть мы хотим передать некоторые данные, например, код 11001100 . Перед началом передачи код дополняется контрольным разрядом.
| бит данных | действие | сумма по модулю 2 |
|---|---|---|
| 1 | — | 1 |
| 1 | 1 ^ 1 | 0 |
| 0 | 0 ^ 0 | 0 |
| 0 | 0 ^ 0 | 0 |
| 1 | 1 ^ 0 | 1 |
| 1 | 1 ^ 1 | 0 |
| 0 | 0 ^ 0 | 0 |
| 0 | 0 ^ 0 | 0 |
В нашем примере контрольный разряд будет равен 0 (сложим 4 единицы и разделим по модулю 2, результат 0). Контрольный разряд передается вместе с основным кодом ( 11001100 + 0 ).
Если в процессе передачи произойдет искажение одного разряда (например, последний разряд кода примет значение 1), то приёмное устройство примет код 11001101 и контрольный разряд «0», равный исходному (там искажения нет).
| бит данных | действие | сумма по модулю 2 |
|---|---|---|
| 1 | — | 1 |
| 1 | 1 ^ 1 | 0 |
| 0 | 0 ^ 0 | 0 |
| 0 | 0 ^ 0 | 0 |
| 1 | 1 ^ 0 | 1 |
| 1 | 1 ^ 1 | 0 |
| 0 | 0 ^ 0 | 0 |
| 1 | 1 ^ 0 | 1 |
Приемное устройство вычисляет контрольный разряд от принятого кода (теперь он будет равен «1», 5 mod 2 = 1), сравнивает его с принятым контрольным разрядом (они не совпадают) и сообщает об ошибке в передаче данных. Обычно после этого передача повторяется.
Такой алгоритм только демонстрирует принцип формирования контрольных сумм. В современной технике никто, разумеется, по байтам данные не передает. Контроль обычно осуществляется на уровне пакета данных добавлением циклического кода целостности (CRC16, CRC32).
Пример защиты
A ^ B = C, C ^ B = A .
Почему то нигде не написано про самое интересное свойство этой функции: если к результату повторно применить аналогичное преобразование, то получим исходные данные.
Эту логическую операцию можно применять для элементарной защиты передаваемой информации. Можно использовать так называемый ключ защиты, который должен быть у передающей и принимающей стороны. Пусть в нашем случае таким ключом защиты будет код 01101101 .
| данные | ключ | зашифрованные данные |
|---|---|---|
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
| 1 | 1 | 0 |
| 1 | 1 | 0 |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
Суммируя по модулю 2 поразрядно передаваемый код и код защиты, получим, что передаваться будет код 10100001 , который отличается от исходного кода. Даже если в случае несанкционированного доступа эта информация будет перехвачена, она ничего не даст злоумышленнику. В то же время, принимающая сторона, имея тот же самый ключ защиты, восстановит исходную информацию.
Если длина передаваемых данных больше длины ключа, то ключ используется повторно для следующего блока данных.
Математическая логика, преобразования
Алгебра логики (англ. algebra of logic) — один из основных разделов математической логики, в котором методы алгебры используются в логических преобразованиях.
Основоположником алгебры логики является английский математик и логик Дж. Буль (1815–1864), положивший в основу своего логического учения аналогию между алгеброй и логикой. Любое высказывание он записывал с помощью символов разработанного им языка и получал «уравнения», истинность или ложность которых можно было доказать, исходя из определенных логических законов, таких как законы коммутативности, дистрибутивности, ассоциативности и др.
Современная алгебра логики является разделом математической логики и изучает логические операции над высказываниями с точки зрения их истинностного значения (истина, ложь). Высказывания могут быть истинными, ложными или содержать истину и ложь в разных соотношениях.
Логическое высказывание — это любое повествовательное предложение, в отношении которого можно однозначно утверждать, что его содержание истинно или ложно.
Например, «3 умножить на 3 равно 9», «Архангельск севернее Вологды» — истинные высказывания, а «Пять меньше трех», «Марс — звезда» — ложные.
Очевидно, что не всякое предложение может быть логическим высказыванием, т. к. не всегда есть смысл говорить о его ложности или истинности. Например, высказывание «Информатика — интересный предмет» неопределенно и требует дополнительных сведений, а высказывание «Для ученика 10-А класса Иванова А. А. информатика — интересный предмет» в зависимости от интересов Иванова А. А. может принимать значение «истина» или «ложь».
Кроме двузначной алгебры высказываний, в которой принимаются только два значения — «истинно» и «ложно», существует многозначная алгебра высказываний. В такой алгебре, кроме значений «истинно» и «ложно», употребляются такие истинностные значения, как «вероятно», «возможно», «невозможно» и т. д.
В алгебре логики различаются простые (элементарные) высказывания, обозначаемые латинскими буквами (A, B, C, D, …), и сложные (составные), составленные из нескольких простых с помощью логических связок, например таких, как «не», «и», «или», «тогда и только тогда», «если … то». Истинность или ложность получаемых таким образом сложных высказываний определяется значением простых высказываний.
Обозначим как А высказывание «Алгебра логики успешно применяется в теории электрических схем», а через В — «Алгебра логики применяется при синтезе релейно-контактных схем».
Тогда составное высказывание «Алгебра логики успешно применяется в теории электрических цепей и при синтезе релейно-контактных схем» можно кратко записать как А и В; здесь «и» — логическая связка. Очевидно, что поскольку элементарные высказывания А и В истинны, то истинно и составное высказывание А и В.
Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение.
Логических значений всего два: истина (TRUE) и ложь (FALSE). Это соответствует цифровому представлению — 1 и 0. Результаты каждой логической операции можно записать в виде таблицы. Такие таблицы называют таблицами истинности.
Основные операции алгебры логики
1. Логическое отрицание, инверсия (лат. inversion — переворачивание) — логическая операция, в результате которой из данного высказывания (например, А) получается новое высказывание (не А), которое называется отрицанием исходного высказывания, обозначается символически чертой сверху ($A↖<->$) или такими условными обозначениями, как ¬, 'not', и читается: «не А», «А ложно», «неверно, что А», «отрицание А». Например, «Марс — планета Солнечной системы» (высказывание А); «Марс — не планета Солнечной системы» ($A↖<->$); высказывание «10 — простое число» (высказывание В) ложно; высказывание «10 — не простое число» (высказывание B ) истинно.
Операция, используемая относительно одной величины, называется унарной. Таблица значений данной операции имеет вид
| A | ¬A |
| истина | ложь |
| ложь | истина |
| A | ¬A |
| 1 | 0 |
| 0 | 1 |
Высказывание $A↖<->$ ложно, когда А истинно, и истинно, когда А ложно.
Геометрически отрицание можно представить следующим образом: если А — это некоторое множество точек, то $A↖<->$ — это дополнение множества А, т. е. все точки, которые не принадлежат множеству А.
2. Конъюнкция (лат. conjunctio — соединение) — логическое умножение, операция, требующая как минимум двух логических величин (операндов) и соединяющая два или более высказываний при помощи связки «и» (например, «А и В»), которая символически обозначается с помощью знака ∧ (А ∧ В) и читается: «А и В». Для обозначения конъюнкции применяются также следующие знаки: А ∙ В; А & В, А and В, а иногда между высказываниями не ставится никакого знака: АВ. Пример логического умножения: «Этот треугольник равнобедренный и прямоугольный». Данное высказывание может быть истинным только в том случае, если выполняются оба условия, в противном случае высказывание ложно.
Таблица истинности операции имеет вид
| A | B | A ∧ B |
| истина | ложь | ложь |
| ложь | истина | ложь |
| ложь | ложь | ложь |
| истина | истина | истина |
| A | B | A ∧ B |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
| 1 | 1 | 1 |
Высказывание А ∧ В истинно только тогда, когда оба высказывания — А и В истинны.
Геометрически конъюнкцию можно представить следующим образом: если А, В — это некоторые множества точек, то А ∧ В есть пересечение множеств А и В.
3. Дизъюнкция (лат. disjunction — разделение) — логическое сложение, операция, соединяющая два или более высказываний при помощи связки «или» (например, «А или В»), которая символически обозначается с помощью знака ∨ (А ∨ В) и читается: «А или В». Для обозначения дизъюнкции применяются также следующие знаки: А + В; А or В; А | B. Пример логического сложения: «Число x делится на 3 или на 5». Это высказывание будет истинным, если выполняются оба условия или хотя бы одно из условий.
Таблица истинности операции имеет вид
| A | B | A ∨ B |
| истина | ложь | истина |
| ложь | истина | истина |
| ложь | ложь | ложь |
| истина | истина | истина |
| A | B | A ∨ B |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
| 1 | 1 | 1 |
Высказывание А ∨ В ложно только тогда, когда оба высказывания — А и В ложны.
Геометрически логическое сложение можно представить следующим образом: если А, В — это некоторые множества точек, то А ∨ В — это объединение множеств А и В, т. е. фигура, объединяющая и квадрат, и круг.
4. Дизъюнкция строго-разделительная, сложение по модулю два — логическая операция, соединяющая два высказывания при помощи связки «или», употребленной в исключающем смысле, которая символически обозначается с помощью знаков ∨ ∨ или ⊕ (А ∨ ∨ В, А ⊕ В) и читается: «либо А, либо В». Пример сложения по модулю два — высказывание «Этот треугольник тупоугольный или остроугольный». Высказывание истинно, если выполняется какое-то одно из условий.
Таблица истинности операции имеет вид
| А | В | А ⊕ B |
| истина | ложь | истина |
| ложь | истина | истина |
| ложь | ложь | ложь |
| истина | истина | ложь |
| А | В | А ⊕ B |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
| 1 | 1 | 0 |
Высказывание А ⊕ В истинно только тогда, когда высказывания А и В имеют различные значения.
5. Импликация (лат. implisito — тесно связываю) — логическая операция, соединяющая два высказывания при помощи связки «если. то» в сложное высказывание, которое символически обозначается с помощью знака → (А → В) и читается: «если А, то В», «А влечет В», «из А следует В», «А имплицирует В». Для обозначения импликации применяется также знак ⊃ (A ⊃ B). Пример импликации: «Если полученный четырехугольник квадрат, то около него можно описать окружность». Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием. Результат операции ложен только тогда, когда предпосылка есть истина, а следствие — ложь. Например, «Если 3 * 3 = 9 (А), то Солнце — планета (В)», результат импликации А → В — ложь.
Таблица истинности операции имеет вид
| А | В | А → В |
| истина | ложь | ложь |
| ложь | истина | истина |
| ложь | ложь | истина |
| истина | истина | истина |
| А | В | А → В |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
| 1 | 1 | 1 |
Для операции импликации справедливо утверждение, что из лжи может следовать все что угодно, а из истины — только истина.
6. Эквивалентность, двойная импликация, равнозначность (лат. aequalis — равный и valentis — имеющий силу) — логическая операция, позволяющая из двух высказываний А и В получить новое высказывание А ≡ В, которое читается: «А эквивалентно B». Для обозначения эквивалентности применяются также следующие знаки: ⇔, ∼. Эта операция может быть выражена связками «тогда и только тогда», «необходимо и достаточно», «равносильно». Примером эквивалентности является высказывание: «Треугольник будет прямоугольным тогда и только тогда, когда один из углов равен 90 градусам».
Таблица истинности операции эквивалентности имеет вид
| А | В | А ∼ В |
| истина | ложь | ложь |
| ложь | истина | ложь |
| ложь | ложь | истина |
| истина | истина | истина |
| А | В | А ∼ В |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
| 1 | 1 | 1 |
Операция эквивалентности противоположна сложению по модулю два и имеет результат «истина» тогда и только тогда, когда значения переменных совпадают.
Зная значения простых высказываний, можно на основании таблиц истинности определить значения сложных высказываний. При этом важно знать, что для представления любой функции алгебры логики достаточно трех операций: конъюнкции, дизъюнкции и отрицания.
| Сложение по модулю два | А ⊕ В | $(A↖ <->∧B) ∧ (A ∧ B↖<->)$ |
| Импликация | А → В | $A↖ <->∨ B$ |
| Эквивалентность | А ∼ В | $(A↖ <->∧ B↖<->) ∨ (A ∧ B)$ |
Приоритет выполнения логических операций следующий: отрицание («не») имеет самый высокий приоритет, затем выполняется конъюнкция («и»), после конъюнкции — дизъюнкция («или»).
С помощью логических переменных и логических операций любое логическое высказывание можно формализовать, т. е. заменить логической формулой. При этом элементарные высказывания, образующие составное высказывание, могут быть абсолютно не связаны по смыслу, но это не мешает определять истинность или ложность составного высказывания. Например, высказывание «Если пять больше двух (А), то вторник всегда наступает после понедельника (В)» — импликация А → В, и результат операции в данном случае — «истина». В логических операциях смысл высказываний не учитывается, рассматривается только их истинность или ложность.
Рассмотрим, например, построение составного высказывания из высказываний А и В, которое было бы ложно тогда и только тогда, когда оба высказывания истинны. В таблице истинности для операции сложения по модулю два находим: 1 ⊕ 1 = 0. А высказывание может быть, например, таким: «Этот мяч полностью красный или полностью синий». Следовательно, если утверждение А «Этот мяч полностью красный» — истина, и утверждение В «Этот мяч полностью синий» — истина, то составное утверждение — ложь, т. к. одновременно и красным, и синим мяч быть не может.
Примеры решения задач
Пример 1. Определить для указанных значений X значение логического высказывания ((X > 3) ∨ (X < 3)) → (X < 4) :
1) X = 1; 2) X = 12; 3) X = 3.
Решение. Последовательность выполнения операций следующая: сначала выполняются операции сравнения в скобках, затем дизъюнкция, и последней выполняется операция импликации. Операция дизъюнкции ∨ ложна тогда и только тогда, когда оба операнда ложны. Таблица истинности для импликации имеет вид
| A | B | A → B |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
| 1 | 1 | 1 |
((1 > 3) ∨ (1 < 3)) → (1 < 4) = ложь ∨ истина → истина = истина → истина = истина;
((12 > 3) ∨ (12 < 3) → (12 < 4) = истина ∨ ложь → ложь = истина → ложь = ложь;
((3 > 3) ∨ (3 < 3)) → (3<4) = ложь ∨ ложь → истина = ложь → истина = истина.
Пример 2. Указать множество целых значений X, для которых истинно выражение ¬((X > 2) → (X > 5)) .
Решение. Операция отрицания применена ко всему выражению ((X > 2) → (X > 5)) , следовательно, когда выражение ¬((X > 2) → (X > 5)) истинно, выражение ((X > 2) →(X > 5)) ложно. Поэтому необходимо определить, для каких значений X выражение ((X > 2) → (X > 5)) ложно. Операция импликации принимает значение «ложь» только в одном случае: когда из истины следует ложь. А это выполняется только для X = 3; X = 4; X = 5.
Пример 3. Для каких из приведенных слов ложно высказывание ¬(первая буква гласная ∧ третья буква гласная) ⇔ строка из 4 символов? 1) асса; 2) куку; 3) кукуруза; 4) ошибка; 5) силач.
Решение. Рассмотрим последовательно все предложенные слова:
1) для слова асса получим: ¬(1 ∧ 0) ⇔ 1, 1 ⇔ 1 — высказывание истинно;
2) для слова куку получим: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 — высказывание истинно;
3) для слова кукуруза получим: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 — высказывание ложно;
4) для слова ошибка получим: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 — высказывание истинно;
5) для слова силач получим: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 — высказывание ложно.
Логические выражения и их преобразование
Под логическим выражением следует понимать такую запись, которая может принимать логическое значение «истина» или «ложь». При таком определении среди логических выражений необходимо различать:
- выражения, которые используют операции сравнения («больше», «меньше», «равно», «не равно» и т. п.) и принимают логические значения (например, выражение а > b , где а = 5 и b = 7, равно значению «ложь»);
- непосредственные логические выражения, связанные с логическими величинами и логическими операциями (например, A ∨ В ∧ С, где А = истина, B = ложь и C = истина).
Логические выражения могут включать в себя функции, алгебраические операции, операции сравнения и логические операции. В этом случае приоритет выполнения действий следующий:
- вычисление существующих функциональных зависимостей;
- выполнение алгебраических операций (вначале умножение и деление, затем вычитание и сложение);
- выполнение операций сравнения (в произвольном порядке);
- выполнение логических операций (вначале операции отрицания, затем операции логического умножения, логического сложения, последними выполняются операции импликации и эквивалентности).
В логическом выражении могут использоваться скобки, которые изменяют порядок выполнения операций.
Пример. Найти значение выражения:
$1 ≤ a ∨ A ∨ sin(π/a — π/b) < 1 ∧ ¬B ∧ ¬(b^a + a^b > a + b ∨ A ∧ B)$ для а = 2, b = 3, A = истина, В = ложь.
Решение. Порядок подсчета значений:
1) b a + a b > a + b, после подстановки получим: 3 2 + 2 3 > 2 + 3, т. е. 17 > 2 + 3 = истина;
2) A ∧ B = истина ∧ ложь = ложь.
Следовательно, выражение в скобках равно (b a + a b > a + b ∨ A ∧ B) = истина ∨ ложь = истина;
3) 1≤ a = 1 ≤ 2 = истина;
4) sin(π/a — π/b) < 1 = sin(π/2 — π/3) < 1 = истина.
После этих вычислений окончательно получим: истина ∨ А ∧ истина ∧ ¬В ∧ ¬истина.
Теперь должны быть выполнены операции отрицания, затем логического умножения и сложения:
5) ¬В = ¬ложь = истина; ¬истина = ложь;
6) A ∧ истина ∧ истина ∧ ложь = истина ∧ истина ∧ истина ∧ ложь = ложь;
7) истина ∨ ложь = истина.
Таким образом, результат логического выражения при заданных значениях— «истина».
Примечание. Учитывая, что исходное выражение есть, в конечном итоге, сумма двух слагаемых, и значение одного из них 1 ≤ a = 1 ≤ 2 = истина, без дальнейших вычислений можно сказать, что результат для всего выражения тоже «истина».
Тождественные преобразования логических выражений
В алгебре логики выполняются основные законы, позволяющие производить тождественные преобразования логических выражений.
| Закон | Для ∨ | Для ∧ |
| Переместительный | A ∨ B = B ∨ A | A ∧ B = B ∧ A |
| Сочетательный | A ∨ (B ∨ C) = (B ∨ A) ∨ C | A ∧ (B ∧ C) = (A ∧ B) ∧ C |
| Распределительный | A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C) | A ∨ B ∧ C = (A ∨ B) ∧ (A ∨ C) |
| Правила де Моргана | $↖<->$ = $A↖ <->∧ B↖<->$ | $↖<->$ = $A↖ <->∨ B↖<->$ |
| Идемпотенции | A ∨ A = A | A ∧ A = A |
| Поглощения | A ∨ A ∧ B = A | A ∧ (A ∨ B) = A |
| Склеивания | (A ∧ B) ∨ (A↖ <->∧ B) = B | (A ∨ B) ∧ (A↖ <->∨ B) = B |
| Операция переменной с ее инверсией | $A ∨ A↖<->$ = 1 | $A ∧ A↖<->$ = 0 |
| Операция с константами | A ∨ 0 = A A ∨ 1 = 1 |
A ∧ 1 = A A ∧ 0 = 0 |
| Двойного отрицания | $A↖<=>$ = A | |
Доказательства этих утверждений производят на основании построения таблиц истинности для соответствующих записей.
Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной алгебре. Они служат для упрощения формул или приведения их к определенному виду путем использования основных законов алгебры логики. Под упрощением формулы, не содержащей операций импликации и эквивалентности, понимают равносильное преобразование, приводящее к формуле, которая содержит либо меньшее по сравнению с исходной число операций, либо меньшее число переменных.
Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т. п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).
Рассмотрим на примерах некоторые приемы и способы, применяемые при упрощении логических формул:
1) X1 ∧ X2 ∨ X1 ∧ X2 ∪ ¬X1 ∧ X2 = X1 ∧ X2 ∨ ¬X1 ∧ X2 = (X1 ∨ ¬X1) ∧ X2 = 1 ∧ X2 = X2 .
Для преобразования здесь можно применить закон идемпотенции, распределительный закон; операцию переменной с инверсией и операцию с константой.
2) X1 ∨ X1 ∧ X2 = X1 ∨ (1 ∨ 1 ∧ X2) = X1 ∨ (1 ∨ X2) = X1 .
Здесь для упрощения применяется закон поглощения.
3) ¬(X1 ∧ X2) ∨ X2 = (¬X1 ∨ ¬X2) ∨ X2 = ¬X1 ∨ ¬X2 ∨ X2 = ¬X1 ∨ 1 = 1 .
При преобразовании применяются правило де Моргана, операция переменной с ее инверсией, операция с константой
Примеры решения задач
Пример 1. Найти логическое выражение, равносильное выражению A ∧ ¬(¬B ∨ C) .
Решение. Применяем правило де Моргана для В и С: ¬(¬B ∨ C) = B ∧ ¬C .
Получаем выражение, равносильное исходному: A ∧ ¬(¬B ∨ C) = A ∧ B ∧ ¬C .
Пример 2. Указать значение логических переменных А, В, С, для которых значение логического выражения (A ∨ B) → (B ∨ ¬C ∨ B) ложно.
Решение. Операция импликации ложна только в случае, когд а из истинной посылки следует ложь. Следовательно, для заданного выражения посылка A ∨ B должна принимать значение «истина», а следствие, т. е. выражение B ∨ ¬C ∨ B , — «ложь».
1) A ∨ B — результат дизъюнкции — «истина», если хотя бы один из операндов — «истина»;
2) B ∨ ¬C ∨ B — выражение ложно, если все слагаемые имеют значение «ложь», т. е. В — «ложь»; ¬C — «ложь», а следовательно, переменная С имеет значение «истина»;
3) если рассмотреть посылку и учесть, что В — «ложь», то получим, что значение А — «истина».
Ответ: А — истина, В — ложь, С — истина.
Пример 3. Каково наибольшее целое число X, при котором истинно высказывание (35