Лабораторная работа "Основы математической логики"

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