«Применение логических операций формул логики»
Цель работы: приобрести навыки применения алгебры логики.
Образовательные результаты, заявленные во ФГОС третьего поколения:
Студент должен
уметь:
- строить логические схемы и алгоритмы;
- использовать средства операционных систем и сред для обеспечения работы вычислительной техники;
- использовать языки программирования строить логически правильные и эффективные программы;
- осваивать и использовать базовые системные программные продукты и пакеты прикладных программ.
.
знать:
- общий состав и структуру персональных ЭВМ и вычислительных систем;
- основные функции назначение и принципы работы распространенных операционных систем;
- состав, структуру, принципы реализации и функционирования информационных технологий;
- общие принципы построение алгоритмов основные алгоритмические конструкции;
- стандартные типы данных;
- базовые системные программные продукты и пакеты прикладных программ.
|
|
Краткие теоретические и учебно-методические материалы по теме практической работы:
Логической основой компьютера является алгебра логики, которая рассматривает логические операции над высказываниями.
Алгебра логики – это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними.
Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.
Пример. «3 – простое число» является высказыванием, поскольку оно истинно.
Не всякое предложение является логическим высказыванием.
Пример. предложение «Давайте пойдем в кино» не является высказыванием. Вопросительные и побудительные предложения высказываниями не являются.
Высказывательная форма – это повествовательное предложение, которое прямо или косвенно содержит хотя бы одну переменную и становится высказыванием, когда все переменные замещаются своими значениями.
Пример. «x+2>5» - высказывательная форма, которая при x>3 является истинной, иначе ложной.
Алгебра логики рассматривает любое высказывание только с одной точки зрения – является ли оно истинным или ложным. Слова и словосочетания «не», «и», «или», «если..., то», «тогда и только тогда» и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками.
Высказывания, образованные из других высказываний с помощью логических связок, называются составными (сложными). Высказывания, которые не являются составными, называются элементарными (простыми).
|
|
Пример. высказывание «Число 6 делится на 2» - простое высказывание. Высказывание «Число 6 делится на 2, и число 6 делится на 3» - составное высказывание, образованное из двух простых с помощью логической связки «и».
Истинность или ложность составных высказываний зависит от истинности или ложности элементарных высказываний, из которых они состоят.
Чтобы обращаться к логическим высказываниям, им назначают имена.
Пример. Обозначим через А простое высказывание «число 6 делится на 2», а через В простое высказывание «число 6 делится на 3». Тогда составное высказывание «Число 6 делится на 2, и число 6 делится на 3» можно записать как «А и В». Здесь «и» – логическая связка, А, В – логические переменные, которые могут принимать только два значения – «истина» или «ложь», обозначаемые, соответственно, «1» и «0».
Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение (табл. 1).
Таблица 1. Основные логические операции
Обозначение операции | Читается | Название операции | Альтернативные обозначения |
НЕ | Отрицание (инверсия) | Черта сверху | |
И | Конъюнкция (логическое умножение) | ∙ & | |
ИЛИ | Дизъюнкция (логическое сложение) | + | |
→ | Если … то | Импликация | |
↔ | Тогда и только тогда | Эквиваленция | ~ |
XOR | Либо …либо | Исключающее ИЛИ (сложение по модулю 2) |
НЕ Операция, выражаемая словом «не», называется отрицанием и обозначается чертой над высказыванием (или знаком). Высказывание А истинно, когда A ложно, и ложно, когда A истинно.
Пример. Пусть А=«Сегодня пасмурно», тогда А=«Сегодня не пасмурно».
И Операция, выражаемая связкой «и», называется конъюнкцией (лат. conjunctio – соединение) или логическим умножением и обозначается точкой «•» (может также обозначаться знаками или &). Высказывание А • В истинно тогда и только тогда, когда оба высказывания А и В истинны.
Пример. Высказывание «Число 6 делится на 2, и число 6 делится на 3» - истинно, а высказывание «Число 6 делится на 2, и число 6 больше 10» - ложно.
ИЛИ Операция, выражаемая связкой «или» (в неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio – разделение) или логическим сложением и обозначается знаком
(или плюсом). Высказывание А В ложно тогда и только тогда, когда оба высказывания А и В ложны.
Пример: Высказывание «Число 6 делится на 2 или число 6 больше 10» - истинно, а высказывание «Число 6 делится на 5 или число 6 больше 10» - ложно.
ЕСЛИ … ТО Операция, выражаемая связками «если …, то», «из … следует», «... влечет …», называется импликацией (лат. implico – тесно связаны) и обозначается знаком →. Высказывание А→В ложно тогда и только тогда, когда А истинно, а В ложно.
Пример. Высказывание «если студент сдал все экзамены на «отлично», то он получит стипендию». Очевидно, эту импликацию следует признать ложной лишь в том случае, когда студент сдал на «отлично» все экзамены, но стипендии не получил. В остальных случаях, когда не все экзамены сданы на «отлично» и стипендия получена (например, в силу того, что студент проживает в малообеспеченной семье) либо когда экзамены вообще не сданы и о стипендии не может быть и речи, импликацию можно признать истинной.
РАВНОСИЛЬНО Операция, выражаемая связками «тогда и только тогда», «необходимо и достаточно», «... равносильно …», называется эквиваленцией или двойной импликацией и обозначается знаком ↔ или ~. Высказывание А↔В истинно тогда и только тогда, когда значения А и В совпадают.
Пример: Высказывание «Число является четным тогда и только тогда, когда оно делится без остатка на 2» является истинным, а высказывание «Число является нечетным тогда и только тогда, когда оно делится без остатка на 2» - ложно.
|
|
ЛИБО … ЛИБО Операция, выражаемая связками «Либо … либо», называется исключающее ИЛИилисложением по модулю 2 и обозначается XOR или . Высказывание А В истинно тогда и только тогда, когда значения А и В не совпадают.
Пример. Высказывание «Число 6 либо нечетно либо делится без остатка на 2» является истинным, а высказывание «Либо число 6 четно либо число 6 делится на 3» – ложно, так как истинны оба высказывания входящие в него.
Замечание. Импликацию можно выразить через дизъюнкцию и отрицание:
.
Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:
.
Исключающее ИЛИ можно выразить через отрицание, дизъюнкцию и конъюнкцию:
.
Операций отрицания, дизъюнкции и конъюнкции достаточно, чтобы описывать и обрабатывать логические высказывания.
Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок договорились считать, что сначала выполняется операция отрицания («не»), затем конъюнкция («и»), после конъюнкции – дизъюнкция («или») и исключающего или и в последнюю очередь – импликация и эквиваленция.
С помощью логических переменных и символов логических операций любое высказывание можно формализовать, то есть заменить логической формулой (логическим выражением).
Логическая формула - это символическая запись высказывания, состоящая из логических величин (констант или переменных), объединенных логическими операциями (связками).
Логическая функция - это функция логических переменных, которая может принимать только два значения: 0 или 1. В свою очередь, сама логическая переменная (аргумент логической функции) тоже может принимать только два значения: 0 или 1.
Пример. – логическая функция двух переменных A и B.
Значения логической функции для разных сочетаний значений входных переменных – или, как это иначе называют, наборов входных переменных – обычно задаются специальной таблицей. Такая таблица называется таблицей истинности.
Приведем таблицу истинности основных логических операций (табл. 2)
|
|
Таблица 2
A | B | ||||||
Опираясь на данные таблицы истинности основных логических операций можно составлять таблицы истинности для более сложных формул.
Алгоритм построения таблиц истинности для сложных выражений:
1. Определить количество строк:
· количество строк = 2n + строка для заголовка,
· n - количество простых высказываний.
2. Определить количество столбцов:
· количество столбцов = количество переменных + количество логических операций;
· определить количество переменных (простых выражений);
· определить количество логических операций и последовательность их выполнени