Для определения истинности сложных высказываний применяются действия булевой алгебры: отрицание (инверсия), умножение (конъюнкция) и сложение (дизъюнкция).
РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА
ПО ИНФОРМАТИКЕ
ДЛЯ СТУДЕНТОВ 1 КУРСА МЕХАНИКО-ТЕХНОЛОГИЧЕСКОГО ФАКУЛЬТЕТА
ЗАДАНИЯ
1.1 Для функции, соответствующей номеру варианта, выполните следующее:
1. Составьте таблицу истинности для исходной функции.
2. Запишите СДНФ и СКНФ функции.
3. Упростите (минимизируйте) выражение для СНДФ.
4. Составьте таблицу истинности для упрощенной функции (т.е. для функции после минимизации).
5. Постройте логические схемы для исходной и упрощенной функции.
1.2На зыке Си напишите программу для определения значения упрощенной функции, полученной в п. 1.1 при различных значениях переменных. Составьте блок-схему алгоритма.
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
Алгебра логики (булева алгебра)оперирует с двоичными переменными (высказываниями). Поэтомулогическая (булева) функция – такая, все переменные которой и сама функция могут принимать только значения 0 или 1.
Если в высказывании говорится только об одном факте, то оно называется простым и в описывающей его логической функции фигурирует одна переменная. Например, если высказывание «масса измеряется в секундах» обозначить буквой A, то соответствующая ему булева функция A=0, т.к. высказывание ложно.
Связкой простых высказываний образуются сложные высказывания. Пример сложного высказывания, состоящего из двух простых истинных высказываний: «Новосибирск основан в 1893 году И вода замерзает при 0 °С». Пример сложного высказывания, состоящего из простого истинного и простого ложного высказывания: «Июль – летний месяц ИЛИ груша – это фрукт».
Для определения истинности сложных высказываний применяются действия булевой алгебры: отрицание (инверсия), умножение (конъюнкция) и сложение (дизъюнкция).
Логическое отрицание (инверсия).Отрицание высказывания можно получить, используя частицу НЕ или выражение «неверно, что…». Например, инверсия высказывания «Москва является столицей России» ( ) запишется как «Москва не является столицей России» (или «Неверно, что Москва является столицей России») и обозначится .
Т.е., инверсия верного высказывание есть ложь, инверия неверного высказывания есть истина, что поясняется таблицей истинности логического отрицания:
Отрицание инверсного высказывания дает истину: «Неверно, что Москва не является столицей России» или . В булевой алгебре данное правило называется двойным отрицанием.
Логическое умножение (конъюнкция) двух высказываний выражается союзом И. В результат конъюнкции – логическое произведение.
Независимо от смысла логическое произведение являестя истинным только в случае истинности составляющих его просых высказываний. Например: «Лимон кислый» (A=1), «Химическая формула железа O2» (B=0), тогда высказывание «Лимон кислый и химическая формула железа O2» выразится выражением .
Таблица истинности для описания конъюнкции:
Для конъюнкции справедливы выражения:
,
,
.
Логическое сложение (дизъюнкция) двух высказываний выражается союзом ИЛИ, результатом дизъюнкции является логическая сумма.
Логическая сумма истинна, когда истинна хотя бы одна из ее составляющих, Например: «Лимон кислый» (A=1), «Химическая формула железа O2» (B=0), тогда высказывание «Лимон кислый или химическая формула железа O2» выразится выражением .
Таблица истинности логического сложения:
Для дизъюнкции справедливы выражения:
,
,
.
Конъюнкция и дизъюнкция коммутативны, т.е. на результат данных логических операций не влияет порядок расположения переменных: и .
Таким образом, логические функции могут быть заданы утвердительным словесным высказыванием, алгебраическим выражением и таблицей истинности (таблице 2.1).
Таблица 2.1
| Способы задания логической функции | ||||||||||
| Примеры | Утвердительное словесное высказывание | Алгебраическое выражение | Таблица истинности | |||||||
| Простые высказывания | Дуб – это хвойное дерево | - | ||||||||
| Дуб – это не хвойное дерево | | |||||||||
| Комар является насекомым | - | |||||||||
| Сложные высказывания | Дуб – это хвойное дерево И комар является насекомым |
| ||||||||
| Дуб – это хвойное дерево ИЛИ комар является насекомым |
|
Сложные высказывагния могут содержать больше двух простых высказываний, т.е. являться результатом большего количества логических действий, например:
.
Для получения таблицы истинности такого высказывания последовательно выполняются логические действия. Для функции таблица истинности имеет вид:
Сложные высказывания, которые описываются различными алгебраическими выражениями, но при этом имеют одинаковые таблицы истинности, называются эквивалентными. Так, по закону двойственности, если в формуле некоторого сложного высказывания заменить все знаки умножения занками сложения и наоборот, получится высказывание, эквивалентное первоначальному. Например:
.
Сложные высказывания тождественны, истинность которых постоянна и не зависит от истинности входящих в них простых высказываний. Например:
· закон противоречия: («Неверно, что автомобиль едет и автомобиль не едет», т.е. это никогда не истинно);
· закон исключенного третьего: («Ночью темно ИЛИ ночью не темно», что всегда истинно).
В таблице 2.2 приведены основные законы и правила алгебры логики.
Таблица 2.2
| Название закона (правила) | Алгебраическое выражение | ||
| Закон противоречиия | |||
| Закон исключенного третьего | |||
| Закон двойного отрицания | |||
| Свойства констант | |||
| Законы идемпотентности (тавтологии) | |||
| Законы коммутативности | |||
| Законы ассоциативности | |||
| Законы дистрибутивности | |||
| Законы поглощения | |||
| Законы слияния | |||
| Законы де Моргана | |||
| Правило замены импликации | |||
| Правило замены эквивалентности | |||
Пользуясь законами и правилами алгебры логики самостоятельно докажите, что выражения и эквивалентны друг другу. Составьте таблици истинности для каждого выражения.
Способы представления сложных высказываний.Сложное высказывание написано в дизъюнктивной нормальной форме (ДНФ), если оно состоит из суммы произведений простых высказываний (или их отрицаний). Примеры:
, (1)
, (2)
. (3)
Во втором слагаемом высказывания (3) отсутствует слагаемое (или ).
Если в составе каждого слагаемого присутствуют все высказывания (или их отрицания), то такое сложное высказывание написано в совершенной дизъюнктивной нормальной форме (СДНФ).
От ДНФ можно перейти к СДНФ. Например, пусть дано выражение . Переход к СДНФ производится путем умножения первого слагаемого на :
.
Логическую функцию можно представить в виде СДНФ по ее таблице истинности (в случае, если она не равна тождественному нулю). Для этого необходимо записать сумму всех произведений переменных, при которых функция принимает значение 1. При этом, если в таблице истинности переменная принимает значение 1, то в произведении записывается в первоначальном виде; если в таблице истинности значение переменной 0, то в произведении записывается ее инверсное значение.
В качстве примера приведена таблица истинности функций и (таблица 2.3), для которых требуется записать СДНФ.
Таблица 2.3
| A | B | ||
Функция принимает значение 1 при трех наборах переменных А и В, поэтому в СДНФ запишется в виде:
.
Значению функции , равному единице, соответствует только один набор переменых, поэтому СДНФ данной функции следующая:
.
Сложное высказывание написано в конъюнктивной нормальной форме (КНФ), если оно состоит из произведений сумм, в каждую из которых входят все простые высказывания или их отрицания. Примеры:
, (4)
, (5)
. (6)
Сложное высказывание, в каждую сумму произведений которго входят все простые высказывания (или их отрицания), написано в совершенной конъюнктивной нормальной форме (СКНФ). Например:
. (7)
Переход от КНФ к СКНФ производится следующим образом. Пусть , тогда, умножив на , можно перейти к виду:
.
Так как по закону двойственности , то
.
Логическую функцию (не равную тождественной единице), заданную таблицей истинности, можно предствавить в виде СКНФ: произведение сумм составляется для наборов переменных, соответствующих нулевому значению функции. При этом значение переменной в сумме записывается неизменным, если в таблице истинности оно равно 0, в противном случае в сумме записывается инверсное значение этой переменной.
Пусть, например, требуется записать СКНФ для функций и , описанных таблицей истинности 2.3.
Нулевому значению функции соответствует один набор переменных, поэтому ее СКНФ запишется в виде:
.
Функция принимает значение 0 в трех случаях, поэтому СДНФ данной функции следующая:
.
Самостоятельно для функции составьте таблицу истинности и запишите СДНФ и СКНФ.
Логичекие схемы. Любую логическую функцию, описывающую работу устройства вычислительной техники, можно описать графически в виде различных комбинаций логических элементов, которые образуют логическую схему.
Физически реализация логических функций может осуществляться с помощью различных элементов: механических, пневматиеских, гидравлических, электрических, электронных. В современной вычислительной технике применяются полупроводниковые логические схемы.
Простейшие логические функции релизуются с помощью логических элементов И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ. Их изображения представлены на рисунке 1.
Рисунок 1 – Изображения логических элементов
Схема реализации функции изображена на рисунке 2.
Рисунок 2 – Логическая схема для реализации функции
Самостоятельно упростите выражение и постройте исходную и упрощенную логические схемы.
Вопросы для самоконтроля.
1. Дайте определение конъюнкции, дизъюнкции, инверсии. Составьте таблицы истинности для данных функций.
2. Дайте определение импликации, эквивалентности. Составьте таблицы истинности для данных функций.
3. Дайте определение ДНФ и СДНФ.
4. Как записать СДНФ для функции, заданной таблицей истинности?
5. Дайте определение КНФ и СКНФ.
6. Как записать СКНФ для функции, заданной таблицей истинности?
7. Что такое логическая схема?
8. Изобразите логические элементы И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ.