85990 (Математическая логика)
Описание файла
Документ из архива "Математическая логика", который расположен в категории "". Всё это находится в предмете "математика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "контрольные работы и аттестации", в предмете "математика" в общих файлах.
Онлайн просмотр документа "85990"
Текст из документа "85990"
Введение
Тема контрольной работы «Математическая логика».
БУЛЬ или БУЛ, а также БУУЛ, Джордж (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 |