36.
(15.01.2006 03:15)
0  
Основы математической логики.
Основные понятия.
Математическая логика – это наука о методах рассуждений, при которых мы отвлекаемся от содержания рассуждений, а используем только их формулу и значение.
 В математической логике мы будем использовать только логические переменные, которые принимают значение либо 0 («ложь»), либо 1 («истина»).
 Функции, которые определены на этих переменных и принимают значения 0 или 1 также называются логическими.
Наборы, на которых задана функция, могут быть представлены виде конституэнтов, двоичных или десятичных эквивалентов.
 Конституэлом называется логическое произведение переменных или их отрицаний в виде
ή
&хσỉi
i=l
где хσỉi= xi при σi=1 и хσỉ= при σi=0.
Двоичный эквиваленты формируются из значений σi.Например, конституэнту x3 соответствует двоичный набор 001, а конституэнту x1 x3 – 101.
Десятичные эквиваленты легко могут быть получены из двоичных с помощью степенного ряда:
0010*22+0*21+1*20=1
1011*22+0*21+1*20=5.
Математическая логика имеет непосредственную связь с теорией проектирования ЭВМ. Поведение различных компонентов ЭВМ может быть описаны с помощью логических функций и законов математической логики.
Кроме того, современные языки программирования просто немыслимы без встроенных в них логических функций.
Логические функции и таблицы истинности.
Рассмотрим основные логические функции. Значения переменных любой логической функции могут принимать только 0 и 1. При N переменных существует 2n различных наборов переменных. Значение самой логической функции тоже может быть только 0 ил 1 («ложь» или «истина»), следовательно, различных логических функций от N переменных может быть 22N.
Для функций с двумя переменными известны 16 логических функций:
• логическое сложение +, или дизъюнкция ;
• логическое умножение *, или конъюнкция &;
• отрицание (по первой переменной) ;
• отрицание (по второй переменной) ;
• импликация или функция следования – левая  и правая ;
• сложение по модулю 2 или жегалкинское сложение ;
• функция Шеффера ;
• стрелка Пирса , или функция Вебба ;
• обратная импликация, или коимпликация – левая и правая ;
• функция тождества, или эквивалентность ;
• единичная функция 1;
• нулевая функция 0;
• функция сохранения первой переменной а;
• функция сохранения второй переменной в.
Значение каждой логической функции описывается таблицей истинности.
Таблица истинности представляет собой таблицу, устанавливающую соответствие между возможными знаниями наборов переменных и значениями функции.
Таблицы истинности логических функций позволяют определить значение; которые принимают эти функции при различных значениях переменных, сравнивать функции между собой, определять, удовлетворяют ли функции заданным свойствам.
Рассмотрим все 16 логических функций.
Логическое сложение А+В, или дизъюнкция АВ.
Читается эта запись как «а плюс б» или «а дизъюнкция б».
Дизъюнкцией двух слагаемых ложна тогда и только тогда, когда ложны оба слагаемых. Таблица истинности у логического сложения следующая:
А В
0 0 0
0 1 1
1 0 1
1 1 1
Логическое умножение А*В, или конъюнкция А&В.
Запись читается как «А и В» или «А конъюнкция В».
Конъюнкция двух сомножителей истина тогда и только тогда, когда истинны оба сомножителя.
Таблица истинности у логического умножения следующая:
А В
0 0 0
0 1 0
1 0 0
1 1 1
Отрицание .
Запись читается как «не А». Отрицание лжи есть истина, отрицание истины есть ложь. Таблица истинности у отрицания следующая:
А
0 1
1 0
Отрицание (по первой переменной) .
А В
0 0 1
0 1 1
1 0 0
1 1 0
=
В данной записи функция не зависит от второй переменной В, которая считается несущественной.
Отрицание (по второй переменной) .
А В
0 0 1
0 1 0
1 0 0
1 1 0
=
Импликация или функция следования – левая АВ и правая АВ.
Запись читается как «А импликация В»или «из А следует В», а запись читается как «В импликация А»или «из В следует А».
Для функции импликации из лжи следует все что угодно, а из истины только истина.
А В
0 0 1
0 1 1
1 0 0
1 1 1
Используя набор функций {+,*,-}, мы получим выражение для импликации в виде = , которое полностью соответствует таблице истинности.
А В
0 0 1
0 1 0
1 0 1
1 1 1
Сама функция соответствует форме:
= .
Сложение по модулю 2 или жегалкинское сложение АВ.
Запись читается как «А плюс по модулю два В». Функция сложения по модулю 2 истинна тогда и только тогда, когда значения переменных различны.
А В
0 0 0
0 1 1
1 0 1
1 1 0
Используя набор функций {+,*,-}, получим:
= .
Функция Шеффера АВ.
Запись читается как «А штрих Шеффера В». Функция ложна тогда и только тогда, когда оба значения переменных истины.
А В
0 0 1
0 1 1
1 0 1
1 1 0
= = .
Стрелка Пирса АВ, или функция Вебба АВ.
Запись читается как «А стрелка Пирса В», а - «А элемент Вебба В». Функция истина тогда и только тогда, когда ложны обе ее переменные.
А В
0 0 1
0 1 0
1 0 0
1 1 0
= = .
Функция тождества, или эквивалентность АВ.
Запись читается как «А эквивалентно В». Функция истина тогда и только тогда, когда значения переменных совподают.
А В
0 0 1
0 1 0
1 0 0
1 1 1
= = .
Единичная функция 1.
Данная функция определяет логическую константу 1.
А В 1
0 0 1
0 1 1
1 0 1
1 1 1
1(А,В)= 1.
Нулевая функция 0.
Данная функция определяет логическую константу 0.
А В 0
0 0 0
0 1 0
1 0 0
1 1 0
0(А,В)= 0.
Функция сохранения первой переменной А.
Данная функция истинна тогда и только тогда, когда переменная А истинна.
А В А
0 0 0
0 1 0
1 0 1
1 1 1
А(А,В)= А.
Функция сохранения второй переменной В.
Данная функция истинна тогда и только тогда, когда переменная В истинна.
А В В
0 0 0
0 1 1
1 0 0
1 1 1
В(А,В)= В.
Существуют более сложные логические функции, которые получаются из простейших функций с помощью подстановки.
Построение таблиц истинности для таких функций можно описать очень просто. Вначале выписываются значения, которые могут принимать наборы переменных в этой функции. В общем случае если переменных n, то различных n – мерных наборов переменных существует 2n.
Затем вычисляется значение функции на каждом наборе. Любая рассматриваемая логическая функция представляет собой суперпозицию элементарных логических функций и может быть вычислена последовательно при помощи подстановок определенных ранее значений.
Алгебра логики и ее законы.
1. Закон идемпотентности (одинаковости):
=А, =А.
2. Закон коммутативности:
= , = .
3. Закон ассоциативности:
= , =
4. Дистрибутивность конъюнкции относительно дизъюнкции:
= ,
Дистрибутивность дизъюнкции относительно конъюнкции:
= .
5. Закон двойного отрицания:
=А
6. Законы деМоргана:
= , = .
7. Законы поглощения:
=А, =А.
8. Законы, определяющие действия с логическими константами 0 и 1:
=А =0 =1 =А =1
=0 =1 =0 =0 =1
=0 = = =1
9. Законы склеивания:
=В =В
10. Закон Блейка – Порецкого:
=
11. Закон свертки логического выражения:
=
Формы представления логических функций.
Для удобства представления логических функций существуют различные формы:
o Дизъюнктивная нормальная форма;
o Конъюнктивная нормальная форма.
 Дизъюнктивная нормальная форма (ДНФ) – это сумма произведений, образованных из переменных и их отрицаний. ДНФ не содержит скобок.
 Конъюнктивная нормальная форма (КНФ) – это произведение сумм, состоящих из переменных и их отрицаний.
Теорема о ДНФ.
Всякая сложная логическая функция может быть сведена к ДНФ.
Для того чтобы сделать это, необходимо:
• Записать функцию в виде {+,*,-};
• С помощью закона де Моргана спустить черту отрицания до отдельных букв и по закону двойного отрицания уничтожить двойные черточки;
• С помощью первого закона дистрибутивности уничтожить все произведения сумм и провести поглощение.
Полученная форма удовлетворяет определению ДНФ.
Если ДНФ функции f1(х1, х1,…, хn) от n переменных в каждой своей конъюнкции содержит все n переменных либо их отношения, то это совершенная дизъюнктивная нормальная форма (СДНФ). Каждая функция имеет одну – единственную СДНФ, и она может быть получена из таблицы истинности этой функции путем записи через знак логического сложения всех наборов переменных, на которых эта функция определена как истинная. Каждый такой набор переменных соответствует конъюнкции, причем если переменная хi = 1, хi входит в нее без отрицания, если хi= 0, то хi входит в нее с отрицанием i.
Теорема о КНФ.
Всякая сложная логическая функция может быть сведена к КНФ.
Для того чтобы сделать это, необходимо:
• Записать функцию в виде {+,*,-};
• С помощью закона де Моргана спустить черту отрицания до отдельных букв и по закону двойного отрицания уничтожить двойные черточки;
• С помощью второго закона дистрибутивности уничтожить все суммы произведений и провести поглощение.
Полученная форма удовлетворяет определению КНФ.
Если КНФ функции f1(х1, х1,…, хn) от n переменных в каждой своей дизъюнкции содержит все n переменных либо их отношения, то это совершенная конъюнктивная нормальная форма (КДНФ). Каждая функция имеет одну – единственную СДНФ, и она может быть получена из таблицы истинности этой функции путем записи через знак логического умножения всех наборов переменных, на которых эта функция определена как ложная. Каждый такой набор переменных соответствует дизъюнкции, причем если переменная хi = 0, хi входит в нее без отрицания, если хi= 1, то хi входит в нее с отрицанием i.
Минимизацию логических функций можно проводить с помощью метода Квайна – МакКласски, который состоит из четырех шагов:
• Представим наборы, на которых функция истинна, в виде двоичных эквивалентов;
• Упорядочим двоичные эквиваленты по ярусам и проведем склейку наборов в соседних ярусах, получая максимальные интервалы до тех пор, пока это возможно; помечаем каждый набор, участвовавший в склейке. Склеиваются только те наборы или интервалы, различие в которых заключается только в значении одного разряда: 001 и 000, 001- и 101- и т.д.
• Построим таблицу Квайна, столбцы которой соответствуют двоичным наборам истинности функции, а строки – максимальным интервалам. Если i- й набор покрывается j –м интервалом, то ставим 1 на пересечении соответствующих строки и столбца, в противном случае ставим 0 или не ставим ничего;
• Находим минимальное покрытие таблицы Квайна, состоящее из минимального количества максимальных интервалов, включающих в себя (покрывающих) все наборы, на которых функция истинна.
Построение логических схем.
Техническая реализация логических функций может быть различна, но существует единая система графического представления логической функциональных элементов. Каждый элемент представляет собой прямоугольник со входами и одним выходом, инверсные входы и выходы соответствуют не закрашенным кружкам. Сам элемент обозначается:
• Единицей, если он реализует логическое сложение;
• Знаком конъюнкции, ели реализуется логическое умножение;
• Mod2, если реализуется сложение по модулю 2;
• , если реализуется функция эквивалентности.
|
