Математическая логика
Введение
Тема контрольной работы «Математическая логика».
БУЛЬ или БУЛ, а также БУУЛ, Джордж (1815-1864) – английский математик, который считается основоположником математической логики.
Математическая логика – это раздел математики, посвященный анализу методов рассуждений, при этом в первую очередь исследуются формы рассуждений, а не их содержание, т.е. исследуется формализация рассуждений.
Формализация рассуждений восходит к Аристотелю. Современный вид аристотелева (формальная) логика приобрела во второй половине XIX века в сочинении Джорджа Буля “Законы мысли”.
Интенсивно математическая логика начала развиваться в 50-е годы XX века в связи с бурным развитием цифровой техники.
1. Элементы математической логика
Основными разделами математической логики являются исчисление высказываний и исчисление предикатов.
Высказывание – есть предложение, которое может быть либо истинно, либо ложно.
Исчисление высказываний – вступительный раздел математической логики, в котором рассматриваются логические операции над высказываниями.
Предикат – логическая функция от п переменных, которая принимает значения истинности или ложности.
Исчисление предикатов – раздел математической логики, объектом которого является дальнейшее изучение и обобщение исчисления высказываний.
Теория булевых алгебр (булевых функций) положена в основу точных методов анализа и синтеза в теории переключательных схем при проектировании компьютерных систем.
1.1 Основные понятия алгебры логики
Алгебра логики – раздел математической логики, изучающий логические операции над высказываниями.
В алгебре логики интересуются лишь истинностным значением высказываний. Истинностные значения принято обозначать:
1 (истина) 0 (ложь).
Каждой логической операции соответствует функция, принимающая значения 1 или 0, аргументы которой также принимают значения 1 или 0.
Такие функции
называются
логическими
или булевыми,
или функциями
алгебры логики
(ФАЛ). При этом
логическая
(булева) переменная
x может
принимать
только два
значения:
.
Таким образом,
- логическая
функция, у которой
логи-ческие
переменные
являются
высказываниями.
Тогда сама
логическая
функция
является сложным
высказыванием.
В этом случае
алгебру логики
можно определить,
как совокупность
множества
логических
функций с заданными
в нем всевозможными
логическими
операциями.
Таким логическим
операциям, как
конъюнкция
(читается И),
дизъюнкция
(ИЛИ), импликация,
эквивалентность,
отрицание (НЕ),
соответствуют
логические
функции, для
которых приняты
обозначения
(&,
·),
~,
– (
),
и имеет место
таблица истинности:
|
|
|
|
|
|
|
x~y |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 |
Это табличный способ задания ФАЛ. Наряду с ними применяется задание функций с помощью формул в языке, содержащем переменные x, y, …, z (возможно индексированные) и символы некоторых конкретных функций – аналитический способ задания ФАЛ.
Наиболее
употребительным
является
язык,содержащий
логические
символы
~, –. Формулы этого
языка определяются
следующим
образом:
1) все переменные есть формулы;
2) если P
и Q – формулы,
то
P ~ Q,
- фор-мулы.
Например,
выражение
~
- формула. Если
переменным
x, y,
z придать
значения из
двоичного
набора 0, 1 и провести
вычисления
в соответствии
с операциями,
указанными
в формуле, то
получим значение
0 или 1.
Говорят, что
формула реализует
функцию. Так
формула
~
реализует
функцию h(x,
y, z):
| x | y | z | h(x, y, z) |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Пусть P и Q – формулы, которые реализуют функции f (x1, x2, …, xn) и g (x1, x2, …, xn). Формулы равны: P = Q, если функции f и g совпадают, т.е. совпадают их таблицы истинности. Алгебра, основным множеством которой является все множество логических функций, а операциями – дизъюнкция, конъюнкция и отрицание, называется булевой алгеброй логических функций.
Приведем
законы и тождества,
определяющие
операции
–
и их связь с
операциями
,
~:
1. Идемпотентность конъюнкции и дизъюнкции:
.
2. Коммутативность конъюнкции и дизъюнкции:
.
3. Ассоциативность конъюнкции и дизъюнкции:
.
4. Дистрибутивность конъюнкции относительно дизъюнкции и дизъюнкции относительно конъюнкции:
.
5. Двойное отрицание:
.
6. Законы де Моргана:
=
,
=
.
7. Склеивание:
.
8. Поглощение
.
9. Действия с константами 0 и 1:
.
10. Законы Блейка-Порецкого:
.
11. Связь импликации
с отрицанием
– и дизъюнкцией
:
.
12. Связь эквивалентности
~ с дизъюнкцией
,
конъюнкцией
и отрицанием:
~
y
=
.
Всякая функция
алгебры логики
может быть
реализована
некоторой
формулой языка
с символами
~,
–.
1.2 Дизъюнктивные
и конъюнктивные
нормальные
формы (ДНФ и
КНФ)![]()
ДНФ и КНФ играют особую роль в алгебре логики и ее приложениях. Введем обозначение:
![]()
Так определенная переменная или ее отрицание называется первичным термом.
Формула
вида![]()
,
где
- двоичный набор,
а среди переменных
нет одинаковых,
называется
элементарной
конъюнкцией.
Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ):
.
Формула вида
называется
элементарной
дизъюнкцией.
Всякая конъюнкция элементарных дизъюнкций называется конъюктивной нормальной формой (КНФ):
.
Пример.
Привести
формулу
~z
к ДНФ
и КНФ.
1) Приведем формулу к ДНФ (последовательно: на основании определений операций импликации и эквивалентности, законов де Моргана и дистрибутивности):
~
~
((
)
=
.
2) Применив закон дистрибутивности к последнему выражению, получим КНФ:
Совершенной ДНФ (СДНФ) называется ДНФ, в которой нет равных элементарных конъюнкций и все элементарные конъюнкции содержат одни и те же переменные, причем каждую переменную – только один раз (включая вхождения под знаком отрицания).
Совершенная КНФ (СКНФ) определяется как такая КНФ, в которой нет одинаковых сомножителей; все сомножители содержат одни и те же переменные, причем каждую переменную – только один раз.
Для каждой
ФАЛ
можно построить
реализующую
ее СДНФ:
,
где дизъюнкция берется по тем двоичным наборам, на которых f = 1.
Каждая функция
алгебры логики
реализуется
следующей СКНФ:
![]()
Пример.
Функция h(x, y, z), рассмотренная ранее, имеет следующую СДНФ (выписывается по единичным значениям) и СКНФ (выписывается по нулевым значениям):
1
![]()
0
;
| x | y | z | h(x,y,z) |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Пример.
Построить СДНФ и СКНФ будевой функции f(x1, x2, x3), заданной таблицей истинности
| x1 | x2 | x3 | f(x1,x2,x3) | x1 | x2 | x3 | f(x1,x2,x3) |
| 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
![]()
.
Разложение
булевой функции
по k
переменным
x1,
x2,…,
xk
называется
разложением
Шеннона.
1.3 Теорема Шеннона
Любая булева
функция
представима
в виде разложе-ния
Шеннона:
![]()
где
,
- первичные
термы.
Пример.
Пусть п = 4, k = 2. Тогда разложение Шеннона будет иметь вид
Следствие.
Предельное
разложение
Шеннона (k
= n)
булевой функции
имеет вид
.
Предельное
разложение
Шеннона булевой
функции
является ее
СДНФ.
В алгебре
логики справедлив
принцип двойственности.
Согласно этому
принципу, будем
иметь следующие
двойственные
разложения
Шеннона булевой
функции
:
по k переменным
![]()
двойственное предельное разложение
.
Двойственное
предельное
разложение
Шеннона булевой
функции
является ее
СКНФ.
2 Булевы функции двух переменных
Рассмотрим простой бинарный элемент – выключатель, который имеет два состояния. Если данный выключатель контролируется входной переменной х,то говорят, что он выключен (открыт) при х = 0 и включен (закрыт) при х = 1, как показано на рис. 1:
![]()
х = 0 х = 1
Рис. 1 - Два состояния выключателя
Будем использовать следующее графическое обозначение для представления таких выключателей:
![]()
х
Рис. 2 - Графическое обозначение выключателя
Рассмотрим соединения лампы с источником питания, представленные следующими схемами:

Рис. 3 - Лампа, управляемая выключателем: а – простое соединение с батареей; б – использование заземления, как обратной связи
Используя условное обозначение L, можно описать состояние лампы как функции входной переменной. Если лампа светится, то L = 1. Если лампа не светится, то L = 0. Поскольку L = 1 при х = 1, L = 0 при х = 0, то можно говорить, что L(х) = х – логическая функция, х – логическая переменная. Это простое логическое выражение описывает выход как функцию от входа.
2.1 Булевы функции от двух переменных
Рассмотрим теперь возможность использования двух выключателей для управления состоянием лампы. Пусть х1 и х2 – управляющие переменные (входы) для этих выключателей. Выключатели могут быть соединены последовательно или параллельно, как показано на рис. 4:

Рис. 4 - Две основные функции: а – последовательное соединение (функция логического умножения AND); б – параллельное соединение (функция логического сложения OR)
2.2 Последовательное соединение двух выключателей
При последовательном
соединении
лампа будет
светиться
только, если
оба выключателя
включены
(одновременно).
Это поведение
может быть
описано выражением:
,
где L
= 1 при х1
= х2
= 1,
L = 0 в противном случае.
Символ
называется
AND-оператором.
Говорят, что
схема на рис.
3.4,а реализует
логическую
AND-функцию
(логическое
умножение).
2.3 Параллельное соединение двух выключателей
При параллельном соединении двух выключателей лампа будет гореть, если выключатели х1 и х2 включены. Лампа также будет гореть, если оба выключателя включены (одновременно). Лампа не будет гореть только, если оба выключателя открыты (разомкнуты, выключены). Это поведение может быть описано как:
,
где L
= 1 при х1
= 1 или х2
= 1, или х1
= х2
= 1; L
= 0 при х1
= х2
= 0.
Символ
называется
OR-оператором.
Говорят, что
схема на рис.
4,б реализует
логическую
OR-функцию
(логическое
сложение).
В приведенных
выше выражениях
для AND
и OR
реализует
результат
(выход)
есть логическая
функция с двумя
входными переменными.
Функции AND
и OR
являются двумя
наиболее важными
логическими
функциями.
Вместе с некоторыми
другими простыми
функциями они
могут быть
использованы
как составные
части (строительные
блоки) для реализации
логических
схем.
Например, на рис. 5 показано, как три выключателя могут быть использованы для управления лампой в более сложном случае. Такое последовательно-параллельное соединение выключателей реализует логическую функцию:
.
Лампа горит, если х3 = 1 и одновременно равны 1 либо х1, либо х2 (х1 = 1 или х2 = 1)

Рис. 5 - Последовательно-параллельное соединение выключателей
2.4 Инверсия
Пусть лампа подсоединяется к источнику питания так, как показано на рис. 6:

Рис. 6 - Инвертирующая схема
В этом случае
выключатель
соединяется
параллельно
с лампой. Лампа
будет гореть,
когда выключатель
выключен. Формально
такое функци-
ональное поведение
выражается:
,
где L
= 1 при х
= 0 и L
= 0 при х
= 1. Значение этой
функции обратно
значению входной
переменной.
Вместо слова инверсия существует более общий термин отрицание.
Таким образом,
есть отрицание
х:
.
Символ Ї
называют
NOT-оператором.
Количество
логических
функций в зависимости
от числа переменных
равно
.
Булевых функций
одной переменной
– четыре:
| x | f0 | f1 | f2 | f3 |
| 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
Индекс I функциональной переменной fi, I = 0, 1, 2, 3, равен десятичному эквивалентному набору значений этой функции, читаемому сверху вниз.
Функции f0(x) и f3(x) – константы 0 и 1 соответственно. Их значения не зависят от значения переменной х. Функция f1(x) “ повторяет “ х: f1(x) = x.
Функция f2(x)
называется
отрицанием
х (или функцией
НЕ) и обозначается
,
т.е. f2(x)
=
.
Ее значение
противоположно
значению х.
Булевых функций двух переменных – шестнадцать:
| x1 | x2 | f0 | f1 | f2 | f3 | f4 | f5 | f6 | f7 | f8 | f9 | f10 | f11 | f12 | f13 | f14 | f15 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Индекс I функциональной переменной fi, I = 0, 1, 2, …, 15, равен десятичному эквивалентному набору значений этой функции, читаемому сверху вниз. Приведем эти булевы функции:
- константа
ноль;
- конъюнкция;
х1
–|→
- левая коимпликация
(читается «не
если х1,
то х2»,
префикс ко
– от лат. conversus
– обратный);
;
х1
←|– х2
- правая коимпликация;
;
-
сложение по
модулю два или
функция неравнозначности,
неэквивалентности;
- дизъюнкция;
х1
◦ х2
= х1
↓ х2
- функция Вебба
(Пирса);
х1
~ х2
– функция
эквивалентности,
равнозначности;
- отрицание
х2;
- правая импликация
(читается «
если х2,
то х1»);
- отрицание
х1;
- левая импликация
(читается «если
х1, то
х2»);
- функция
Шеффера;
- константа
единица.
2.5 Свойства элементарных функций алгебры логики
2.5.1 Функция сложения по модулю два (по mod 2)
Пусть
Операция
“сложениe
по mod
p
“ определяется
следующим
образом: а
b
= c,
где с
– остаток от
деления на p
числа a
+ b.
Например, если
р = 7, то
.
Тогда
,
.
При сложении
по mod
2: р = 2,
.
Тогда при а
= х1,
b
= x2
получим:
![]()
| х1 | х2 |
|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
.
Справедливы коммутативный и ассоциативный законы. Дистрибутивный закон имеет вид:
![]()
Аксиомы:
![]()
Связь