Математическая логика

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

КЫРГЫЗСКОЙ РЕСПУБЛИКИ

 

 

ИНСТИТУТ НОВЫХ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

 

 

ЦЕНТР ДИСТАНТНОГО ОБРАЗОВАНИЯ.

 

КОНТРОЛЬНАЯ РАБОТА

 

 

 

По предмету: Математическая логика

 

 

 

 

 

 

Выполнела: ст. 3-курса Жумаева Наргиза

Проверил(а):__________________________

 

 

 

 

 

 

Бишкек-201

Введение

 

Тема  контрольной работы «Математическая  логика».

БУЛЬ  или БУЛ, а также БУУЛ, Джордж (1815-1864) – английский математик, который  считается основоположником математической логики.

Математическая  логика – это раздел математики, посвященный анализу методов  рассуждений, при этом в первую очередь  исследуются формы рассуждений, а не их содержание, т.е. исследуется  формализация рассуждений.

Формализация  рассуждений восходит к Аристотелю. Современный вид аристотелева (формальная) логика приобрела во второй половине XIX века в сочинении Джорджа Буля “Законы мысли”.

Интенсивно  математическая логика начала развиваться  в 50-е годы XX века в связи с бурным развитием цифровой техники.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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 (x₁, x₂, …, x_n) и g (x₁, x₂, …, x_n). Формулы равны: P = Q, если функции f и g совпадают, т.е. совпадают их таблицы истинности. Алгебра, основным множеством которой является все множество логических функций, а операциями – дизъюнкция, конъюнкция и отрицание, называется булевой алгеброй логических функций.

Приведем  законы и тождества, определяющие операции – и их связь с операциями , ~:

1. Идемпотентность конъюнкции и  дизъюнкции:

 

.

2. Коммутативность конъюнкции и  дизъюнкции:

 

.

3. Ассоциативность конъюнкции и  дизъюнкции:

.

4. Дистрибутивность конъюнкции относительно  дизъюнкции и дизъюнкции относительно  конъюнкции:

.

5. Двойное отрицание:

.

6. Законы де Моргана:

 

= , = .

7. Склеивание:

.

8. Поглощение

.

9. Действия с константами 0 и  1:

.

 

10. Законы Блейка-Порецкого:

.

11. Связь импликации  с отрицанием – и дизъюнкцией :

12. Связь эквивалентности ~ с дизъюнкцией  , конъюнкцией и отрицанием:

~ y = .

Всякая  функция алгебры логики может  быть реализована некоторой формулой языка с символами  ~, –.

 

2. Теорема  Шеннона

Любая булева функция  представима в виде разложе-ния Шеннона:

где , - первичные термы.

Пример.

Пусть п = 4, k = 2. Тогда разложение Шеннона будет иметь вид

Следствие.

Предельное  разложение Шеннона (k = n) булевой функции имеет вид

.

Предельное  разложение Шеннона булевой функции  является ее СДНФ.

В алгебре логики справедлив принцип  двойственности. Согласно этому принципу, будем иметь следующие двойственные разложения Шеннона булевой функции  :

по k переменным

двойственное  предельное разложение

.

Двойственное  предельное разложение Шеннона булевой  функции  является ее СКНФ.

4 Способы  представления функций алгебры  логики

Для булевых функций существуют различные  способы представления: таблица  истинности, числовой, аналитический.

Пример.

Пусть функция  задана таблицей истинности:

 

№ набора	х1	х2	х3
0	0	0	0	1
1	0	0	1	0
2	0	1	0	0
3	0	1	1	1
4	1	0	0	1
5	1	0	1	0
6	1	1	0	0
7	1	1	1	0

 

В таблице в первом столбце под  номером набора понимается десятичный эквивалент соответствующего двоичного  набора.

Тогда запись или является числовым представлением этой функции, где в скобках показаны номера наборов, на которых функция принимает значение 1.

Запись 

представляет  собой аналитическое представление булевой функции.

Можно в выражении функции вместо конъюнкций термов записать соответствующие двоичные наборы. Тогда получим:

 

.

Булеву  функцию можно задать с помощью единичного п – мерного куба (рис. 7).

Рис. 7

Единичным п – мерным кубом называется граф, каждая вершина которого взаимно однозначно соответствует двоичному набору. Две вершины соединены ребром, если соответствующие наборы отличаются только в одном разряде (в одной координате).

На  рис. 7 показаны п-мерные кубы для булевых функций: двух переменных (а), трех переменных (б), четырех переменных (в).

Отметив вершины, в которых булева функция  принимает единичные значения, получим  геометрическое представление булевой  функции. Так функция 

примет  вид:

Рис. 8

Часто для изображения булевых функций  двух и трех переменных используют прямоугольную систему координат:

Рис. 9

Изображение булевых функций числа переменных более трех в этом случае невозможен.

В методе минимизации булевых функций  Квайна – Мак-Класки используется кубическое представление булевых функций (аналог п-мерных кубов).

Терм  максимального ранга принято  называть 0-кубом и обозначать К ⁰. Если два 0-куба из комплекса К ⁰ различаются только по одной координате, то они образуют куб (отрезок) K ¹.

Пример.

Для

  .

 

 

 

 

 

Литература

 

1. Горбатов  В.А. Основы дискретной математики. – М.: Высшая школа, 1986. – 311 с.

2. Коршунов  Ю.М. Математические основы кибернетики.  – М.: Энергоатомиздат, 1987. – 496 с.

3. Кузнецов  О.П., Адельсон-Вельский Г.М. Дискретная  математика для инженера. – М.: Энергоатомиздат, 1988. – 480 с.

4. Сигорский  В.П. Математический аппарат инженера. – М.: Техника, 1975. – 768 с.

5. Шапорев  С.Д. Дискретная математика. –  СПб., 2006. - 400 с.

6. Хаханов  В.И., Чумаченко С.В. Дискретная  математика. Конспект теоретического  материала (электронная версия). ХНУРЭ, 2003.

7. Яблонский  С.В. Введение в дискретную  математику. – М.: Наука, 1979. – 272 с.

8. Гаврилов  Г.П., Сапоженко А.А. Задачи и  упражнения по дискретной математике. – М.: ФИЗМАТЛИТ, 2005. – 416 с.